I used this method, which I called "possession arrow", to simulate a uniform randomizer in versions of LJ65 (then called tetramino) prior to 0.33. In that version, I switched to the LRU system to reduce repetition, following Arika's TGM games that use a conceptually similar system.Kasumi wrote:Seven pieces. He used 3 bits. Seven of the possibilities deal the piece it corresponds to. (1= I, 2 = O, etc.) When the eighth possibility comes up he increments (or decrements) and wraps around a variable and deals the piece that corresponds to the current value of the variable.
Random Number Generation?
Moderator: Moderators
- neilbaldwin
- Posts: 481
- Joined: Tue Apr 28, 2009 4:12 am
- Contact:
This question comes up a lot, so I've thought about it some.
I'm not sure I'm analyzing it correctly (and I haven't actually
tested it so take this with agrain of salt )
My thought is to take a random number MOD your range and then
accumulate and hope that the bias accumulates and distributes
itself over the range. (or the bias ends up "diluted" in the
accumulation, depending on how you look at it)
Choose a range of random numbers that's easy to MOD to your target
range.
So eg if you random number generator returns numbers 0-FF,
and you want random numbers in the range 0-1B mask off the lower
five bits (the next higher power of two, and if you start with
a range that's a power of two and MOD for a range thats a power
of two that shouldn't introduce any bias)
MOD that to your target range
Add it to your random number accumulator
MOD that to your target range.
something like this:
Edit:
I forgot to mention you could use the next lesser power of two
to start and save some MODing.
My gut says that the larger the range you start with the better
off you'll be distribution wise.
So it becomes something of a trade off between the size of the range
and the effort spent doing the MOD.
I'd guess that using the next lesser power of two probably
wouldn't make a lot of difference especially if it's close to
your target range.
I'm not sure I'm analyzing it correctly (and I haven't actually
tested it so take this with agrain of salt )
My thought is to take a random number MOD your range and then
accumulate and hope that the bias accumulates and distributes
itself over the range. (or the bias ends up "diluted" in the
accumulation, depending on how you look at it)
Choose a range of random numbers that's easy to MOD to your target
range.
So eg if you random number generator returns numbers 0-FF,
and you want random numbers in the range 0-1B mask off the lower
five bits (the next higher power of two, and if you start with
a range that's a power of two and MOD for a range thats a power
of two that shouldn't introduce any bias)
MOD that to your target range
Add it to your random number accumulator
MOD that to your target range.
something like this:
Code: Select all
; return a number in the range 0-1B
; start with a random number 0-FF in a
; myrand needs to be intialized to be in range
; MOD to an easier power of two
and #$1F ; the assumption is if a is random in a range
; that's a power of two this result should be random
; MOD that to the target range
cmp #$1C
bcs ACCUMULATE
sbc #$1B ; biased to account for carry clear
ACCUMULATE
clc
adc myrand
; MOD to the target range
cmp #$1C
bcs SAVE_MYRAND
sbc #$1B ; biased to account for carry clear
SAVE_MYRAND
sta myrand
rts
I forgot to mention you could use the next lesser power of two
to start and save some MODing.
My gut says that the larger the range you start with the better
off you'll be distribution wise.
So it becomes something of a trade off between the size of the range
and the effort spent doing the MOD.
I'd guess that using the next lesser power of two probably
wouldn't make a lot of difference especially if it's close to
your target range.
Last edited by bogax on Sat Aug 07, 2010 11:52 am, edited 1 time in total.
Here's one I came up with for use to generate a random value between 0-79, with uniform distribution (for use in Litewall, which has a 10x8 grid it wants to generate random coordinates into):
It divides by 80 and takes the modulus. This takes care of the first 240 values, leaving 16 extra. In that case, it gets a new random value and tries again. The probability of retrying the first time is 16 in 256, or 1 in 16. The probability of it retrying two times in a row is 1 in 16*16 = 1 in 256, and so on. This means that on average, it takes only slightly longer than random_256, but worst-case, it could take forever, assuming random_256 has an infinite period. If random_256 is a simple 8-bit LFSR, this routine will always terminate, since random_256 would then generate each value every 256 calls.
Code: Select all
random_80:
@retry:
jsr random_256 ; A = random 8-bit value
sec
sbc #80
bcc @done
sbc #80
bcc @done
sbc #80
bcs @retry
@done:
adc #80
rts
Or in C:
Code: Select all
unsigned char rand80() {
unsigned char raw;
do {
raw = random_256();
} while (raw >= 240);
return raw % 80;
}
In a video game or a real-time demo, you want the RNG to terminate within a guaranteed amount of cycles so that you don't overflow frame time. In this case, I'd recommend something similar to possession arrow logic for cases where the base RNG returns 240-255: increment a counter by 16 (mod 80) and then combine that with the low bits of the remainder. Or 3 bits for Y and 3 bits plus an LRU unit for X.blargg wrote:If random_256 is a simple 8-bit LFSR, this routine will always terminate
Re: Random Number Generation?
Sorry for the necro post, but I didn't see another thread on the topic.
I want to produce a large number of random sequences of the numbers 0-15 where each number must occur exactly once. A 4-bit LSFR would make the sequence predictable very quickly, and an 8-bit LSFR (which would be much less predictable) doesn't guarantee that any 4 bits I choose (the last 4 out of 8, for example) do not have the same combination of values in a 16 values long sequence, as far as I know.
One solution could be to run fisher-yates on an array of the numbers I want, where the random number (i.e. the index) is taken from the last 4 bits of an 8-bit LSFR (picking the next value or truncating it should it be out of range) that is periodically seeded by the unknowing player by counting the number of frames passed between certain actions (in this case, pulling the trigger on the Zapper). That should give pretty good randomness, but I could be wrong, and I don't even know whether there's a way I could prove myself right or wrong.
Another solution could be to keep a table of sequences that are chosen from by the aforementioned frame counter, but that seems like a pretty bad idea considering, uh, [grabs a calculator] there are nearly 21 trillion different possible sequences and each sequence would need 8 bytes of memory for storage. So yeah, very bad idea.
So... does anyone feel right away that the 8-bit LSFR + Fisher-Yates solution is also a bad idea, for any reason? In particular, is anyone good enough at math to tell me whether or the sequences that are produced by this method are equally likely to happen, or whether there's a tendency to prefer a particular set of sequences? The delay between trigger pulls is likely to have some kind of normal distribution around 60 frames or so, but other than that... not sure whether I should investigate further or just try it and see how well it works. It's going to be in silico either way.
I want to produce a large number of random sequences of the numbers 0-15 where each number must occur exactly once. A 4-bit LSFR would make the sequence predictable very quickly, and an 8-bit LSFR (which would be much less predictable) doesn't guarantee that any 4 bits I choose (the last 4 out of 8, for example) do not have the same combination of values in a 16 values long sequence, as far as I know.
One solution could be to run fisher-yates on an array of the numbers I want, where the random number (i.e. the index) is taken from the last 4 bits of an 8-bit LSFR (picking the next value or truncating it should it be out of range) that is periodically seeded by the unknowing player by counting the number of frames passed between certain actions (in this case, pulling the trigger on the Zapper). That should give pretty good randomness, but I could be wrong, and I don't even know whether there's a way I could prove myself right or wrong.
Another solution could be to keep a table of sequences that are chosen from by the aforementioned frame counter, but that seems like a pretty bad idea considering, uh, [grabs a calculator] there are nearly 21 trillion different possible sequences and each sequence would need 8 bytes of memory for storage. So yeah, very bad idea.
So... does anyone feel right away that the 8-bit LSFR + Fisher-Yates solution is also a bad idea, for any reason? In particular, is anyone good enough at math to tell me whether or the sequences that are produced by this method are equally likely to happen, or whether there's a tendency to prefer a particular set of sequences? The delay between trigger pulls is likely to have some kind of normal distribution around 60 frames or so, but other than that... not sure whether I should investigate further or just try it and see how well it works. It's going to be in silico either way.
Last edited by Dafydd on Wed Mar 06, 2013 11:25 am, edited 2 times in total.
Re: Random Number Generation?
What I'd use is a 16-bit LFSR (use Greg Cook's CRC16 from 6502.org) feeding Fisher-Yates.
Re: Random Number Generation?
Is there any reason you can't do a straightforward shuffle of 16 values in RAM? Write an array with 0-15, then step through each of the 16 entries and swap it with a random entry from the array.
Re: Random Number Generation?
How is a "straightforward" shuffle different from Fisher-Yates? It swaps with any value, not just the remaining ones? How does that ensure I don't get more than one of the same value in the sequence?
EDIT: Oh, wait. I'm stupid. Sorry.
EDIT: Oh, wait. I'm stupid. Sorry.
Re: Random Number Generation?
Now I'm really confused. When swapping a with a[j] in an array of length N, what is the purpose of having 0 <= j <= i (as in Fisher-Yates) when it might as well be 0 <= j <= N-1 (as blargg suggests)? It should have something to do with breaking the (un-)bias, but I don't know for sure.
Re: Random Number Generation?
In theory, there's a bias in the case of 0 <= j < N. Proof: There are N! distinct permutations after the algorithm. With 0 <= j <= i, there are also N! distinct paths to these permutations. But with 0 <= j < N, there are N^N equally distributed paths. Because N! does not generally divide N^N (example: N = 3; 3! = 6 does not divide 3^3 = 27), these states don't all have the same number of paths to them; therefore bias.
But in practice, I dare someone else to prove that this bias is any more noticeable than the limitation that a CRC16 can generate only 65536 of the 2.1×10¹³ distinct permutations.
But in practice, I dare someone else to prove that this bias is any more noticeable than the limitation that a CRC16 can generate only 65536 of the 2.1×10¹³ distinct permutations.
Re: Random Number Generation?
I drew a trinary tree of possibilities for the array of [1, 2, 3] (i.e. length 3) and came up with 27 leaves, distributed like so:
123 x 4
132 x 5
213 x 5
231 x 5
312 x 4
321 x 4
I came up with a more elegant explanation, but tepples beat me to it.
Anyway, in this particular case, as tepples suggests, I think I'll run with blargg's version, because it's much easier to implement, and because the bias isn't going to matter, especially since the input will be shuffled from last time anyway.
Thanks, guys!
123 x 4
132 x 5
213 x 5
231 x 5
312 x 4
321 x 4
I came up with a more elegant explanation, but tepples beat me to it.
Anyway, in this particular case, as tepples suggests, I think I'll run with blargg's version, because it's much easier to implement, and because the bias isn't going to matter, especially since the input will be shuffled from last time anyway.
Thanks, guys!
Re: Random Number Generation?
I used ARCFOUR, running several times per frame when nothing else is doing, and including the microphone if it is available.
(Free Hero Mesh - FOSS puzzle game engine)
- TmEE
- Posts: 960
- Joined: Wed Feb 13, 2008 9:10 am
- Location: Norway (50 and 60Hz compatible :P)
- Contact:
Re: Random Number Generation?
This is not exactly NES stuff but in my MD game "Glass Breaker" I used this to create some garbage for random enemy business :
It takes quite little time and provided me adequate enough output for the things I needed.
I did not really spend much time on, just arranged some instructions until I got satisfying result...
Code: Select all
MOVE.W (GARBAGE), D0
MOVE.W D0, D1
NOT.W D1
ROR.W #3, D0
EOR.W D1, D2
ADD.W D1, D0
ROL.W #7, D1
ADD.W D1, D0
EOR.W D2, D0
MOVE.W D0, (GARBAGE)
I did not really spend much time on, just arranged some instructions until I got satisfying result...