Sega Genesis Programming Part 12: Scenes and NPCs

Future plans

I'm at a bit of a crossroad. I'd really like to start adding new areas for our little sprite to explore but I also want to get all the basic game mechanics worked out. After a few seconds of thought it was obvious to me that the latter is the right priority. If I start adding new scenes I'll almost certainly have to rework them once I figure out how to handle NPCs and events. The more scenes I add the more re-work I'll have later.

So for the next few iterations I'll be working on completing a one-room demo. This will be a fully-functional, albeit extremely short, game. It will also serve as the "tutorial level" assuming I have enough patience to keep working on this.

The plot of this demo is pretty simple: it's closing time at the mall and you have one customer who won't leave. You can't close your store until he's gone. Meanwhile your older sister, who's stuck giving you a ride home, is growing impatient. You have to figure out how to get this customer out of your store.

Specifically, you have to get this guy out of the store:

New NPC sprite

He's not based off anyone in particular, just a generic 80s business casual guy who's feeling grumpy.

The things that need to be built for this to happen are:

1) Dialog between characters - meaning an NPC says something to you and you respond. Maybe you respond with more dialog, maybe you give them an item. That leads to...

2) Inventory management - along with basic stuff like taking and giving items.

3) Game event tracking - we need a way to say "if [X] happened and you talk to character [Y] then do [Z]", I'll probably over-complicate this.

4) Scripted sprite movements - if the ultimate goal is to get a customer to leave a store then there needs to be an animation where they walk away.

5) Adding & removing NPCs from the current scene - the one NPC is hard-coded, there needs to be a way to move NPCs in and out of scenes.

6) To make this look like a real demo I should really create a title screen and ending message.

7) Dozens of things I didn't think of that will all be painful to work out.

You might notice there's nothing called "battles", that's because I'm unlikely to add them. If I end up building an entire story, and that only takes 5 minutes to play through, then perhaps I'll reconsider. Right now it's something that would chew up a lot of time.

Speaking of time, one downside to building a one-room demo is it might be a year (or more) before there are any new locations. As I joked somewhere else in this series, at least I don't have to rush to get this out before Christmas 1994.

Anyway, I'm trying to not make this a too ambitious project. My last attempt at something like this was roughly a decade ago and it failed for a number of reasons. Now with a different perspective I realize a major reason was trying to build out a massive framework first, rather than a series of small incremental working components. I suffered from a defect a lot of programmers have in which they try to solve general problems before specific ones. You end up with bloated "frameworks" that aren't very good at satisfying any real-world use case. I outgrew this way of thinking and now follow a process more like:

1) What is the real problem that needs to be solved / thing that needs to be built?

2) Write the minimal amount of code needed to solve the problem.

3) Test, fix edge cases and wacky bugs.

4) Refactor into something more modular when needed.

This approach so far has been working out OK in this crazy experiment. In my old way of thinking I'd still be writing a massive event processor & game state manager without anything to show for it. Sure, I don't have an awful lot to show right now but at least I have something.

I think the first item from this list I'll tackle is #5 - "Adding & removing NPCs from the current scene". That's because, well, we need to add another NPC to the scene. Along the way I'm certain to encounter bits of #7 too.

General NPC handling

With the super-sophisticated process I outlined there are a lot of items stuck in step 3. One of them is managing NPCs. Let's kick-off this round with updating the main game loop to handle an arbitrary number of NPCs.

There was already a data structure for the first NPC but there are a few additions needed:

MEM_NPC0_SPRITE_ID=$FFFF003C ; sprite table id of NPC0 sprite
MEM_NPC0_SPRITE_X=$FFFF003E ; virtual x position of NPC0 sprite
MEM_NPC0_SPRITE_Y=$FFFF0040 ; virtual y position of NPC0 sprite
MEM_NPC0_SPRITE_PATTERN_INDEX=$FFFF0042 ; index of pattern in VDP
MEM_NPC0_SPRITE_DIRECTION=$FFFF0044 ; which direction NPC0 faces
MEM_NPC0_SPRITE_FRAME=$FFFF0046 ; animation frame of NPC0 sprite
MEM_NPC0_SPRITE_STEP_COUNTER=$FFFF0048 ; used to determine when to move
MEM_NPC0_MOVEMENT_COUNTER=$FFFF004A ; used to determine how far to move
MEM_NPC0_MOVE_FREQUENCY=$FFFF004C ; how often to move
MEM_NPC0_MOVE_PATTERN=$FFFF004E ; movement pattern
MEM_NPC0_MOVE_PATTERN_LENGTH=$FFFF0052 ; length of movement pattern
MEM_NPC0_MOVE_INDEX=$FFFF0054 ; where the sprite is the movement pattern
[repeat for N NPCs]

The new pattern index field is there to fix the first NPC having a hard-coded movement pattern. At some point this will help when scripted movements are implemented. The movement frequency field is there for a similar reason. The first NPC had this hard-coded and it looks goofy if all the sprites move at the same time. Eventually we'll also have sprites that never move and maybe even ones that pace around frantically. There are also some new constants which will be used to reference these fields:


Ten or so articles ago we looked at sprite definitions. They contain things like the sprite size, pattern, and location. For NPCs we care about some of these fields, like the pattern, but not ones like the location because that will be set when they're loaded into a scene. This means we need a relatively light character definition that will be used when NPCs are loaded:

; 00
dc.l PlayerSpriteTilesStart
 ; priority, palette, flip, pattern
 dc.w %0110000100000000 ; priority=0,palette=2,vflip=0,hflip=0,pattern=5
; 01
 dc.l NPCSpriteDaniTilesStart
 ; priority, palette, flip, pattern
 dc.w %0110000101100000 ;priority=0,palette=2,vflip=0,hflip=0,pattern=160
; 02
 dc.l NPCSpriteMaleShopper0Start
 ; priority, palette, flip, pattern
 dc.w %0110000111000000 ;priority=0,palette=2,vflip=0,hflip=0,pattern=1C0

Hmm.. looking at this I realized the pattern really needs to be set when the NPC is loaded into the scene because it's based on the order they're loaded (this might make sense later on in the article). Well, at least I have an exciting new problem to look into. Anyway getting back to things..

Now the main game loop needs to be updated to iterate through all NPCs to determine when they should move:

 cmpi.w #$0000,(STRUCT_SPRITE_MOVEMENT_COUNTER,a5) ; is the NPC moving?
 bne .2 ; if 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 (STRUCT_SPRITE_MOVE_FREQUENCY,a5),d0 ; and against it
 cmp.w (STRUCT_SPRITE_MOVE_FREQUENCY,a5),d0 ; test 
 bne.s MainGameLoopUpdateNPCSpritesLoopEnd ; not time to move
 ; set the direction
 addq #$2,(STRUCT_SPRITE_MOVE_INDEX,a5) ; increment index of movement
 cmp.w (STRUCT_SPRITE_MOVE_INDEX,a5),d6 ; end of the array?
 bge.s .1 ; not at the end of the array
 move.w #$0000,(STRUCT_SPRITE_MOVE_INDEX,a5) ; reset to zero
.2 ; decrement NPC movement counter and test if they should stop moving
 subq #$0001,(STRUCT_SPRITE_MOVEMENT_COUNTER,a5) ; decrement counter
 bne .3 ; if MOVEMENT_COUNTER=0 now then we need to stop the sprite
 move.l a5,a6 ; setup call to StopSprite
 bsr.w StopSprite ; stop the sprite
 bra.s MainGameLoopUpdateNPCSpritesLoopEnd ; done updating this sprite
.3 ; move the NPC sprite
 move.l a5,a6 ; setup call to StopSprite
 bsr.w MoveSprite ; branch to move MoveSprite
 ; move to next NPC sprite
 adda.l #NPC_RECORD_SIZE,a5 ; increment a5
 ; dbra doesn't work against a memory address
 subq #$1,(MEM_NPC_LOOP_COUNTER) ; decrement loop counter
 bgt.w MainGameLoopUpdateNPCSpritesLoop ; branch

With more sprites on the screen we need to worry about the sprite link order again. I burnt a lot of time trying to write a routine that reordered all the sprites based on Y position until something occurred to me...

In Phantasy Star 2 and 3, which are obviously major inspirations for me, they avoid reordering NPCs by never letting them overlap. Just look at how far apart they are:

Phantasy Star 2 and 3 sprites

They totally punted on this problem and so will I. We don't really need to reorder all the sprites if the NPCs don't socialize. We only need to make sure the player sprite is in the right order relative to the NPCs. This means we can be lazy and:

1) Load NPCs into the scene in Y-order (which we'll be doing shortly).

2) Only reorder sprites when the player Y position changes.

3) To be slightly less lazy, track the player sprite links and only go through the effort of changing links when absolutely needed.

MEM_SPRITE_Y_ORDER_CHANGED=$FFFF001C ; track if sprite order has changed
MEM_PLAYER_SPRITE_LINK_TO=$FFFF0038 ; sprite ID the player sprite links to
MEM_PLAYER_SPRITE_LINK_FROM=$FFFF003A ; sprite ID linked to the player sprite
 ; test if sprites need to be reordered
 tst (MEM_SPRITE_Y_ORDER_CHANGED) ; has the sprite Y order changed?
 beq.w MainGameLoop ; hasn't changed, no need to order sprites
 move.l (MEM_GAME_STATE),d7 ; copy current game state to d7
 btst.l #STATE_FLAG_EXPLORING,d7 ; test game state
 beq.w MainGameLoop ; not exploring, no need to order sprites
 ; else order sprites and loop
 bsr.w OrderSprites ; reorder the sprites
 bra.w MainGameLoop ; return to start of game loop
 tst (MEM_ACTIVE_NPC_COUNT) ; are there any NPC sprites?
 bne.w OrderSpritesTestNPC1 ; branch if there are NPCs to check
 ; sprite zero link field
 move.w #$0000,d2 ; sprite ID 0 is the sprite to modify
 move.w (MEM_PLAYER_SPRITE_ID),d3 ; link to player sprite
 bsr.w SetSpriteLink ; set the link
 ; player link field
 move.w (MEM_PLAYER_SPRITE_ID),d2 ; player sprite is the sprite to modify
 move.w #$0000,d3 ; link to sprite 0
 bsr.w SetSpriteLink ; set the link
 bra.w ExitOrderSprites ; exit subroutine
OrderSpritesTestNPC1: ; test if player sprite is lowest priority
 move.w (MEM_NPC1_SPRITE_Y),d6 ; copy NPC Y to d6
 cmp.w (MEM_PLAYER_SPRITE_Y),d6 ; test which is higher
 ble.s OrderSpritesTestNPC0
 ; test if the player sprite links are already correct
 cmp.w #$0000,(MEM_PLAYER_SPRITE_LINK_TO) ; check "to" link
 bne.s .1 ; links need to be set
 cmp.w #$0002,(MEM_PLAYER_SPRITE_LINK_FROM); check "from" link
 beq.w ExitOrderSprites ; exit if the links are already OK

Somewhere along the way I wrote a little subroutine to set sprite links. This might be the most useful bit of code in this entire article:

; SetSpriteLink
; sets the sprite link field for a sprite
; Parameters
; d2 = ID of sprite to change
; d3 = ID of sprite to link to
; d5 is modified in this routine
 move.l #VDP_VRAM_WRITE_SPRITE,d5 ; start at base sprite vram address
 ; workaround for lack of mulu.l on 68000
 mulu.w #$0008,d2 ; move to address of sprite to modify 
 swap d2 ; move result to high word
 and.l $%11110000,d2 ; clear low word
 add.l d2,d5 ; add address of sprite to modify
 add.l #$00020000,d5 ; move to index 2
 add.w #SPRITE_DEF_WORD2_BASE,d3 ; add base value to link field in d3
 move.l d5,(VDP_CONTROL) ; set write location in VDP
 move.w d3,(VDP_DATA) ; store new sprite link field

Yes, I'm aware this is not the best way to pass parameters to subroutines. At some point I need to go back and fix this everywhere.

Loading NPCs into scenes

Now that multiple NPCs are supported there needs to be a way to load them into scenes. First off, let's setup a place to track which NPCs are in which location. This is pretty simple, it's just a list:

MEM_NPC_LOCATIONS=$FFFF0018 ; table to track where NPCs are located
 move.w #$0102,(a0)+ ; location 00 - NPCs 0,1
 move.w #$0000,(a0)+ ; location 00 - NPCs 2,3

Next I decided to create "NPC slots" in the scene. These are areas that define the location of an NPC, how often they move, and what their movement pattern is. The reason I tied this to the scene rather than the NPC is because the scene contains the layout & collision data. So an "NPC slot" is more like "a region in the scene where an NPC can pace around without running into things or getting in the way". For example, this could be used to define a place where an NPC stood behind the counter and never moved. That seems like something I'm likely to need later. Here's where our now two NPCs can go in the first store:

; NPC locations
dc.w $0001 ; two npc slots
; npc0
dc.w $0180 ; starting x location of npc0
dc.w $0110 ; starting y location of npc0
dc.w DIRECTION_DOWN ; starting direction of npc0
dc.w $A0F1 ; movement frequency of npc0
dc.l RandomNPCMovement0Start ; location of movement pattern for npc0
dc.w (RandomNPCMovement0End-RandomNPCMovement0Start-1) ; pattern length
; npc1
dc.w $00B0 ; starting x location of npc1
dc.w $0100 ; starting y location of npc1
dc.w DIRECTION_DOWN ; starting direction of npc1
dc.w $0FF0 ; movement frequency of npc1
dc.l RandomNPCMovement1Start ; location of movement pattern for npc1
dc.w (RandomNPCMovement1End-RandomNPCMovement1Start-1) ; pattern length

Now we need to load NPCs when the scene is loaded. This requires looping through MEM_NPC_LOCATIONS to see which NPCs are in this scene and loading their tiles. My goal for this LoadScene subroutine is to do everything needed to get a scene ready. It means it's a large subroutine but it's only called when changing scenes so it's not going to effect gameplay.

MEM_ACTIVE_NPC_COUNT=$FFFF00BE ; number of NPCs in the current scene
NPC_LIST_LENGTH=$0004	; max items in the NPC list
; load NPCs
 move.w (a6)+,d7 ; number of NPC slots in the scene
 move.w #$0002,d6 ; use d6 to track sprite ID
 lea MEM_NPC0_SPRITE_ID,a0 ; point a0 to the first NPC sprite
 cmpi.w #(NPC_LIST_LENGTH-1),d7 ; test to defend against my own stupidity
 bls.s LoadSceneLoadNPCDataLoop ; did I add more NPCs than supported?
 move.w #(NPC_LIST_LENGTH-1),d7 ; set d7 to the max possible NPCs
 move.w d6,(a0)+ ; ID
 move.w (a6)+,(a0)+ ; x
 move.w (a6)+,(a0)+ ; y
 move.w #$0000,(a0)+ ; pattern
 move.w (a6)+,(a0)+ ; direction
 move.w #$0000,(a0)+ ; frame
 move.w #$0000,(a0)+ ; step counter
  move.w #$0000,(a0)+ ; move counter
 move.w (a6)+,(a0)+ ; movement frequency
 move.l (a6)+,(a0)+ ; movement pattern
 move.w (a6)+,(a0)+ ; movement pattern length
 move.w #$0000,(a0)+ ; movement index
 addq #$1,d6 ; increment sprite ID
 dbra d7,LoadSceneLoadNPCDataLoop
 ; lookup which NPCs sprites are in this scene and add them
 move.w #$0000,(MEM_ACTIVE_NPC_COUNT) ; reset active scene NPC count
 lea MEM_NPC_LOCATIONS,a1 ; point a1 to the start of the list
 move.w (MEM_ACTIVE_SCENE_ID),d5 ; copy active scene ID to d5
 mulu.w #NPC_LIST_LENGTH,d5 ; multiply by list length
 adda.w d5,a1 ; add result to a1 to move to npc list for active scene
 ; setup loop control - 2 NPCs per word in MEM_NPC_LOCATIONS
 move.w #(NPC_LIST_LENGTH-1)/2,d3 ; use d3 for loop control
 ; loop through all NPCs in the scene and add their sprites
 move.w #$0002,d2 ; use d2 to track sprite ID
 move.w (a1)+,d4 ; copy next NPC pair to d4
 move.w d4,d5 ; use d5 for first byte
 and.w #$FF00,d5 ; clear low byte 
 beq.s .1 ; branch if the result of the and is zero
 lsr.w #$8,d5 ; shift upper word to lower
 jsr LoadNPC ; load this NPC sprite
.1 ; second NPC in the pair
 move.w d4,d5 ; copy NPC pair to d5 again
 and.w #$00FF,d5 ; clear high byte
 beq.s .2 ; branch if the result of the and is zero
 jsr LoadNPC ; load this NPC sprite
 dbra d3,LoadSceneLoadNPCSpritesLoop ; loop
 ; once all NPCs have been added, rebuild the object list
 bsr.w BuildNPCObjectList
; setup to rebuild sprite order after loading new NPCs
 move.w #$FFFF,(MEM_SPRITE_Y_ORDER_CHANGED) ; set to redraw sprite order
 move.w #$FFFF,(MEM_PLAYER_SPRITE_LINK_TO) ; player is linking to nothing
 move.w #$FFFF,(MEM_PLAYER_SPRITE_LINK_FROM) ; nothing links to player
 lea CharacterDefinitionStart,a2 ; point a2 to the character definition
 ; d5 contains NPC ID
 mulu.w #CHARACTER_DEFINITION_SIZE,d5 ; multiply to get NPC def location
 adda.w d5,a2 ; increment a2 to the NPC definition
 lea MEM_NPC0_SPRITE_ID,a3 ; point a3 to the first NPC memory location
 move.w d2,d5 ; d2 has sprite ID, copy it to d5
 subq #$2,d5 ; decrement to account for player sprite & sprite 0
 mulu.w #NPC_RECORD_SIZE,d5 ; multiply to get location
 adda.w d5,a3 ; increment a3 to the NPC memory location
 ; load the tiles
 move.w #SPRITE_TILESET_LWORDS,d0 ; number of tiles in a sprite tileset
 movea.l (a2)+,a0 ; set address of first tile to load
 ; calculate VDP write address
 move.l d2,d1 ; copy sprite ID to d1
 subq #$1,d1 ; subtract 1 to account for sprite 0 having no tiles
 mulu #(SPRITE_TILESET_LWORDS*LWORD_SIZE),d1 ; multiply to get location
 swap d1 ; move to upper word
 add.l #SPRITE_VDP,d1 ; add base address
 ; note - a0, d0, and d1 are modified by this call
 bsr.w LoadTiles ; branch to LoadTiles subroutine
 ; update base pattern
 ; --------------------------------------------------------------------------
 ; update x, y, and pattern in the sprite table
 ; this could be optimized a bit to use fewer calculation
 ; --------------------------------------------------------------------------
 ; y
 move.l d2,d6 ; copy sprite ID to d1
 mulu.w #$08,d6 ; multiply sprite ID by 8 to get sprite array offset
 swap d6 ; move to upper word
 add.l #VDP_VRAM_WRITE_SPRITE,d6 ; add to sprite table address
 move.l d6,(VDP_CONTROL) ; set write location in VDP
 move.w (STRUCT_SPRITE_Y,a3),(VDP_DATA) ; copy the new y-coordinate
 ; x
 move.w d2,d6 ; store sprite ID in d6
 mulu.w #$08,d6 ; multiply sprite ID by 8 to get sprite array offset
 addq #STRUCT_SPRITEDEF_X,d6 ; move to x-coordinate
 swap d6 ; move to upper word
 add.l #VDP_VRAM_WRITE_SPRITE,d6 ; add to sprite table address
 move.l d6,(VDP_CONTROL) ; set write location in VDP
 move.w (STRUCT_SPRITE_X,a3),(VDP_DATA) ; copy the new y-coordinate
 ; pattern
 move.w d2,d6 ; store sprite ID in d6
 mulu.w #$08,d6 ; multiply sprite ID by 8 to get sprite array offset
 addq #STRUCT_SPRITEDEF_PATTERN,d6 ; move to x-coordinate
 swap d6 ; move to upper word
 add.l #VDP_VRAM_WRITE_SPRITE,d6 ; add to sprite table address
 move.l d6,(VDP_CONTROL) ; set write location in VDP
 move.w (STRUCT_SPRITE_BASE_PATTERN,a3),(VDP_DATA) ; copy the new pattern
 ; block the sprite's initial map positon
 move.l a6,a4 ; workaround caused by my lack of planning
 move.l a3,a6 ; setup call to FlipSpriteMapPosition
 ; note - a3, d5, d6, and d7 are modified by this call
 bsr.w FlipSpriteMapPosition ; block the sprite's initial position
 move.l a4,a6 ; workaround caused by my lack of planning
 addq #$1,d2 ; increment sprite ID
 addq #$1,(MEM_ACTIVE_NPC_COUNT) ; increment active scene NPC count

After all this work, plus wiring-up some dialog, we have a new NPC pacing around that the player can look at. It's not too impressive but it's still progress.


Did I mention I added some new scenery too? Hopefully Sega won't send me a takedown notice over that box design. Also, I should find a real artist to help with this.

What's next?

There are a lot of little bugs to fix (as usual). I need to spend a little bit of time working through some of them. I think the next big piece of work will be the first item on the list that started this article (Dialog between characters). Tackling that will require a little work on the third item too (Game event tracking). I also might get distracted and go after something not on the list at all.


Download the latest source code on GitHub