Romhacking.net
Romhacking => Programming => Topic started by: PolishedTurd on September 10, 2018, 10:23:07 am

I am trying to write a random number generator for the NES that will work on any ROM. The goal is to be able to pass the max value as a parameter via a register, and receive the random number in another register. For example, if I pass in 10 (decimal), I expect to get a value between 0 and 9.
My strategy is to sample a regularly changing number that is larger than the input arg (e.g., a timer that decrements every cycle and wraps at 0), and subtract the input successively until the value is less than the input (modular arithmetic). But I'm not aware of a ROMindependent way to get the regularly changing value. It's not the end of the world to hunt for a timer register in every ROM I work with, but I'm wondering if there is a better way. For example, I vaguely recall someone sampling the noise register for random values, but this doesn't seem reliable.

pRNGs typically work on a mathematical algorithm. The most basic might look something like this:
out = (in * A) + B
Where A and B are moderately sized prime numbers. 'out' is the generated random number (which can be later scaled down to a specific range), and 'out' is also used as 'in' for the next iteration.
(Note: this is extraordinarily simplistic  modern RNGs are much more complex.. there's an entire field of study dedicated to this shit. But I'm assuming you don't need a great one)
All you need from there is an initial value for 'in' (known as the "Seed"). An easy value for the seed is the system clock at time of program launch (if available)  or on machines where that's not possible (like NES/SNES/etc), the count of frames between power on and the first user input is sometimes used, since that's unlikely to be identical between games.
Either way, an RNG consisting of both a 'generate' function and a 'seed' function is pretty much the universal norm, and trying to make one without a separate seed function will pretty much guarantee your RNG will suck. My advice is to have these two functions in your RNG and leave it up to the game that uses it to figure out how to seed it properly.
EDIT 2:
So.. "hunt down the timer in each game" is what I'm recommending in this case. The NES doesn't really have any readable register that will produce something pseudorandom, so you're SOL as far as that's concerned.
/EDIT 2
As for scaling the number down, rather than looped subtraction (which can be painfully slow if the number is small), you might consider multiplying up by the scalar and then dropping the low byte(s):
out = rng_output * scalar / max_possible_rng_output_plus_one
Example: if your RNG is single byte and produces values 0255, 'max_possible' would be 256. And if you want a value between 09, 'scalar' would be 10. Dividing by 256 here is trivial (just drop the low byte), and this ensures output that is less than the scalar:
255 * 10 / 256 = 9
EDIT:
Also for systems like the NES where multiplication is a little expensive and the RNG period is going to be low anyway, the RNG computation could be replaced with a 256byte lookup table that contains the generated sequence.

See: RNG for NES (https://wiki.nesdev.com/w/index.php/Random_number_generator). Found quickly with google. LFSRs are a reasonable alternative to linear congruential generators (LCGs.) However, neither are particularly fast and none of that addresses your desire to specify the upper end of a range of values where you would want, I imagine, a uniform distribution, as well. But converting a linear distribution over one range (the range of the generator, which is typically a symbol space size based on a power of 2) to another range (your specified range) involves yet another multiplication of some kind to achieve. So, avoiding multiplication is probably going to fail. If you only had one range to work with, you could design an LCG to provide exactly that range and thus avoid making this into two steps, both involving multiplication, by combining them to make it into one such step. But since I imagine your range is variable, depending upon purpose, you probably cannot avoid the remapping efforts.
(Interesting juxtaposition between the title's mention of x86 and the content's discussion of the NES.)

If you could limit your random limiting to multiples of 15 or ranges that could be bitmasked you could do something like this at least as far as limiting the random range once you have the number.
Example limit random number to 015
LDA randomNum
AND maxvalue
random = 0xF5 AND with 0x0F = 0x05
Example limit random number to 0 to 3
LDA randomNum
AND maxvalue
random = 0x59 AND with 0x03 = 0x01

See: RNG for NES (https://wiki.nesdev.com/w/index.php/Random_number_generator). Found quickly with google.
(Interesting juxtaposition between the title's mention of x86 and the content's discussion of the NES.)
You're right; sorry about that. I searched for random number generation here and saw a post about Final Fantasy and RNG, but I assumed they were talking about the "range" attribute of a character. :[ And I meant 6502, not x86. Must've forgotten to take my smart pills again, although I think somebody switched them to jelly beans long ago.
LFSR is a clever concept, and treating bits as polynomial coefficients is yet another layer of ingenuity. The algorithm looks so elegant; I'll have to try it.
I've already scratched up my original algorithm, so I can run a comparison and see how my primitive implementation stacks up.
@Disch I was having a hard time coming up with something as straightforward as sampling a timer. For all your experience, I'm glad it gets your imprimatur as well.
I appreciate the advice about scaling too. I'll run some tests and report what I find.

I am circling back to this. I have found some elegant algorithms for RNG in 6502, but I am struggling with the part about scaling. Is it truly a uniform distribution to simply AND the RNG output with the upper limit operand, as bruddogtecmo says? It seems reasonable and very efficient, but I would like to test it.
Disch's scaling algorithm makes perfect sense algebraically, but doesn't dropping the low byte mean if the product of the upper limit operand and RNG output is less than 256, it will always scale as 0? It doesn't seem right.
But in either case, I could use a suitable test environment to run these algorithms by the thousands and plot the output. Can someone recommend a good free utility?

I am circling back to this. I have found some elegant algorithms for RNG in 6502, but I am struggling with the part about scaling. Is it truly a uniform distribution to simply AND the RNG output with the upper limit operand, as bruddogtecmo says? It seems reasonable and very efficient, but I would like to test it.
If the RNG output is uniform 0255, then yes  ASSUMING you are ANDing all low bits with no gaps.
IE: This only works with powerof2 ranges (AND with powerof2 minus one)
AND #$3F ; < Good  $40 is a power of 2, $3F is powerof2 minus one
AND #$3E ; < BAD  will not work, $3F is not a powerof2
Basically you're just dropping the high bits.
Disch's scaling algorithm makes perfect sense algebraically, but doesn't dropping the low byte mean if the product of the upper limit operand and RNG output is less than 256, it will always scale as 0? It doesn't seem right.
Yes, output less than 256 would be zero. That is desired behavior.
You can plug in some numbers to see how it'd work. Say you want a number between 02
(all numbers in hex)
RNG output  multiply by 3  drop low byte  odds of result

00 to 55  0000 to 00FF  00  56 / 100
56 to AA  0102 to 01FE  01  55 / 100
AB to FF  0201 to 02FD  02  55 / 100
As you can see, you have SLIGHTLY higher odds of hitting the low numbers, but it's as uniform as possible. That bias towards lower numbers increases as your range gets higher. This is easy to see with something like a range of 0254, where odds of getting zero becomes twice as likely as getting any other number.
Only way I can think of to get TRULY uniform numbers (in a nonpowerof2 range) would be to conditionally reroll the RNG on certain results. IE: if you want 0254, then you'd reroll if the RNG produced 255. But that's tough to generalize in 6502 and would be time consuming.
EDIT:
Nevermind, rerolling wouldn't even work. Since the pRNG is just a repeating sequence, this would just widen the window of the next value in the sequence. IE, rerolling on 255 would just improve the odds of getting whatever number follows 255 in the sequence, since there are now 2 ways to produce it.
Rerolling only works if the RNG is truly random  like with actual dice or something.
So yeah.. I have no idea how you'd get perfectly uniform distribution here. So multiplyanddroplowbyte approach is going to be as good as anything.
/EDIT
EDIT 2:
Or maybe I'm wrong and rerolling would work? I don't know, I'm not confident in either answer. =x
/EDIT 2
But in either case, I could use a suitable test environment to run these algorithms by the thousands and plot the output. Can someone recommend a good free utility?
You could whip something up in python, I suppose. There are even online python interpreters, so you don't even need to install it.
Here's the first one I found: https://repl.it/languages/python3
Dunno if you can use a plotting library with that, though, but you could print the results out as text easily enough. If you have Python installed then you can probably get the matplotlib library.

EDIT:
Nevermind, rerolling wouldn't even work. Since the pRNG is just a repeating sequence, this would just widen the window of the next value in the sequence. IE, rerolling on 255 would just improve the odds of getting whatever number follows 255 in the sequence, since there are now 2 ways to produce it.
Rerolling only works if the RNG is truly random  like with actual dice or something.
So yeah.. I have no idea how you'd get perfectly uniform distribution here. So multiplyanddroplowbyte approach is going to be as good as anything.
/EDIT
EDIT 2:
Or maybe I'm wrong and rerolling would work? I don't know, I'm not confident in either answer. =x
/EDIT 2
The nonuniformity due to rerolling diminishes rapidly with cycle length.

If you need to do division / modulo (or even just multiplication), here is an article I have written that may be of help. https://bisqwit.iki.fi/story/howto/bitmath/

I'm not particulary knowledgeable in random number generation, but my first instinct for the problem of non power of 2 ranges would be this: assuming you start with an acceptable 00FF random value, repeatedly subtract the length of your desired range (e.g., for 09, use 10, decimal) until you reach a number under that value. You will end up with 09 all the time, but I can't say if the final result will be reasonably uniform with a larg enough sample. However, with lower ranges, it may become quite costly in terms of CPU cycles. And even more so if you're using multiple bytes.

This will obviously lead to nonuniform results : In that specific case (using a 8bit random value as a source of a random number in the range 09), you will get 05 more often than 69; Because you'd get 05 if the RNG triggered 250255; so there's a 1/25 supplementary chance of them happening.
The only simple way to have uniform result is to do a RNG for the upper power of 2 (in this case, 16 with 4bit RNG); and retrigger the RNG if the result is outide of the range (in this case 1015).

I ended up finding some truly elegant algorithms online that seemed to satisfy (practically if not academically) the problem of uniform distribution for any input operand up to, say, 32. If I recall, it involved integer division and some clever rounding to get "close enough."
Unfortunately, real life caught up with me pretty hard and I had to table the project. Pretty sure I kept my notes though, and I'd love to get back to it.
I'll look for them at the next opportunity and post what I found.

Here's something that I found that doesn't need division. It's pretty much what Bregalad was suggesting.
random_in_range:
sta scratch
clc
sbc #1
ora #1
ldx #$FF
;determine which mask to use by counting leading zeroes
@count: inx
rol a
bcc @count
;loop until random <= range1
@try: jsr random
and mask_bytes, x
cmp scratch
bcs @try
rts
mask_bytes: .db $FF, $7F, $3F, $1F, $0F, $07, $03, $01
EDIT: As other people have said, if the period's too short this can cause problems, but there are algorithms you can use that fit pretty nicely on the 6502 and have periods on the order of 2^{32}, which is probably long enough that it's fine.