Random Thoughts

And now a side-trek on random number generation…

Pseudo-random numbers have been a part of software design for awhile. It’s a field that is still very heavy in the mathematics area, because a large part of it is about trying to design an algorithm to create a random value quickly but also predictably.

However, if you started with BASIC in the old days, all that was hidden from you. You just called a RAND or RND function and got a number. The better BASIC languages offered a way to change or update the random seed, but otherwise you just used what they gave you and didn’t know what it did under the hood.

For most 99’ers, the earliest best example of an assembly random number generator came from the source code for Tombstone City, a cartridge game from Texas Instruments. The source code was provided with the Editor/Assembler package as a learning tool. (Sadly, as a teenager, I wasn’t aware of this. Studying source code may have made my early frustrations with assembly programming easier. Ah well…)

Here is the routine from it:

RANDNO LI   R4,28645
       MPY  @RAND16,R4
       AI   R5,31417
       MOV  R5,@RAND16
       RT

As you can see, not a lot to this one. Let’s say you started with a random seed of 0 and went a few cycles:

• 0 * 28645 = 0 + 31417 = 31417
• 31417 * 28645 = 65149 (low word) + 31417 = 31030
• 31030 * 28645 = 55118 (low word) + 31417 = 20999
• 20999 * 28645 = 26947 (low word) + 31417 = 58364

This is pretty much what every pseudo-random algorithm does. It generates a sequence of values using the prior value as a key to generate the new value. It also creates a predictable sequence, which can be useful in situations where you want the randomness to be more controlled. It also produces an exact sequence of 65536 different values; changing the seed value just changes where you start in the sequence.

However, it consistently produces an even/odd pattern. In some cases, this may be desirable! But for most random routines you want the even/oddness to be variant.

A simple fix, which is what I introduced and it did the trick at the time, was to throw in a bit shift of an odd value on the random seed, as follows:

RANDNO LI   R4,28645
       MPY  @RAND16,R4
       AI   R5,31417
       SRC  R5,5
       MOV  R5,@RAND16
       RT

By shifting the bits an odd number of times it broke up the even/odd cycle. It however still creates a predictable sequence since you are always shifting by a predictable amount.

So my next solution was to have the bit shift be determined by an outside factor.

The TI-99/4a has a vertical sync clock which ticks at 1/60 of a second. By using that value to determine the bit shift, I was able to have it shift to a completely different place in the sequence in an unpredictable fashion:

RANDNO LI   R4,28645
       MPY  @RAND16,R4
       AI   R5,31417
       MOV  @CLOCK,R0
       ANDI R0,>000F
       SRC  R5,0
       MOV  R5,@RAND16
       RT

@CLOCK in this instance is a word that I increment every time there is a vertical sync.

But even THIS one is not perfect… because when I tried to use it to generate random map content, which involved consecutive calls to the random function in a tight time frame when the vertical clock did not actually change, it created strange symmetric patterns every 4th or 5th iteration.

So I decided to change the routine, for the map generation at least, to a different approach:

MASK   DATA >B400
RANDNO MOV  @RAND16,R0
       SRL  R0,1
       JNC  NOCARR
       XOR  @MASK,R0
NOCARR MOV  R0,@RAND16

This rather clever routine avoids the use of multiplication (which is unavailable in many assembly languages of the era, and is cycle-costly) and uses XOR instead to invert the bits when there is no carry. This creates a predictable sequence that varies high and low.

Let’s step through it a bit, starting with 0:

• 0 >> 1 = 0, No carry, XOR >B400 = 46080
• 46080 >> 1 = 23040, No carry, XOR >B400 = 60928
• 60928 >> 1 = 30464, No carry, XOR >B400 = 49920
• 49920 >> 1 = 24960, No carry, XOR >B400 = 54656

So this one worked better, since it wasn’t relying upon the clock value. Until I reached a particular map where I was placing random tiles in a smaller area. Suddenly every single map produced the EXACT SAME pattern of tiles in an odd diagonal line. I realized then that I had to go back to the drawing board.

The solution (at present anyway) is to use a different clock. I needed one that counted faster than 1/60 of a second, and wasn’t reliant upon the vertical sync, which requires you to have interrupts enabled to update the value.

I found one in the interface chip the TMS9901, which has a 14-bit counter value you can set. It decrements it at clock-cycle speed so it’s VERY fast. It requires a bit of setup in your program to initialize with a value, but after that it’s readily accessible. After I put this in, my random values are EXTREMELY random and satisfying.

* Somewhere at program start
* Set up 9901 counter
       CLR  R12             * CRU base of the TMS9901
       SBO  0               * Enter timer mode
       LI   R1,>000F        * Set counter to 15
       INCT R12             * Address of bit 1
       LDCR R1,14           * Load value
       DECT R12
       SBZ  0               * Exit clock mode, start decrementer
* Random function
RANDNO LI   R4,23729        * Load with 15-bit value
       MPY  @RSEED,R4       * Multiply by the random seed
       AI   R5,31871        * Add a 15-bit value to the lower word
       CLR  R12             * CRU base of the TMS9901
       SBO  0               * Enter timer mode
       STCR R0,15           * Read current value (plus mode bit)
       SRL  R0,1            * Get rid of mode bit
       SBZ  0               * Exit clock mode, decrementer continues
       SRC  R5,0            * Rotate seed based on clock value
       MOV  R5,@RSEED       * Copy back to RSEED
       RT

Alternatively, if I was coding in a system that lacked such a handy counter, I would try and create some kind of clock that is incremented by other parts of my program that I could use in it’s place. The most important aspect of it is that it can’t be in the random function itself!

One other option, that occurred to me afterwards, is that I could have opened the interrupts on the TI during the random function so that the clock value would get incremented. I’m reluctant to do this, though, because in many places I’m doing more during interrupts than just a clock, and they would steal resources away from map generation.

So for now, I seem to have enough randomness to use everywhere in the CRPG. 🙂