It is currently Sat Dec 16, 2017 12:28 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 44 posts ]  Go to page 1, 2, 3  Next
Author Message
PostPosted: Thu Jul 07, 2016 12:55 am 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1516
Would you say that the randomizer of CC65 is a good one?
https://github.com/cc65/cc65/blob/maste ... mon/rand.s

My problem is: I have a character in a game that has a 3 out of 8 chance to do the motion where it is attackable.

My call is basically this:
Code:
/* 3 out of 8 chance
   (random values can go from 0-7)
   to be attackable. */
if ((rand() & 0x07) < 3)
    PrepareMovementAttackable();

/* If non-attackable,
   the movement is chosen by a
   1 to 1 (i.e. 1 out of 2) chance. */
else if ((rand() & 0x01) == 0)
    PrepareMovementNonAttackable1();
else
    PrepareMovementNonAttackable2();

But the attackable movement is triggered quite rarely.

Yesterday, the character did a non-attackable movement probably 10 times in a row before I finally gave up.
(In the moment, I only have one distinct non-attackable movement, so I couldn't check in how much that second random call switched between both alternatives.)

Is this normal? Or is the randomizer crap?

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 1:39 am 
Offline
User avatar

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1046
I would say it's normal. A random number generator does not try for an even distribution of values. It tries for random values. It does not try to flip heads only half the time. It could flip heads 10 times in a row.

If that is not desirable you can use a variable so that it doesn't do the non-attackable movement more than X times in a row even if the random number generator says that's what it should do.

_________________
https://kasumi.itch.io/indivisible


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 2:01 am 
Offline
User avatar

Joined: Sun Sep 19, 2004 9:28 pm
Posts: 3192
Location: Mountain View, CA, USA
I don't see a call to srand() anywhere. Maybe that's partially the problem? (Normally with libc you only call this function once)

But in general, I can't see how a "generic rand()" is going to be "extremely random". A per-system (and/or per-architecture) implementation would be needed. There should be several threads here on the forum of how people go about getting "random data" in their NES games. In fact, here's a great one.


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 2:17 am 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1516
Kasumi wrote:
I would say it's normal. A random number generator does not try for an even distribution of values. It tries for random values. It does not try to flip heads only half the time. It could flip heads 10 times in a row.

Sure, but I had to struggle with this for a few times now. It's never that the attackable movement comes too often. It's always the non-attackable that is much more frequent. (But the attackable stuff does appear from time to time.)

Kasumi wrote:
If that is not desirable you can use a variable so that it doesn't do the non-attackable movement more than X times in a row even if the random number generator says that's what it should do.

Sure, I can do this when the randomizer is definitely working correctly. But first I need to be sure that the randomizer itself isn't faulty.

koitsu wrote:
I don't see a call to srand() anywhere. Maybe that's partially the problem?

You don't see a function head either, do you? Which means it was just a code snippet and not a fully-working example. So, why do you think that the srand function should be anywhere near the movement function of one specific character?

koitsu wrote:
But in general, I can't see how a "generic rand()" is going to be "extremely random".

It doesn't need to be extremely random, but the one that I'm using still seems a little off.

koitsu wrote:
There should be several threads here on the forum of how people go about getting "random data" in their NES games.

If I'm not even sure whether one specific randomizer works correctly, in how far would it help me to have 10 more randomizers (unconfirmed ones, that is) that people posted in various forum threads?

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 3:56 am 
Offline
User avatar

Joined: Mon Jan 03, 2005 10:36 am
Posts: 2983
Location: Tampere, Finland
Here's another older thread about RNGs: viewtopic.php?f=2&t=9598. One trick shown there is that you can keep running the RNG in your VBlank poll loop, which will add an ounce of randomness to the mix since the poll time typically varies.

I know linear congruential RNGs, often used on modern platforms for rand(), have widely documented problems with randomness if you use modulo (or bitwise AND) to limit their range. But cc65's implementation is probably not a LCG because that would require a multiplication.

If you want some data, you can quite easily test the implementation by using the "sim65" target of cc65. Just generate some numbers with rand() (possibly with some additional masking), print with printf(), and look at the results in a spreadsheet program or whatever floats your boat.

EDIT: Turns it out it is an LCG in ca65, just with a multiplier (0x01010101) that allows an efficient implementation.

_________________
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: kkfos.aspekt.fi


Last edited by thefox on Thu Jul 07, 2016 10:33 am, edited 2 times in total.

Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 4:27 am 
Offline

Joined: Mon May 27, 2013 9:40 am
Posts: 363
Even if it's not perfect, I'm quite content with Shiru's implementation in neslib. Have you tried?

_________________
http://www.mojontwins.com


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 5:40 am 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 1868
Location: DIGDUG
I think this is another example of 'humans don't understand the concept of randomization'

http://www.dailymail.co.uk/home/moslive ... stand.html

Like when you tell an ipod to shuffle, but then get mad when it plays two songs from the same artist in a row.

If you want a hard 3 times out of 8, have it randomly pick from SETS of 8 (pre-shuffled), where each set has exactly 3 in it (but in a different order).

_________________
nesdoug.com -- blog/tutorial on programming for the NES


Last edited by dougeff on Thu Jul 07, 2016 5:44 am, edited 1 time in total.

Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 5:42 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7317
Location: Chexbres, VD, Switzerland
Quote:
Like when you tell an ipod to shuffle, but then get mad when it plays two songs from the same artist in a row.

Actually, some shufflers picks the same song twice, which sucks a bit.


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 5:47 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19348
Location: NE Indiana, USA (NTSC)
Some game designs make an enemy invulnerable at random times, make no attempt to ensure an occasional vulnerable state, and give the player no way to bypass the encounter. These games have a flaw that the invulnerable state may last too long if the player. A Luck-Based Mission is rarely fun.

If you want short-term randomness but don't want a long-term string of the same result, I recommend using the least recently used (LRU) algorithm to modulate the output of your RNG. You store a list of all outcomes sorted by how recent they are. Then you choose one closer to the front of the list. For example, if you have two outcomes, with 3/8 probability for outcome A and 5/8 probability for outcome B, you toss three A's and five B's into a list. Then you randomly choose one of the four elements at the head of the list, move it to the back, and move all elements after it forward one space.

Tetris the Grand Master uses "history with rerolls" (similar to LRU) to determine which piece to deal next. Thwaite uses LRU to select targets for enemy missiles, and RHDE uses LRU to for the same thing as TGM.

Ninja'd:

Dougeff describes a different randomizer, which EA Games and the Tetris fan community have referred to as the "bag" method. Fill the list with the three A and five B. Then each time, select a random element from that list and remove it. Once the set is empty, refill it with the original set. Most Tetris games since about 2001 use a bag of all seven pieces to address past concerns of an "I drought" (not receiving the straight "I" shaped piece for an extended period) wrecking one's game. Occasionally, as Bregalad alludes, you get two of a piece in a row when one bag ends with a particular piece and the next starts with the same piece. This has caused some TGM fans to refer to bag as the "SZSZ" randomizer, based on a perceived tendency to allow clumps of the S and Z pieces near the boundary between two bags. LRU allows the occasional drought but is less likely to allow brief floods.

The practical problem with bag on a 6502 is that selection without replacement from a set of variable size needs either multiplication with a variable multiplier or modulo with a variable divisor. With LRU, you can tune the length of the head to always be a power of two, allowing (fast) shifts and ANDs to select an outcome.

If you're fine with results repeating themselves after about 32000 or so steps, you can use Greg Cook's fast implementation of CRC16 to generate eight pseudorandom bits quickly. And srand(time(NULL)) won't work on any pre-Dreamcast console, as they lack a real-time clock. Instead seed it based on the time from power on to the player pressing Start.


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 5:54 am 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1516
thefox wrote:
I know linear congruential RNGs, often used on modern platforms for rand(), have widely documented problems with randomness if you use modulo (or bitwise AND) to limit their range.

Why should there be a problem with it as long as the range isn't limited in the randomizer's value itself, but only with the returned copy?
Or do you mean that, for example, values where the third bit from the right is a 1 appear less often than values where the third bit from the right is a 0, so that it shouldn't be used for getting values from 0 to 7 since it will mostly produce values from 0 to 3 since the highest bit is mostly 0?

I guess I really need to write a test program: Generating numbers from 0 to 15, then using the sprite tiles to check how many of them have been created within a certain loop.


na_th_an wrote:
Even if it's not perfect, I'm quite content with Shiru's implementation in neslib. Have you tried?

No. As I said, this is not about trying out a dozen randomizers that I happen to come by, nor do I want to implement some specific algorithm myself. I want to make sure whether the randomizer in CC65 has any specific issues, so that I need to use another one.

tepples wrote:
And srand(time(NULL)) won't work on any pre-Dreamcast console, as they lack a real-time clock.

Sure, I know that of course.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 6:07 am 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1516
dougeff wrote:
I think this is another example of 'humans don't understand the concept of randomization'

This is not about understanding or not understanding randomization. This is about the the fact that randomizers in programs don't create truly random numbers, but use a mathematical algorithm and I get a bit suspicious when there's a very large bias towards a certain outcome.

But as I said, I'll do some tests with the randomizer in CC65 and post the results here later.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 8:44 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5899
Location: Canada
DRW wrote:
koitsu wrote:
There should be several threads here on the forum of how people go about getting "random data" in their NES games.

If I'm not even sure whether one specific randomizer works correctly, in how far would it help me to have 10 more randomizers (unconfirmed ones, that is) that people posted in various forum threads?

You seem to be referring directly to this other thread where you asked a very similar question?

rand.s is a linear congruential generator, which is the same kind of PRNG that a lot of C standard libraries use.

If you want to test how good a random number generator is, just write a program to test it. You seem to be interested in whether results happen with even probability, and whether you're getting too many of a particular value in a row. Here's some statistics on a million iterations of rand.s:
Code:
rand() % 2 statistics:
         0 happened     499999 times, average run      1.984
         1 happened     500001 times, average run      1.985
rand() % 8 statistics:
         0 happened     125001 times, average run      1.143
         1 happened     124999 times, average run      1.143
         2 happened     125001 times, average run      1.143
         3 happened     124998 times, average run      1.143
         4 happened     124998 times, average run      1.143
         5 happened     125000 times, average run      1.143
         6 happened     125000 times, average run      1.143
         7 happened     125003 times, average run      1.143

So... looks perfectly fine; this is as good a result as I could hope from any PRNG, for these particular tests. You can try other random number generators if you're interested. Any good one should perform in a similar way, really. Most PRNGs will exhibit some kind of flaw if you throw the right test at it, but a lot of usage won't be affected by the flaw in a relevant way.

The test program is attached, so that you can verify my implemenation, but also so that you can modify and try it with other random number generators or other tests, if you like.

Edit: I realized later, that lower bits are independent of higher ones and the implementation unnecessarily discards 8 bits, so "rand() & 1" has an unfortunate sequence length of only 512 (9 bits), and "rand() % 8" only 2048 (11 bits), for example, so despite having normal frequency of bits, they are badly repetitive.


Attachments:
File comment: Python 3 program to test cc65's rand.s LCG
lcg_test.py [949 Bytes]
Downloaded 43 times


Last edited by rainwarrior on Tue Jul 12, 2016 12:23 am, edited 2 times in total.
Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 9:36 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19348
Location: NE Indiana, USA (NTSC)
Code:
def rand():
    global seed
    seed *= 0x01010101
    seed += 0x31415927
    seed &= 0xFFFFFFFF
    return (seed >> 8) & 0x7FFF

Clever. I hadn't thought to use 16843009 as the multiplier for an LCG. I can see how it was chosen for ease of computation; it may be one of the few LCGs practical on a 6502. But has anyone done spectral tests on it? A spectral test determines longer-term correlations among elements in the LCG's sequence.

But if it's shifting right by only 8 ((seed >> 8) & 0x7FFF), it's using bits 22-8 of seed, with bits 31-23 calculated but never affecting anything. I tested the following, and it produces the same sequence with only 3 bytes of state:
Code:
def rand():
    global seed
    seed *= 0x010101
    seed += 0x415927
    seed &= 0x7FFFFF
    return (seed >> 8)


The following (untested) should return the same sequence with slightly fewer cycles. It turns out to be even faster than Greg Cook's CRC16. Thank you for suggesting that I look at it.
Code:
;
; Random number generator
;
; Written and donated by Sidney Cadot - sidney[at]ch[dot]twi[dot]tudelft[dot]nl
; Optimized by Damian Yerrick - pino[at]pineight[dot]com
; May be distributed with the cc65 runtime using the same license.
;
; This implements a linear congruential generator with period 2^23.
; The multiplier in an LCG needs to be congruent to 1 (mod 4),
; and the addend needs to be odd.
; Bits 22-8 are returned because LCGs are known for patterns
; in low-order bits.
;

.export _lcg23_rand, _lcg23_srand

.data

; At main() entry, the program expects srand(1) to have been called.
; Initialize the seed as if so.
rand: .byte 1, 0, 0
rand_addend = 4282663

.code

;;
; int lcg23_rand(void);
;
; Clocks the LCG using the iteration
;     seed[n+1] = ((seed[n] * 65793) + 4282663) & ((1<<23) - 1)
; @return bits 22-8 of seed.
.proc _lcg23_rand
  ; Multiply by 0x10101: 22 cycles
  clc
  lda rand+0
  adc rand+1
  sta rand+1
  adc rand+2
  sta rand+2

  ; Add 0x415927: 34 cycles
  clc
  lda rand+0
  adc #<rand_addend
  sta rand+0
  lda rand+1
  adc #>rand_addend
  sta rand+1
  lda rand+2
  adc #^rand_addend
  and #$7F
  sta rand+2
 
  ; Get return value in XXAA: 6 cycles + 6 for RTS
  tax
  lda rand+1
  rts
.endproc

;;
; void lcg23_srand(unsigned int seed);
;
; Sets the state of the LCG to a particular value.
; Only 1/256 of states are reachable from this function.
.proc _lcg23_srand
  sta rand+0
  stx rand+1
  lda #0
  sta rand+2
  rts
.endproc


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 11:42 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5899
Location: Canada
tepples wrote:
But has anyone done spectral tests on it? A spectral test determines longer-term correlations among elements in the LCG's sequence.

Here's a quick X/Y plot of 9000 iterations of rand() % 256:
Attachment:
File comment: 9000 iterations of cc65's rand() plotted as X/Y pairs modulo 256.
cc65_256_9000.png
cc65_256_9000.png [ 11.33 KiB | Viewed 2222 times ]


Specifically a spectral test is graphing correlations between successive elements; i.e. can you predict the next output if you knew the last one? All LCGs exhibit planes in spectral tests depending on how you organize it; it's actually a good way to detect and study LCGs, and it's why they aren't cryptographically secure. A "better" LCG has more even distribution (i.e. more planes). cc65's rand() seems pretty good for an LCG, though this visible pattern is a good example why you don't usually want to use an LCG for generating X,Y pairs; it's one of the usage cases that exposes this flaw of the LCG paradigm.

For comparison here's what a "very good" spectral test looks like, from the LFSR PRNG example on the wiki, which DRW doesn't want to use because it was written by a "random" person like me:
Attachment:
File comment: LFSR with 8 bits of entropy
lfsr8_256_9000.png
lfsr8_256_9000.png [ 14.37 KiB | Viewed 2222 times ]


And a "very bad" test, made using the same generator but with the entropy turned down to 1 bit per iteration:
Attachment:
File comment: LFSR with 1 bit of entropy
lfsr1_256_9000.png
lfsr1_256_9000.png [ 2.39 KiB | Viewed 2222 times ]


All three PRNGs from these spectral tests pass the other tests (even distribution of values, even distribution of run lengths) from my previous post, though. Again, whether or not this particular flaw matters depends on how you're using it.


tepples wrote:
But if it's shifting right by only 8 ((seed >> 8) & 0x7FFF), it's using bits 22-8 of seed, with bits 31-23 calculated but never affecting anything.

That seems an oversight worth pointing out to the maintainers of CC65. (Are you on the CC65 mailing list?) I suspect, though, that the better solution would not be to reduce it to a 24-bit PRNG for efficiency, but rather to repair it as a full 32-bit PRNG.


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 12:19 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5899
Location: Canada
By the way, if you do a complete cycle with that modulo 256 graph on cc65's rand(), you get 50% coverage of the plane, which is actually very good for an LCG. A "bad" LCG would have them pile up in fewer planes.

Again, you could be using other PRNGs, but for the question of how good the output of CC65's is, I'd say so far it looks pretty good. Probably no worse than most C library implementations of rand().

Edit: eventually discovered the low bits have poor sequence length, keep reading.


Attachments:
File comment: 2<<24 iterations of cc65's rand()
cc65_256_24bit.png
cc65_256_24bit.png [ 2.31 KiB | Viewed 2208 times ]


Last edited by rainwarrior on Tue Jul 12, 2016 12:24 am, edited 1 time in total.
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 44 posts ]  Go to page 1, 2, 3  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: Bing [Bot] and 8 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