Random number generator, not so random?

[Cropsy]

I'm been working on a small project in bB and as part of it I need to randomly place some playfield pixels. The problem is instead of producing a more of less random placement of pixels a small number of pixels are being set repeatedly.

 

I've produced a small sample program that demonstrates the problem. I guess one of two things are happening, either I've missed something obvious (quite possible) or the random number generator isn't well suited to this task. It seems like a replacement random number generator could be dropped into std_routines.asm if the random number generator is the problem but I'd like some feedback before I hunt around for a different generator.

 

I've attached the sample program with source and a screen shot.

 

  dim frame_count=a
  frame_count=0
  COLUBK = 0 : COLUPF = 90
  rand = 44
game_loop
  drawscreen
  frame_count=frame_count+1
  if frame_count=10 || frame_count=40 then gosub test_pf
  if frame_count=20 || frame_count=50 then AUDV0=0
  if frame_count=60 then frame_count=0
  goto game_loop

test_pf
  AUDV0 = 2 : AUDC0 = 12 : AUDF0 = 4
  x = rand : y = rand
  rem Limit X to Range 0 - 31 actually 1 - 31 as rand never returns 0
  x = x & %00011111
  rem Limit Y to Range 0 - 7 actually 1 - 17 as rand never returns 0
  y = y & %00000111
  pfpixel x y on
  return

 

random_test.binrandom_test.bas

[+Random Terrain]

Isn't the problem here:

 

rand = 44

 

If you take that out, wouldn't it be more random?

[Thomas Jentzsch]

Try using different bits of rand for X and Y.

Y = Y % 11100000
Y = Y / 32

[SeaGtGruff]

I'm been working on a small project in bB and as part of it I need to randomly place some playfield pixels. The problem is instead of producing a more of less random placement of pixels a small number of pixels are being set repeatedly.

 

I've produced a small sample program that demonstrates the problem. I guess one of two things are happening, either I've missed something obvious (quite possible) or the random number generator isn't well suited to this task. It seems like a replacement random number generator could be dropped into std_routines.asm if the random number generator is the problem but I'd like some feedback before I hunt around for a different generator.

 

I've attached the sample program with source and a screen shot.

 

  dim frame_count=a
  frame_count=0
  COLUBK = 0 : COLUPF = 90
  rand = 44
game_loop
  drawscreen
  frame_count=frame_count+1
  if frame_count=10 || frame_count=40 then gosub test_pf
  if frame_count=20 || frame_count=50 then AUDV0=0
  if frame_count=60 then frame_count=0
  goto game_loop

test_pf
  AUDV0 = 2 : AUDC0 = 12 : AUDF0 = 4
  x = rand : y = rand
  rem Limit X to Range 0 - 31 actually 1 - 31 as rand never returns 0
  x = x & %00011111
  rem Limit Y to Range 0 - 7 actually 1 - 17 as rand never returns 0
  y = y & %00000111
  pfpixel x y on
  return

 

random_test.binrandom_test.bas

996276[/snapback]

 

I haven't analyzed your program listing, but you're correct-- the random number generator isn't really random, it always produces the same sequence of numbers, although the sequence can start with any number between 1 and 255. If you seed the random number generator with the same number every time (as you're doing with the statement "rand = 44"), you'll always get the same numbers in the same order. (By the way, I think this is how other BASICs work, too.) To get different results each time you run your program, you need to either not seed the random number generator at all, or else seed it with a random value ("rand = rand"). Note that seeding it with 0 will break it, but "rand" never returns a 0 anyway (unless you break it by seeding it with 0), so "rand = rand" will never seed it with 0.

 

Also, you might want to try using a different method for reducing the result to an acceptable value, because I don't think that masking the bits is the best way. The method I like to use it to subtract a given value until the result falls within the desired range. For example, to get a random value between 0 and 31:

 

  x = rand : rem * x will be between 1 and 255 inclusive
  x = x - 1 : rem * now x is between 0 and 254 inclusive
reduce_x
  if x > 31 then x = x - 32 : goto reduce_x
  rem * after exiting the loop, x will be between 0 and 31 inclusive

 

To understand why I think this is a better method for reducing x, consider what will happen if you want x to be between 0 and 3 inclusive. Masking x with %00000011 will produce 0 an inordinate number of times, because if you start with an x that has 0 in bit 0 and in bit 1, it will always reduce to 0. But if you keep subtracting until you get a value in the desired range (i.e., reducing x with a "mod" function), you won't get 0 an inordinate number of times, if you see what I mean.

 

We can even define a "mod" function in bB, as in the following example:

 

  rem * test of a mod function

  rand = rand
  COLUBK = $04
  scorecolor = $1A

rand_loop
  x = rand : rem * x will be from 1 to 255
  x = x - 1 : rem * now x is from 0 to 254
  x = mod(x,32) : rem * now x should be from 0 to 31
  score = 0
  if x > 0 then for t = 1 to x : score = score + 1 : next

display_loop
  drawscreen
  if joy0fire then goto rand_loop
  goto display_loop

  function mod
  rem * the second parameter should be > 0
  temp3 = temp2 - 1
mod_loop
  if temp1 > temp3 then temp1 = temp1 - temp2 : goto mod_loop
  return temp1
end

 

In this example, the "mod" function will return a value in the desired range, as long as the second parameter is greater than 0. For example, "a = mod(b,16)" will return the mod 16 value of b, and store it in a:

 

If b = 0, a will be = 0.

If b = 1, a will be = 1.

If b = 2, a will be = 2.

If b = 3, a will be = 3.

If b = 4, a will be = 4.

If b = 5, a will be = 5.

If b = 6, a will be = 6.

If b = 7, a will be = 7.

If b = 8, a will be = 8.

If b = 9, a will be = 9.

If b = 10, a will be = 10.

If b = 11, a will be = 11.

If b = 12, a will be = 12.

If b = 13, a will be = 13.

If b = 14, a will be = 14.

If b = 15, a will be = 15.

If b = 16, a will be = 0.

If b = 17, a will be = 1.

If b = 18, a will be = 2.

If b = 19, a will be = 3.

If b = 20, a will be = 4.

etc.

 

Michael Rideout

[djmips]

My approach to this problem and after reading up on the issue was two things.

 

First, let's say you want a random number between 0 and 31, you should loop the random routine 5 times then because it currently only generates one random bit per call.

 

But this is a problem with the current Random # routine in bBasic because it has only got a 256 cycle period before it repeats. So you could not use this as it stands, therefore I also suggest using at least a 16 bit if not 24 bit random (LFSR) to increase the period.

 

What I did was to call the random routine with the # bits desired in a register and then it would loop # times and return the new random number.

 

A big drawback is the additional overhead that this random method can give. Depending on what you are doing, you can get away with generating less random bits per call (ie loop less than 8 times or even none when you need a new random number between 0 - 255) but your correlation increases. At the minimum, going with a longer period random routine will improve the situation.

[supercat]

Depending on what you are doing, you can get away with generating less random bits per call (ie loop less than 8 times or even none when you need a new random number between 0 - 255) but your correlation increases. At the minimum, going with a longer period random routine will improve the situation.

996718[/snapback]

 

Random number generation on the 2600 is hard. Depending upon what you're doing, an 8-bit LFSR may be adequate, but only if there are many other unpredictable factors at work (in a game like Splatform, an 8-bit LFSR that's iterated once per frame would be perfectly adequate, since the time between uses is unpredictable and will vary unpredictably with generated numbers. But for things like screen generation, something better is probably pretty necessary.

[djmips]

OK, so I understand that the above post is probably going to be a little hard to deal with for several reasons, not the least of which is my confusing writing style.

 

So here's the code that's in bBasic right now, which is located in std_routines.asm. It will return a number between 1-255 (where zero is illegal). It will also generate every number between 1-255 before it repeats (sometimes useful).

 

randomize
 lda rand
 lsr
 bcc noeor
 eor #$B2
noeor
 sta rand
 rts

 

Every consecutive call will only differ by one bit from the previous call. Therefore you will have some correlation. To fix the situation, you should replace the code in std_routines.asm with the following.

 

randomize
 lda rand1
 asl
 rol rand
 bcc noeor
 eor #$D7
noeor
 sta rand1
 rts

 

This routine will have a period of 65535. Sorry, but I haven't tested the above code but I hope it's correct. Let me know if you have questions.

 

:!: In the current version of bBasic, the variables are directly equated and do not use the ds directive, so it is difficult to add variables without having to propagate through everything else. If you want, you can also change 2600basic.h (where the zpage vars are defined) and add a rand1 = $DA, which is noted as free.

 

Remember to call it several times in a loop before you use the result if you want to reduce the correlation between succesive calls.

[supercat]

This routine will have a period of 65535. Sorry, but I haven't tested the above code but I hope it's correct. Let me know if you have questions.

 

Remember to call it several times in a loop before you use the result if you want to reduce the correlation between succesive calls.

996743[/snapback]

 

I'd suggest a few changes:

 

-1- Iterate it a couple times with straight-line code. No real need for a loop.

 

-2- Rotate the two halves of the LFSR in opposite directions.

 

-3- Return the EOR of the two halves from your random generator.

 

randomize
   lda rand1
   eor rand; Undo effect of "previous eor"
   asl
   ror rand
   bcc noeor1
   eor #$D7
noeor1
   asl
   ror rand
   bcc noeor2
   eor #$D7
noeor2
   eor rand ; Will be "undone" next time through
   sta rand1
   rts

Note that steps 2 and 3 still won't give you a great random-number generator, but they'll improve considerably on the correlation problem; all 65,535 possible pairs of consecutive bytes will be output (a zero byte cannot follow another zero, but all other combinations are possible). Despite this, some visible multi-byte correlations will still exist if you only iterate the thing twice as shown above. Note that you should avoid iterating it by any number of times that's is a factor of, or shares any factors with, 65,535 (in particular, don't do it 3, 5, 6, 9, 10, 12, 15, 17, 18, etc. times)

Edited January 9, 2006 by supercat

[Thomas Jentzsch]

To fix the situation, you should replace the code in std_routines.asm with the following...

This routine will have a period of 65535. Sorry, but I haven't tested the above code but I hope it's correct.

I am not sure if this is a working LFSR pattern. According to my docs, for a 16 bit LFSR, you always have to EOR both registers

[Thomas Jentzsch]

...in a game like Splatform, an 8-bit LFSR that's iterated once per frame would be perfectly adequate, since the time between uses is unpredictable and will vary unpredictably with generated numbers...

Actually I iterate only when required, but simply EOR the result with the frame counter.

[+batari]

:!:  In the current version of bBasic, the variables are directly equated and do not use the ds directive, so it is difficult to add variables without having to propagate through everything else. If you want, you can also change 2600basic.h (where the zpage vars are defined) and add a rand1 = $DA, which is noted as free.

 

Remember to call it several times in a loop before you use the result if you want to reduce the correlation between succesive calls.

996743[/snapback]

I chose an 8-bit LFSR because it's adequate for most purposes and only takes one byte. You can also help this along by also getting a random number every time the player moves.

 

I was going to suggest a 16-bit LSFR in this case and give some code to be pasted as inline asm but you beat me to it. Regarding 24-bits that I think was mentioned earlier, it's hard for me to imagine a situation where this would ever be needed in a 2600 game, and it takes up another valuable byte...

 

If one does use the routine, I don't recommend modifying the 2600basic.h header file - adding "dim rand1=$DA" to the beginning of a bB program will do the same thing. Actually, I don't recommend this either, as the free byte is now being used in the upcoming version, so I'd use one of the 26 general purpose variables instead.

[+batari]

To fix the situation, you should replace the code in std_routines.asm with the following...

This routine will have a period of 65535. Sorry, but I haven't tested the above code but I hope it's correct.

I am not sure if this is a working LFSR pattern. According to my docs, for a 16 bit LFSR, you always have to EOR both registers

996764[/snapback]

I don't know if djmips's code will work, but I did write a 16-bit LFSR a few months ago that I tested and seems to work:

 lda rand
 lsr rand1
 ror
 bcc noeor
 eor #$B2
 tax
 lda rand1
 eor #$A0
 sta rand1
 txa
noeor
 sta rand
 rts

Probably can be improved, but I did test this one and I remember it having all unique values.

Edited January 9, 2006 by batari

[Thomas Jentzsch]

Probably can be improved, but I did test this one and I remember it having all unique values.

Quite good, but it does repeat after "only" 57337 iterations.

[+batari]

Probably can be improved, but I did test this one and I remember it having all unique values.

Quite good, but it does repeat after "only" 57337 iterations.

996778[/snapback]

My testing procedure clearly wasn't thorough enough

 

Anyway, I read your link and not surprisingly, A0B2 is not on the 16-bit list. So taking some values from the list, this one appears viable:

 lda rand
 lsr rand1
 ror
 bcc noeor
 eor #$5D
 tax
 lda rand1
 eor #$B3
 sta rand1
 txa
noeor
 sta rand
 rts

[djmips]

I tested the routine I posted and it does work. It repeats correctly and it fills 8192 bytes worth of bits where each number is mapped to one bit.

 

It has the advantage that all the taps are in the one byte, so the code is a little more efficient.

[Artlover]

Odd ramble from C64 days, which may or may not be of any value to anyone.

 

We used to seed the RND off a derivative of the system counter/clock.

[Thomas Jentzsch]

I tested the routine I posted and it does work. It repeats correctly and it fills 8192 bytes worth of bits where each number is mapped to one bit.

Confirmed.

 

I am a bit surprised that you can get away with EORing only one byte. We should test the randomness compared to other 16-bit LFSRs.

Edited January 9, 2006 by Thomas Jentzsch

[Artlover]

Ah, just noticed this is the 2600 programm section. Does the 2600 even have a system counter? Could this be why there was mention of using the frame counter. I should probably shut up and go away, being a total 2600 programming noob.

[Thomas Jentzsch]

Does the 2600 even have a system counter? Could this be why there was mention of using the frame counter. I should probably shut up and go away, being a total 2600 programming noob.   

996841[/snapback]

No, yes and yes!

[Bruce Tomlin]

I am not sure if this is a working LFSR pattern. According to my docs, for a 16 bit LFSR, you always have to EOR both registers

Interesting link. But I downloaded the 16-bit table and it had these numbers in it:

 

9C00 B400 BD00 CA00 EB00 FC00

 

So apparently you actually don't always have to EOR both bytes with the feedback. Those might not produce well distributed sequences, but apparently they do produce full sequences.

 

 

Some things that can be done to improve randomness are:

 

* use a much larger shift register than the range of randomness you need (for instance, by using no more than 8 bits per call out of a 16-bit LFSR)

 

* call the random number generator and throwing away the results quite often, dependent upon user input. Or XOR parts of the seed with external input. The fractional part of user response time is itself truly random (if the granularity of sampling is fast enough), and can be used to add some randomness to your RNG in this way.

 

* increase the granularity of such sampling by using fast counters. In the 2600, the RIOT timer runs at full speed after it expires, and on a Z-80 based system, the R register is a 7-bit counter that constantly increments for DRAM refresh.

[+batari]

I am not sure if this is a working LFSR pattern. According to my docs, for a 16 bit LFSR, you always have to EOR both registers

Interesting link. But I downloaded the 16-bit table and it had these numbers in it:

 

9C00 B400 BD00 CA00 EB00 FC00

996945[/snapback]

Cool... So djmips's routine is actually using EB00, but with reversed bit order.

 

D7 = 1101 0111

EB = 1110 1011

 

It's nice and short but still uses that extra byte of RAM, so I think I will add this code in as an option, with the requirement that the user dim rand1 as a variable, in case a better random number generator is needed. So no need to use inline asm here once the new version of bB is out...

[+batari]

OK, after some investigation, I think this will work as a general-purpose 8-bit OR 16-bit LFSR. All the user needs to do to use a 16-bit random number is:

 

dim rand16={variable}

 

randomize
       lda rand
       lsr
ifconst rand16
       ror rand16
endif
       bcc noeor
       eor #$B4
noeor
       sta rand 
       rts
          

Cool, huh?

Edited January 10, 2006 by batari

[djmips]

Cool, huh?

997142[/snapback]

 

 

Yes.

 

I would be nice to also initialize rand16 to get more than 1 of 255 starting cycles, but since you are using INTIM which is only one byte I don't know where you'd get the other byte at startup.

 

BTW - is INTIM really random? Do you get 255 different startup values? How does it behave on all the various versions of hardware (including the FB2). I see in the Z26 release notes that they explicitly randomize INTIM on startup....

[supercat]

OK, after some investigation, I think this will work as a general-purpose 8-bit OR 16-bit LFSR.  All the user needs to do to use a 16-bit random number is:

997142[/snapback]

 

When using a 16-bit LFSR, I'd highly recommend shifting the two halves in opposite directions and getting a result by XOR'ing them together. Depending upon the constant used, this will allow all 65,535 byte pairs other than (0,0) to appear on consecutive invocations (i.e. after reading one byte, the next byte can be anything unless the first byte was zero, in which case the second byte can be anything non-zero).

 

Also, although I've not done it yet in my own code, I'd suggest that it might be good to, in the Kernel's "wait for timer" loop, to spin the random number generator continuously until the RIOT is within 1 count (64 cycles) of being correct, then WSYNC until the RIOT has the right value.

[supercat]

I would be nice to also initialize rand16 to get more than 1 of 255 starting cycles, but since you are using INTIM which is only one byte I don't know where you'd get the other byte at startup.

997167[/snapback]

 

On a real 2600, INTIM will probably be pretty random. Even if it were to always start with the same value, a 0.1% variation in the time required to charge the reset timing capacitor would probably be sufficient to generate all INTIM values.

 

Other sources of randomness on a real 2600 include the TIA line phase (store a zero in TIM1T, then do a sta WSYNC, and INTIM may then read any of 76 different values) and RAM contents on startup. The 7800 will preload memory with fixed values, however, and I wouldn't be surprised if it clobbers the TIA line phase as well. Still, even 256 choices for cartridge startup should be enough, especially if every control input can affect things unpredictably.