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

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

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

@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:

       SRL  R0,1
       JNC  NOCARR
       XOR  @MASK,R0

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

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

This entry was posted in Assembly, CRPG, Design, TI-99/4a. Bookmark the permalink.

7 Responses to Random Thoughts

  1. Ethan Roberts says:

    Wow, when I was doing QBasic, I always just used Randomize Timer, and never thought about it

  2. Brian (aka arthurdawg) says:

    Same here… it’s been a billion years since, but I recall struggling with not so random numbers in GW-BASIC on my old Tandy 1000. Or possibly with Apple BASIC on a class program we wrote back in the 80s on the IIe computers at school. It’s been a while! We thought we could just use the randomize function, but we generated the same random number sequence every time. I’m a bit foggy but I think we randomized a clock on the IIe to get closer to randomness.

    Who’d a thunk randomness would be so random?

  3. adamantyr says:

    The Apple II random numbers were VERY predictable. I would play lemonade stand and I knew that the first day of clouds it ALWAYS rained, so I never spent any money on supplies that day.

    In that case though, I think they deliberately seeded the game with a fixed value. The game’s progression had several days of “normal” weather, then a hot spell, normal weather, THEN a cloudy day with rain. A pretty good pattern for a little kid. If it was completely random, you’d have no idea what to expect and it may be less fun.

  4. Ethan Roberts says:

    Adamantyr, do you ever go to the Portland Retro Game Expo? It is in October, and it is pretty neat.

  5. Alex Johnson says:

    Microsoft used a simple multiply and add approach in BASIC. On C64 when programming in assembly it was often suggested to read the CIA fast timer that counted every clock at the CPU frequency, or to do a multiply/add approach and exclusive-OR with this timer’s contents. Another solution I heard was to program the SID sound chip to generate very high frequency noise and read the waveform.

    Atari 2600 games typically just used a shift register updated during VBLANK since time was so critical in that environment.

    • adamantyr says:

      The CIA fast timer sounds very similar to the 9901 timer, which counts the clock frequency. With that and a shift you can basically make a near perfect “true” random number generator that is sustainable with a number of operations.

Leave a Reply

Your email address will not be published. Required fields are marked *