Random Thoughts

And ... we're back, and picking-up right where we left things with random numbers.

Getting the Meanies to move randomly requires a little bit of code to generate a random value which will indicate how the little blue guys should change position. Generating random numbers is reasonably straight-forward, provided you choose your generation source carefully - what is needed is a source of values that change frequently, which you can tap as the baseline value to use in deriving what looks like randomness. The problem with computer-generated random numbers is that they're never 'truly' random, because ultimately the environment is deterministic - we want the computer to behave in a known, repeatable, predictable way, and having random unpredictable stuff happening is highly undesirable. So we have to create the illusion of randomness by using some root value that appears to be unpredictably different every time we look at it.

I'd been thinking about using the VIC Raster Counter register at $9003/$9004 as the baseline value for a RNG (Random Number Generator) and Muttleys' earlier comment on a previous post shows that this is a typical approach. The VIC doesn't support hardware raster interrupts (unlike its' successor the C64) so the raster counter simply keeps track of how many video raster lines have been drawn per frame - it starts at zero and rapidly counts up to however many lines are displayed (which varies depending on whether you're looking at the picture on a PAL or NTSC model) before resetting. Since this counter runs very rapidly, consecutive reads of the register will return different values, and provided you aren't reading it at precise intervals you'll get a different value from the range every time.

Of course, the Meanie code is fairly linear, so there is a slight chance that we could fall into a situation where we are reading the raster counter at regular intervals - which means we might get the same value every time. Ironically, this is precisely what coders want when they need to synchronise video effects to the raster line, but for the purposes of generating random numbers it's a disaster. So we need to add a further skewing value to what we get out of the raster counter, to ensure that even if we do end-up synchronised to it, we'll still get a variable result - and that's why I'm using a page of ROM data as an additional source (Muttley uses another memory area on the C64) to guarantee variability. By adding sequential values from ROM to the value obtained from the raster counter, we get pseudo-randomness - in the worst case, where we've synchronised to the raster count, we'll still get 256 successive values from the ROM that have the appearance of being random.

But that still isn't random 'enough', because we'd still only have a domain of a maximum of 256 values (which is itself unlikely, since a page of ROM code is probably going to contain a tiny subset of that) and that is quite a small working set - small enough that a keen eye could eventually spot a pattern and might therefore be able to predict with some success what was going to happen next. So we also need a 'seed' value, which changes over time, to act as a further layer of randomness - by incorporating the seed in the algorithm, we add an additional level of complexity to the values the RNG produces, ensuring that the worst-case scenario (synchronisation to the raster counter and a predictable ROM pattern) still generates apparent randomness.

The VIC raster counter occupies 9 bits, with $9004 holding the first 8 bits and the 9th bit sitting in bit 7 of $9003 - this makes sense, because a PAL or NTSC screen is made up of either 312 or 261 raster lines respectively, both of which require 9 bits to represent in binary. The VIC registers, like every other memory location, are bytes - so they contain 8 bits, and that means the 9th bit has to go somewhere else. In this case, it tucks into the end of the register at $9003, and is therefore clear when the counter is less than 256, and set when greater-than or equal to 256.

We can ignore that 9th bit though, and just read the contents of $9004 - it'll give us values from 0-255, and it doesn't matter that it wraps back to zero before the end of the frame when bit 7 of $9003 is set for raster lines 256-312  (or 261 for NTSC). So I'm going to create a little subroutine that will pick-up the current value of $9004, add it to a sequentially-incremented ROM location (actually, thinking about it, I might use Zero Page - it's a faster operation, and just as 'random') and finally add a seed value. I'll post the code once it's in place, in a day or two.