Which randomizer to use?

[lidnariq]

Well, there's the RNG from the C64's BASIC. It appears to be yet another kind of wikipedia:linear congruential generator, like the very first thing you posted.

Personally, I'd recommend any maximal-period 24 to 32 bit LFSR. They're fast (for a processor without much RAM, not wanting to spend lots of ROM on lookup tables, and no hardware multiplier) and reasonably random. A lot of the state-of-the-art RNGs from the 1980s aren't very good, and LFSRs are not appreciably worse while being faster.

[rainwarrior]

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 placed my example on the wiki here: http://wiki.nesdev.com/w/index.php/Rand ... _generator

I'd like to think that it's of fairly generic purpose (8 bit result, sequence of length 65535), simple and short code, and reasonably efficient, which I hope would satisfy your needs.

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?

Well, the difference between the various generators is pretty subtle. Telling you which one to pick would really requiring knowing a lot of detail about your needs and how you want to use it. If you want the "fastest" thing, you can often trade quality for speed. This is very true with the LFSR generators. If you have a specific need, tell us what it is. If you don't, use any one that looks okay to you, a lot of them will probably serve you fine. (If you want my advice, use the one I just wrote. If you don't like the one I wrote, maybe explain why it doesn't meet your needs?)

The reason many of us keep suggesting LFSRs is that they're very simple in design and operation, and their behaviour is very well known. When properly formed, they will visit every single value in their sequence once before repeating (except 0), which generally creates a very good PRNG.

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.

The page for that BASIC RND says "this is a pretty nutty algorithm". Does that inspire confidence for you? I wouldn't use it.

CC65's rand() has what looks like a 32 bit linear-congruential generator. At first glance it seems like sensible code to me: https://github.com/cc65/cc65/blob/maste ... mon/rand.s

I have no idea who or what you would accept as "official". If you can't take my word for it, or anyone else's here, then you must decide whom you trust as an authority.

[freem]

If "official" is shorthand for "made by Nintendo", the only Nintendo-provided RNG I can think of is in the Famicom Disk System BIOS (Referred to as "Random" in the wiki).

[DRW]

I have no idea who or what you would accept as "official". If you can't take my word for it, or anyone else's here, then you must decide whom you trust as an authority.

With official, I mean algorithms that are included, for example, in actual compiler suites or that are published in language standards etc.

The thing is: When I use an algorithm written by a private person and uploaded to his personal homepage, I would feel morally obliged to mention his name in the credits of my game. But on the other hand, I don't want to mention a person in the credits just because I used one little function from him where I could have used any other function as well.
That's why I was looking for an "official" algorithm: Something from the C64 or the Atari or from an old version of Visual C++. Something that isn't tied to a random person, so that my credits don't have to look like this (KK is my colleague):

Idea: DRW and KK
Graphics: KK
Programming: DRW
Compiled with CC65
10 lines of programming code: John Doe from www.johnscoolhomepage.com


But it looks like you already solved the problem: I wasn't aware of the fact that CC65 has an implementation of rand and srand. So, I guess I'll just use this one. Since it comes with the compiler that I create my game with, it is an "official" algorithm to me.

[rainwarrior]

You might want to delete these two lines, if you use CC65's rand():

Code: Select all

and     #$7f            ; Suppress sign bit (make it positive)
tax

This will make that routine leave X alone, so that calling the routine will only change A/flags.

Of course, if you want a positive (signed) 16-bit value returned in X:A then leave it in, or if you're actually using C, you'd need it in there so that the return type matches the definition of rand().

[tepples]

Or take it out, define unsigned short int u16rand(), and then have rand() call that:

Code: Select all

#include <limits.h>
#include <stdlib.h>

static unsigned long int srand_value = 0x87654321U;

void srand(unsigned int seed) {
  srand_value = (unsigned short int)seed ^ 0x87654321U;
}

/**
 * Generates a pseudorandom number from 0 to USHRT_MAX.
 */
unsigned short int u16rand(void) {
  /* Constants taken from BCPL's "excellent" LCG per
     http://random.mat.sbg.ac.at/results/karl/server/node4.html */
  srand_value = srand_value * 2147001325U + 715136305U;
  /* The xor here helps to break up the Marsaglia hyperplanes
     http://stats.stackexchange.com/q/38328/86988 */
  return (srand_value >> 16) ^ srand_value;
}

/**
 * Generates a pseudorandom number from 0 to RAND_MAX.
 * Conforms to standard iff RAND_MAX is no greater
 * than USHRT_MAX.
 */
int rand(void) {
  return u16rand() & RAND_MAX;
}

/* Assertion to back up assumption in previous function */
extern char assert_randmax_u16[RAND_MAX <= USHRT_MAX ? 1 : -1];

I hereby make the preceding code available under CC0 1.0 Public Domain Dedication.

[hackfresh]

Just chiming in on the method used in a game I've been commenting the dissassembly for: Tecmo Super Bowl. It doesn't look as good as the other methods posted but just thought I'd share it. It's a PRNG.

This game creates 3 "random" single numbers. Each one is updated AT LEAST once per frame. Sometimes there are subroutines that re-update the randoms mid frame. Basically the randoms are generated by adding prime numbers to each other. This has he problem of looping every 256 frames.

This is the one that is done once per frame.

Code: Select all

update_randoms:
	LDA RANDOM_3B
	CLC
	ADC #$83
	STA RANDOM_3B
	LDA RANDOM_3C
	ADC #$0D
	STA RANDOM_3C
	LDA RANDOM_3D
	ADC #$11
	STA RANDOM_3D
	RTS

There are also individual functions to update just one of the random numbers at a time. The functions are just subsets of the code above. The individual functions are often called when it is checking the same random multiple times a frame (for things like defender actions) .


When the game needs a "more random" number it does the following.

Code: Select all

L_D8F7:
	JSR update_randoms
	LDA RANDOM_3B
	AND #%00000011
	BEQ @Loop3
	CMP #%00000001
	BEQ @Loop2
	CMP #%00000010
	BEQ @Loop1
@Loop0:
	LDA RANDOM_3D
	RTS
@Loop1:
	LDA RANDOM_3C
	RTS
@Loop2:
	LDA RANDOM_3D
	CLC
	ADC RANDOM_3C
	RTS
@Loop3:
	LDA RANDOM_3D
	CLC
	ADC RANDOM_3C
	ADC RANDOM_3B
	RTS

[DRW]

Of course, if you want a positive (signed) 16-bit value returned in X:A then leave it in, or if you're actually using C, you'd need it in there so that the return type matches the definition of rand().

Yes, I do use C. So, I'll just leave it as it is. Also, I'd rather prefer only positive numbers.


A little off-topic question: Apart from rand, are there any other general purpose C functions that might be useful in an NES game?
I mean, you don't need printf. (Is this even implemented for the NES?) And of course, all the stuff that's actually for the NES, like startup code etc. and controller reading, is always written by me.
But can you think of any function from the "stdlib.h" or any other standard header file that might be useful in programming the general game logic?

[tepples]

A little off-topic question: Apart from rand, are there any other general purpose C functions that might be useful in an NES game?
I mean, you don't need printf. (Is this even implemented for the NES?)

NovaSquirrel discovered that Koei's sims for NES implement at least a subset of the printf family. Unless you're willing to develop your own implementation of stream I/O (FILE *), the most helpful might be sprintf.

But can you think of any function from the "stdlib.h" or any other standard header file that might be useful in programming the general game logic?

After a quick check of the C standard headers:

• If you need to divide and need both a quotient and a remainder, div in stdlib.h
• If you need to wrap sprintf to work with your display system, va_* in stdarg.h
• Most of math.h is floating-point, and floating-point is far too slow for real-time use on an NES. So most of your trig for aiming and the like will be done with the help of lookup tables.
• iso646.h defines macros for bitwise operators, which can be useful if developing on a foreign keyboard that makes certain punctuation characters are hard to type.
• ctype.h helps manipulate characters in your game's character set, assuming that your game's character set is known to the compiler and library. I'm not sure to what extent cc65 supports non-ASCII character encodings.
• You may want to override assert in assert.h to provide your own "blue screen of death" when an assertion fails in a debug build.

[lidnariq]

All the multiplication routines are in the 6502's C runtime, as well as various other non-8-bit math things. You can use ar65 to get a full list of all the modules that the library provides, although finding out what each one does requires the cc65 source.

Note that you shouldn't read the joystick from C if you enable the optimizer, for reasons that thefox pointed out here: http://kkfos.aspekt.fi/projects/nes/lib ... -for-cc65/

[tepples]

From the linked page on kkfos.aspect.fi:

Use the optimizer (“-Oirs” switch) BUT be aware that it might in some cases produce broken code. One such case is when you read the controllers by strobing $4016, then reading it eight times. The first read is optimized away. Of course when you’re using this library you can simply use read_joy().

True, I/O routines on the NES should usually be written in assembly language because they need to be fast, unlike cc65 output. But why does it optimize out reads even when the joystick ports are declared as volatile char *? Does it disregard volatile?

Code: Select all

#define JOY1 (*(volatile unsigned char *)0x4016)
unsigned char broken(void) {
  unsigned char presses = 0;
  JOY1 = 1;
  JOY1 = 0;
  for (unsigned char i = 8; i > 0; --i) {
    presses = (presses << 1) | ((JOY1 & 0x03) > 0);
  }
  return presses;
}

But this doesn't work because cc65 still enforces a restriction on the position of variable declarations that was removed from the C standard sixteen years ago.

Code: Select all

#define JOY1 (*(volatile unsigned char *)0x4016)
unsigned char broken(void) {
  unsigned char presses = 0;
  unsigned char i;
  JOY1 = 1;
  JOY1 = 0;
  for (i = 8; i > 0; --i) {
    presses = (presses << 1) | ((JOY1 & 0x03) > 0);
  }
  return presses;
}

Resulting assembly language with -Oirs:

Code: Select all

;
; File generated by cc65 v 2.14 - Git N/A
;
	.fopt		compiler,"cc65 v 2.14 - Git N/A"
	.setcpu		"6502"
	.smart		on
	.autoimport	on
	.case		on
	.debuginfo	off
	.importzp	sp, sreg, regsave, regbank
	.importzp	tmp1, tmp2, tmp3, tmp4, ptr1, ptr2, ptr3, ptr4
	.macpack	longbranch
	.export		_broken

; ---------------------------------------------------------------
; unsigned char __near__ broken (void)
; ---------------------------------------------------------------

.segment	"CODE"

.proc	_broken: near

.segment	"CODE"

	lda     #$00
	jsr     pusha
	jsr     decsp1
	lda     #$01
	sta     $4016
	lda     #$00
	sta     $4016
	lda     #$08
	ldy     #$00
L001A:	sta     (sp),y
	lda     (sp),y
	beq     L000A
	iny
	ldx     #$00
	lda     (sp),y
	asl     a
	bcc     L0019
	inx
L0019:	jsr     pushax
	lda     $4016
	and     #$03
	jsr     boolne
	jsr     tosora0
	ldy     #$01
	sta     (sp),y
	dey
	lda     (sp),y
	sec
	sbc     #$01
	jmp     L001A
L000A:	iny
	tax
	lda     (sp),y
	jmp     incsp2

.endproc

How many times does this assembly language execute the code at L0019? Is cc65 -Oirs respecting or ignoring volatile?

[ Thematic break ]

But here's why your I/O should be in assembly language. Compare the above to a formal-equivalent translation of the C code that is halfway optimized:

Code: Select all

.export _broken

.proc _broken
  lda #1
  sta $4016
  lda #0
  sta $4016
  ldy #8
L000P:
  tax        ; save `pressed` in a register
  lda $4016
  and #$03
  cmp #$01  ; boolne in one instruction!
  txa
  rol a
  dey
  bne L000P
  rts
.endproc

Not to mention the fact that use of a ring counter, which is impractical in C because of C's lack of any language construct resembling a carry flag, can produce something even more efficient:

Code: Select all

.export _broken

.proc _broken
  ldx #1
  stx $4016
  dex
  stx $4016
  inx  ; init the ring counter to 1
L000P:
  lda $4016
  and #$03
  cmp #$01  ; boolne in one instruction!
  txa
  rol a
  tax
  bcc L000P  ; 1 shifted left 8 times fills carry
  rts
.endproc

[lidnariq]

Does it disregard volatile?

The volatile keyword doesn't have an effect. This is not as bad as it sounds, since the 6502 has so few registers that it isn't possible to keep values in registers anyway.

[rainwarrior]

But this doesn't work because cc65 still enforces a restriction on the position of variable declarations that was removed from the C standard sixteen years ago.

C99 is not the C standard, it is a C standard. C89 is still the most widely supported C standard. Actually meeting the C99 standard requires a great many things, not just variable order. Many modern compilers (and very notably MSVC) have only partial C99 support, but almost all have full C89 support. If there is a C standard you could call the standard, it is C89, not C99.

CC65 has "mostly" complete C89 support, and only a few conveniences from C99 (with an option to disable for better C89 compliance). See: Differences to the ISO standard

Please note that the compiler does not support the C99 standard and never will. c99 mode is actually c89 mode with a few selected C99 extensions.

[Sik]

This game creates 3 "random" single numbers. Each one is updated AT LEAST once per frame. Sometimes there are subroutines that re-update the randoms mid frame. Basically the randoms are generated by adding prime numbers to each other. This has he problem of looping every 256 frames.

Is it me or it doesn't clear the carry between additions? That would be basically doing a 24-bit addition then.

[DRW]

Unless you're willing to develop your own implementation of stream I/O (FILE *), the most helpful might be sprintf.

I didn't mean that I need anything like that. It was just a little side question. If I want to show text on the screen, I will do it like with every other graphics.

From your list, those are all things that I probably won't need. Sorry.
(They really created macros for the bitwise operations. What is this? Visual Basic?)

One function that I might need is memcpy.
I have an array for all the background data that shall be updated during the next NMI call. This array includes PPU starting addresses, the PPUCTRL value (for horizontal or vertical drawing) and the graphical data. And the terminating character for one block of data is 0xFE (so that the same array can include update information for various portions of the screen) and the final terminating character is 0xFF. And when a certain boolean variable is set to true, the NMI reads this array (and then sets the boolean variable back to false, so that it isn't read in the next frame anymore) and puts the data into the PPU.
memcpy might be helpful to copy graphical information from the ROM into this array.
Same with palette data.

Note that you shouldn't read the joystick from C if you enable the optimizer, for reasons that thefox pointed out here: http://kkfos.aspekt.fi/projects/nes/lib ... -for-cc65/

That's no problem. I already implemented my controller reading function in assembly. The whole controller status is written into one simple variable once per frame. And the C code then merely has to check this variable.

In fact, I don't access any of the NES registers or any of that low-level stuff from within C. While I prepare general arrays that do include NES-specific data (like the PPU address high byte and low byte to write to and the PPUCTRL value that shall be set for this drawing process) in C, the actual communication with the PPU itself is always done in assembly.