Making a random number in Assembly

[Kakemoms]

For example in 0.5K or 1K minigames and such, sometimes all you need is the smallest random number routine. Here's a handy one:

Code: Select all

Random  subroutine
        lda     #$01 <------+
        asl                 |
        bcc     .1          |
        eor     #$4d        |
.1                          |
        sta     Random+1 ---+
        eor     $9124
        rts

Too random? To get a predetermined sequence of 255 values in range of $01-$ff instead, just remove eor $9124. You can then initialize the random seed at Random+1. Seed $00 hangs the PRNG and also without eor $9124 the routine never outputs a zero.

Well, at "bcc" the carry is always going to be clear (due to asl which puts "bit7" of $01 into carry), so you could just remove the eor #$4d, meaning this routine is always going to put 1 into Random+1.

Look closer.

Ok, that makes more sense

[Kweepa]

These threads have some relevant info:
http://sleepingelephant.com/ipw-web/bul ... f=2&t=2304
http://sleepingelephant.com/ipw-web/bul ... f=2&t=2348

[Kakemoms]

Interesting. Also see the second entry of this tread which discusses the idea of having random game elements.

Its like when someone sets a new world record in Super Mario Brothers.. there are very few instances left to random behaviours.

[MrSterlingBS]

Hello,

For practice purposes, I programmed Mike's Madness demo in assembler.

I use the following code as a random generator:

Code: Select all

randomgen_y:
        LDA zero
        ADC seed_y
        ADC $9128	; or $9004 for x
        STA seed_y
        LDA seed_y
        cmp #192		; #168
        BCS randomgen_y
        INC randomgen_y+1
        RTS

An 8k+ expansion RAM is needed.
You can clear the screen with the ENTER key.

I would be very grateful for suggestions, improvements and optimizations.

What I haven't fully understood yet is how to block interrupts. How are the command SEI and these related?

Code: Select all

							; disable interrupt
		SEI
		
		lda #$7f
		sta $912e       ; Disable and acknowledge interrupts.
		sta $912d
		sta $911e       ; Disable restore key NMIs.
		sta $911d       ; Disable restore key NMIs.

And is it necessary to block $911E and $911D?
Or are these mirror images of $912E and $912D?

[Mike]

I use the following code as a random generator: [...] I would be very grateful for suggestions, improvements and optimizations.

As I wrote earlier in the thread, and to quote Knuth once again: "Random numbers should not be generated with a method chosen at random." - your timer based "RNG" is as good or bad as any other timer based method. Generally, timer based methods suffer from correlations with the execution time of the client program (i.e. the elapsed time between calls of the RNG).

I implemented the QDRand generator from Numerical Recipies and used the Madness program to demonstrate it. QDRand is a LCG (linear congruential generator) which employs a 32-bit seed. It has the properties as defined and expected from that class of RNGs.

Timer based methods, together with human interaction, are however a good method to obtain a seed. Any further random number generation can use that seed, but should otherwise be completely deterministic.

For practice purposes, I programmed Mike's Madness demo in assembler.

For what matters, the Madness demo already is completely implemented in assembler. There is a little bit of set-up using MINIGRAFIK (to init the hires screen) and the main loop is POKEd into memory from BASIC - but once SYS15360 is executed, only machine code (RNG + fast line routine) runs.

So, it is not quite clear for me what this bought you. As I said, the relevant parts had already been written in assembler.

What I haven't fully understood yet is how to block interrupts. How are the command SEI and these related?

SEI/CLI specifically inhibit/allow IRQ processing of the CPU. Any raised NMI is still honoured by the CPU.

The accesses to the VIA registers explicitly refer to the VIAs as interrupt sources. There are several of them, and the code snippet you cite here disables and acknowledges all IRQ and NMI sources of the VIAs. Please refer to the VIA data sheet for further details (and actually, I think the aspects of interrupt processing also are not relevant in the context here).

[chysn]

Timer based methods, together with human interaction, are however a good method to obtain a seed. Any further random number generation can use that seed, but should otherwise be completely deterministic.

One thing I learned the hard way was this: I had a tape-based game seed a random number generator with the timer. When I converted this game to cartridge, the levels became deterministic, because unlike LOAD/RUN from tape, a cartridge always starts up in the same way every time. So I moved back the seed to the first human interaction of starting the game.

Generally, timer based methods suffer from correlations with the execution time of the client program

This has been my experience. Tying pseudorandom numbers too closely to any cycle-based timer is problematic, because routines will tend to be executed at consistent intervals, and take a consistent number of cycles. So you will see patterns that are hard to account for unless you realize that. I suspect that may be an issue with your randomgen_y routine above, MrSterlingBS. I tried something like this to generate mazes once, and I was dismayed at the result.

A shift register provides a sort of extra layer between the timer-based seed and the results. Here's the random number generator that I use (I add and remove the RandX entry points as needed). The entry point determines the bit length of the result. RNDNUM is a temporary storage location for the result, and P_RAND is the 16-bit seed (see below):

Code: Select all

; Pseudo Random
Rand3:      lda #%01000000      ; 2-bit entry point
            .byte $3c           ; Skip word (SKW)
Rand31:     lda #%00001000      ; 5-bit entry point
            .byte $3c           ; Skip word (SKW)
Rand255:    lda #%00000001      ; 8-bit entry point
PRand:      sta RNDNUM
-loop:      lsr P_RAND
            ror P_RAND+1
            bcc shift_rnd
            lda P_RAND
            eor #$aa
            sta P_RAND
            lda P_RAND+1
            eor #$2b
            sta P_RAND+1
shift_rnd:  rol RNDNUM
            bcc loop
            lda RNDNUM
            rts

I generate the seed as follows, when the user does something like start the game. The key here is that both seed values are non-zero, hence the ORAs.

Code: Select all

            lda TIME_L          ; Seed random number generator ($a2)
            ora #$01            ; ,,
            sta P_RAND          ; ,,
            lda VIATIME         ; ,, ($9114)
            ora #$80            ; ,,
            sta P_RAND+1        ; ,,

Over the long term, the mean stays very close to 1/2 of the max, and the distribution is good. It's a pithy routine. I probably got it or something like it from this forum somewhere*; as they say, it's good enough for rock and roll**!

________________
* It should come as little surprise that it is based on the routine Mike presented here https://sleepingelephant.com/ipw-web/bu ... f=2&t=2304

** By "rock and roll" I mean "arcade games."