It is currently Tue Jun 18, 2019 6:12 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 29 posts ]  Go to page Previous  1, 2
Author Message
 Post subject:
PostPosted: Fri Aug 06, 2010 6:26 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21441
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 07, 2010 12:51 am 
Offline
User avatar

Joined: Tue Apr 28, 2009 4:12 am
Posts: 469
@Tetris randomiser : just ace! I wish I could think like that :D


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 07, 2010 2:25 am 
Offline

Joined: Wed Jul 30, 2008 12:03 am
Posts: 34
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:
 ; 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.


Last edited by bogax on Sat Aug 07, 2010 11:52 am, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 07, 2010 4:46 am 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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:
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.


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 07, 2010 6:46 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21441
Location: NE Indiana, USA (NTSC)
Or in C:
Code:
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.


Top
 Profile  
 
PostPosted: Tue Mar 05, 2013 4:08 pm 
Offline
User avatar

Joined: Sun Mar 16, 2008 1:45 am
Posts: 114
Location: Uppsala, Sweden
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.


Last edited by Dafydd on Wed Mar 06, 2013 11:25 am, edited 2 times in total.

Top
 Profile  
 
PostPosted: Tue Mar 05, 2013 4:42 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21441
Location: NE Indiana, USA (NTSC)
What I'd use is a 16-bit LFSR (use Greg Cook's CRC16 from 6502.org) feeding Fisher-Yates.

_________________
Pin Eight | Twitter | GitHub | Patreon


Top
 Profile  
 
PostPosted: Tue Mar 05, 2013 5:01 pm 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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.


Top
 Profile  
 
PostPosted: Tue Mar 05, 2013 5:18 pm 
Offline
User avatar

Joined: Sun Mar 16, 2008 1:45 am
Posts: 114
Location: Uppsala, Sweden
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.


Top
 Profile  
 
PostPosted: Tue Mar 05, 2013 5:31 pm 
Offline
User avatar

Joined: Sun Mar 16, 2008 1:45 am
Posts: 114
Location: Uppsala, Sweden
Now I'm really confused. When swapping a[i] 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.


Top
 Profile  
 
PostPosted: Tue Mar 05, 2013 6:11 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21441
Location: NE Indiana, USA (NTSC)
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.

_________________
Pin Eight | Twitter | GitHub | Patreon


Top
 Profile  
 
PostPosted: Tue Mar 05, 2013 6:21 pm 
Offline
User avatar

Joined: Sun Mar 16, 2008 1:45 am
Posts: 114
Location: Uppsala, Sweden
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!


Top
 Profile  
 
PostPosted: Sat Mar 09, 2013 1:03 am 
Offline
User avatar

Joined: Mon Feb 07, 2011 12:46 pm
Posts: 1040
I used ARCFOUR, running several times per frame when nothing else is doing, and including the microphone if it is available.

_________________
.


Top
 Profile  
 
PostPosted: Tue Mar 12, 2013 5:36 am 
Offline
User avatar

Joined: Wed Feb 13, 2008 9:10 am
Posts: 694
Location: Estonia, Rapla city (50 and 60Hz compatible :P)
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:
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...

_________________
http://www.tmeeco.eu


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 29 posts ]  Go to page Previous  1, 2

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group