It is currently Wed Sep 18, 2019 5:00 am

 All times are UTC - 7 hours

 Page 2 of 2 [ 27 posts ] Go to page Previous  1, 2
 Print view Previous topic | Next topic
Author Message
 Posted: Sun Nov 25, 2018 5:54 pm

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

 Posted: Sun Nov 25, 2018 7:32 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7582
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

 Posted: Sun Nov 25, 2018 8:36 pm

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

 Posted: Mon Nov 26, 2018 1:53 am

Joined: Thu Sep 15, 2016 6:29 am
Posts: 903
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

 Posted: Mon Nov 26, 2018 7:01 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21591
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.

_________________
Pin Eight | Twitter | GitHub | Patreon

Top

 Posted: Mon Nov 26, 2018 10:11 am

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

 Posted: Mon Nov 26, 2018 1:22 pm

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

_________________
A few of my web games
https://www.embed.com
Or if you're bored at work
https://www.classicsolitaire.com
Top

 Posted: Tue Dec 04, 2018 2:01 pm

Joined: Thu Sep 15, 2005 9:23 am
Posts: 1236
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

 Posted: Tue Dec 04, 2018 2:41 pm

Joined: Sat Jan 09, 2016 9:21 pm
Posts: 625
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

 Posted: Tue Dec 04, 2018 3:05 pm

Joined: Thu Sep 15, 2005 9:23 am
Posts: 1236
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

 Posted: Tue Dec 04, 2018 3:15 pm

Joined: Sun Apr 13, 2008 11:12 am
Posts: 8559
Location: Seattle
Top

 Posted: Tue Dec 04, 2018 5:45 pm

Joined: Sat Jan 09, 2016 9:21 pm
Posts: 625
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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 2 of 2 [ 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 forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2019 NESdev Competition       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki