Jump to content





step 10 - "Random Numbers"

Posted by SpiceWare, in Collect 10 July 2014 · 1,431 views

And yes, those are air quotes  ;)
 
Inside the Atari (and computers in general), there's no such thing as a Random Number.  We can, however, simulate random numbers by using a Linear Feedback Shift Register.  The LFSR we're going to use was posted by batari, it's a rather slick bit of code in that it can be either an 8-bit or 16-bit LFSR.  
Random:
        lda Rand8
        lsr
 ifconst Rand16
        rol Rand16      ; this command is only used if Rand16 has been defined
 endif
        bcc noeor
        eor #$B4 
noeor 
        sta Rand8
 ifconst Rand16
        eor Rand16      ; this command is only used if Rand16 has been defined
 endif
        rts   
 
 
LFSR's create what appear to be a random sequence of numbers, but they're not.  A properly constructed 8-bit LFSR will start repeating values after 255 values have been obtained.    All you need to do in order to use the above routine as an 8-bit LFSR is allocate a variable called Rand8:
   ; used by Random for an 8 bit random number
Rand8:          ds 1    ; stored in $AB
 
 
A 16-bit LFSR will repeat after 65535 values have been obtained - that's a lot better than 255; however, it requires you to allocate another variable. With the Atari's limited 128 bytes of RAM, games often didn't have RAM to spare so they'd just use an 8-bit LFSR. Collect is a rather simple game though, so we have RAM to spare and will allocate the second variable Rand16.
; optionally define space for Rand16 for 16 bit random number
Rand16:         ds 1    ; stored in $AC    
 
 
The random number generator does have potential problem to be aware of - if you're using an 8-bit LFSR and Rand8 has the value of 0 then the LFSR will always return 0. Likewise for the 16-bit LFSR if both Rand8 and Rand16 are 0 it will always return 0. So we need to initialize the LFSR as CLEAN_START set all the RAM variables to 0.
InitSystem:
        CLEAN_START
...
    ; seed the random number generator
        lda INTIM       ; unknown value
        sta Rand8       ; use as seed
        eor #$FF        ; both seed values cannot be 0, so flip the bits 
        sta Rand16      ;   just in case INTIM was 0
 
 
One thing that helps when using an LFSR is to keep reading values at a regular rate, even if you don't need the value.  What this does is impose an element outside of the Atari's control - namely the time it takes the human to do things: hit the RESET switch to start a game, collect the next box, etc.  I've added this to VerticalBlank
VerticalBlank:
        jsr Random
...
 
 
Now that we have a function for random numbers we need to use them. First up is new routine that will randomly position any object. To use this function we just need to call it with X register holding a value that denotes which object to position. The values are the same ones used for the PosObject function, namely 0=player0, 1=player1, 2=missile0, 3=missile1 and 4=ball.
RandomLocation:
        jsr Random      ; get a random value between 0-255
        and #127        ; limit range to 0-127
        sta Temp        ; save it
        jsr Random      ; get a random value between 0-255
        and #15         ; limit range to 0-15
        clc             ; must clear carry for add
        adc Temp        ; add in random # from 0-127 for range of 0-142
        adc #5          ; add 5 for range of 5-147
        sta ObjectX,x   ; save the random X position
        
        jsr Random      ; get a random value between 0-255
        and #127        ; limit range to 0-127
        sta Temp        ; save it
        jsr Random      ; get a random value between 0-255
        and #15         ; limit range to 0-15
        clc             ; must clear carry for add
        adc Temp        ; add in random # from 0-127 for range of 0-142
        adc #26         ; add 26 for range of 26-168
        sta ObjectY,x   ; save the random Y position
        rts
 
 
I've renamed InitPos to NewGame and modified it to call RandomLocation.  It runs through a loop setting all the box objects.  Starting X value will be 1 or 2 based on the number of players in the selected game variation. 
NewGame:
...
    ; Randomly position the boxes for the new game.  Set X to 1 for a 1 player
    ; game or 2 for a 2 player game so that the appropriate objects will be
    ; randomly placed in the Arena.
        lda Variation
        and #1              ; value of 0=1 player game, 1=2 player game
        tax                 ; transfer to X
        inx                 ; start with 1 for a 1 player game, or 2 for a 2 player game
IPloop:
        jsr RandomLocation  ; randomly position object specified by X
        inx                 ; increase X for next object
        cpx #5              ; check if we hit 5
        bne IPloop          ; branch back if we haven't  
...
       rts
 
 
I also modified OverScan so that during a 1-player variation a collision between player0 and player1 will be detected.  If so, it calls another new function, CollectBox.
OverScan:
...
        bit Players     ; test how many players are in this game variation
        bmi RightPlayer ; test Right Player collisions if its a 2 player game
        bit CXPPMM      ; else see if left player collected box drawn by player1
        bpl OSwait      ; player0 did not collide wth player1
        ldx #1          ; which box was collected 
        jsr CollectBox  ; update score and reposition box
        jmp OSwait      ; 1 player game, so skip Right Player test
...
 
 
CollectBox will increase the player's score and call RandomLocation again to move it to a new position.  When CollectBox is called, Y must hold which player (0 for left, 1 for right) and X must hold the object that was collected.
CollectBox:
        SED                 ; SEt Decimal flag
        clc                 ; CLear Carry bit
        lda #1              ; 1 point per box
        adc Score,y         ; add to player's current score
        sta Score,y         ; and save it
        CLD                 ; CLear Decimal flag
        jsr RandomLocation  ; move box to new location
        rts
 
 
CollectBox means that the game is now playable for 1-player games! I managed to score 26 on game variation 1, how well can you do?
Attached Image
 
 
One thing you might notice in that screenshot is that the right player's score is not visible. Since we're done using the score for diagnostics, I've made a few changes to the digit graphics:
Attached Image

The first change is the left 0 image was blanked out - this provides leading zero suppression
Attached Image

The second change is the A image is now blanked out - NewGame uses this to blank out the right player's score in 1 player games.
NewGame:
...
    ; reset scores
        ldx #0
        stx Score
        bit Players         ; check # of players
        bpl BlankRightScore
        stx Score+1
        rts      
        
BlankRightScore:
        lda #$AA            ; AA defines a "space" character
        sta Score+1
        rts
 
 
Lastly the graphics for B thru F have been removed to save ROM space.


ROM
Attached File  collect_20140710.bin (2KB)
downloads: 103

Source
Attached File  Collect_20140710.zip (49.74KB)
downloads: 100




I did some tests using ENT, which showed a significant improvement in serial correlation if you rotate Rand8 and Rand16 in opposite directions (like you do). Which is no surprise because the return value XORs both values
(though, the higher the value for the XOR value, the less relevant this becomes; especially $eb and $fc are even slightly better without reversing the direction; I guess the number of high bits set plays a role here).

I also tested all possible values for XOR ($9c, $b4, $bd, $ca, $eb, $fc) and especially $9c gave good results for all tests (especially chi square).

  • Report
There's been some questions regarding the ifconst and endif in the Random subroutine.    Basically they're instructions that dasm uses to determine whether or not dasm "sees" the code appears between the two instructions.  
 
Basically ifconst is asking "does the value listed next exist in the program?".   If the answer is yes, then anything text between the ifconst and endif will be included in your program.  If the answer is no, then dasm will ignore any text between the ifconst and endif.
 
In the case of the Random subroutine dasm checks to see if Rand16 exists in the program.  As written our program has this in it:
 
   ; optionally define space for Rand16 for 16 bit random number
Rand16:         ds 1    ; stored in $AC    
 
So the answer to ifconst Rand16 is "yes, the value exists" and dasm will "see" the code like this:
Random:
        lda Rand8
        lsr
        rol Rand16      ; this command is only used if Rand16 has been defined
        bcc noeor
        eor #$B4 
noeor 
        sta Rand8
        eor Rand16      ; this command is only used if Rand16 has been defined
        rts    
 
If we deleted the following from our program:
   ; optionally define space for Rand16 for 16 bit random number
Rand16:         ds 1    ; stored in $AC  



the answer to ifconst Rand16 is "no, the value does not exist" so dasm will "see" the code like this:
Random:
        lda Rand8
        lsr
        bcc noeor
        eor #$B4 
noeor 
        sta Rand8
        rts   
  • Report

Hi!

 

Two things..  I'm amazed that the LSFR will always go through 255 or 65,535 cycles without repeating.  I would think that at least some seed values would cause that to change...

 

Secondly a question.  What is the reason the CollectBox routine switches to decimal mode?  Does it have to do with displaying the score?  I could see masking the left or right nibble to get the offset for 10s or 1s digit graphics.  Is that it?

  • Report

Howdy!

1 - the EOR value (also known as the tap) is what dictates the number of cycles without repeating. At Maximal Length LFSR Feedback Terms, you can find a list of values that give the maximum cycles before repeating.  For 8 bit values there are 16 different taps.  For 16 bit values there are 2048 (one of which is $B400, which is why this routine works for both 8 bit and 16 bit LFSR).

2 - Normally when you add $02 to $09 you'd get $0B. Decimal Mode changes it so that each nybble of the byte is treated like a decimal value of 0-9.  That makes it so the same addition of $02 and $09 results in $11 instead. We use it because displaying $0B as a human readable value of "11" is computationally expensive, while displaying $11 as "11" is not.

  • Report

Ahh..  I think I only had (have, really) a grasp of the two bit tap (The Wikipedia example).  So it looks like from the description you gave, once the LSFR is seeded, any seed will produce all sorts of cycle lengths all chained together one after another.  Correct?

  • Report

For any given tap, the sequence of numbers is always the same.  Slide 81 of the last presentation I gave shows the sequence returned if tap $B4 is used with a seed value of $84.  If you seed it with $7C (last value on first line), the values returned would begin with $3E (first value on second line).

 

If you change the code to use a different tap value, but still one from that list I linked to yesterday, you'll get a different sequence of 255 values. 

 

If you use a tap with a value other than those 16 you'll end up using one of multiple shorter sequences, which sequence you're in will depend upon the seed value.

  • Report

One note - a maxlen LFSR will have one "dead" value (typically 0, but might be another value) where the output value is the same as the input value.  It's therefore a good idea to either initialize the LFSR with a good seed or detect the "dead" value and handle it.

  • Report

Yep, covered that in paragraph 4, not counting the air quotes comment.  I didn't realize the dead value could be something other than 0, so that's good to know :thumbsup:

  • Report

Hmm, I doubt that there is any other dead value, especially for a maxlen LFSR.

 

I am sure that 0 is always the one and only dead value (at least for the code above), because there is no bit to trigger the EOR. And by definition a maxlen LFSR has 2^n-1 values. So there cannot be any other dead value.

  • Report

Search My Blog

Latest Visitors

0 user(s) viewing

0 members, 0 guests, 0 anonymous users