It is currently Sun Sep 15, 2019 1:00 am

 All times are UTC - 7 hours

 Page 1 of 2 [ 27 posts ] Go to page 1, 2  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Is there a clever way to do small random numbers?Posted: Fri Nov 16, 2018 10:31 am

Joined: Sun Apr 08, 2018 11:45 pm
Posts: 46
Location: Southern California
I've got a working version of the random number generator from the wiki, and I'm trying to think of a good way to generate numbers that in the 0-5 or 0-10 range. I know a good general purpose way of generating numbers in a range is to keep generating values until you get a number under the ceiling, but that might be a lot of work to get a number under 5. It would be easy for me to do a table look up, which would be a fine solution for our current small game, but I wouldn't want to do that a lot for a large game.

One other idea I had was something like:

Code:
var n = random number from 0..255
var a = 0
var b = 0
while a < n
increment a
increment b
if b > ceiling
b = 0

but that's also pretty slow, I feel like I'm missing something obvious. Is there a more clever way to do this?

Top

 Posted: Fri Nov 16, 2018 10:40 am

Joined: Mon Jan 03, 2005 10:36 am
Posts: 3141
Location: Tampere, Finland
One simple way is to mask it down into a power of two, then use rejection sampling.

So if you want 0..5, generate the number 0..255, mask it down to 0..7 (use bitwise AND), then reroll if the result is 6 or 7.

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

Top

 Posted: Fri Nov 16, 2018 11:18 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21589
Location: NE Indiana, USA (NTSC)
Or generate an 8-bit random number, multiply by 6, and keep the high byte. This incurs a small, probably imperceptible, percentage of uneven distribution.

_________________
Pin Eight | Twitter | GitHub | Patreon

Top

 Posted: Fri Nov 16, 2018 1:17 pm

Joined: Fri May 08, 2015 7:17 pm
Posts: 2558
Location: DIGDUG
I like tepples idea. Multiply by 6 can be optimized fairly well in ASM with bit shifting.

clear high byte, save low byte temp, shift left, add temp, shift left again.

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

Top

 Posted: Fri Nov 16, 2018 3:56 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7581
I don't think a reroll is that bad a solution for many cases, and is usually very easy to implement. Each iteration the probability that it will keep looping gets exponentially smaller. In practice these don't tend to loop very many times.

Some alternatives:

Omegamatrix once wrote a bunch of division routines for various constant values, which may potentially be useful in a situation like this:
https://forums.nesdev.com/viewtopic.php?f=2&t=11336

Also, you can trade precision/distribution-bias for speed or table size...
Code:
; modulo by subtraction loop
jsr prng ; 8-bit result in A
and #(8-1) ; this could by 8, 16, 32, 64...
sec
:
tax
;sec ; unnecessary
sbc #RANGE
bcs :-
; result now in X

; modulo by table
jsr prng
and #(8-1)
tax
lda mod8by5, X
; result now in A

In the subtraction loop, you can control speed by decided how many times it could loop with the size of your AND. Each extra loop reduces the bias. (If space was tight, this routine might be made generic by using variables instead of immediates for the AND and SBC too.)

In the table lookup, the speed is constant, but similarly the size of the AND determines the size of the table and the sizes of the bias.

E.g. is a 1/8 probability bias for some values okay? 1/16? 1/32?

Top

 Posted: Fri Nov 16, 2018 6:30 pm

Joined: Sun Apr 08, 2018 11:45 pm
Posts: 46
Location: Southern California
Thanks for the suggestions! I knew there was something a bit more fit to purpose.

Top

 Posted: Sat Nov 17, 2018 11:53 am

Joined: Tue Oct 16, 2018 5:46 am
Posts: 98
Location: Gothenburg, Sweden
Maybe this video from Retro Game Mechanics could be of use?

https://youtu.be/q15yNrJHOak

If used to it's fullest by not changing the seed values outside of the routines, it apparently loops after 27776 calls.

I implemented it in my game with some opcodes changed for the 6502 and it seems to work:

Code:
;; variables needed

; rng_seed_1          .db 1
; rng_seed_2          .db 1
; rng_output_1        .db 1
; rng_output_2        .db 1

GetRand:   tya
pha
ldy #1
jsr TickRNG
dey
jsr TickRNG
pla
tay
lda rng_output_1
rts

TickRNG:   lda rng_seed_1
asl a
asl a
sec
sta rng_seed_1
asl rng_seed_2
lda #\$20
bit rng_seed_2
bcc @label1
beq @label3
bne @label2
@label1:   bne @label3
@label2:   inc rng_seed_2
@label3:   lda rng_seed_2
eor rng_seed_1
sta rng_output_1, y
rts

I set the first seed value at the start of a level with another variable that's incremented each frame, so it won't always start from 0. I don't fully understand how the routines work yet but they do.

Top

 Posted: Tue Nov 20, 2018 5:19 pm

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 4210
How bout a linear feedback shift register?

_________________
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!

Top

 Posted: Wed Nov 21, 2018 11:36 am

Joined: Sun Apr 08, 2018 11:45 pm
Posts: 46
Location: Southern California
Dwedit wrote:
How bout a linear feedback shift register?

I'm not familiar with it, but I'll google it. What should I look for to map to this problem?

Top

 Posted: Sun Nov 25, 2018 12:20 pm

Joined: Wed Sep 05, 2018 11:13 am
Posts: 152
So I had a solution that I haven't seen anyone else use. It seems to work for my purposes, not sure what anyone else would think about it, but basically

I pre-generated 128 random numbers from 0-127 with no repeats.

I set aside a block of 128 bytes to put those values in there.

I have a frame counter that increments every execution of the game loop.

Whenever there is any input from the gamepad I add the frame counter to the random pointer and AND it with #%01111111

Whenever there is any request for a random number I have a macro that gives you the value pointed to by the random pointer,
increments the random pointer and ANDs it with #%01111111

My reasoning for why this would work is that any input from the player will effectively have a random frame count into the game since there are 60fps and the player can't time his input. It does have some issues that there will be patterns if there are long periods where the player has no input. Also taking up 128 bytes for the random pattern is fairly large.

Anyway, I'd be interested in hearing other opinions on my solution and why it is better or worse than some of the other solutions I've seen.

Thanks

_________________
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 4:14 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7581
The disadvantage of what you just proposed is an extremely short period.

Consider this: anything in your game that happens with a 1/64 probability can only happen once in that PRNG sequence you just proposed. That means that any time that event happens, the player will know exactly what's going to happen next with everything else, not just that one event. This isn't just about exploitation; 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.

Tables of numbers are indeed used in PRNGs sometimes. I think zzo38 was a proponent of using ARCFOUR, which keeps a table of numbers in RAM... probably not something you want to budget that much RAM for but tables by themselves aren't a bad component of a solution here. Small tables can be combined with other operations to create longer periods. The main reason tables come up is for speed; a lookup is really fast, and can sometimes replace a whole series of computations in a single step (e.g. see the table in CRC32).

Top

 Posted: Sun Nov 25, 2018 5:12 pm

Joined: Wed Sep 05, 2018 11:13 am
Posts: 152
rainwarrior wrote:
The disadvantage of what you just proposed is an extremely short period.

Consider this: anything in your game that happens with a 1/64 probability can only happen once in that PRNG sequence you just proposed. That means that any time that event happens, the player will know exactly what's going to happen next with everything else, not just that one event.

My thought is this is only an issue during periods where there is no input from the player. Every time there is input from the player the pointer would shift around randomly through the sequence. My thought was this would work great for games where there was a lot of player input but poorly for games where there was little player input.

Thoughts?

_________________
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 5:19 pm

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

Player timing is somewhat "random" in long term aggregate and maybe a reasonable way to build up entropy gradually over time, but if your sequence is that short, no this will be very noticeable in a lot of cases.

Also, player input doesn't really change that often. Playing a game often involves sitting still, or holding in one direction for seconds at a time, etc.. Input changes are sparse. During any such case it is contributing zero entropy for you.

Top

 Posted: Sun Nov 25, 2018 5:21 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21589
Location: NE Indiana, USA (NTSC)
A circular buffer in RAM can also help keep the same outcome from happening too close together, improving perceived randomness (at the expense of true randomness) and allowing use of a power-of-2 RNG for a non-power-of-2 outcome count. I've used it in Thwaite (for targets), RHDE (for piece sequence in build phase), robotfindskitten (for NKIs), and a couple other games. In a way, it resembles a neutered ARCFOUR:

At start, initialize a circular buffer outcomes[] containing all outcomes, with more common outcomes stored more than once and outcomes that aren't desirable in the early game stored later. For example, RHDE fills each player's buffer with two of the smallest piece, and it puts the most complex (5-block) pieces later so that they're less likely to be generated while the player is still getting the hang of build phase. Then for each event:

1. Generate a random number r with a range smaller than the length L of the circular buffer. Consider making r a power of 2 close to L / 2.
2. Swap outcomes[x] with outcomes[(x + r) mod L].
3. Yield outcomes[x].
4. Add 1 to x (mod L).

_________________
Pin Eight | Twitter | GitHub | Patreon

Top

 Posted: Sun Nov 25, 2018 5:32 pm

Joined: Mon Sep 20, 2004 6:04 am
Posts: 3721
Location: Indianapolis
battagline wrote:
rainwarrior wrote:
The disadvantage of what you just proposed is an extremely short period.

Consider this: anything in your game that happens with a 1/64 probability can only happen once in that PRNG sequence you just proposed. That means that any time that event happens, the player will know exactly what's going to happen next with everything else, not just that one event.

My thought is this is only an issue during periods where there is no input from the player. Every time there is input from the player the pointer would shift around randomly through the sequence. My thought was this would work great for games where there was a lot of player input but poorly for games where there was little player input.

Thoughts?

Sounds about right. Though I would amend that to say if the game requires input from the player before something is randomly generated, that probably works OK. One button press and one random event. Like in Asteroids, you shoot the asteroid and it splits off in random directions. OTOH, if something is generated continually with a short period RNG, and the player sees the beginning of a favorable pattern, they could just exploit it by not pressing any buttons.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 2 [ 27 posts ] Go to page 1, 2  Next

 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