Ideal Two Parameter PRNG

[+Gemintronic]

I'm looking for the ideal pseudo random number generator that takes two 8-bit values as input.

 

The requirements are:

 

* The result of prng(128, 25) should be different from prng(25, 128)

* Fairly decent distribution. i.e. it should be hard for the end user to detect a pattern.

* Should not cause the CPU to go over cycle

 

I already have a cobbled together solution for my Destiny game but it goes over cycle.

http://www.atariage....86-destiny-wip/

 

 

A two parameter PRNG would make large world Atari 2600 games easy to implement as worldx/worldy could be used as inputs to generate unique areas.

 

Any thoughts on how to implement this would be greatly appreciated!

[+GroovyBee]

What are the parameters for? Are they the range or the seed?

[+Omegamatrix]

Edit: Groovybee already asked it above.

[+Gemintronic]

What are the parameters for? Are they the range or the seed?

 

I'd say prng(worldx, worldy) and leave the output to be 0-255

 

So, yes. The two input values would be a seed. Which is also why I would like (234, 43) to generate a different output than (43, 234)

 

At one point I tried:

 

output = (worldx + worldy + worldy)

 

But that didn't seem to give greatly random results.

[+GroovyBee]

There are some very economical PRNGs e.g. :-

 

   lda theRand256Seed
   lsr
   bcc @AllDone
   eor #$B8
@AllDone:
   sta theRand256Seed

 

Takes an 8 bit seed (not zero!) and gives an 8 bit random number in A.

[+Gemintronic]

There are some very economical PRNGs e.g. :-

 

lda theRand256Seed
lsr
bcc @AllDone
eor #$B8
@AllDone:
sta theRand256Seed

 

Takes an 8 bit seed (not zero!) and gives an 8 bit random number in A.

 

Does that take two parameters for the seed? How about the distribution? How would I give it the two arguments and retrieve the result in bB?

 

The idea here is similar to the polynomial counter in Pitfall. Instead of a 1 dimensional plane I'd like to use it for a 2D grid. Every time the player lands on worldx = 145 by worldy = 200 it should output the same unique number for that area.

[+Omegamatrix]

There are some very economical PRNGs e.g. :-

 

lda theRand256Seed
lsr
bcc @AllDone
eor #$B8
@AllDone:
sta theRand256Seed

 

Takes an 8 bit seed (not zero!) and gives an 8 bit random number in A.

 

Yes, that is essentially the random generator BB is using, except for #$B4 as a EOR value. The rand16 gives to possibility of a zero. It might be easy to pass the 2nd parameter as an EOR value. Or just make a copy of rand16 that uses a different hardcoded EOR value.

 

Here's BB's Rand routine

 

randomize
  lda rand
  lsr
ifconst rand16
  rol rand16
endif
  bcc noeor
  eor #$B4
noeor
  sta rand
ifconst rand16
  eor rand16
endif
  RETURN

[+GroovyBee]

Only takes an 8 bit parameter and will repeat after 255 calls.

[+GroovyBee]

If thats almost the same as the bB version then theloon's bottleneck isn't the random function its something else.

[+Gemintronic]

Thank for the input! Um, how does a one argument/seed routine help in my case?

 

 

The idea here is similar to the polynomial counter in Pitfall. Instead of a 1 dimensional plane I'd like to use it for a 2D grid. Every time the player lands on worldx = 145 by worldy = 200 it should output the same unique number for that area.

[+GroovyBee]

How do you get to that grid reference? Is it a linear course?

[+Gemintronic]

How do you get to that grid reference? Is it a linear course?

 

My failing math experience is obviously making this more difficult than it should be to explain.

 

Assuming a level map consists of a 2d array each screen would have a type value between 0-255

 

So, level[23,45] might have a value of 242. Where x, y is the screen location in the level and the output value is the type of screen (outside of castle, blue maze area, hallway, etc..)

 

I intend to use a pseudo random number generator to calculate each room type value per worldx/worldy coordinate instead of storing in a 2d array.

 

Something along the lines of a = prng(worldx, worldy) where worldx and worldy are seed values and a is the result of the pseudo random number generator.

 

I cannot use a single seed prng because the level data must not be symmetrical. If I fed rand = (worldx + worldy) then it would output the same value as rand = (worldy + worldx)

[+SpiceWare]

I did a couple of blog entries for Frantic about how I generated the walls based on the room's X, Y position within the "building". The X and Y values are both 0-255.

 

Basically you want to use a 16-bit Linear Feedback Shift Register. Searching for 6502 16-bit LFSR turns up a number of prior posts here at AtariAge. Batari posted a nice one here:

 

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

[+Gemintronic]

I did a couple of blog entries for Frantic about how I generated the walls based on the room's X, Y position within the "building". The X and Y values are both 0-255.

 

Basically you want to use a 16-bit Linear Feedback Shift Register. Searching for 6502 16-bit LFSR turns up a number of prior posts here at AtariAge. Batari posted a nice one here:

 

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

 

Hmmn, thanks SpiceWare! So, I store worldx in rand and worldy into rand1 and run this inline asm.. then read the value of rand into a result variable?

[enthusi]

I can highly recommend codebase64.org

There you find pretty nice PRNGs. In your case Id use an 16bit prng.

x as LSB, y as MSB and if you need 8bit result only, you can just ditch either byte.

For that you need a better PRNG as the one posted first.

Also take a look at the magic-byte list. Not every combination yields ALL 256 output bytes!

And depending on what you want to achieve, that can be pretty ugly.

For those shifters, the upper bits are quite often 'more random'.

If you can afford an extra page of memory I'd use the outcome of the PRNG as a pointer into a page of REAL random data.

For my recent C64 game I set up a real Rijandel SBOX for that but that's kinda overkill

[+SpiceWare]

Yep. Per this bB already supports 16-bit LFSR, and it wouldn't surprise me in the least if it's that exact same routine that I quoted from batari's post.

The standard random number generator should be random enough for most games. However, if it isn't random enough, you can optionally specify a 16-bit random number generator. This requires that you set aside one variable, and you can't use this variable for other purposes. To use the improved routine, place:

 

dim rand16 = <var>

 

at the beginning of your program. <var> is one of your 26 variables (a-z.) Then you use rand as you normally would.

 

to use it you'd set rand=worldx and rand16=worldy

Edited March 15, 2013 by SpiceWare

[+RevEng]

Yep. Per this bB already supports 16-bit LFSR...

 

Yep. I threw together a quick example of running and rerunning a sequence with the bB rand-LFSR in the Simon Says thread.

 

theloon, if you want to use random numbers elsewhere in your game you'll need to save rand and rand16 before setting them to your seed values, and restore them when you're done.