Sega Genesis Programming Part 5: Collision detection



The Plane, The Plane

Over the course of the last four articles we've created some palettes, background tiles, a sprite, and played little background music. Along the way I made a few mistakes that need to be cleaned-up before trying something new.

The first mistake I made was drawing the floor tiles to plane A instead of plane B. The reason is my brain said "A comes before B so it must be the lower plane". In reality, plane A is drawn on top of plane B. The ordering of planes on the Sega Genesis goes like this:

Sega Genesis Planes

When I went to fix this I found my next, slightly larger, mistake - I was drawing sprites on both the sprite plane and plane B. Since I was drawing the background to plane A it (literally) covered up this mistake.

The reason for this error goes back to VDP initialization. There are 24 registers in the VDP (with some unused) that effect its behavior. There are four we'll look at today that impact what values are used for writing data to the VPD.

Let's start by looking at how to write data to the VDP.

VDP_CONTROL=$00C00004

VDP_DATA=$00C00000

VDP_VRAM_WRITE_A=$40000003

VDP_VRAM_WRITE_B=$60000003

VDP_VRAM_WRITE_SPRITE=$58000003

VDP_VRAM_WRITE_WINDOW=$70000003

[...]

move.l #VDP_VRAM_WRITE_B,(VDP_CONTROL)

move.w d0,(VDP_DATA)

Those two commands are saying "write the value in register d0 to the VDP at address 60000003." Where did these magic constant values come from though? VDP_CONTROL & VDP_DATA are easy enough to explain - that's what they are. The VDP_VRAM_WRITE ones are based on the VDP registers 2-5.

The base write address for the VDP is 40000000 which in binary is:

01000000000000000000000000000000

We have to set the write addresses for each plane by setting bits 0-1 and 27-29 in the long value sent to the VDP control port.

01000000000000000000000000000000

I realize this is very non-intuitive, it gets worse.

Now when we set the VDP registers we need to map seemingly random bits from those values to that long value to get the write address for each plane.

VDPInitDataStart:

[...]

; Register 2: VRAM Address for Scroll A

; bits 3-5 = bits 15-13 in the address of the pattern name table

; 30 = 00110000 -> 1100000000000000 ->

; 01000000000000000000000000000011 -> 40000003

dc.w $8230

 

; Register 3: VRAM Address for Window

; bits 1-5 = bits 15-11 in the address of the pattern name table

; 3E = 00111100 -> 1111000000000000 ->

; 01110000000000000000000000000011 -> 70000003

dc.w $833E

 

; Register 4: VRAM Address for Scroll B

; bits 0-2 = bits 15-13 in the address of the pattern name table

; 07 = 00000111 -> 1110000000000000 ->

; 01100000000000000000000000000011 -> 60000003

dc.w $8407

 

; Register 5: VRAM Address for Sprite Attributes

; bits 0-6 = bits 15-9 in the address of the pattern name table

; 6C = 01101100 -> 1101100000000000 ->

; 01011000000000000000000000000011 -> 58000003

dc.w $856C

[...]

The reason for this goofiness is because the commands sent to the VDP control port, via a long number, aren't done with continuous values. They are instead laid out as:

01LLLLLLLLLLLLLL00000000000000HH

Where the Ls are the low bytes for the address and the Hs are the high bytes for the address. Why they didn't just use the entire upper word is a mystery to me, maybe it's documented somewhere I overlooked.

After a couple minor updates everything is now drawing where it's supposed to:

Background in scroll B

With this all sorted out we can move on to...


Adding scenery

A sprite walking around some ugly carpet isn't all that interesting. Let's give them some scenery, since the setting is a mall in 1989 a store counter seems like an obvious thing to start with. The counter should have a region the sprite can walk behind where they're partially covered. Here's a rough design for the layout:

Counter design

The end tiles could probably be one tile with some rotation going on but I'm trying to start simple and optimize later. Generally when writing any kind of software this is good advice. If you start off trying to implement some giant design pattern or waste time optimizing early on you'll just about never finish. I've seen a lot of projects die because the lead on it had a thought process like "I need to draw some background tiles so first I'll need to create an AbstractTileFactoryBuilder class, hmm, that's a little too concrete so let's start with writing our own AbstractFactoryBuilder interface and then create AbstractFactoryBuilderImpl which AbstractTileFactoryBuilder can extend..."

Putting this rough design into the hastily written tile editor I made a couple articles ago produces a 32x32 tile set with two tiles to spare (technically one to spare since we need a blank tile):

Counter design

I won't bore you with the code for each individual tile.

The layout of the tiles is then:

Tile layout

Some of these tiles are going to be written to scroll A high and others scroll A low. That leaves us with two tile sets:

PatternCounterLowStart:

 dc.w $3,$3,$3,$3,$3,$3,$D,$C

 dc.w $3,$3,$3,$3,$3,$3,$F,$E

 dc.w $3,$3,$3,$3,$3,$3,$F,$E

 dc.w $3,$3,$3,$3,$3,$3,$3,$3

 dc.w $1,$5,$5,$5,$5,$5,$5,$9

 dc.w $2,$6,$6,$6,$6,$6,$6,$A

PatternCounterLowEnd:

PatternCounterHighStart:

 dc.w $0,$4,$4,$4,$4,$4,$B,$8

PatternCounterHighEnd:

What we need now is a subroutine that can translate a tile set to tiles. After a good deal of trial & error I came up with this:

VDP_DATA=$00C00000

VDP_CONTROL=$00C00004

ROW_HEIGHT=$800000

[...]

; DrawTileset

; draws a set of tiles

; Parameters

; a1 = starting address of tileset

; d0 = base pattern (ID+palette+high/low) of first tile in the tileset

; d1 = number of rows in the tileset

; d2 = number of columns in the tileset

; d3 = initial VRAM write address

; other registers used

; d6 = loop counter

; d7 = used to store the VDP pattern

DrawTileset:

DrawCounterRowLoop:

 move.w d2,d6 ; reset d6 to store the number of columns to loop over

 move.l d3,(VDP_CONTROL) ; set VDP address

DrawCounterColumnLoop:

 move.w (a1)+,d7 ; store the next tile index in d7

 add.w d0,d7 ; add base tile ID to tile index

 ; draw the tile

 move.w d7,(VDP_DATA) ; copy the pattern to VPD

 dbf d6,DrawCounterColumnLoop ; decrement value of d6 (column) and loop

 add.l #ROW_HEIGHT,d3 ; move to the next row

 dbf d1,DrawCounterRowLoop ; decrement value of d1 (row) and loop until 0

 rts

Calling this new subroutine to draw the counter is the relatively easy part. We'll start with the low tiles:

DrawCounter:

 ; setup call to DrawTileset for low tiles

 lea PatternCounterLowStart,a1 ; store the low starting address in a1

 ; tile 0 for the counter pattern should be at index 65h

 move.w #$0065,d0 ; store base tile ID in d0

 move.w #$0005,d1 ; 6 rows in the pattern - 1

 move.w #$0007,d2 ; 8 columns in the pattern - 1

 move.l #VDP_VRAM_WRITE_A,d3 ; initial address offset

 add.l #$00A00000,d3 ; initial address offset

 bsr.w DrawTileset ; branch to DrawTileset subroutine

So far this looks alright. I mean, my artwork skills are terrible but at least things are drawing where they're supposed to.

Counter - scroll A low

Next let's draw the high plane tiles:

 ; setup call to DrawTileset for high tiles

 lea PatternCounterHighStart,a1 ; store the high starting address in a2

 ; tile 0 for the counter pattern should be at index 65h

 move.w #$8065,d0 ; store base tile ID in d0

 move.w #$0000,d1 ; 2 rows in the pattern - 1

 move.w #$0007,d2 ; 8 columns in the pattern - 1

 move.l #VDP_VRAM_WRITE_A,d3 ; initial address offset

 add.l #$02200000,d3 ; initial address offset

 bsr.w DrawTileset ; branch to DrawTileset subroutine

Now our little sprite can stand behind the counter.

Counter

The problem is the sprite can also walk right through the counter, so I guess we need to implement some collision detection.


Collision detection

Let's start by creating a vector of collision data. The sprite plane is 512x512 and tiles are 8x8, that leaves us with a 64x64 grid to represent collision points on the map. This means we can use two long words (32-bit) to store collision points for each row in the map:

Collision detection data grid

Again, I'm not thinking about optimization too much right now so maybe there's a more compact way to do this than a long string of 0s and 1s. The long words for each row need to mirror the collision points since 0 is the lowest bit and 31 is the highest. An example will probably make more sense..

The collision data for our counter is:

11111111111111110000000000000000 00000110000000000000000011111111

11111111111111110000000000000000 00000110000000000000000011111111

11111111111111110000000000000000 00000110000000000000000011111111

11111111111111110000000000000001 11111110000000000000000011111111

11111111111111110000000000000001 11111110000000000000000011111111

11111111111111110000000000000001 11111110000000000000000011111111

The 1s are solid and 0s are open. The reason for the 1s around the edge are because I haven't implemented scrolling yet so they are off screen. The long words for these rows need to be stored with the bits reversed. The bits above are ordered left to right for readability. However, as numbers the leftmost digit is bit 31 and the rightmost is 0 so we need to flip them:

; row 17 - 11111111111111110000000000000000 00000110000000000000000011111111

dc.l $0000FFFF

dc.l $FF000060

; row 18 - 11111111111111110000000000000000 00000110000000000000000011111111

dc.l $0000FFFF

dc.l $FF000060

; row 19 - 11111111111111110000000000000000 00000110000000000000000011111111

dc.l $0000FFFF

dc.l $FF000060

; row 20 - 11111111111111110000000000000001 11111110000000000000000011111111

dc.l $8000FFFF

dc.l $FF00007F

; row 21 - 11111111111111110000000000000001 11111110000000000000000011111111

dc.l $8000FFFF

dc.l $FF00007F

; row 22 - 11111111111111110000000000000001 11111110000000000000000011111111

dc.l $8000FFFF

dc.l $FF00007F

The method to test for sprite collision against this map is a tad long so let's look at it in pieces. First is the basic setup of determining the collision point on the sprite and storing the direction they're moving. We already have some memory reserved from the sprite animation work. The collision point is just the lower left tile of the sprite:

TestSpriteCollision:

 ; 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

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

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

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

 add.w #$11,d6 ; sprites are 32px tall, test collision against lower half

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

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

Now we need to figure out which direction the sprite is moving to determine which bit of collision data to test. What we're trying to get out of this bit of code is the row of the collision data to look at:

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

 bne.s TestDownCollision ; branch if not

 sub.w #$08,d6 ; sprite is moving up, test tile 1 up from sprite

TestDownCollision:

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

 bne.s TestSpriteCollisionRoundToRow ; branch if not

 add.w #$08,d6 ; sprite is moving down, test tile 1 down from sprite

TestSpriteCollisionRoundToRow:

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

 suba.l #$6,a4 ; move back to a4+6 -> SPRITE_X

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

 bne.s TestLeftCollision ; branch if not

 move.w (a4),d7 ; d7 is no longer needed, copy sprite x to it

 add.w #$08,d7 ; sprite is moving right, test tile 1 right from sprite

 bra.s TestCollisionColumn ; sprite can't move both left & right

TestLeftCollision:

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

 bne.s NoHCollision ; branch if not

 move.w (a4),d7 ; d7 is no longer needed, copy sprite x to it

 sub.w #$08,d7 ; sprite is moving left, test tile 1 left from sprite

 bra.s TestCollisionColumn ; skip default copy of (a4) to d7

NoHCollision:

 move.w (a4),d7 ; left & right flows store sprite x in d7

At this point we know the row of collision data, now we need the column. Since there are two columns of collision data per row we need to figure out whether the sprite is on the left or right side of the screen. Once we determine that we can test whether the row & column that the sprite is moving into is open or solid.

TestCollisionColumn:

 cmpi.w #$0100,d7 ; is sprite on the left or right side of the screen?

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

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

TestMapCollision:

 move.w d6,MEM_COLLISION_TEST ; copy d6 to collision test location

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

 adda.w (MEM_COLLISION_TEST),a3 ; move to row & col

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

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

 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 ExitTestSpriteCollision ; no collision, exit

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

ExitTestSpriteCollision:

 rts

The last step is updating the MoveSprite subroutine created in the sprite animation article to call TestSpriteCollision:

MoveSprite:

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

 ; collision detection

 bsr.w TestSpriteCollision ; branch to test sprite collision

 tst.w (MEM_COLLISION_RESULT) ; 0 = no collision

 beq.s NoCollision ; no collision, continue moving

 bsr.w StopSprite ; collision, stop moving

 bra.w ExitMoveSprite ; collision, exit

NoCollision:

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

 move.w (a5),d7 ; store direction in a7

[... existing code to move the sprite, minus the edge detection which is now part of TestSpriteCollision ...]

Now our sprite can walk up to the counter, I might tweak the map data a little so they can get closer:

Collision - up

Hitting it from the left side is working fine:

Collision - left

The one issue is it's possible to squeeze into a place where the sprite's legs are drawn over the counter.

Collision glitch

I don't think this is a flaw in the collision detection code. I think I need to make the counter bigger because the more I look at it the more I realize it's way too small. I don't know what I'm going to tackle next except that figuring out the scenery for the full store needs to be done soon.


Now what?

So at this point my Sega Genesis demo is roughly equivalent feature-wise to my Android SpriteWalker Demo. They both have a player-controlled sprite moving around a simple location with music and collision detection. The Genesis version doesn't save the player state when the game quits and that might be fun to try next.

Assuming I continue with my zany RPG ideas I have to choose whether to go with Android or Sega Genesis. I'm not going to write a 3rd demo on a different platform, it's going to be one of these two.

There are a number of trade-offs to consider:

  Android Sega Genesis
Development Tools Most of my experience is with Eclipse which works well for Android development. Google would prefer if everyone moved over to Android Studio which in my limited experience is only good at producing an endless stream of obtuse Gradle errors. I managed to build one application in Android Studio and I still think it was an accident. Effectively non-existent, to just build this tiny demo I had to write one development tool. If I continue this path I'll have to write a few more.
Testing If it runs on an emulator there's a 50% chance it will run on real hardware. For the few small applications I've written I think I spent the majority of my time figuring out why Environment.getExternalStorageDirectory() functions differently on some, but not all, Samsung phones. If it runs on an emulator there's a 99% chance it will run on real hardware. If I continue this path I'll need to buy an over-priced flash cart but at least I only need to test on one piece of hardware.
Community Support Very large, active community of developers to work with. I've yet to find a problem that there wasn't a blog entry or StackOverflow topic containing the solution. Tiny community of active developers, the couple I've interacted with are nice enough. Overall though this is a "figure it out yourself" endeavor.
Audio Programming Nearly zero effort, just find some public domain mp3s and play them. Converting public domain .xm files is an option, not a great one but better than nothing.
Platform Stability For all we know Google could lose a lawsuit to Oracle and all Android development has to move to Go (or something else) Obsolete, unsupported platforms are remarkably stable.
Forward Compatibility There are regular Android upgrades that sometimes (often) require code changes. It's expected that I'd have to update any Android application about once a year. Obviously not an issue.
Ability to Commercialize There's practically no relationship between the quality of a mobile game and the amount of money it makes. I have no way to predict whether I could make a profitable game on Android. I'm certain I could not make a profitable game on the Genesis so at least I won't be frustrated trying to figure out how to do it.
Resume Padding Being able to program for Android is a marketable, in-demand skill. On the other hand, I'd much rather work for someone who was more impressed by the ability to program a Genesis.
Fun I feel like most of the time I've spent doing Android development involves (1) dealing with IDE errors (2) updating code because of a breaking change in a new release (3) figuring out how to make something run in both the latest version and any previous one (4) going insane trying to resolve device-specific problems. None of these issues are especially fun. The Sega Genesis demo took about 10x longer to produce but was bizarrely more fun to work on. I don't know exactly how to put it, there's just something enjoyable (to me) about trying to figure out how to do simple things on the Genesis. Building any software is just an exercise in solving lots & lots of simple problems. If I continue to take an incremental approach to writing a Genesis game I think I will continue having fun doing it.

Right now the Genesis is definitely in the lead...

Download the latest source code on GitHub




Tweet