your fave random routine

[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:

 

_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 May 13, 2007 by Heaven/TQA

[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]

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]

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]

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 May 15, 2007 by batari

[Thomas Jentzsch]

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]

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]

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!)

 

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]

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]

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.