Is there a clever way to do small random numbers?

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

User avatar
battagline
Posts: 152
Joined: Wed Sep 05, 2018 11:13 am
Location: Colorado
Contact:

Re: Is there a clever way to do small random numbers?

Post by battagline »

rainwarrior wrote:Input from the player isn't "random", it's a deliberate response to what is happening in the game. If it responds the same way to the same input it's not very random.
It's more a question of the player's precision. The frame increments every 16.6 milliseconds, and humans just aren't able to time their keypress to that level of precision. All humans would fall into a Gaussian distribution around certain points within the game they are responding to, but each slight difference in timing from the press of the key will contribute to random jumps in the sequence. The more user input in your game the more random those jumps will be.

I gotta read through the other posts so please don't judge me if there was a follow up to this I haven't commented on yet.
A few of my web games
https://www.embed.com
Or if you're bored at work
https://www.classicsolitaire.com
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Is there a clever way to do small random numbers?

Post by rainwarrior »

battagline wrote:It's more a question of the player's precision. The frame increments every 16.6 milliseconds, and humans just aren't able to time their keypress to that level of precision. All humans would fall into a Gaussian distribution around certain points within the game they are responding to, but each slight difference in timing from the press of the key will contribute to random jumps in the sequence. The more user input in your game the more random those jumps will be.
What I'm saying is that any "rare" event is basically a reset of the sequence to a known point. You see something happen and you know what will follow.

Maybe the player sees a 4 of clubs, and then notices the next card is always one of two things. Or even worse, the player will notice that they can control which card comes up depending on whether they hold a button while the cards filp. The question isn't whether there has been enough input prior now, the question is how much that input has changed between the last noticeable point in the sequence, and the next thing that happens. Depends on the game, but probably not a lot of input happens between events, possibly none.

Use a longer sequence than and this isn't a problem... for generic applications at least. Really how "random" you need your numbers to be depends on your game of course. There's plenty that will "work fine" if used in a situation where the PRNG's flaws are orthogonal to the outcome.
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Is there a clever way to do small random numbers?

Post by rainwarrior »

battagline wrote:Whenever there is any input from the gamepad I add the frame counter to the random pointer and AND it with #%01111111
It might be worth taking a close look at this sequence of indices and how it works.

No matter what index you start on, this sequence will have 128 values, and then the same sequence will repeat in reverse order before starting over. If you were looking at the output of this, you would be able to spot each reversal whenever a value is repeated twice in a row.

Here's the 3 bit equivalent for any given starting seed:

Code: Select all

00 >  0 1 3 6 2 7 5 4 4 5 7 2 6 3 1 0...
01 >  1 2 4 7 3 0 6 5 5 6 0 3 7 4 2 1...
02 >  2 3 5 0 4 1 7 6 6 7 1 4 0 5 3 2...
03 >  3 4 6 1 5 2 0 7 7 0 2 5 1 6 4 3...
04 >  4 5 7 2 6 3 1 0 0 1 3 6 2 7 5 4...
05 >  5 6 0 3 7 4 2 1 1 2 4 7 3 0 6 5...
06 >  6 7 1 4 0 5 3 2 2 3 5 0 4 1 7 6...
07 >  7 0 2 5 1 6 4 3 3 4 6 1 5 2 0 7...
Like I said, this pattern may not matter depending on the application, but generally the goal when designing a PRNG is to eliminate discernible patterns of output. All patterns like this have the potential to manifest as unwanted repetitive / exploitable behaviour when applied to a process like an interactive game.

There have been a lot of poor quality PRNGs in general use, and of course especially in games, and random scraps of code shared on the internet you'll find plenty. :P A very popular but heavily flawed version of rand() made it into very many C compiler libraries, for example, so even pro solutions may have drawbacks. It's really common to see people write fast PRNG routines and end up with flawed distribution that seems fine for whatever the limited application they put it to, but might cause problems if you drop it into a different game.

For more generic purposes, Long period LFSRs are good, statistically, as long as you tick the LFSR for each bit you need (not just each byte). After some review and tuning up, cc65's rand seems quite good as well. "Cryptographically secure" PRNGs are of course very good, but overkill for games.
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: Is there a clever way to do small random numbers?

Post by Sumez »

rainwarrior wrote:even if the player doesn't know how it works, they will see the same arbitrary sequence of stuff happening over and over, and this is not good. The problem is nearly as bad even if it's 1/32 and there's only 2 possible outcones, or 4, or 8... these just aren't very random and it will be very noticeable.
I'd say it's important to at least be aware of this, but it's not necessarily a weakness. One thing I think adds to the charm of most older games is how often there's a noticeable pattern or predictability to random stuff. That kind of stuff can be really central to the experience of playing a game, and Ghosts 'n Goblins (the arcade version) has always been a great example of that IMO.

In some cases you want complete unpredictability, but more often you want unpredictability with a decent amount of spread (such as massaging your PRNG output to prevent repeats). In other cases you just want the game's behavior to vary depending on certain factors.
It makes sense that a boss enemy behaves with certain patterns with mild unpredictability. But if you're making Tetris you don't want bias towards certain pieces, etc.

Btw, if you're basing a part of your game's randomness on a counter that counts every frame, I'd consider making it count multiple times during each frame instead. For example at the end of your "main loop" while you are waiting for a signal from NMI, if you alter your counter for as long as you have free CPU time, that can add a lot of unpredictability (providing your game isn't prone to slowdown)
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Is there a clever way to do small random numbers?

Post by tepples »

battagline wrote:It's more a question of the player's precision. The frame increments every 16.6 milliseconds, and humans just aren't able to time their keypress to that level of precision. All humans would fall into a Gaussian distribution around certain points within the game they are responding to, but each slight difference in timing from the press of the key will contribute to random jumps in the sequence. The more user input in your game the more random those jumps will be.
And if the player is pressing the Start button on a particular beat of the music at the title screen, the player can probably make that press happen within a 66-millisecond window for one of four outcomes. You have two usable bits of entropy at that point.

People have in fact exploited RNGs in the wild. See the story of Michael Larson on the game show Press Your Luck.
User avatar
battagline
Posts: 152
Joined: Wed Sep 05, 2018 11:13 am
Location: Colorado
Contact:

Re: Is there a clever way to do small random numbers?

Post by battagline »

tepples wrote: And if the player is pressing the Start button on a particular beat of the music at the title screen, the player can probably make that press happen within a 66-millisecond window for one of four outcomes. You have two usable bits of entropy at that point.
I think for most games if the player learns to time to 66ms based on some queue they have 4 possible starting states. As they continue through the game, additional inputs result in additional random jumps in the sequence. I think the solution would work fine for games requiring a moderate to large amount of input from different buttons/directional presses. It would not work well for a SMB2 style slot machine... but whatever they used for randomness didn't seem all that random either.
A few of my web games
https://www.embed.com
Or if you're bored at work
https://www.classicsolitaire.com
User avatar
battagline
Posts: 152
Joined: Wed Sep 05, 2018 11:13 am
Location: Colorado
Contact:

Re: Is there a clever way to do small random numbers?

Post by battagline »

So I put a little demonstration of my random number generator on github. As I said, it's worked well for me, but it might not work for all cases:
https://github.com/battlelinegames/nes-random

I've also attached a .nes file demonstration. Press any button and it will generate new random numbers. I'm doing too much in the NMI so there's some junk getting generated when you press a button, but that doesn't have anything to do with me generating the numbers. It's just because of the way I'm changing the background.

generates numbers 0-15
Attachments
random.nes
Quick and Dirty PRNG
(40.02 KiB) Downloaded 151 times
A few of my web games
https://www.embed.com
Or if you're bored at work
https://www.classicsolitaire.com
WedNESday
Posts: 1284
Joined: Thu Sep 15, 2005 9:23 am
Location: Berlin, Germany
Contact:

Re: Is there a clever way to do small random numbers?

Post by WedNESday »

The only way for a NES to 'generate' a random number is to use player input as a source.

1. I can remember playing a game about 25 years ago (can't remember which one) which used player input as a way of generating a different way of starting the first level. I noticed even back then what the game was doing and managed to get a favourable outcome by spamming one of the buttons as much as a could as the intro started.

2. A NES could use the number of times a player pushed the A button on the controller at the end of a level as a random number for the next level. I would imagine that by the time I have finished a level in Contra, it would have been pushed 100's of times. The problem is, this would only give the NES 1 8-bit number to play around with. It is not ideal if you require 100's of randomly generated numbers.
User avatar
gauauu
Posts: 779
Joined: Sat Jan 09, 2016 9:21 pm
Location: Central Illinois, USA
Contact:

Re: Is there a clever way to do small random numbers?

Post by gauauu »

WedNESday wrote:The only way for a NES to 'generate' a random number is to use player input as a source.
There's been some experiments with using the state of OAM at startup to seed a random number. In my tests on my 2 original consoles, it turned out to work reasonably well, although I wouldn't necessarily depend on it.
WedNESday
Posts: 1284
Joined: Thu Sep 15, 2005 9:23 am
Location: Berlin, Germany
Contact:

Re: Is there a clever way to do small random numbers?

Post by WedNESday »

gauauu wrote:There's been some experiments with using the state of OAM at startup to seed a random number. In my tests on my 2 original consoles, it turned out to work reasonably well, although I wouldn't necessarily depend on it.
Could you please post some results? When you say startup, do you mean reset or power-on?
User avatar
gauauu
Posts: 779
Joined: Sat Jan 09, 2016 9:21 pm
Location: Central Illinois, USA
Contact:

Re: Is there a clever way to do small random numbers?

Post by gauauu »

WedNESday wrote:
Could you please post some results? When you say startup, do you mean reset or power-on?
Power-on. See the link lidnariq posted. I used it for randomizing my title screen sequence on a game. It worked nicely for randomly picking an intro.
Post Reply