Random Number Generation

[+TwentySixHundred]

Hi guys, im playing around trying to generate random numbers from 0-154 or preferably 4-154. However im seeing glaring patterns no matter what i try. It seems whatever the math it tries to hug one area more then the other, for example.

 

Something like this tends to hug the middle range more then anything.

(rand/4) + (rand&31) + (rand&15) + (rand&15) + (rand&15) + (rand&3) + 12

 

Then something like this will tend to hug the higher range more.

(rand/4) + (rand&31) + (rand&15) + (rand&15) + (rand&3) + 27

 

And something else i was playing around with was hugging the lower range more often. Im finding random is not-so random and other places on the net have mentioned, it's quite tricky to generate random numbers without patterns emerging. The question i have is what are the best and fastest ways to overcome this issue, if possible?

 

I mean im having more luck with wrapping the the sprites out of bounds with higher values then the said desired range. The only issue with that is the odd sprite that the wrap around is visible on both side of the screen.

[+Random Terrain]

When I was working on Seaweed Assault, I had to mix division with & in the right combination. I just kept playing with it until the glaring patterns were gone. You'll probably end up alternating them (division, &, division, & . . .).

[+TwentySixHundred]

20 minutes ago, Random Terrain said:

When I was working on Seaweed Assault, I had to mix division with & in the right combination. I just kept playing with it until the glaring patterns were gone. You'll probably end up alternating them (division, &, division, & . . .).

 

I was actually just thinking if that would work, i have a feeling this part could too uniform but not sure.

(rand&15) + (rand&15) + (rand&15)

 

This is the best setup i have got so far however like i was saying it's heavily generating numbers within the mid range

(rand/4) + (rand&31) + (rand&15) + (rand&15) + (rand&15) + (rand&3) + 12

 

I will try mixing it up with some extra division and shuffle them all around to see what happens.

Edited February 18, 2020 by TwentySixHundred

[+Random Terrain]

Yeah, instead of this:

 

(rand/4) + (rand&31) + (rand&15) + (rand&15) + (rand&15) + (rand&3) + 12

 

You'd try this:

 

(rand/4) + (rand&31) + (rand/16) + (rand&15) + (rand/16) + (rand&3) + 12

 

If that doesn't work, alternate them the other way. If that doesn't work, try other combinations. You'll find something that works.

[+TwentySixHundred]

17 minutes ago, Random Terrain said:

Yeah, instead of this:

 

(rand/4) + (rand&31) + (rand&15) + (rand&15) + (rand&15) + (rand&3) + 12

 

You'd try this:

 

(rand/4) + (rand&31) + (rand/16) + (rand&15) + (rand/16) + (rand&3) + 12

 

If that doesn't work, alternate them the other way. If that doesn't work, try other combinations. You'll find something that works.

Thanks i have managed to fan it out a bit more with this

(rand/16) + (rand&15) + (rand/4) + (rand&31) + (rand&15) + (rand/64) + 12

 

However it's the extreme highs and lows it struggles to generate like say a 4 or 150. Still hugs the middle range more then id like. I want the middle range more so although need the highs and lows to generate more often then they do. Might keep playing around with the combination, i was hoping the rand/64 at the end would shuffle the chances some more.

[+Random Terrain]

If you find the perfect combination, be sure to post it. I wonder if there is a difference between DPC+ results and rand16 standard kernel results.

[+TwentySixHundred]

8 minutes ago, Random Terrain said:

If you find the perfect combination, be sure to post it. I wonder if there is a difference between DPC+ results and rand16 standard kernel results.

Will do, i have a test program going however still haven't found anything im happy with yet. I will keep plugging away ?The ability to change the rand seed would be great however with what im trying doesn't seem to have much effect

Edited February 18, 2020 by TwentySixHundred

[+Karl G]

The more ranges you add together, the more of a bell curve effect you will get with probabilities toward the center of the range, as you observed. Maybe someone else can come up with a better suggestion, but this one would at least give a much less steep bell curve, and might be good enough for your purposes:

    Position = rand ; (0-255)
    If Position > 150 then Position = Position - 128 (23-127)
    Position = Position + 4 (4-154)

This will still have a slight bias away from the extreme ends of the range, but much less so, I think. I'm interested in hearing if others have cleaner solutions, though.

[+TwentySixHundred]

7 minutes ago, Karl G said:

The more ranges you add together, the more of a bell curve effect you will get with probabilities toward the center of the range, as you observed. Maybe someone else can come up with a better suggestion, but this one would at least give a much less steep bell curve, and might be good enough for your purposes:

    Position = rand ; (0-255)
    If Position > 150 then Position = Position - 128 (23-127)
    Position = Position + 4 (4-154)

This will still have a slight bias away from the extreme ends of the range, but much less so, I think. I'm interested in hearing if others have cleaner solutions, though.

Thanks Karl, yeah i was just experimenting with something similar. Was trying to pre-seed the playerx position with a rand number then have the code below make the final randomization. Very buggy at the moment as i think it's causing the sprites to wrap around. However there is some really random placement happening. I like your method and will have a play around with it ?

(rand/16) + (rand&15) + (rand/4) + (rand&31) + (rand&15) + (rand/64) + 12

[+TwentySixHundred]

Well i managed to get nice randomization by randomizing a seed then adding the value of that seed to rand. It's not perfect however it seems to work quite nicely for a quick throw together. When i have a fresh set of eyes tomorrow i will see what tweaks can be done as im sure there is room for fine tuning. Anyway here is the bas and bin

 

Random Generation.bin

Random Generation.bas

[+SpiceWare]

@TwentySixHundred - I see you're a member of the Harmony/Melody Club.  One of the things you have to look forward to is:

 

position = ((151 * (Random32() & 0xff)) >> 8) + 4;

• (Random32() & 0xff) = 0-255
• 151 * = 0 - 38505
• >> 8 = 0 - 150
• + 4 = 4 - 154

 

[+Karl G]

2 hours ago, SpiceWare said:

• (Random32() & 0xff) = 0-255
• 151 * = 0 - 38505
• >> 8 = 0 - 150
• + 4 = 4 - 154

Since you are here anyway, how would you do it in bB or 6502 ASM?  ? 

 

Edit: I mean as a best approximation, rather than trying to do 32-bit operations.

[+SpiceWare]

13 minutes ago, Karl G said:

Since you are here anyway, how would you do it in bB or 6502 ASM?  ? 

 

Edit: I mean as a best approximation, rather than trying to do 32-bit operations.

 

I would do what they're doing, but with as few rand as possible. So for bB:

(rand & 127) + (rand & 15) + (rand & 7) + 4

which would be 4-153.  Can add (rand & 1) if you absolutely must have 4-154.

 

The other thing I would do is use rand once every frame, but discard the value.  I cover this in step 10 - "Random Numbers" of my Collect Tutorial.

 

Quote

One thing that helps when using an LFSR is to keep reading values at a regular rate, even if you don't need the value. What this does is impose an element outside of the Atari's control - namely the time it takes the human to do things: hit the RESET switch to start a game, collect the next box, etc. I've added this to VerticalBlank
 

VerticalBlank:
        jsr Random
...

 

 

Likewise step 10 includes example asm code to get a random position.

[bogax]

here's one. not perfect

 

temp1 = rand/2: temp1 = (((((temp1/2 + temp1)/2 + temp1)/2 +temp1)/2 + temp1)/4 + temp1)/8 + temp1 + 4

Edited February 19, 2020 by bogax

[+TwentySixHundred]

8 hours ago, SpiceWare said:

@TwentySixHundred - I see you're a member of the Harmony/Melody Club.  One of the things you have to look forward to is:

 

position = ((151 * (Random32() & 0xff)) >> 8) + 4;

• (Random32() & 0xff) = 0-255
• 151 * = 0 - 38505
• >> 8 = 0 - 150
• + 4 = 4 - 154

 

That will be a breath of fresh air to have 32bit operations, yeah i have a read over at the club every now and then. Always something new to learn and possibly can translate some of the methods used into bB. That does look very similar to the examples in C over at Stackoverflow ?

5 hours ago, SpiceWare said:

 

I would do what they're doing, but with as few rand as possible. So for bB:

(rand & 127) + (rand & 15) + (rand & 7) + 4

which would be 4-153.  Can add (rand & 1) if you absolutely must have 4-154.

I am thinking that's the best possible way however incorporating the method i found works best with using a variable "seed" to randomize the overall rand value before this statement. So rather then the general pseudo random number generated that is seeded from a zero (i assume). It's got a rolling variable to mix up the final results. I have noticed the longer it runs the more random it becomes.

 

However with still having this

(rand & 127) + (rand & 15) + (rand & 7) + 4

I find will be the soother way to keep that random value within the boundaries, although the part i need to work out is how to incorporate that random fed variable along with rand into the statement. I feel replacing rand with seed alone won't be enough to yield the desired results.

[+TwentySixHundred]

So with the method i was using previously by simply changing the seed variable to a float (8.8 fixed point) there seems to be more randomness. Obviously the actual positioning of the sprites will still be to the nearest integer, however having the remainder adds that further refinement. Probably nothing too major and i doubt worth the loss of an additional variable, never-the-less it seems to mix things up a bit more.

 

Random_Number_Generation.bas

Random_Number_Generation.bin

[RevEng]

On 2/18/2020 at 9:46 PM, bogax said:

here's one. not perfect

 

temp1 = rand/2: temp1 = (((((temp1/2 + temp1)/2 + temp1)/2 +temp1)/2 + temp1)/4 + temp1)/8 + temp1 + 4

It's about as even a distribution as you can get, in 8 bits.  

[bogax]

On 2/18/2020 at 7:56 AM, TwentySixHundred said:

Hi guys, im playing around trying to generate random numbers from 0-154 or preferably 4-154. However im seeing glaring patterns no matter what i try. It seems whatever the math it tries to hug one area more then the other, for example.

 

Something like this tends to hug the middle range more then anything.

(rand/4) + (rand&31) + (rand&15) + (rand&15) + (rand&15) + (rand&3) + 12

 

Then something like this will tend to hug the higher range more.

(rand/4) + (rand&31) + (rand&15) + (rand&15) + (rand&3) + 27

 

And something else i was playing around with was hugging the lower range more often. Im finding random is not-so random and other places on the net have mentioned, it's quite tricky to generate random numbers without patterns emerging. The question i have is what are the best and fastest ways to overcome this issue, if possible?

 

I mean im having more luck with wrapping the the sprites out of bounds with higher values then the said desired range. The only issue with that is the odd sprite that the wrap around is visible on both side of the screen.

if you add up a bunch of pieces there's more ways to get the middle numbers and you end up with a trapazoidal distribution

 

if you call rand 5 times each time you want a number you'll only get 255/5 different numbers (255 is the length of the rand cycle)

 

if I understand what you mean by wrapping, you're taking rand MOD the screen width and you'll have more of the lower numbers (the numbers 0 to 255-max)

MOD is probably the best way if you can spare a variable to (sort of) carry that bias forward

 

edit: but the best thing to do with a spare variable would be use rand16

 

something like

 

  temp1 = myseed
 
  myseed = myseed + rand

  if temp1 > myseed then myseed = myseed - max

  if myseed > max then myseed = myseed - max

Edited May 3, 2020 by bogax
clarify, goof, more clarity