IGNORED

# Fast and random MOB placement

## Recommended Posts

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
slr r1, 2
slr r1, 1
slr r1, 1

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

; 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
slr r1, 2
slr r1, 2

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

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

; Adjustments due to rounding errors.
cmpi #96*2, r0
cmpi #96, r0

@@ModuloInRange:
movr r5, pc

subi #96*2, r0
movr r5, pc

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.

##### Share on other sites

Great! Thanks for posting this, GroovyBee!

##### Share on other sites

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

##### Share on other sites

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

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

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.

##### Share on other sites

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

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.