No-computation "RNG" by baking random numbers into the ROM

[mcmillen]

Newbie to SNES assembly, so pardon me if this is already well-known but: I wanted some random bytes for my game, but didn't really want to waste valuable CPU time with computing random bytes at runtime using an actual PRNG algorithm. I'm sharing my trick here in case it's helpful for others.

The gist is that I fill a ROM bank with random bytes using the assembler, and then call a GetRandomByte macro that fills A with the next random byte, and updates a pointer for the next time GetRandomByte is called. The code snippet is here:

Code: Select all

.define randomBytePtr $1A  ; Pick any free 2-byte address in your game's RAM.

; Stores result to A.
; Assumes 16-bit X & 8-bit A.
; Modifies X.
; Updates randomBytePtr.
.MACRO GetRandomByte
    ldx randomBytePtr
    lda $028000, X  ; $028000: beginning of ROM bank 2.
    inx
    cpx #$8000  ; This is the size of the entire ROM bank.
    bne +
    ldx #0
+
    stx randomBytePtr
.ENDM

; Fill an entire bank with random numbers.
.SEED 1
.BANK 2 SLOT 0
.ORG 0
.SECTION "RandomBytes"
.DBRND 32 * 1024, 0, 255
.ENDS

This "wastes" an entire bank by filling it with random numbers, but I wasn't using that bank anyways (and if you wanted, you could easily change the code so that it only used 1024 bytes, or whatever.) You could also change it to be a subroutine instead of a macro, if you care more than I do about code size.

[tepples]

I wanted some random bytes for my game, but didn't really want to waste valuable CPU time with computing random bytes at runtime using an actual PRNG algorithm.

How many random bytes do you need in a frame? Greg Cook's CRC16 is a 16-bit linear feedback shift register that takes about 70 cycles to produce 8 pseudorandom bits.

[mcmillen]

Thanks! I'll save that for the future

I definitely don't need many bytes per frame, but my main concerns here were: 1) easy to understand and 2) given that I don't know how much CPU I'll need, no need to be wasteful about it now, whereas I can't currently imagine running out of memory

[tepples]

I guess on the NES it's different, as there's a culture of making all your code fit into 32K.

[Khaz]

The problem I see with your approach is that it could lead to things seeming very deterministic and not-random. Since you will always pull out the same numbers in the same order, the only way you'll get any variation in your game is by changing the order in which things request random numbers, which I can think of many situations where that wouldn't happen leaving you with a scripted fight that goes the exact same way every time.

The only game whose RNG calculation I can speak to is Dragon View, and it does it like this:

Code: Select all

8187be jsl $80e3bc	;Subroutine assumes already in 8-bit A mode
80e3bc phb
80e3bd lda #$80
80e3bf pha
80e3c0 plb		;Switch to bank $80
80e3c1 lda $2137	;Latch screen draw pixel position
80e3c4 lda $213c
80e3c7 pha
80e3c8 lda $213c	;double read as it has a first/second-read flip-flop system (in $213F)
80e3cb pla		;second read is discarded
80e3cc adc $a5
80e3ce sta $a5	;$A5 is the RNG variable.  So add in the lo byte of horizontal scanline location
80e3d0 lda $213d
80e3d3 pha
80e3d4 lda $213d	;same double-read business as $213C
80e3d7 bit #$01	;test highest bit ($213C and $213D are allegedly 9 bits long)
80e3d9 bne _dontAddVerticalByte
80e3db pla
80e3dc adc $a5
80e3de sta $a5	;add in the lo byte of vertical scanline position IFF hi byte bit0 is not set.
80e3e0 bra _doneRNGCalc

_dontAddVerticalByte:
80e3e2 pla

_doneRNGCalc:
80e3e3 lda $a5
80e3e5 plb
80e3e6 rtl

Doesn't seem like the fastest code I've ever seen but it'll definitely make things nice and random provided your RNG routine isn't being called first thing in a frame or at a totally deterministic time. Generally speaking, if your joypad routine comes before your RNG calls just what the player is pressing at that moment should ensure enough randomness in the screen position by the RNG call. And since every time it adds into the previous number, it becomes basically impossible to get stuck in a situation where you keep seeing the same reactions.

Your proposal just kinda strikes me as a glorified version of this, and while I can see the motivation for and the advantages of that method, I just don't feel like it'd be "random" enough...

[Sik]

I guess on the NES it's different, as there's a culture of making all your code fit into 32K.

Probably because of mappers in case you want to get it on a real cartridge.

And yeah, if you just need something that looks random (without really having to be random, e.g. stuff for some quick effects), a look-up table is probably easier to implement than an actual PRNG. So you lose memory in favor of making it easier and faster to do.

[tepples]

In one demo I made for Game Boy Advance, I stored a permutation of the numbers 0 to 255 in ROM, derived from the S-box of the AES cipher. I used it to compute horizontal offsets for one of the raster effects, where the display would fuzz out (like a bad analog TV connection) and then come back into focus. Because it was called for every scanline 30 times a second on a 16.8 MHz ARM that was already running other distortion effects and animation logic, it had to be wicked fast. So I used the "ordinary" RNG once per frame to find an 8-bit starting offset into this table and then stepped through one line of the table per GBA scanline.

[rainwarrior]

If space isn't an issue, your table-based PRNG is at least as good as the PRNG used to generate the table, and close to optimally fast, I suppose. There's nothing at all wrong with it as a technique, as long as the space comes "free".

If it's not, a single tick of an LFSR PRNG would take a similar amount of cycles and lines of code as your lookup, and requires no lookup table. To get good entropy, you should really tick an LFSR once per bit needed before using the result, but even a single tick provides a lower-entropy random number that in a lot of cases may be very usable. (Lets you trade speed for entropy on a case-by-case basis.)

[tepples]

To get good entropy, you should really tick an LFSR once per bit needed before using the result

Agreed. That's why I use Greg Cook's code, which is equivalent to eight ticks per call. Before I found that, I had used an LFSR where I passed the number of ticks in Y.

[mcmillen]

The problem I see with your approach is that it could lead to things seeming very deterministic and not-random. Since you will always pull out the same numbers in the same order, the only way you'll get any variation in your game is by changing the order in which things request random numbers

This depends on the application -- for something that "eats" a different number of random bytes per-frame depending on player action, it'll only appear deterministic as long as the player keeps doing the same input on the same frames. For something less twitch-based (like an RPG or interactive fiction, where every instance of "randomness eaten" is easy to control), that'd be more of a concern. Fact of the matter is, all PRNGs have to be seeded somehow, and either they have a static seed (like this does), and produce the same bytes in the same order, or set the initial seed (or periodically update the internal state) based on some unpredictable signal such as a timer, which you could also do here.

For example, you could also set the initial "next random byte" pointer based on the numVBlanks count at the time the player clicks 'start game'"... which might also be deterministic if they get really good at pressing Start on the first possible frame, and reset the system after every play.. but if they're that obsessed about exploiting my RNG, I think I should just be happy that they're playing my game so passionately

[rainwarrior]

Well, all PRNG create a repeating series. That's why they're called PRNG and not RNG.

You can reduce determinism, though, by allowing the game to tick the PRNG in response to user input that is expected to be unpredictable. Typically this is triggered by events that are difficult for a human to time. For example, when a user presses A to make a choice in a menu, you could tick the PRNG every frame while the button is held. Will they hold it for 4 frames, or 10, or 80?

A TAS can always exploit this, but exploiting PRNGs is a big part of TAS.

Final Fantasy IV on the GBA tried to seed its PRNG based on how long you waited on the title screen after reset. Unfortunately, they seeded it with the number of seconds, rather than the number of frames, allowing me to easily exploit it without any special tools.

[Sik]

On the Mega Drive you can avert it in two ways: the initial values in RAM are undefined because it's DRAM (they're defined on soft reset but unpredictable enough to still be useful), and the initial value of the HV counter (the beam can start at any point, and on soft reset the reset could have happened at any point as well). Both are useful for determining an initial seed, and the latter can also be used to turn the PRNG into an actual RNG (since you really can't tell for sure what the HV counter will be even for code that runs about the same amount of cycles).

Does the SNES have similar stuff?

[Near]

The SNES' H/V counter at reset is deterministic.

The only really random output I know of is caused by a counter glitch in the SNES SMP timers, which was fixed for the SNES Jr.

Best bet is probably to upload a 64KB SMP program and then clock the H/V counters. Different oscillators fluctuate based on age, temperature, cosmic rays (probably not, but...), etc. So this is a good source of generating a randomized seed.

Another easy trick is to store the LFSR in SRAM, if it's available.

[Myask]

Well, all PRNG create a repeating series. That's why they're called PRNG and not RNG.

You can reduce determinism, though, by allowing the game to tick the PRNG in response to user input that is expected to be unpredictable. Typically this is triggered by events that are difficult for a human to time. For example, when a user presses A to make a choice in a menu, you could tick the PRNG every frame while the button is held. Will they hold it for 4 frames, or 10, or 80?

A TAS can always exploit this, but exploiting PRNGs is a big part of TAS.

Final Fantasy IV on the GBA tried to seed its PRNG based on how long you waited on the title screen after reset. Unfortunately, they seeded it with the number of seconds, rather than the number of frames, allowing me to easily exploit it without any special tools.

For a more in-depth treatment of PRNG-defeats, see here, with more articles linked at the end.

On the subject of human manipulation, title-screen variance can be easy if the programmers allow buffering or simply holding the button to count. Waiting for an edge (or pair of edges) in buttons-pressed makes it harder to time an action correctly than just waiting for a valid is-pressed.

[rainwarrior]

My suggestion was not just for the title screen or startup. You can collect entropy from user input nearly any time they have to interact with the game. It's not just important to start with a random seed, but to break the predictability of the sequence once begun.

Techniques like reading RAM on startup are often only good for an initial seeding, and useless on emulators, but user input is an endless fountain.