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. 🙂
