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:

STRUCT_SPRITE_ID=$0

STRUCT_SPRITE_X=$2

STRUCT_SPRITE_Y=$4

STRUCT_SPRITE_BASE_PATTERN=$6

STRUCT_SPRITE_DIRECTION=$8

STRUCT_SPRITE_FRAME=$A

STRUCT_SPRITE_STEP_COUNTER=$C

STRUCT_SPRITE_MOVEMENT_COUNTER=$E

STRUCT_SPRITE_MOVE_FREQUENCY=$10

STRUCT_SPRITE_MOVE_PATTERN=$12

STRUCT_SPRITE_MOVE_PATTERN_LENGTH=$16

STRUCT_SPRITE_MOVE_INDEX=$18

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:

CharacterDefinitionStart:

; 00

CharacterDefinitionPlayer:

dc.l PlayerSpriteTilesStart

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

 ; priority, palette, flip, pattern

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

 ;pccvhnnnnnnnnnnn

 dc.w %0110000100000000 ; priority=0,palette=2,vflip=0,hflip=0,pattern=5

CharacterDefinitionPlayerEnd:

; 01

CharacterDefinitionDani:

 dc.l NPCSpriteDaniTilesStart

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

 ; priority, palette, flip, pattern

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

 ;pccvhnnnnnnnnnnn

 dc.w %0110000101100000 ;priority=0,palette=2,vflip=0,hflip=0,pattern=160

; 02

CharacterDefinitionMaleShopper0:

 dc.l NPCSpriteMaleShopper0Start

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

 ; priority, palette, flip, pattern

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

 ;pccvhnnnnnnnnnnn

 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:

[...]

MainGameLoopUpdateNPCSpritesLoop:

 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

 move.w #NPC_SPRITE_MOVE_STEPS,(STRUCT_SPRITE_MOVEMENT_COUNTER,a5) ; reset

 ; set the direction

 addq #$2,(STRUCT_SPRITE_MOVE_INDEX,a5) ; increment index of movement

 move.w (STRUCT_SPRITE_MOVE_PATTERN_LENGTH,a5),d6

 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

.1

 move.l (STRUCT_SPRITE_MOVE_PATTERN,a5),a6

 adda (STRUCT_SPRITE_MOVE_INDEX,a5),a6

 move.w (a6),(STRUCT_SPRITE_DIRECTION,a5)

.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

MainGameLoopUpdateNPCSpritesLoopEnd:

 ; 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

[...]

MainGameLoopEnd:

 ; 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

[...]

OrderSprites:

 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

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

SetSpriteLink:

 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

 rts

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

[...]

InitNPCLocations:

 lea MEM_NPC_LOCATIONS,a0

 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

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

LoadSceneLoadNPCData:

 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

LoadSceneLoadNPCDataLoop:

 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

LoadSceneLoadNPCSprites:

 ; 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

LoadSceneLoadNPCSpritesLoop:

 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

.2

 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

[...]

LoadNPC:

 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

 move.w (a2)+,(STRUCT_SPRITE_BASE_PATTERN,a3)

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

 ; 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

ExitLoadNPC:

 addq #$1,d2 ; increment sprite ID

 addq #$1,(MEM_ACTIVE_NPC_COUNT) ; increment active scene NPC count

 rts

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.

New NPC

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