Page 2 of 2

Posted: Fri Aug 06, 2010 6:26 pm
by tepples
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.
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.

Posted: Sat Aug 07, 2010 12:51 am
by neilbaldwin
@Tetris randomiser : just ace! I wish I could think like that :D

Posted: Sat Aug 07, 2010 2:25 am
by bogax
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:

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
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.

Posted: Sat Aug 07, 2010 4:46 am
by blargg
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):

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
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.

Posted: Sat Aug 07, 2010 6:46 am
by tepples
Or in C:

Code: Select all

unsigned char rand80() {
  unsigned char raw;
  do {
    raw = random_256();
  } while (raw >= 240);
  return raw % 80;
}
blargg wrote:If random_256 is a simple 8-bit LFSR, this routine will always terminate
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.

Re: Random Number Generation?

Posted: Tue Mar 05, 2013 4:08 pm
by Dafydd
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.

Re: Random Number Generation?

Posted: Tue Mar 05, 2013 4:42 pm
by tepples
What I'd use is a 16-bit LFSR (use Greg Cook's CRC16 from 6502.org) feeding Fisher-Yates.

Re: Random Number Generation?

Posted: Tue Mar 05, 2013 5:01 pm
by blargg
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?

Posted: Tue Mar 05, 2013 5:18 pm
by Dafydd
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.

Re: Random Number Generation?

Posted: Tue Mar 05, 2013 5:31 pm
by Dafydd
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?

Posted: Tue Mar 05, 2013 6:11 pm
by tepples
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.

Re: Random Number Generation?

Posted: Tue Mar 05, 2013 6:21 pm
by Dafydd
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!

Re: Random Number Generation?

Posted: Sat Mar 09, 2013 1:03 am
by zzo38
I used ARCFOUR, running several times per frame when nothing else is doing, and including the microphone if it is available.

Re: Random Number Generation?

Posted: Tue Mar 12, 2013 5:36 am
by TmEE
This is not exactly NES stuff but in my MD game "Glass Breaker" I used this to create some garbage for random enemy business :

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