Sega Genesis Programming Part 7: NPC sprites



Formalities

I need to start by getting one thing out of the way.. previously the code to these Genesis programming experiments was released under a GPL license. I decided that's the wrong license for a Genesis game so all my original code is now under the MIT License. I'm not lawyer but I'm not even sure GPL can be used for a cartridge game running on proprietary hardware. For things like the Echo Sound Engine the original license text is retained as-is in the source files. I'm not interested in claiming someone else's work as my own.

I started using GPL for all my projects out of frustration with the game editing community. Plenty of folks released cool free game editors but kept the source under lock & key. I never understood why unless they're purposely trying to be unhelpful to others who are learning how to make tools. For a community built on modifying the works of others they were strangely resistant to having their own work modified. So I made my utilities, like Hapsby and Aridia GPL so anyone could re-use the source provided their project complied with GPL.

Releasing this code under the MIT License lets people use it more or less however they like. I don't think this code is especially great but it may be helpful to someone. If you do use some of my code I'd appreciate credit but that's it.

In the next iteration I'll probably get around to starting a Github project for this. There are a couple things I want to clean-up before then that I didn't get around to yet.

Fixing Collision Testing

I have a feeling that every one of these articles will start with me fixing horrible bugs from the previous one. Unfortunately I can't buy an O'Reilly book to learn this, it's all trial and error.

Not a real book

There are a couple good getting started tutorials on the internet but I'm getting past what they can help with. Even worse, I'm at the point where I Google various Genesis programming questions and just end-up finding my own page. I'm nowhere near an expert on the subject so that should give some indication of how scarce good information is. This leads me to believe that back in the day Genesis developers either had a lot of help from Sega or were way smarter than me (likely both). Also, I'm only able to spend a couple hours a week on this so I guess I shouldn't compare myself to someone working 40-60 hours a week on a game for months. Whatever, moving on..

One buggy bit I left around was a clipping issue in my collision detection routine. It was possible for the sprite to walk over/under things they shouldn't be able to.

Clipping problems

To troubleshoot this I borrowed a page from my Android SpriteWalker Demo and created some debug tiles. Doing this made it obvious what was going on..

Debugging clipping

The sprite's (x,y) position is the top left corner. My first pass at collision detection looked at the sprite's (x,y) and the 8x8 column next to it. This works fine if the sprite always moves 8 pixels, like in the Phantasy Star games, but breaks if the spite can move freely. Of course, this is probably something I also debugged in that aforementioned Android demo. So much for learning from past mistakes.

In the Phantasy Star games if the player just taps the controller their sprite will move 8 pixels, when holding a direction down the sprite always moves 8 pixels at a time and stops at some multiple of 8. This is the case for II and III at least, it's been a while since I played IV but I think the sprite motion is largely cloned from II. Using a fixed step makes collision detection a bit easier.

I may go and change things so the sprite is locked into a virtual grid to make the collision detection routine simpler. At this point I can't say if the method I wrote will be a performance issue until I have more stuff going on in the demo. When I think about a game like Herzog Zwei though, where the game is managing two independent scrolling sections and dozens of sprites, it makes me suspect it will take a lot of bad code to slow things down.

For now I'm going to keep plugging along with a system where the sprite can move fluidly around the map. This means updating the collision detection to check the left & right edges of the sprite when moving vertically, and the top & bottom edges when moving horizontally.

Sprite collision tests

Here's the updated collision detection code, you'll notice some code duplication and other badness that needs to be cleaned-up:

;-------------------------------------------------------------------------------

; TestSpriteCollision

; a6 = address of sprite info start

;-------------------------------------------------------------------------------

TestSpriteCollision:

 ;---------------------------------------------------------------------------

TestSpriteCollisionSetup:

 ;---------------------------------------------------------------------------

 ; the setup section performs the following:

 ; -clears the result from the previous subroutine call

 ; -copies the sprite x position to d6, adjusts for scroll

 ; -copies the sprite y position to d5, adjusts for scroll & collision point

 ; -copies the sprite direction to d7

 ;---------------------------------------------------------------------------

 move.w #$0000,(MEM_COLLISION_RESULT) ; clear result

 ; copy sprite x postion to d6, and adjust for scroll

 movea.l a6,a4   ; store address in a4 because it is manipulated

 adda.l #$2,a4   ; move to a4+2 -> SPRITE_X

 move.w (a4),d6   ; store sprite x in d6

 add.w (MEM_MAP_POSITION_X),d6 ; adjust for scroll

 ; copy sprite y postion to d5, and adjust for scroll & collision point

 adda.l #$2,a4   ; move to a4+4 -> SPRITE_Y

 move.w (a4),d5   ; copy the sprite's y-position to d5

 add.w #SPRITE_COLLISION_Y,d5 ; test against collision box

 add.w (MEM_MAP_POSITION_Y),d5 ; adjust for scroll

 ; copy sprite direction to d7

 adda.l #$4,a4   ; move to a4+8 -> SPRITE_DIRECTION

 move.w (a4),d7   ; store direction in d7

TestSpriteVCollision:

TestUpCollision:

 cmpi.w #DIRECTION_UP,d7 ; test if sprite is moving up

 bne.w TestDownCollision  ; branch if not

TestUpCollisionLeftEdgeSetup:

 move.w d5,d3 ; copy y position to d3 because it is manipulated

 sub.w #SPRITE_COLLISION_UP,d3 ; test up from sprite

 andi.b #%11111000,d3 ; clear bits 0-2 to round to nearest power of 8

 cmpi.w #MAP_MID_X,d6 ; is sprite on the left or right side of the screen?

 blt.s TestUpCollisionLeftEdge ; check if crossing the boundary

 add.w #$0004,d3  ; on the right side, use 2nd lword for the column

TestUpCollisionLeftEdge:

 lea  MEM_COLLISION_DATA,a3 ; move address of map data to a3

 adda.w d3,a3     ; move to row

 move.l (a3),MEM_COLLISION_MAP_ROW ; copy row data to memory

 move.w d6,d3 ; copy the sprite's x-position to d3

 and.w #$00FF,d3 ; remove all bits over 255

 divu.w #$08,d3 ; divide by 8 to get index in map data

 ; clear remainder from high word (easy68k.com/paulrsm/doc/trick68k.htm)

 swap d3  ; swap upper and lower words

 clr.w d3 ; clear the upper word

 swap d3  ; swap back

 move.l MEM_COLLISION_MAP_ROW,d7  ; move map data to d7

 btst.l d3,d7       ; test for collision

 beq.w TestUpCollisionRightEdgeSetup ; no collision, test other side

 move.w #$FFFF,(MEM_COLLISION_RESULT) ; collision is true, set result

 bra.w ExitTestSpriteCollision   ; exit

TestUpCollisionRightEdgeSetup:

 move.w d5,d3 ; copy y position to d3 because it is manipulated

 sub.w #SPRITE_COLLISION_UP,d3 ; test up from sprite

 andi.b #%11111000,d3 ; clear bits 0-2 to round to nearest power of 8

 add.w #DEFAULT_SPRITE_WIDTH,d6 ; move to right edge of sprite

 cmpi.w #MAP_MID_X,d6 ; is right half on right side of the screen?

 blt.s TestUpCollisionRightEdge ; check if crossing the boundary

 add.w #$0004,d3  ; on the right side, use 2nd lword for the column

TestUpCollisionRightEdge:

 lea  MEM_COLLISION_DATA,a3 ; move address of map data to a3

 adda.w d3,a3     ; move to row

 move.l (a3),MEM_COLLISION_MAP_ROW ; copy row data to memory

 move.w d6,d3 ; copy the sprite's x-position to d3

 and.w #$00FF,d3 ; remove all bits over 255

 divu.w #$08,d3 ; divide by 8 to get index in map data

 ; clear remainder from high word (easy68k.com/paulrsm/doc/trick68k.htm)

 swap d3  ; swap upper and lower words

 clr.w d3  ; clear the upper word

 swap d3  ; swap back

 move.w #$0000,(MEM_COLLISION_RESULT) ; clear result

 move.l MEM_COLLISION_MAP_ROW,d7  ; move map data to d7

 btst.l d3,d7       ; test for collision

 beq.w ExitTestSpriteCollision   ; no collision, exit

 move.w #$FFFF,(MEM_COLLISION_RESULT) ; collision is true, set result

 bra.w ExitTestSpriteCollision   ; exit

TestDownCollision:

 cmpi.w #DIRECTION_DOWN,d7   ; test if sprite is moving down

 bne.w TestSpriteHCollision ; branch if not

TestDownCollisionLeftEdgeSetup:

 move.w d5,d3 ; copy y position to d3 because it is manipulated

 add.w #SPRITE_COLLISION_DOWN,d3 ; test down from sprite

 andi.b #%11111000,d3 ; clear bits 0-2 to round to nearest power of 8

 cmpi.w #MAP_MID_X,d6 ; is sprite on the left or right side of the screen?

 blt.s TestDownCollisionLeftEdge ; check if crossing the boundary

 add.w #$0004,d3  ; on the right side, use 2nd lword for the column

TestDownCollisionLeftEdge:

 lea  MEM_COLLISION_DATA,a3 ; move address of map data to a3

 adda.w d3,a3     ; move to row

 move.l (a3),MEM_COLLISION_MAP_ROW ; copy row data to memory

 move.w d6,d3 ; copy the sprite's x-position to d3

 and.w #$00FF,d3 ; remove all bits over 255

 divu.w #$08,d3 ; divide by 8 to get index in map data

 ; clear remainder from high word (easy68k.com/paulrsm/doc/trick68k.htm)

 swap d3  ; swap upper and lower words

 clr.w d3  ; clear the upper word

 swap d3  ; swap back

 move.l MEM_COLLISION_MAP_ROW,d7  ; move map data to d7

 btst.l d3,d7       ; test for collision

 beq.w TestDownCollisionRightEdgeSetup ; no collision, test other side

 move.w #$FFFF,(MEM_COLLISION_RESULT) ; collision is true, set result

 bra.w ExitTestSpriteCollision   ; exit

TestDownCollisionRightEdgeSetup:

 move.w d5,d3 ; copy y position to d3 because it is manipulated

 add.w #SPRITE_COLLISION_DOWN,d3 ; test down from sprite

 andi.b #%11111000,d3 ; clear bits 0-2 to round to nearest power of 8

 add.w #DEFAULT_SPRITE_WIDTH,d6 ; move to right edge of sprite

 cmpi.w #MAP_MID_X,d6 ; is sprite on the left or right side of the screen?

 blt.s TestDownCollisionRightEdge ; check if crossing the boundary

 add.w #$0004,d3  ; on the right side, use 2nd lword for the column

TestDownCollisionRightEdge:

 lea  MEM_COLLISION_DATA,a3 ; move address of map data to a3

 adda.w d3,a3     ; move to row

 move.l (a3),MEM_COLLISION_MAP_ROW ; copy row data to memory

 move.w d6,d3 ; copy the sprite's x-position to d3

 and.w #$00FF,d3 ; remove all bits over 255

 divu.w #$08,d3 ; divide by 8 to get index in map data

 ; clear remainder from high word (easy68k.com/paulrsm/doc/trick68k.htm)

 swap d3  ; swap upper and lower words

 clr.w d3  ; clear the upper word

 swap d3  ; swap back

 move.w #$0000,(MEM_COLLISION_RESULT) ; clear result

 move.l MEM_COLLISION_MAP_ROW,d7  ; move map data to d7

 btst.l d3,d7       ; test for collision

 beq.w ExitTestSpriteCollision   ; no collision, exit

 move.w #$FFFF,(MEM_COLLISION_RESULT) ; collision is true, set result

 bra.w ExitTestSpriteCollision   ; exit

TestSpriteHCollision:

TestRightCollision:

 cmpi.w #DIRECTION_RIGHT,d7 ; test if sprite is moving right

 bne.w TestLeftCollision ; branch if not

TestRightSetup:

 ; d5 will have top edge, d3 will have bottom edge

 move.w d5,d3 ; copy y position to d3 to store bottom edge

 add.w #(DEFAULT_SPRITE_HEIGHT/2),d3 ; move d3 to the bottom edge

 andi.b #%11111000,d5 ; clear bits 0-2 to round to nearest power of 8

 andi.b #%11111000,d3 ; clear bits 0-2 to round to nearest power of 8

 add.w #SPRITE_COLLISION_RIGHT,d6 ; test right from sprite

 cmpi.w #MAP_MID_X,d6 ; is collision on left or right side of the screen?

 blt.s TestRightCollisionTopEdge ; left side, go directly to collision test

 add.w #$0004,d3  ; on the right side, use 2nd lword for the column

 add.w #$0004,d5  ; on the right side, use 2nd lword for the column

TestRightCollisionTopEdge:

 lea  MEM_COLLISION_DATA,a3 ; move address of map data to a3

 adda.w d5,a3 ; move to row & col of top edge

 move.l (a3),MEM_COLLISION_MAP_ROW ; copy row data to memory

 ;move.w d7,d3 ; copy the sprite's x-position to d3

 and.w #$00FF,d6 ; remove all bits over 255

 divu.w #$08,d6 ; divide by 8 to get index in map data

 ; clear remainder from high word

 ; credit to http://www.easy68k.com/paulrsm/doc/trick68k.htm for this trick

 swap d6  ; swap upper and lower words

 clr.w d6  ; clear the upper word

 swap d6  ; swap back

 move.w #$0000,(MEM_COLLISION_RESULT) ; clear result

 move.l MEM_COLLISION_MAP_ROW,d7  ; move map data to d7

 btst.l d6,d7       ; test for collision

 beq.w TestRightCollisionBottomEdge ; no collision, check lower half

 move.w #$FFFF,(MEM_COLLISION_RESULT) ; collision is true, set result

 bra.w ExitTestSpriteCollision   ; exit

TestRightCollisionBottomEdge:

 lea  MEM_COLLISION_DATA,a3 ; move address of map data to a3

 adda.w d3,a3 ; move to row & col of bottom edge

 move.l (a3),MEM_COLLISION_MAP_ROW ; copy row data to memory

 move.l MEM_COLLISION_MAP_ROW,d7  ; move map data to d7

 btst.l d6,d7       ; test for collision

 beq.w ExitTestSpriteCollision   ; no collision, exit

 move.w #$FFFF,(MEM_COLLISION_RESULT) ; collision is true, set result

 bra.w ExitTestSpriteCollision   ; exit

TestLeftCollision:

 cmpi.w #DIRECTION_LEFT,d7 ; test if sprite is moving Left

 bne.w TestLeftCollision ; branch if not

TestLeftCollisionSetup:

 ; d5 will have top edge, d3 will have bottom edge

 move.w d5,d3 ; copy y position to d3 to store bottom edge

 add.w #(DEFAULT_SPRITE_HEIGHT/2),d3 ; move d3 to the bottom edge

 andi.b #%11111000,d5 ; clear bits 0-2 to round to nearest power of 8

 andi.b #%11111000,d3 ; clear bits 0-2 to round to nearest power of 8

 sub.w #SPRITE_COLLISION_LEFT,d6 ; test left from sprite

 cmpi.w #MAP_MID_X,d6 ; is collision on left or right side of the screen?

 blt.s TestLeftCollisionTopEdge ; left side, go directly to collision test

 add.w #$0004,d3  ; on the right side, use 2nd lword for the column

 add.w #$0004,d5  ; on the right side, use 2nd lword for the column

TestLeftCollisionTopEdge:

 lea  MEM_COLLISION_DATA,a3 ; move address of map data to a3

 adda.w d5,a3 ; move to row & col of top edge

 move.l (a3),MEM_COLLISION_MAP_ROW ; copy row data to memory

 ;move.w d7,d3 ; copy the sprite's x-position to d3

 and.w #$00FF,d6 ; remove all bits over 255

 divu.w #$08,d6 ; divide by 8 to get index in map data

 ; clear remainder from high word

 ; credit to http://www.easy68k.com/paulrsm/doc/trick68k.htm for this trick

 swap d6  ; swap upper and lower words

 clr.w d6  ; clear the upper word

 swap d6  ; swap back

 move.w #$0000,(MEM_COLLISION_RESULT) ; clear result

 move.l MEM_COLLISION_MAP_ROW,d7  ; move map data to d7

 btst.l d6,d7       ; test for collision

 beq.w TestLeftCollisionBottomEdge ; no collision, check lower half

 move.w #$FFFF,(MEM_COLLISION_RESULT) ; collision is true, set result

 bra.w ExitTestSpriteCollision   ; exit

TestLeftCollisionBottomEdge:

 lea  MEM_COLLISION_DATA,a3 ; move address of map data to a3

 adda.w d3,a3 ; move to row & col of bottom edge

 move.l (a3),MEM_COLLISION_MAP_ROW ; copy row data to memory

 move.l MEM_COLLISION_MAP_ROW,d7  ; move map data to d7

 btst.l d6,d7       ; test for collision

 beq.w ExitTestSpriteCollision   ; no collision, exit

 move.w #$FFFF,(MEM_COLLISION_RESULT) ; collision is true, set result

ExitTestSpriteCollision:

 rts

Again, yes this can likely be optimized quite a bit. On the bright side that annoying clipping issue is now fixed:

Clipping fixed


Fixing Sprite Animation

The other thing annoying me was the sprite animation. My poor little sprite looked like he was having a seizure. There were two causes for this 1) I was updating the animation far too often 2) the animation frames didn't look like how an actual person walks.

Let's start with the second of these issues. When the sprite was moving it was cycling through two frames.

Two animation frames

This created an effect that looked like galloping for horizontal movement and doing the twist for vertical movement. To look more natural, the sprite should move through tiles in an order like this:

Four animation frames

Rather than duplicating tiles I changed the order they're displayed. In the previous demos the sprite standing still is using frame 0 with frames 1 & 2 alternating during movement. What I changed this to was 0,1,0,2. This work was done in the SetSpritePattern subroutine:

;-------------------------------------------------------------------------------

; SetSpritePattern

; sets the pattern for a sprite based on its direction and frame

; a6 = address of sprite info start

; a6 is not modified in this subroutine

; a5 is modified instead of a6 to avoid issues in MoveSprite

; d5 is used to store the sprite id and compute the address table value

; d6 is used to compute the sprite pattern

; d7 is used for various operations

;-------------------------------------------------------------------------------

SetSpritePattern:

 ;---------------------------------------------------------------------------

 ; a6 = SPRITE_ID

 ; a6 + 2 = SPRITE_X

 ; a6 + 4 = SPRITE_Y

 ; a6 + 6 = SPRITE_PATTERN_INDEX

 ; a6 + 8 = SPRITE_DIRECTION

 ; a6 + A = SPRITE_FRAME

 ; a6 + C = SPRITE_STEP_COUNTER

 ;---------------------------------------------------------------------------

 ; setup

 movea.l a6,a5 ; store address in a5 because it is manipulated

 move.w (a5),d5 ; copy sprite id to d5

 ; test if it's time to update the animation frame and if so update it

 adda.l #$C,a5 ; move up to a5+C -> SPRITE_STEP_COUNTER

 addq #$1,(a5) ; increment counter

 cmpi.w #SPRITE_ANIMATION_STEPS,(a5); is it time to update animation frame?

 ble.s DrawSprite ; animation hasn't changed, draw the sprite

IncrementSpriteFrame:

 move.w #$0000,(a5) ; reset SPRITE_STEP_COUNTER

 suba.l #$2,a5 ; move back to a5+A -> SPRITE_FRAME

 addq #$1,(a5) ; increment SPRITE_FRAME counter

 cmpi.w #SPRITE_FRAME_COUNT,(a5) ; do we need to loop back to the start?

 bls.w UpdateSpritePattern ; if not, go to animation

 ; reset the frame

 move.w #$0000,(a5) ; toggle between frames while sprite is moving

UpdateSpritePattern:

 movea.l a6,a5 ; store address in a5 because it is manipulated

 move.w (a5),d5 ; copy sprite id to d5

 mulu.w #$08,d5 ; multiply sprite ID by 8 to get sprite array offset

 ; change the sprite pattern

 addq #$4,d5 ; palette and pattern is at index 4 in the sprite definition

 swap d5 ; move to upper word

 add.l #VDP_VRAM_WRITE_SPRITE,d5 ; add to sprite table address

 ; set the pattern, pattern=(base pattern number)+(direction*24)+(frame*8)

 adda.l #$6,a5 ; move to a6+6 -> SPRITE_PATTERN_INDEX

 move.w (a5),d6 ; start with base pattern in d6

 adda.l #$2,a5 ; move to a6+8 -> SPRITE_DIRECTION

 move.w (a5),d7 ; copy direction to d7

 mulu.w #$18,d7 ; multiply direction * 24

 add.w d7,d6 ; add result to d1

 adda.l #$2,a5 ; move to a6+A -> SPRITE_FRAME

 move.w (a5),d7 ; copy frame to d7

 ;---------------------------------------------------------------------------

 ; cycle between the frames

 ; frame 0 = animation 0

 ; frame 1 = animation 1

 ; frame 2 = animation 0

 ; frame 3 = animation 2

 ;---------------------------------------------------------------------------

 btst.l #$0,d7 ; test if the frame is even (0 or 2)

 bne.s .1

 ; 0 or 2 logic

 moveq #$0,d7 ; zero out if 2, unnecessary 50% of the time of course

 bra.s .3 ; move to add step

.1: ; 1 or 3 logic

 btst.l #$1,d7 ; test if the frame is 1 or 3

 bne.s .2 ; frame number is 3

 ; 3 logic

 moveq #$8,d7 ; set animation frame to 1*8

 bra.s .3 ; move to add step

.2 ; 3 logic

 move.w #$0010,d7 ; set animation frame to 2*8

.3: ; add (frame*8) to pattern

 add.w d7,d6 ; add result to d6

 add.w #$2000,d6 ; TODO compute value using palette id

DrawSprite:

 move.l d5,(VDP_CONTROL) ; set write location in VDP

 move.w d6,(VDP_DATA) ; write the new pattern

ExitSetSpritePattern:

 rts

Fixing the animation timing took a couple of changes, the first was getting the movement frequency right. To prevent them from flying across the screen we don't want them to move on every frame (every vblank):

MEM_FRAME_COUNTER=$00FF0000A

[...]

SPRITE_MOVE_FREQUENCY=$0001 ; how many frames to wait between sprite moves

[...]

VBlank:

 addq #$1,(MEM_FRAME_COUNTER) ; increment frame counter

[...]

MainGameLoop:

 bsr.w WaitVBlank ; wait for vblank to complete

 ; test if it's time to move sprites

 cmpi.w #SPRITE_MOVE_FREQUENCY,(MEM_FRAME_COUNTER); is it time to move?

 bne.s MainGameLoopEnd ; exit if it's not time to move

 move.w #$0000,(MEM_FRAME_COUNTER) ; reset counter to 0

 bsr.w MovePlayer ; move the player sprite

[...]

The other part of this fix was in SetSpritePattern, the whole method is above so here's the relevant part:

SPRITE_ANIMATION_STEPS=$000A ; how many steps between animation frame changes

[...]

 cmpi.w #SPRITE_ANIMATION_STEPS,(a5); is it time to update animation frame?

 ble.s DrawSprite ; animation hasn't changed, draw the sprite

IncrementSpriteFrame:

 move.w #$0000,(a5) ; reset SPRITE_STEP_COUNTER

[...]

What this does is throttle how often the animation frame changes. The sprite will keep their current animation frame for SPRITE_ANIMATION_STEPS and then toggle to the next one.

The animation still isn't quite where I want it to be but it's enough of an improvement that I'm willing to move on. Maybe the next article will start with "OK, now I really think I fixed it for real this time, I'm super serious...."


NPC Sprites

Alright, it's finally time to add some new features.

Our store employee seems a little lonely, so I added a new sprite I'm tentatively calling "1989 mall shopper". Try to not feel too inspired by that name. She is also modeled after a Phantasy Star II sprite which I'll eventually have to replace with a different style.

Store with NPC

Adding our shopper required creating the tiles & a new sprite definition, both of which appear in a previous article (and will be in the source code at the bottom of the page).

An NPC can't just stand around, unless they're one of those types that's blocking an entrance or something. We need to make them pace around like any self-respecting NPC would.

To make things interesting let's have the NPC move at a pseudo-random interval. They could move on a fixed interval, like every 1-2 seconds, but by randomizing it things look a bit more natural. When more NPCs are added they also won't all move in unison either, which would look really weird. So we need a random number generator. The Sega Genesis doesn't have a built-in random number generator, we need to write one. I'm going to use the EOR of two counters for this. In previous articles I added a counter for each time the main loop executes and another for each vblank event. Under normal game play an EOR of the two would look pretty darn random. Someone running the game frame-by-frame in an emulator could easily generate any random of their choice.

;-------------------------------------------------------------------------------

; PseudoRandomWord

; not random since on an emulator it would be easy to get predicable results

; on normal game play the results should look pretty random

; d0 contains the result of the operation

; d1 is used to compute the pseudo random number

;-------------------------------------------------------------------------------

PseudoRandomWord:

 move.w MEM_VBLANK_COUNTER,d0 ; copy vblank counter to d0

 move.w MEM_MAINLOOP_COUNTER,d1 ; copy main loop counter to d1

 eor.w d1,d0 ; eor them and store the result in d0

 rts ; return

I briefly debated having them move in a random direction each time but decided against it because over time the NPC would get stuck in a corner. So instead they'll act like an average RPG NPC and walk around a central point on the map, never straying far from it. Instead I created a fixed pattern of 16 steps they'll repeat:

RandomNPCMovementStart:

 dc.w DIRECTION_RIGHT,DIRECTION_DOWN,DIRECTION_LEFT,DIRECTION_UP

 dc.w DIRECTION_DOWN,DIRECTION_RIGHT,DIRECTION_UP,DIRECTION_LEFT

 dc.w DIRECTION_UP,DIRECTION_RIGHT,DIRECTION_DOWN,DIRECTION_LEFT

 dc.w DIRECTION_LEFT,DIRECTION_DOWN,DIRECTION_RIGHT,DIRECTION_UP

RandomNPCMovementEnd:

Next we're going to add some variables to keep track of our NPC. The data structure used for the player sprite will be replicated along with two new additions (bolded):

MEM_NPC1_SPRITE_ID=$00FF0001E ; sprite table id of NPC1 sprite

MEM_NPC1_SPRITE_X=$00FF00020 ; virtual x position of NPC1 sprite

MEM_NPC1_SPRITE_Y=$00FF00022 ; virtual y position of NPC1 sprite

MEM_NPC1_SPRITE_PATTERN_INDEX=$00FF00024 ; index of pattern in VDP

MEM_NPC1_SPRITE_DIRECTION=$00FF00026 ; which direction NPC1 faces

MEM_NPC1_SPRITE_FRAME=$00FF00028 ; animation frame of NPC1 sprite

MEM_NPC1_SPRITE_STEP_COUNTER=$00FF0002A ; used to determine when to move

MEM_NPC1_MOVEMENT_COUNTER=$00FF0002C ; used to determine how far to move

MEM_NPC1_MOVEMENT_INDEX=$00FF0002E ; used to determine which direction to move

The purpose of MEM_NPC1_MOVEMENT_COUNTER is to store how many steps the NPC has left in their current movement. This will be reused later whenever I get around to scripted events, like an NPC entering the scene on a fixed path. MEM_NPC1_MOVEMENT_INDEX is a pointer to an address in RandomNPCMovementStart. Again, this will be useful for scripted events.

Now we need to put this all together in the main game loop:

MainGameLoop:

[...]

 ; test if it's time to move sprites

 cmpi.w #SPRITE_MOVE_FREQUENCY,(MEM_FRAME_COUNTER); is it time to move?

 bne.w MainGameLoopEnd ; exit if it's not time to move

MainGameLoopUpdateSprites:

 ; move the player sprite

 move.w #$0000,(MEM_FRAME_COUNTER) ; reset counter to 0

 bsr.w MovePlayer ; move the player sprite

 ; move NPCs

 cmpi.w #$0000,(MEM_NPC1_MOVEMENT_COUNTER) ; is the NPC moving?

 bne .2 ; if MEM_NPC1_MOVEMENT_COUNTER > 0 then the sprite is moving

 ; test if it's time for them to move again

 bsr.w PseudoRandomWord ; store a random number in d0

 and.w #SPRITE_NPC1_MOVE_TEST,d0 ; and d0 against SPRITE_NPC1_MOVE_TEST

 cmpi.w #SPRITE_NPC1_MOVE_TEST,d0 ; test if multiple

 bne.s MainGameLoopSetScroll ; not time to move, jump to next section

 move.w #SPRITE_ANIMATION_STEPS,(MEM_NPC1_MOVEMENT_COUNTER) ; reset counter

 ; set the direction

 addq #$2,MEM_NPC1_MOVEMENT_INDEX ; increment index of sprite movement

 cmpi.w #$20,MEM_NPC1_MOVEMENT_INDEX ; are we at the end of the array?

 blt.s .1 ; not at the end of the array

 move.w #$0000,MEM_NPC1_MOVEMENT_INDEX ; reset to zero

.1

 lea RandomNPCMovementStart,a6

 adda (MEM_NPC1_MOVEMENT_INDEX),a6

 move.w (a6),(MEM_NPC1_SPRITE_DIRECTION)

.2 ; decrement NPC movement counter and test if they should stop moving

 subq #$0001,(MEM_NPC1_MOVEMENT_COUNTER) ; decrement counter

 bne .3 ; if MEM_NPC1_MOVEMENT_COUNTER=0 now then we need to stop the sprite

 lea (MEM_NPC1_SPRITE_ID),a6 ; setup call to StopSprite

 bsr.w StopSprite ; stop the sprite

 bra.s MainGameLoopSetScroll ; done updating sprites

.3 ; move the NPC sprite

 lea (MEM_NPC1_SPRITE_ID),a6 ; setup call to MoveSprite

 bsr.w MoveSprite ; branch to move MoveSprite

MainGameLoopSetScroll:

[...]

MainGameLoopEnd:

 bra.w MainGameLoop ; return to start of game loop

This is all great except for one glaring problem, complete lack of sprite collision detection.

No sprite collision detection

Sprite Collision Detection

The Genesis contains hardware sprite collision detection. That's a great feature but it's also an after-the-fact notification. In the typical overhead RPG-ish game the characters can walk up to other sprites but not collide with them.

The approach I'm going to try will be updating the collision data when a sprite moves. This means I won't have to rewrite the existing collision detection at least. This first step is copying the collision data into RAM, previously it was accessed from the ROM. This is something that's probably a good idea anyway for performance reasons:

MEM_COLLISION_DATA=$00FF0003C ; collision data for the current map

[...]

LoadMapCollisionData:

 lea MapStoreCollision,a0 ; store address of collision data

 lea MEM_COLLISION_DATA,a1 ; store destination memory location

 move.w #$7F,d0 ; 128 longs of collision data

LoadMapCollisionLoop:

 move.l (a0)+,(a1)+

 dbra d0,LoadMapCollisionLoop

As previously noted, the sprites in this demo can move freely rather than from one fixed square to another. I might regret this decision later but for now this is the type of movement I'd prefer to have. The underlying collision map is a 512x512 grid composed of 8x8 tiles. As the sprite moves it needs to block & clear collision data. If the collision box is the lower half of the sprite then the area the sprite is blocking looks like:

Sprite collision tiles

The blue boxes are the top half of the sprite, the red is the lower half, and the darker gray represent the blocked map data.

To make this work, we first need a routine to determine which cells of collision data need to be updated. Let's do that by storing of the four corners that the sprite collision zone occupies:

MEM_ACTIVE_SPRITE_LEFT_COLUMN=$00FF00030 ; left column of active sprite

MEM_ACTIVE_SPRITE_HIGH_LEFT=$00FF00032 ; high left row of active sprite

MEM_ACTIVE_SPRITE_LOW_LEFT=$00FF00034 ; low left row of active sprite

MEM_ACTIVE_SPRITE_RIGHT_COLUMN=$00FF00036 ; right column of active sprite

MEM_ACTIVE_SPRITE_HIGH_RIGHT=$00FF00038 ; high right row of active sprite

MEM_ACTIVE_SPRITE_LOW_RIGHT=$00FF0003A ; low right row of active sprite

[...]

MAP_MID_X=$100

[...]

;-------------------------------------------------------------------------------

; SetActiveSpriteMapRowCol

; sets values for:

; MEM_ACTIVE_SPRITE_LEFT_COLUMN

; MEM_ACTIVE_SPRITE_RIGHT_COLUMN

; MEM_ACTIVE_SPRITE_HIGH_LEFT

; MEM_ACTIVE_SPRITE_HIGH_RIGHT

; MEM_ACTIVE_SPRITE_LOW_LEFT

; MEM_ACTIVE_SPRITE_LOW_RIGHT

; a6 = address of sprite info start

; d6 is used to store x values

; d5 is used to store y values

; d7 is used for all other operations

;-------------------------------------------------------------------------------

SetActiveSpriteMapRowCol:

 ;---------------------------------------------------------------------------

 ; a6 = SPRITE_ID

 ; a6 + 2 = SPRITE_X

 ; a6 + 4 = SPRITE_Y

 ; a6 + 6 = SPRITE_PATTERN_INDEX

 ; a6 + 8 = SPRITE_DIRECTION

 ; a6 + A = SPRITE_FRAME

 ; a6 + C = SPRITE_STEP_COUNTER

 ;---------------------------------------------------------------------------

SetActiveSpriteLeftCol:

 ; copy sprite x postion to d7 and adjust for scroll

 clr.l d7

 clr.l d6

 adda.l #$2,a6 ; move to a6+2 -> SPRITE_X

 move.w (a6),d7 ; store sprite x in d7

 add.w (MEM_MAP_POSITION_X),d7 ; adjust for scroll

 move.w d7,d6 ; copy to d6 for later use

 and.w #$00FF,d7 ; remove all bits over 255

 divu.w #$08,d7 ; divide by 8 to get index in map data

 ; clear remainder from high word (easy68k.com/paulrsm/doc/trick68k.htm)

 swap d7  ; swap upper and lower words

 clr.w d7 ; clear the upper word

 swap d7  ; swap back

 move.w d7,(MEM_ACTIVE_SPRITE_LEFT_COLUMN) ; copy left column value

SetActiveSpriteLeftHighLow:

 ; copy sprite y postion to d7 and adjust for scroll

 adda.l #$2,a6 ; move to a6+4 -> SPRITE_Y

 move.w (a6),d7 ; store sprite y in d7

 add.w (MEM_MAP_POSITION_Y),d7 ; adjust for scroll

 add.w #$18,d7 ; top edge of lower 1/4

 

 move.w d7,d5 ; copy the adjusted y value

 add.w #$08,d5 ; move d5 to bottom edge of lower 1/4

 ; map the sprite y position to a column

 andi.b #%11111000,d7 ; clear bits 0-2 to round to nearest power of 8

 andi.b #%11111000,d5 ; clear bits 0-2 to round to nearest power of 8

 cmpi.w #MAP_MID_X,d6 ; is column on the left or right side of the screen?

 blt.s .2 ; branch if on left side

 add.w #$0004,d7 ; on the right side, use 2nd lword for the column

 add.w #$0004,d5 ; on the right side, use 2nd lword for the column

.2

 move.w d7,(MEM_ACTIVE_SPRITE_HIGH_LEFT) ; copy high left value

 move.w d5,(MEM_ACTIVE_SPRITE_LOW_LEFT) ; copy low left value

SetActiveSpriteRightCol:

 add.w #$10,d6 ; move d6 to right side of sprite

 move.w d6,d7 ; store sprite x in d7

 and.w #$00FF,d7 ; remove all bits over 255

 divu.w #$08,d7 ; divide by 8 to get index in map data

 ; clear remainder from high word (easy68k.com/paulrsm/doc/trick68k.htm)

 swap d7  ; swap upper and lower words

 clr.w d7 ; clear the upper word

 swap d7  ; swap back

 move.w d7,(MEM_ACTIVE_SPRITE_RIGHT_COLUMN) ; copy left column value

SetActiveSpriteRightHighLow:

 ; copy sprite y postion to d7 and adjust for scroll

 move.w (a6),d7 ; store sprite y in d7

 add.w (MEM_MAP_POSITION_Y),d7 ; adjust for scroll

 add.w #$18,d7 ; top edge of lower 1/4

 move.w d7,d5 ; copy the adjusted y value

 add.w #$08,d5 ; move d5 to bottom edge of lower 1/4

 ; map the sprite y position to a column

 andi.b #%11111000,d7 ; clear bits 0-2 to round to nearest power of 8

 andi.b #%11111000,d5 ; clear bits 0-2 to round to nearest power of 8

 cmpi.w #MAP_MID_X,d6 ; is column on the left or right side of the screen?

 blt.s .4 ; branch if on left side

 add.w #$0004,d7 ; on the right side, use 2nd lword for the column

 add.w #$0004,d5 ; on the right side, use 2nd lword for the column

.4

 move.w d7,(MEM_ACTIVE_SPRITE_HIGH_RIGHT) ; copy high left value

 move.w d5,(MEM_ACTIVE_SPRITE_LOW_RIGHT) ; copy low left value

 suba.l #$04,a6 ; move a6 back to SPRITE_ID

 rts

Now we need a couple routines to block & clear map data. These will be called from MoveSprite and StopSprite.

;-------------------------------------------------------------------------------

; Blocks the map data where a sprite is located

; a6 = address of sprite info start

; a3 is modified used to reference collision data

; d6 is modified to temporarily store sprite row & column

; d7 is modified to store & update map collision data

;-------------------------------------------------------------------------------

BlockSpriteMapPosition:

 ;---------------------------------------------------------------------------

 ; a6 = SPRITE_ID

 ; a6 + 2 = SPRITE_X

 ; a6 + 4 = SPRITE_Y

 ; a6 + 6 = SPRITE_PATTERN_INDEX

 ; a6 + 8 = SPRITE_DIRECTION

 ; a6 + A = SPRITE_FRAME

 ; a6 + C = SPRITE_STEP_COUNTER

 ;---------------------------------------------------------------------------

 bsr.w SetActiveSpriteMapRowCol ; set the active map position

 ; left side

 move.w (MEM_ACTIVE_SPRITE_LEFT_COLUMN),d6 ; copy left column to d6

 lea  MEM_COLLISION_DATA,a3 ; move start address of map data to a3

 adda.w (MEM_ACTIVE_SPRITE_HIGH_LEFT),a3 ; move to row

 move.l (a3),d7 ; copy row data to memory

 bset.l d6,d7 ; set map data to blocked

 move.l d7,(a3) ; save the map data back

 lea  MEM_COLLISION_DATA,a3 ; move start address of map data to a3

 adda.w (MEM_ACTIVE_SPRITE_LOW_LEFT),a3 ; move to row

 move.l (a3),d7 ; copy row data to memory

 bset.l d6,d7 ; set map data to blocked

 move.l d7,(a3) ; save the map data back

 ; right side

 move.w (MEM_ACTIVE_SPRITE_RIGHT_COLUMN),d6 ; copy left column to d6

 lea  MEM_COLLISION_DATA,a3 ; move start address of map data to a3

 adda.w (MEM_ACTIVE_SPRITE_HIGH_RIGHT),a3 ; move to row

 move.l (a3),d7 ; copy row data to memory

 bset.l d6,d7 ; set map data to blocked

 move.l d7,(a3) ; save the map data back

 lea  MEM_COLLISION_DATA,a3 ; move start address of map data to a3

 adda.w (MEM_ACTIVE_SPRITE_LOW_RIGHT),a3 ; move to row

 move.l (a3),d7 ; copy row data to memory

 bset.l d6,d7 ; set map data to blocked

 move.l d7,(a3) ; save the map data back

 rts

 

;-------------------------------------------------------------------------------

; Clears the map data where a sprite is located

; a6 = address of sprite info start

; a3 is used to reference collision data

; d6 is modified to temporarily store sprite row & column

; d7 is modified to store & update map collision data

;-------------------------------------------------------------------------------

ClearSpriteMapPosition:

 ;---------------------------------------------------------------------------

 ; a6 = SPRITE_ID

 ; a6 + 2 = SPRITE_X

 ; a6 + 4 = SPRITE_Y

 ; a6 + 6 = SPRITE_PATTERN_INDEX

 ; a6 + 8 = SPRITE_DIRECTION

 ; a6 + A = SPRITE_FRAME

 ; a6 + C = SPRITE_STEP_COUNTER

 ;---------------------------------------------------------------------------

 bsr.w SetActiveSpriteMapRowCol ; set the active map position

 ; left side

 move.w (MEM_ACTIVE_SPRITE_LEFT_COLUMN),d6 ; copy left column to d6

 lea  MEM_COLLISION_DATA,a3 ; move start address of map data to a3

 adda.w (MEM_ACTIVE_SPRITE_HIGH_LEFT),a3 ; move to row

 move.l (a3),d7 ; copy row data to memory

 bclr.l d6,d7 ; set map data back to zero

 move.l d7,(a3) ; save the map data back

 lea  MEM_COLLISION_DATA,a3 ; move start address of map data to a3

 adda.w (MEM_ACTIVE_SPRITE_LOW_LEFT),a3 ; move to row

 move.l (a3),d7 ; copy row data to memory

 bclr.l d6,d7 ; set map data back to zero

 move.l d7,(a3) ; save the map data back

 ; right side

 move.w (MEM_ACTIVE_SPRITE_RIGHT_COLUMN),d6 ; copy left column to d6

 lea  MEM_COLLISION_DATA,a3 ; move start address of map data to a3

 adda.w (MEM_ACTIVE_SPRITE_HIGH_RIGHT),a3 ; move to row

 move.l (a3),d7 ; copy row data to memory

 bclr.l d6,d7 ; set map data back to zero

 move.l d7,(a3) ; save the map data back

 lea  MEM_COLLISION_DATA,a3 ; move start address of map data to a3

 adda.w (MEM_ACTIVE_SPRITE_LOW_RIGHT),a3 ; move to row

 move.l (a3),d7 ; copy row data to memory

 bclr.l d6,d7 ; set map data back to zero

 move.l d7,(a3) ; save the map data back

 rts

Now the sprites can't run into each other which is nice.

Sprite collision

This all works well on the left, right, and lower sides. There's still something that's not quite right though...

Still Funky

The sprite overlap isn't working as I'd like. The player sprite is always super-imposed over the NPC sprite. That looks fine when the player walks across the lower half of the NPC but is awful when the walk across the top half:

Sprite overlap

The desired effect can best be seen in Phantasy Star II:

Desired sprite overlap effect

At first I thought this might have been accomplished by making each character two sprites - one occupying the high plane and one occupying the low plane. A quick look at a layer debugger immediately disproved this idea. Rather than debug this and not post anything for another month I'm doing to stop here and save this for next time...

Download

Download the latest source code on GitHub




Tweet