Which randomizer to use?

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems.

Moderator: Moderators

User avatar
DRW
Posts: 2044
Joined: Sat Sep 07, 2013 2:59 pm

Which randomizer to use?

Post by DRW » Tue Aug 25, 2015 5:50 pm

When I program an NES game and need a randomizer, which function is usually used for it?

I had a look into Visual C++ 6.0 and the functions there basically look like this:

Code: Select all

static long holdrand = 1L;

void srand(unsigned int seed)
{
    holdrand = (long)seed;
}

int rand(void)
{
    return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7FFF);
}
I assume this isn't really an ideal way for an NES game with the multiplication and the long values.

So, what does the typical NES randomizer look like?
My game "City Trouble": www.denny-r-walter.de/city.htm

tepples
Posts: 22281
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Which randomizer to use?

Post by tepples » Tue Aug 25, 2015 6:18 pm

The C code you quoted is a linear congruential generator, which depends on fast 32-bit multiplication.

On the 6502, a "typical" randomizer looks like Greg Cook's table-free implementation of CRC16. Initialize it with something nonzero, then just feed it a zero whenever you want a random number.

User avatar
freem
Posts: 163
Joined: Mon Oct 01, 2012 3:47 pm
Location: freemland (NTSC-U)
Contact:

Re: Which randomizer to use?

Post by freem » Tue Aug 25, 2015 6:57 pm

Examples of other random number generators can be found on codebase64 (personally, I use White Flame's 8 and 16-bit routines)

User avatar
rainwarrior
Posts: 8002
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Which randomizer to use?

Post by rainwarrior » Tue Aug 25, 2015 9:50 pm

I usually recommend a Galois Linear Feedback Shift Register for general purpose random numbers on the NES. I would usually suggest a 16-bit generator even if you're only reading 8-bit values from it (an 8-bit generator loops after only 255 samples, which may not be great if you're looking for unpredictability).

Most of the code samples in freem's link are forms of a Galois LFSR. There are other efficient ways to make random numbers on the NES, but this is a pretty practical method.

Some stuff I could find in older threads:
- A 16-bit galois LFSR I suggested to improve shiru's C library: viewtopic.php?p=130725#p130725
- Another previous thread: viewtopic.php?f=10&t=11241

tepples
Posts: 22281
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Which randomizer to use?

Post by tepples » Wed Aug 26, 2015 7:06 am

rainwarrior wrote:I usually recommend a Galois Linear Feedback Shift Register for general purpose random numbers on the NES. I would usually suggest a 16-bit generator even if you're only reading 8-bit values from it (an 8-bit generator loops after only 255 samples, which may not be great if you're looking for unpredictability).
The CRC16 that I linked above is an LFSR that generates 8 bits per call, as opposed to 1 with a naive LFSR implementation.

User avatar
rainwarrior
Posts: 8002
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Which randomizer to use?

Post by rainwarrior » Wed Aug 26, 2015 8:46 am

Is it really an LFSR clocked 8 times? I'd be interested in knowing how this was arrived at. Could you describe the underlying LFSR that it implements? It's a bit beyond me to try and decompose 8 LFSR steps from the steps in this code.

User avatar
rainwarrior
Posts: 8002
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Which randomizer to use?

Post by rainwarrior » Wed Aug 26, 2015 9:14 am

Been looking at this CRC16 algorithm posted by tepples, and it seems a bit curious. It has two dead spots (0, 61471), and two periods of length 32767 (lowest values: 1, 3).

Is there some reason that it can't have a full period of 65535? Why is it split in two? Is it standard for a CRC to sacrifice 1 bit of sequence length for error checking? This design goal seems somewhat contrary to the goals of a PRNG. With some understanding of how it works, would it be possible to modify the algorithm for a period of 65535?

Alternative possibility is that my implementation was incorrect, so it is attached for review.



Edit: Python scripts were later disallowed on this forum. Uploading a ZIP with what I think was the original script.
Attachments
crc16.py.zip
(1.28 KiB) Downloaded 290 times

[The extension py has been deactivated and can no longer be displayed.]

Last edited by rainwarrior on Tue Jun 12, 2018 12:51 pm, edited 1 time in total.

User avatar
rainwarrior
Posts: 8002
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Which randomizer to use?

Post by rainwarrior » Wed Aug 26, 2015 10:11 am

Okay, apparently decomposing it was not as tricky as I had thought. The algorithm is equivalent to 8 ticks of the following Galois LFSR:

Code: Select all

# python
def lfsr(seed):
	seed = seed << 1
	if (seed & 0x10000) != 0:
		seed = seed ^ 0x1021
	seed = seed & 0xFFFF
	return seed

User avatar
DRW
Posts: 2044
Joined: Sat Sep 07, 2013 2:59 pm

Re: Which randomizer to use?

Post by DRW » Wed Aug 26, 2015 10:19 am

tepples wrote:On the 6502, a "typical" randomizer looks like Greg Cook's table-free implementation of CRC16. Initialize it with something nonzero, then just feed it a zero whenever you want a random number.
I'm a bit confused: Why is CRC, i.e. hash values, used for randomization?
freem wrote:Examples of other random number generators can be found on codebase64 (personally, I use White Flame's 8 and 16-bit routines)
Thanks. I'll have a look at them.
rainwarrior wrote:I usually recommend a Galois Linear Feedback Shift Register for general purpose random numbers on the NES. I would usually suggest a 16-bit generator even if you're only reading 8-bit values from it (an 8-bit generator loops after only 255 samples, which may not be great if you're looking for unpredictability).
Yeah, 255 is probably a bit low.

By the way, is there an "official" randomizer for NES games that many companies used? For example, did Nintendo, Konami or Capcom use one specific randomizer for their games or did it change from game to game?
My game "City Trouble": www.denny-r-walter.de/city.htm

JRoatch
Formerly 43110
Posts: 394
Joined: Wed Feb 05, 2014 7:01 am
Location: us-east
Contact:

Re: Which randomizer to use?

Post by JRoatch » Wed Aug 26, 2015 10:48 am

rainwarrior wrote:Been looking at this CRC16 algorithm posted by tepples, and it seems a bit curious. It has two dead spots (0, 61471), and two periods of length 32767 (lowest values: 1, 3).
About a month ago, I suspected that something like this was true when I found that the CRC-16-CCITT polynomial was not in a list of maximal-length polynomials. Ever since, I've been using the 0xb400 polynomial for my 16-bit right shifted Galois LFSR to complement my 32-bit 0xa3000000 LFSR. Thank you for confirming that suspicion.
Last edited by JRoatch on Wed Aug 26, 2015 11:19 am, edited 1 time in total.

User avatar
rainwarrior
Posts: 8002
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Which randomizer to use?

Post by rainwarrior » Wed Aug 26, 2015 11:18 am

So, just for comparison. Here's a simple 16-bit LFSR, using $002D for the feedback. This is the lowest 16-bit polynomial with maximal sequence length (65535).

Code: Select all

; 1 bit at a time
lfsr:
	lda seed+0      ; 3
	asl             ; 2
	rol seed+1      ; 5
	bcc :+          ; 2-3 (+1 if branch taken)
		eor #$2D     ; 2
	:               ;
	sta seed+0      ; 3
	rts             ; total: 16-17 cycles (11 bytes)

; 8 bits at a time
lfsr8:
	lda seed+0        ; 3
	.repeat 8         ;
		asl            ; 2
		rol seed+1     ; 5
		bcc :+         ; 2-3
			eor #$2D    ; 2
		:              ;
	.endrepeat        ; loop: 11-12 cycles (7 bytes)
	sta seed+0        ; 3
	rts               ; total: 94-102 cycles (60 bytes)

; 5 bits at a time
lfsr5:
	... ; as above, change .repeat 8 to .repeat 5
	rts ; total: 61-66 cycles (39 bytes)
So, with this naive approach, 5 bits at a time is comparable in speed/size to that CRC16 (62 cycles, 36 bytes). It would only have 5 bits of entropy, but it does have maximum sequence length (and leaves X/Y registers intact). If you typically need less than 6 bits at a time (e.g. you need random numbers in the range of 0-31), I think I'd recommend against using CRC16. Also you could create 8 entry points for the 1-bit lfsr, allowing you to specify the number of bits as needed on a case-per-case basis, allowing you to save cycles where you need fewer bits.

Code: Select all

	jsr lfsr4
	and #15 ; A = pseudo-random number from 0-15
It might be possible to make something that does 8 bits at once like Greg Cook's CRC16 algorithm, but I don't know how he constructed it. If it were adapted for a maximal-length polynomial, would it have the same efficiency, or require more code? I kind of suspect it's not a generic process, and that $1021 had to be hand-picked to be constructible in a low number of cycles.

User avatar
rainwarrior
Posts: 8002
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Which randomizer to use?

Post by rainwarrior » Wed Aug 26, 2015 11:25 am

DRW wrote:I'm a bit confused: Why is CRC, i.e. hash values, used for randomization?
Hashing and a PRNG have similar goals: try to produce a "random" state from the previous state. Hashes want to avoid clustering similar results (things should be spread out evenly to avoid collisions), so this is very similar to the idea of a PRNG that is trying to produce a number very different from the last one.

Tepples wasn't saying that people use CRC code specifically as PRNGs, just that the common LFSR PRNG algorithms are very similar calculations to a CRC.
DRW wrote:By the way, is there an "official" randomizer for NES games that many companies used? For example, did Nintendo, Konami or Capcom use one specific randomizer for their games or did it change from game to game?
I've never seen the same one twice in an NES game, but I haven't done any kind of extensive survey. I think if you went through games by one company you'd probably find a copy-pasted PRNG now and then. Not all games even require a PRNG, and very often it's practical to have more than one.
Last edited by rainwarrior on Wed Aug 26, 2015 11:31 am, edited 1 time in total.

JRoatch
Formerly 43110
Posts: 394
Joined: Wed Feb 05, 2014 7:01 am
Location: us-east
Contact:

Re: Which randomizer to use?

Post by JRoatch » Wed Aug 26, 2015 11:26 am

rainwarrior wrote:It might be possible to make something that does 8 bits at once like Greg Cook's CRC16 algorithm, but I don't know how he constructed it. If it were adapted for a maximal-length polynomial, would it have the same efficiency, or require more code? I kind of suspect it's not a generic process, and that $1021 had to be hand-picked to be constructible in a low number of cycles.
I did it for a 32-bit LFSR, but I'm not certain the process I used will help make an optimized 16-bit one.

User avatar
rainwarrior
Posts: 8002
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Which randomizer to use?

Post by rainwarrior » Wed Aug 26, 2015 1:09 pm

here's 8 ticks of the $002D LFSR at once as a multiply and XOR. ($2D = %101101, so this is 4 operations of shift + XOR).

Code: Select all

lfsr8:
	ldx seed+0
	lda seed+1
	sta seed+0 ; low x << 0 (9 cycles)
	lda seed+1
	asl
	asl
	pha
	eor seed+0
	sta seed+0 ; low x << 2 (+15 = 24 cycles)
	pla
	asl
	pha
	eor seed+0
	sta seed+0 ; low x << 3 (+12 = 36 cycles)
	pla
	asl
	asl
	eor seed+0
	sta seed+0 ; low x << 5 (+12 = 48 cycles)
	lda seed+1
	stx seed+1 ; high x << 8
	lsr
	lsr
	lsr
	pha
	eor seed+1
	sta seed+1 ; high x << 5 (+20 = 68 cycles)
	pla
	lsr
	lsr
	pha
	eor seed+1
	sta seed+1 ; high x << 3 (+14 = 82 cycles)
	pla
	lsr
	eor seed+1
	sta seed+1 ; high x << 2 (+10 = 92 cycles)
	lda seed+0
	rts ; total: 95 cycles (57 bytes)
This runs in constant time, but average time is almost the same as the .repeat version (also requires one byte of temporary storage? X in this example). Compared to the other version, it can't be broken down by number of bits needed like I suggested, though, so I think this way is inferior, at least. This is optimizing only the 8-bits case at the expense of cases requiring less. (Warning: this code is untested and could have errors, but I was only investigating how many cycles it should take. If this is incorrect, a correct version should be comparable.)

Actually, now that I've compared this I can see where Cook's CRC16 gets its added efficiency from. If I eliminated one of the taps here, I could probably cut ~25 cycles (putting it a lot closer to the CRC16 algorithm), but I'd also be losing maximal length at the same time (just like CRC16 does).

So, really, making an LFSR efficient for 8 bits at once is probably mostly a matter of finding a polynomial that will minimize the number of shifts required. There's probably some extra optimization hiding in Cook's method versus my naive multiply and XOR, but it's a bit minor compared to what it picks up by sacrificing sequence length.

User avatar
DRW
Posts: 2044
Joined: Sat Sep 07, 2013 2:59 pm

Re: Which randomizer to use?

Post by DRW » Wed Aug 26, 2015 4:22 pm

Since I don't know much about the various details of the random number generator, which one shall I use now?

I would prefer a simple and fast algorithm. Seed value, a nice little calculation, that's it. It should of course work on 16 bits so that it doesn't already repeat after 256 calls. But other than that, it doesn't need to be specifically advanced.

I could just pick one of the various generators listed. Choosing a "random" one, so to say. But I'd like to have a "reason" to pick a specific one. Some established, "official" algorithm would be best.
Do you know which one I could take?
For example, is there an official implementation from an old 6502 library or does the implementation of the RND command from BASIC work for the NES? Or does the original C library have a rand function that doesn't use multiplication and division?

Something like that. Simple in its implementation, but with a touch of "officialness". Not just a "random" algorithm written by anybody and published on some private homepage.
My game "City Trouble": www.denny-r-walter.de/city.htm

Post Reply