Tummai Games

In the last post, I got the hero sprite moving. But there’s a problem: she can walk through walls. I need to add collision detection with background tiles. Collision detection with the background can be summed up like this:

if the player tries to move:
    check the space they want to move to
    if that space is solid/blocked:
        don't move
    else:
        move

The looks pretty easy, but it can actually be quite complicated. Here are some issues:

1. The hero sprite has x and y coordinates, which are on the pixel level. My room tile data is stored in ram on the metatile level. We need to make a conversion there.
2. There isn’t any one point on the hero that is a catch-all for movement checks. If the player tries to move left, we will want to check for a collision with the left side of the hero. If the player tries to move right, we want to check for a collision with the right side of the hero. So we will need to make a hit box.
3. Each side of the hit box will have a length > 1, so we may have to check for a collision with more than one background tile. For example, say the player wants to move right. We will check using the right side of the hit box. But it’s possible that the top half of the hit box will be adjacent to one tile, while the bottom half is adjacent to another.
   

   If we only checked the top-right corner of this hit box for collision, it would show the way as clear. But it really isn't, because the bottom half of the hit box collides with a solid tile.

Step 1

First thing I want to do is make a hit box. I’m going to put it around the hero sprite’s feet. I define where the edges are relative to the hero’s X/Y coords, then make a subroutine to calculate the box every frame:

;collision box for the hero sprite (box around the feet)
HERO_MOVEMENT_BOX_TOP = 26
HERO_MOVEMENT_BOX_BOTTOM = 31
HERO_MOVEMENT_BOX_LEFT = 5
HERO_MOVEMENT_BOX_RIGHT = 11

hero_box: .res 4 ;top bottom left right

set_hero_box:
    lda hero_x
    clc
    adc #HERO_MOVEMENT_BOX_LEFT
    sta hero_box+2
    lda hero_x
    clc
    adc #HERO_MOVEMENT_BOX_RIGHT
    sta hero_box+3
    lda hero_y
    clc
    adc #HERO_MOVEMENT_BOX_TOP
    sta hero_box
    lda hero_y
    clc
    adc #HERO_MOVEMENT_BOX_BOTTOM
    sta hero_box+1
    rts

Movement within a metatile

Since every metatile is 16 pixels wide and 16 pixels tall, I can take a shortcut if I determine that the player is not at the edge of a tile. Check out these two cases:

We don't need to check for a collision in the left case. The player is already on a walkable tile, and will remain on that tile if they move a pixel to the right.

Let’s assume the player is trying to move right. The player is on a walkable tile in both cases. In the first case, they are in the middle of the tile. In the second case they are at the edge. We only need to check for a collision in the second case. Checking the first case would be a waste of time, because we’d be checking the tile the player is already on for walkability, but we know it must be walkable since the player is already on it. So right away we can skip over a collision check if we determine the player to be in the middle of the tile (ie, not on the edge).

This is very easy to pull off with 16×16 metatiles. In all cases, the left edge of a metatile will have an x-coord of $x0, and the right edge will be $xF. The top edge of a metatile will have a y-coord of $x0 and the bottom will be $xF. So in our collision detection routines, we can do something like this:

can_move_right:
    ldx hero_box+3 ;right edge of movement box
    inx ;we want to peek at the next pixel over
    txa

    and #$0F ;isolate right nibble,
         ; tells us where we are WITHIN a tile

    bne @move_ok ;not on the edge.  movement within current
                 ;square OK (in other words, if the right
                 ;nibble is 0, we are on the left edge of the
                 ;NEXT tile, and therefore need to check
                 ;for collision)

    ;... check for collisions

@move_ok:
    sec  ;return a 1 if movement is OK
    rts

I use a similar check at the beginning of can_move_left, can_move_up and can_move_down.

How many checks?

Do I need to check one bg tile for collision or two? It depends on the hero sprite’s position. Imagine the player is moving right again. If the top and bottom edges of the hit box are both within the boundaries of a single tile, we only need to check one bg tile for collision. But check this picture (should look familiar):

moving right, the top and bottom edges of the hit box touch two different bg tiles. We need to make two checks.

In this case, the top and bottom edges of our hit box line up with two different bg tiles. So we need to check both. If either of them are unwalkable, we don’t allow movement.

So, two checks or one check? There are a couple of ways to determine if the top and bottom edges of our hit box touch different tiles. I do it this way:

    ;find how many tiles to check (1 or 2)
    lda hero_box ;top edge of movement hit box

    ora #$F0 ;we are going to add the box height,
             ;so set us up to check for a FF->00 transition

    adc #HERO_MOVEMENT_BOX_HEIGHT ;negative means our box is
                                  ;h-aligned with one tile.
                                  ;positive = 2 tiles
    bmi @not_two

    ;... check a tile

@not_two:
    ;... check a tile

I do similar tests for the other directions, but for can_move_up and can_move_down I will check the left and right edges instead of the top and bottom edges.

Hero pixel coords to a room coords

I need to turn the hero’s pixel coordinates into room coordinates so that I can find which bg tiles to check. Here’s my subroutine to do that:

;------------------------------
; set_hero_map_coords finds the x and y room coords for the 
; topleft pixel of the player's movement hit box
set_hero_map_coords:
    lda hero_box+2 ;left
    ldx #$00
    sec
:
    sbc #$10
    bcc :+
    inx
    jmp :-
:
    stx hero_map_x

    lda hero_box ;top
    ldx #$00
    sec
:
    sbc #$10
    bcc :+
    inx
    jmp :-
:
    dex
    dex ;correct y for the status bar
    stx hero_map_y
    rts

Once I have the hero’s room coordinates, I can add to or subtract from them to find the coordinates for the adjacent tiles I want to check for walkability.

Walkability

How do I check for walkability? With a lookup table:

;tile ids
.enum
    floor
    wall
    block
    water
    block_breakable
    stairs_up
    stairs_down
    pitfall
.endenum

.enum ;walkability
    unwalkable
    walkable
.endenum

tile_walkability:
    .byte walkable, unwalkable, unwalkable, unwalkable
    .byte unwalkable, walkable, walkable, walkable

I read a tile id from the room map in RAM and use it to index into the tile_walkability table.

Here’s a simplified can_move_right. (I took out checks for room boundaries to make it more readable):

can_move_right:
    ldx hero_box+3 ;right edge of movement box
    inx
    txa

    and #$0F ;isolate right nibble, where are we WITHIN a tile?

    bne @move_ok ;not on edge. move within current square OK

    ;how many tiles to check (1 or 2)
    lda hero_box ;top edge of movement box
    ora #$F0
    adc #HERO_MOVEMENT_BOX_HEIGHT
    bmi @not_two

    ldy hero_map_y
    iny
    ldx hero_map_x
    inx
    jsr get_room_offset ;takes x/y room coords and returns an
                        ;array index in y

    lda room, y
    tay
    lda tile_walkability, y
    beq @no_move

@not_two:
    ldy hero_map_y
    ldx hero_map_x
    inx
    jsr get_room_offset

    lda room, y
    tay
    lda tile_walkability, y
    beq @no_move
@move_ok:
    sec return 1 in the carry if we can move
    rts
@no_move:
    clc return 0 in the carry if we can't move
    rts

I have seperate routines for the other 3 directions. They are all very similar. The last step is to update my move_hero subroutine to call these collision detection routines before moving, and then skip movement on carry clear.

Conclusion

Now I have a sprite that changes direction, moves, animates and bumps into walls. Here’s the latest video demo: