It is currently Wed Dec 12, 2018 3:35 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 27 posts ]  Go to page Previous  1, 2
Author Message
PostPosted: Sun Nov 25, 2018 5:54 pm 
Offline
User avatar

Joined: Wed Sep 05, 2018 11:13 am
Posts: 152
Location: Colorado
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


Top
 Profile  
 
PostPosted: Sun Nov 25, 2018 7:32 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7011
Location: Canada
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.


Top
 Profile  
 
PostPosted: Sun Nov 25, 2018 8:36 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7011
Location: Canada
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:
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.


Top
 Profile  
 
PostPosted: Mon Nov 26, 2018 1:53 am 
Offline
User avatar

Joined: Thu Sep 15, 2016 6:29 am
Posts: 827
Location: Denmark (PAL)
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)


Top
 Profile  
 
PostPosted: Mon Nov 26, 2018 7:01 am 
Offline

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


Top
 Profile  
 
PostPosted: Mon Nov 26, 2018 10:11 am 
Offline
User avatar

Joined: Wed Sep 05, 2018 11:13 am
Posts: 152
Location: Colorado
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


Top
 Profile  
 
PostPosted: Mon Nov 26, 2018 1:22 pm 
Offline
User avatar

Joined: Wed Sep 05, 2018 11:13 am
Posts: 152
Location: Colorado
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:
File comment: Quick and Dirty PRNG
random.nes [40.02 KiB]
Downloaded 12 times

_________________
A few of my web games
https://www.embed.com
Or if you're bored at work
https://www.classicsolitaire.com
Top
 Profile  
 
PostPosted: Tue Dec 04, 2018 2:01 pm 
Offline

Joined: Thu Sep 15, 2005 9:23 am
Posts: 1211
Location: Berlin, Germany
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.


Top
 Profile  
 
PostPosted: Tue Dec 04, 2018 2:41 pm 
Offline
User avatar

Joined: Sat Jan 09, 2016 9:21 pm
Posts: 518
Location: Central Illinois, USA
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.

_________________
My games: http://www.bitethechili.com


Top
 Profile  
 
PostPosted: Tue Dec 04, 2018 3:05 pm 
Offline

Joined: Thu Sep 15, 2005 9:23 am
Posts: 1211
Location: Berlin, Germany
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?


Top
 Profile  
 
PostPosted: Tue Dec 04, 2018 3:15 pm 
Offline

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7817
Location: Seattle
viewtopic.php?p=109825#p109825


Top
 Profile  
 
PostPosted: Tue Dec 04, 2018 5:45 pm 
Offline
User avatar

Joined: Sat Jan 09, 2016 9:21 pm
Posts: 518
Location: Central Illinois, USA
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.

_________________
My games: http://www.bitethechili.com


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

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 2 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