15 replies to this topic

[Heaven/TQA]

what is your fave "seed based" random routine? i am using this one for generating level maps so it should be able to recreate the sequenze:

[code]
_get_Random: ;cld
_rand inc rnd2
lda rnd2
clc
adc rnd1
adc rnd2
sta rnd1
eor rnd2
sta rnd2
sbc rnd0
sta rnd0
rts

rnd0 dta 0
rnd1 dta 0
rnd2 dta 0

[Thomas Jentzsch]

I prefer LSFRs:

  lda random
  lsr
  bcc .skipEor
  eor #$b2
.skipEor
  sta random

Just 8 bits, but works similar with 16 or more bits too.

[Heaven/TQA]

thanks Thomas, where do i store the starting seed (=level # of the map)? i guess random? ;=)?

Edited by Heaven/TQA, Sun May 13, 2007 2:57 PM.

[Thomas Jentzsch]

Not sure if I get you.

Just load random with the initial value for that level.

[Heaven/TQA]

but thomas. looking at your code... what happens when random=0? i mean for me it will skip the EOR forever so it will stay at 0?

[Thomas Jentzsch]

Heaven/TQA, on Mon May 14, 2007 12:18 PM, said:

but thomas. looking at your code... what happens when random=0? i mean for me it will skip the EOR forever so it will stay at 0?

Unless initialized with 0, this will never happen (bit 7 is always set with EOR).

BTW: There are several "good" EOR values, resulting into a 255 different values sequence.

Info here: http://www.ece.cmu.edu/~koopman/lfsr/

[supercat]

Thomas Jentzsch, on Mon May 14, 2007 8:39 AM, said:

BTW: There are several "good" EOR values, resulting into a 255 different values sequence.

I prefer to use a 16-bit randomizer, with one half shifting right and the other shifting left. That avoids some of the patterns that may otherwise appear. Another approach is to XOR the output of the randomizer with some other variable. This will also help avoid many types of patterns.

[Heaven/TQA]

supercat. any code example?

[batari]

Heaven/TQA, on Tue May 15, 2007 12:33 AM, said:

supercat. any code example?

This is a 16-bit LFSR that uses Supercat's suggestions:

randomize
		lda rand
		lsr
		rol rand16
		bcc noeor
		eor #$B4
noeor
		sta rand
		eor rand16
		rts

You need two bytes, rand and rand16. You can seed this routine with anything except two zeros. To use it, just JSR there and you get a random byte in the accumulator.

Edited by batari, Tue May 15, 2007 12:35 AM.

[Thomas Jentzsch]

batari, on Tue May 15, 2007 8:35 AM, said:

This is a 16-bit LFSR that uses Supercat's suggestions:

Not a very good LFSR, since it doesn't eor rand16 and the generated sequence is (probably much) shorter than 2^16-1. Taking a good 16 bit value from the link I posted above, mirroring the high byte and eoring that one too would result into better randoms.

Though I doubt shifting in different directions or eoring high and low bytes makes the result any more random.

NextRandom SUBROUTINE
  lda randHi
  lsr
  ror randLo
  bcc .skipEor
  eor #HI_EOR
  sta randHi
  lda randLo
  eor #LO_EOR
  sta randLo
.skipEor:
  lda randLo

BTW: Actually a LFSR generates just one single bit with each iteration. The other bits are depending on each other somehow.

[batari]

Thomas Jentzsch, on Tue May 15, 2007 9:13 AM, said:

batari, on Tue May 15, 2007 8:35 AM, said:

This is a 16-bit LFSR that uses Supercat's suggestions:

Not a very good LFSR, since it doesn't eor rand16 and the generated sequence is (probably much) shorter than 2^16-1. Taking a good 16 bit value from the link I posted above, mirroring the high byte and eoring that one too would result into better randoms.

Though I doubt shifting in different directions or eoring high and low bytes makes the result any more random.

It actually is 65535 bytes long. And while rand16 isn't eor'ed with a constant, its result isn't intended to be used as a random number.

Shifting opposite directions doesn't make it more random, but the eor at the end does reduce the correlation with previous values according to random number tests (and this routine had excellent results from said tests.)

[Thomas Jentzsch]

batari, on Tue May 15, 2007 8:58 PM, said:

It actually is 65535 bytes long. And while rand16 isn't eor'ed with a constant, its result isn't intended to be used as a random number.

I stand corrected. (notes to himself: next time check the complete list!)

Quote

but the eor at the end does reduce the correlation with previous values according to random number tests (and this routine had excellent results from said tests.)

Do you have any links? I am really interested.

[Thomas Jentzsch]

I did some tests with Ent.

Supercats sequence is no better than a normal 16 bit sequence, except for sequence correlation. There is is much better than the normal LFSR!

[DEBRO]

Thomas Jentzsch, on Mon May 14, 2007 9:39 AM, said:

Heaven/TQA, on Mon May 14, 2007 12:18 PM, said:

but thomas. looking at your code... what happens when random=0? i mean for me it will skip the EOR forever so it will stay at 0?

Unless initialized with 0, this will never happen (bit 7 is always set with EOR).

BTW: There are several "good" EOR values, resulting into a 255 different values sequence.

Info here: http://www.ece.cmu.edu/~koopman/lfsr/

If you do bcs instead of bcc then you will get 255 values regardless of the seed being 0. I wrote a test for this that spit out the 255 values (or was it 256...I can't remember).

[supercat]

Thomas Jentzsch, on Tue May 15, 2007 3:33 PM, said:

Supercats sequence is no better than a normal 16 bit sequence, except for sequence correlation. There is is much better than the normal LFSR!

If you generate 8 bit random numbers by using half of a normal 16-bit LFSR, or the XOR of the top and bottom halves, then after some value is output the next number can only have one of two values (based upon whether the other half of the generator shifts out a '1'). By contrast, when using opposite-direction shifts, any value may be output after any other value, except that a zero will not follow another zero. The only "ugliness" in the generator occurs when it outputs the sequence (128,64,32,16,4,2,1,1,2,4,8,16,32,64,128). Depending upon what the generator is being used for, XORing the output with a constant like $B3 may make that pattern less objectionable.

[Heaven/TQA]

i will use the random routines for building level maps... i will see how they perform at the end of the day.