Getting better random numbers with Shiru's C lib?

[Scoth42]

I've recently jumped into the world of NES development, and since I know a little C I decided to start with it. So far it's gone great and I'm about 99% done with my first project with it, but I'm having a little trouble getting my random numbers to be very random. I know getting anything close to true random numbers (or PRNG even) out of an NES is not really feasible, but I'm confused by the behavior I'm seeing. I've looked at the source of Zooming Secretary and a couple other homebrews and I see they have an otherwise-unused rand16() in the title screen loop, and in various other places, to burn through random numbers and start the game with (hopefully) different numbers. However, doing that, I only seem to get maybe 6 or 8 different playfield arrangements no matter how long I wait at the title screen. My code that bit is pretty simple:

Code: Select all

while(1)
	{
		ppu_wait_frame();
		rand16();
		if(pad_trigger(0)&PAD_START) break;

	}

In addition, using set_rand function just seems to screw the whole thing up and I end up with my randomly-positioned spites all lined up on the left.

I'm still a noob when it comes to NES internals, so apologies if this is addressed somewhere that I've missed. It's tricky to search for "C"!

[rainwarrior]

I know getting anything close to true random numbers (or PRNG even) out of an NES is not really feasible

The NES is capable of running all standard PRNG algorithms, even modern ones. Most NES developers favour simpler ones so they can use them often and not eat up too many cyles, and the quality is sometimes not an issue (e.g. AI fuzzy logic doesn't usually require a high quality PRNG).

Some suggestions for addressing your problem:

1. Test your random seed. Display it to the screen directly instead of viewing it indirectly through your generator. Make sure you're getting different numbers out of it.

2. Check your generation process, possibly the lack of variety has to do with how it's set up and not the PRNG itself.

3. Taking output of a PRNG in regular blocks, like if you're just dumping it to rows of the screen, 32 samples at a time, etc. will tend to reveal cyclic patterns in low quality PRNGs. Either try to make your sampling less regular, or possibly find a new PRNG.

[tepples]

To search for C on this board, search for cc65.

As for PRNGs, the typical way of seeding them is to count vblanks from power on to pressing Start. The rand call during the title screen is for this. And Greg Cook's CRC16 is a decent PRNG that returns 8 bits at a time with a 16-bit state. What are you randomizing?

[rainwarrior]

This is the rand16 code I found in shiru's examples:

Code: Select all

;Galois random generator, found somewhere
;out: A random number 0..255

rand1:
	lda <RAND_SEED
	asl a
	bcc @1
	eor #$cf
@1:
	sta <RAND_SEED
	rts

rand2:
	lda <RAND_SEED+1
	asl a
	bcc @1
	eor #$d7
@1:
	sta <RAND_SEED+1
	rts

_rand8:
	jsr rand1
	jsr rand2
	adc <RAND_SEED
	rts



;unsigned int __fastcall__ rand16(void);

_rand16:
	jsr rand1
	tax
	jsr rand2
	rts


;void __fastcall__ set_rand(unsigned char seed);

_set_rand:
	sta <RAND_SEED
	stx <RAND_SEED+1
	rts

To me this looks like 2 8-bit generators running in parallel, which is probably very poor quality as a 16-bit PRNG, for the following reasons:

1. The two bytes are independent PRNGs, so if you're using the low 8 bits, for example, it will have a maximum period of 255 and there is no advantage over a simpler 8-bit PRNG.
2. Possibly both PRNGs have a period of 255, which would mean they run in lock-step with each other and rand16() will only produce 255 different values.
3. A random seed with 0 in the high or low byte will disable that byte of the PRNG.

I think throwing this away and trying a true 16-bit PRNG would be prudent.


Though, if one of the two 8-bit PRNGs does have a different period, the _rand8 function might be worthwhile. It would actually have a much longer sequence, maybe like 10000 rather than 255.

[rainwarrior]

It looks like rand1 has a period of 255, but rand2 has several periods of 17, so you will get a cycle of about 4000 out of _rand8. However, _rand16 will still only have a cycle of 255 if you're only using the low byte.

You could still probably do a lot better with a different 16-bit PRNG implementation though. There were some ideas posted here: viewtopic.php?f=10&t=11241

Here's a quick one I just wrote. It has a cycle of 65535:

Code: Select all

;
; 6502 16-bit Galois LFSR
;

; unsigned int __fastcall__ rand16(void);

_rand16:
    asl <RAND_SEED
    rol <RAND_SEED+1
    bcc @1
    lda <RAND_SEED
    eor #$E7
    sta <RAND_SEED
    tax
    lda <RAND_SEED+1
    eor #$8D
    sta <RAND_SEED+1
    rts
@1:
    ldx <RAND_SEED
    lda <RAND_SEED+1
    rts

//
// equivalent C++
//

static unsigned short int rand_seed = 1; // note: a value of 0 will kill the LFSR
unsigned short int rand16()
{
     bool high_bit = (rand_seed & 0x8000) != 0;
     rand_seed = rand_seed << 1;
     if (high_bit)
     {
         rand_seed = rand_seed ^ 0x8DE7;
     }
     return rand_seed;
}

Note that with the Galois LFSR it is only gathering one bit of entropy per call. To get an 8-bit random number, you would ideally call rand16() 8 times before using the result & 0xFF. You can probably get away with calling it fewer times, or even just once, depending on your needs (but avoid calling it in groups of 3/5/15, as these divide the period of 65535 evenly). It takes 31 or 42 cycles per call, depending on the high bit of the current seed, so you can do approximately 2 per scanline.

[Scoth42]

Thanks for the replies, this is some great info. It's always interesting getting into something new and figuring out the nuances. I'll likely be digging into nerdy night's stuff stuff soon; I've done a very very little bit of 6502 ASM as a kid on Atari 8-bit but it's been literally fifteen or twenty years since I looked at it.

As for what I'm randomizing, I'm starting with a version of robotfindskitten. There isn't one for NES and it's been a great way to learn sprite handling, nametables, etc. So I need a way to randomize kitten and non-kitten objects. It's basically done at this point but I'd like to improve the level generation. I'll be posting it when I'm done!

[Scoth42]

The updated RNG worked great. Thanks rainwarrior! This pretty much completes my robotfindskitten port; I've submitted it to the website. I've uploaded the rom to http://iamscott.net/robotfindskitten.nes if anyone wants to try it out. Nothing super fancy by the standards of some of the things I've seen on here but I'm pleased with it for a first project.

Thanks again!

[tepples]

Thank you. It works in FCEUX. I noticed the 20K of NKIs in the ROM; how did you determine what to include and what to leave out?

So is it OK to make and sell copies of this game on the next community multicart?

[Scoth42]

Absolutely! I'd be honored to be included! I plan on making my own cart of it myself once I get a label figured out - I can do coding, eproms, soldering, and such, but artistic skill eludes me. So I stick with what I'm good at.

[Scoth42]

Thank you. It works in FCEUX. I noticed the 20K of NKIs in the ROM; how did you determine what to include and what to leave out?

So is it OK to make and sell copies of this game on the next community multicart?

I've just reuploaded a slightly updated version to http://iamscott.net/robotfindskitten.nes . Turns out I misunderstood my emulator's presentation of NTSC cutoff and it likely would have been screwed up. Also fixed a bug with robot getting to move out of bounds. This should be a good baseline version, although it's been suggested I look into proportional fonts for the NKOs. May or may not get to that; I'm fairly pleased with it as it is.