It is currently Sat Dec 15, 2018 11:13 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 27 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Fri Nov 16, 2018 10:31 am 
Offline
User avatar

Joined: Sun Apr 08, 2018 11:45 pm
Posts: 29
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
 Profile  
 
PostPosted: Fri Nov 16, 2018 10:40 am 
Offline
User avatar

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
 Profile  
 
PostPosted: Fri Nov 16, 2018 11:18 am 
Offline

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


Top
 Profile  
 
PostPosted: Fri Nov 16, 2018 1:17 pm 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 2354
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
 Profile  
 
PostPosted: Fri Nov 16, 2018 3:56 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7019
Location: Canada
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
 Profile  
 
PostPosted: Fri Nov 16, 2018 6:30 pm 
Offline
User avatar

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


Top
 Profile  
 
PostPosted: Sat Nov 17, 2018 11:53 am 
Offline

Joined: Tue Oct 16, 2018 5:46 am
Posts: 34
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
         adc rng_seed_1
         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
 Profile  
 
PostPosted: Tue Nov 20, 2018 5:19 pm 
Offline
User avatar

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

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


Top
 Profile  
 
PostPosted: Wed Nov 21, 2018 11:36 am 
Offline
User avatar

Joined: Sun Apr 08, 2018 11:45 pm
Posts: 29
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
 Profile  
 
PostPosted: Sun Nov 25, 2018 12:20 pm 
Offline
User avatar

Joined: Wed Sep 05, 2018 11:13 am
Posts: 152
Location: Colorado
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
 Profile  
 
PostPosted: Sun Nov 25, 2018 4:14 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7019
Location: Canada
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
 Profile  
 
PostPosted: Sun Nov 25, 2018 5:12 pm 
Offline
User avatar

Joined: Wed Sep 05, 2018 11:13 am
Posts: 152
Location: Colorado
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
 Profile  
 
PostPosted: Sun Nov 25, 2018 5:19 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7019
Location: Canada
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
 Profile  
 
PostPosted: Sun Nov 25, 2018 5:21 pm 
Offline

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


Top
 Profile  
 
PostPosted: Sun Nov 25, 2018 5:32 pm 
Offline
Site Admin
User avatar

Joined: Mon Sep 20, 2004 6:04 am
Posts: 3601
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
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 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 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