Fast and random MOB placement

[GroovyBee]

If you wanted to get a random X and a random Y coordinate to place a MOB on screen you could do something like this (I'm ignoring the need to add 8 to both X and Y to simplify things a little) :-

 

; Get a random X coordinate
   call GetRandom16     ; Yields a 16 bit random number in r0.
   andi #$FF, r0
   cmpi #160, r0
   blt @@SpriteIsOnScreenInX
   subi #160, r0
@@SpriteIsOnScreenInX:
   mvo r0, theSpriteX

; Get a random Y coordinate.
   call GetRandom16    ; Yields a 16 bit random number in r0.
   andi #$7F, r0
   cmpi #96, r0
   blt @@SpriteIsOnScreenInY
   subi #96, r0
@@SpriteIsOnScreenInY:
   mvo r0, theSpriteY

 

It might look fast and compact but the distribution of where MOBs are placed on screen becomes very skewed. A better approach is to use a modulo operation to get a number between 0 and 159 (inclusive) for the MOB's X position and between 0 and 95 (inclusive) for the MOB's Y position when supplied with a random number for each computation.

 

In C/C++ this would be :-

 

unsigned short int spriteX=GetRandom16()%160;
unsigned short int spriteY=GetRandom16()%96;
...

 

Modulo is an expensive operation on the CP1610 in terms of CPU cycles because its computed as the remainder of a division. If your game isn't very complex or only needs random placement at the start of the wave/level then limited use of 16 bit division is acceptable. However, for arcade style games or if you need a new random screen position in the main loop of the game another approach is required. So.... If we think of a division as being a multiplication by a reciprocal instead and we also allow for a small amount of tolerable error say less than 0.5% (it is a game after all and not a life critical application) things can be simplified into an unrolled sequence of shifts, adds and a subtract when compared against a full 16 bit division routine.

 

With that in mind modulo 160 becomes :-

; --------------------------------------------------------------------------
; FastModulo160
; --------------------------------------------------------------------------
; Compute modulo 160.
; --------------------------------------------------------------------------
; In :-
;    r0 - A 16 bit random number
;
; Out :-
;   r0 - Modulo 160 of the input e.g. "return(aVal%160);"
;
; Trashes :-
;   r0, r1, r2
; 
; --------------------------------------------------------------------------
FastModulo160: PROC
; Limit the input range.
   andi #$7FFF, r0

; If aVal in the range 0 to 159 that is already the result.
   cmpi #160, r0
   bnc @@ModuloInRange ; Unsigned 16bit comparison.

; Compute t=aVal*0.00622559.
   movr r0, r1
   slr r1, 1
   addr r0, r1
   slr r1, 2
   slr r1, 1
   addr r0, r1
   slr r1, 1
   addr r0, r1

; Compute v=t*160.
   slr r1, 2
   slr r1, 1
   andi #$FFE0, r1
   movr r1, r2
   sll r2, 2
   addr r2, r1

; Compute m=aVal-v;
   subr r1, r0

; Adjustment due to rounding errors.
   cmpi #160, r0
   bne @@ModuloInRange
   subi #160, r0
@@ModuloInRange:

   movr r5, pc

   ENDP

 

And module 96 becomes :-

; --------------------------------------------------------------------------
; FastModulo96
; --------------------------------------------------------------------------
; Compute modulo 96.
; --------------------------------------------------------------------------
; In :-
;    r0 - A 16 bit random number
;
; Out :-
;   r0 - Modulo 96 of the input e.g. "return(aVal%96);"
;
; Trashes :-
;   r0, r1, r2
; 
; --------------------------------------------------------------------------
FastModulo96: PROC
; Limit the input range.
   andi #$7FFF, r0

; If aVal in the range 0 to 95 that is already the result.
   cmpi #96, r0
   bnc @@ModuloInRange ; Unsigned 16bit comparison.

; Compute t=aVal*0.010376.
   movr r0, r1
   slr r1, 2
   addr r0, r1
   slr r1, 2
   addr r0, r1
   slr r1, 2
   addr r0, r1

; Compute v=t*96.
   slr r1, 2
   andi #$FFF8, r1
   movr r1, r2
   sll r2, 1
   addr r2, r1

; Compute m=aVal-v;
   subr r1, r0

; Adjustments due to rounding errors.
   cmpi #96*2, r0
   bge @@AdjusModulo2xOver
   cmpi #96, r0
   bge @@AdjusModulo1xOver

@@ModuloInRange:
   movr r5, pc

@@AdjusModulo2xOver:
   subi #96*2, r0
   movr r5, pc

@@AdjusModulo1xOver:
   subi #96, r0
   movr r5, pc

   ENDP

 

Both routines produce the expected modulo for input values between 0 and $7FFF. Input values above $7FFF will need different routines to avoid arithmetic overflow during computation.

[+DZ-Jay]

Great! Thanks for posting this, GroovyBee!

[+Gemintronic]

This stuff fascinates me endlessly! Too bad I don't have the chops to truly understand it

 

One idea I just had is:

 

1. Increment the random number by one

2. Shift to the left

3. Add the current joystick state

[Rev]

I dont know what weird language is being spoken in this thread, but carry on!

[catsfolly]

Why not generate an 8 bit random number, and then multiply it by 160( or 96 for y) and then divide by 256?

 

Dividing by 256 would take less code than multiplying by some odd fraction.

 

Wouldn't that spread out the distribution evenly?

 

Just a thought...

[GroovyBee]

Why not generate an 8 bit random number, and then multiply it by 160( or 96 for y) and then divide by 256?

 

That is another approach but I haven't tried it out myself. The only reason I like 16 bit random numbers is because I have a tried and tested 16bit PRNG.

[JamesD]

I'm not real familiar with the CP1610 but given the clocks / instruction, wouldn't it be a good idea to come up with a way to use tables?

Since target coordinates are under 256 there has to be a way to do this with some logic and a 256 byte (or less) table.

Any way to reduce the number of instructions. But then I guess ROM is limited as well.

[GroovyBee]

Like most things in games its always a trade off with speed and ROM size.