This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Which randomizer to use?

Which randomizer to use?
by on (#154048)
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:
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?
Re: Which randomizer to use?
by on (#154049)
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.
Re: Which randomizer to use?
by on (#154052)
Examples of other random number generators can be found on codebase64 (personally, I use White Flame's 8 and 16-bit routines)
Re: Which randomizer to use?
by on (#154068)
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: http://forums.nesdev.com/viewtopic.php?p=130725#p130725
- Another previous thread: http://forums.nesdev.com/viewtopic.php?f=10&t=11241
Re: Which randomizer to use?
by on (#154088)
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.
Re: Which randomizer to use?
by on (#154098)
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.
Re: Which randomizer to use?
by on (#154101)
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.
Re: Which randomizer to use?
by on (#154107)
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:
# python
def lfsr(seed):
   seed = seed << 1
   if (seed & 0x10000) != 0:
      seed = seed ^ 0x1021
   seed = seed & 0xFFFF
   return seed
Re: Which randomizer to use?
by on (#154110)
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?
Re: Which randomizer to use?
by on (#154112)
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.
Re: Which randomizer to use?
by on (#154113)
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:
; 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:
   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.
Re: Which randomizer to use?
by on (#154114)
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.
Re: Which randomizer to use?
by on (#154115)
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.
Re: Which randomizer to use?
by on (#154120)
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:
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.
Re: Which randomizer to use?
by on (#154145)
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.
Re: Which randomizer to use?
by on (#154148)
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.
Re: Which randomizer to use?
by on (#154158)
DRW wrote:
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/Random_number_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.

Quote:
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.

Quote:
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/master/libsrc/common/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.
Re: Which randomizer to use?
by on (#154165)
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).
Re: Which randomizer to use?
by on (#154181)
rainwarrior wrote:
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.
Re: Which randomizer to use?
by on (#154184)
You might want to delete these two lines, if you use CC65's rand():
Code:
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().
Re: Which randomizer to use?
by on (#154191)
Or take it out, define unsigned short int u16rand(), and then have rand() call that:

Code:
#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.
Re: Which randomizer to use?
by on (#154192)
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:
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:
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
Re: Which randomizer to use?
by on (#154203)
rainwarrior wrote:
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?
Re: Which randomizer to use?
by on (#154205)
DRW wrote:
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.

Quote:
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.
Re: Which randomizer to use?
by on (#154206)
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/
Re: Which randomizer to use?
by on (#154208)
From the linked page on kkfos.aspect.fi:
Quote:
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:
#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:
#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:
;
; 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:
.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:
.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
Re: Which randomizer to use?
by on (#154209)
tepples wrote:
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.
Re: Which randomizer to use?
by on (#154212)
tepples wrote:
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.
Re: Which randomizer to use?
by on (#154214)
hackfresh wrote:
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.
Re: Which randomizer to use?
by on (#154215)
tepples wrote:
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.


lidnariq wrote:
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.
Re: Which randomizer to use?
by on (#154223)
hackfresh wrote:
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.



Sik wrote:
Is it me or it doesn't clear the carry between additions? That would be basically doing a 24-bit addition then. I guess that means that the 3D byte will go the longest without looping???



Ahh good point. I guess for the main routine that occurs every frame you are correct it is doing 24 bit addition!

The game does call these individual routines at times where it updates the single bytes.


Code:
update_random_3B:
   LDA RANDOM_3B
   CLC
   ADC #$83
   STA RANDOM_3B
   RTS

update_random_3C:
   LDA RANDOM_3C
   CLC
   ADC #$0D
   STA RANDOM_3C
   RTS

update_random_3D:
   LDA RANDOM_3D
   CLC
   ADC #$11
   STA RANDOM_3D
   RTS
Re: Which randomizer to use?
by on (#154225)
The prime factorization of $110D83 (1117571) is 7 x 13 x 12281, so it's perfectly fine as a mod(224) cycle of additions. I would expect this to have slightly better behaviour than 3 independent 8-bit cycles.

Super Mario 3 actually ticks its random number generator once per frame, and anything that needs a random number that frame just samples it. Pretty similar to what you're doing there. It seems like this method could lead to bad things like two of the same enemies onscreen moving in lock-step with each other, but it's probably easy to avoid if you're careful. (Or maybe that's the kind of bug that is "fun" to have?)

I actually use mod(2n) addition cycles like that for lots of things in my game. I do OAM cycling by picking a different additive factor each frame and cycling through my objects to draw in that order. In this case, though, I am not looking for "random" as much as I am looking for "different order each frame". Sort of a different concern than a PRNG, because I want it to predictably cycle through a well behaved set of orderings.

The big reason there's so many different PRNG code samples out there is that for a lot of purposes there's a really low bar for "random". If you just need something that seems uncorrelated you can do some really trivial / quick stuff that works fine in the context it gets used. (Example: Yars' Revenge just uses the game's ROM as "random" looking background data, because it was quicker/easier than generating it, I guess.) The problems usually come from expecting a random generator that works fine for a very limited application to work everywhere. Producing a generic PRNG that is suitable for wide usage takes a bit more theory and testing. It's not uncommon for "bad" PRNG code to get copied to a lot of places because it seemed fine in most cases and nobody really tested it thoroughly. Example RANDU.
Re: Which randomizer to use?
by on (#154252)
rainwarrior wrote:
Super Mario 3 actually ticks its random number generator once per frame, and anything that needs a random number that frame just samples it. Pretty similar to what you're doing there. It seems like this method could lead to bad things like two of the same enemies onscreen moving in lock-step with each other, but it's probably easy to avoid if you're careful. (Or maybe that's the kind of bug that is "fun" to have?)

Actually, enemies going in lock-step is probably more useful than harmful...