Collisions In Tile-Based Worlds

Know your tiles and other mundanities

Before we jump head first into collision detection like a child in shallow water, let's make sure we're on the same page. This article focuses on collisions within a grid-structured 2D world. We're not going to make something like Namco's Mappy or Pony's Fruit Panic because I don't believe those use tile-based collisions.

First let's design our world by creating generic blocks/materials with a unique index number to represent solid walls, background elements and whatnot.

Inside our program it'll look like this (we're only going to use plain colors but the principle is identical for graphics: reserve a list of images somewhere, store your graphic data, then reference the image by index.)

CONST cBlockIsSolid = &h8000 ' Block is solid.

TYPE blockType
  iColor AS INTEGER
  iFlags AS INTEGER
END TYPE

DIM SHARED gBlock(15) AS blockType

gBlock(0).iColor = 0
gBlock(0).iFlags = 0

gBlock(1).iColor = 3
gBlock(1).iFlags = cBlockIsSolid

To determine if a block is solid, we just:

' iIsSolid is either True (-1) or False (0)
iIsSolid = ((gBlock(x).iFlags AND cBlockIsSolid) <> 0)

So far so good. Next, we allocate memory to a rectangular grid divided in cells of equal dimensions to represent our world. Finally we assign each cell an index number that points to a block type. From there, we can check the definition of our blocks to know how the cell should be rendered and how it should behave.

In our code, the world will be stored in a one-dimensional array (QuickBASIC's multi-dimensional arrays are notoriously slower than 1D arrays.)

CONST cCellWidth = 16       ' Cell width in pixels.
CONST cCellHeight = 16      ' Cell height in pixels.
CONST cMaxCells = 512       ' Array size in cells.

DIM SHARED gMapData(cMaxCells - 1) AS INTEGER
DIM SHARED gMapWidth AS INTEGER, gMapHeight AS INTEGER

' Cells are 16x16 and mode 13 is 320x200. This means we can
' have a one-screen map of 20 columns by 12 rows. Those values
' will be assigned to gMapWidth and gMapHeight.
DATA 20, 12

' This is our world data. Right now we only have two types of
' blocks: 0 (non-solid) and 1 (solid.)
DATA "11000000000000000011"
DATA "11000000000000000011"
DATA "11000000000001111011"
DATA "11000000000011110011"
DATA "11000110000000000011"
DATA "11000110000000000011"
DATA "11111111111110000011"
DATA "11000001100000001111"
DATA "11000001100000011111"
DATA "11001000000000111111"
DATA "11000000001100000011"
DATA "11111111111111111111"

Cells are organized left to right and top to bottom. The very first cell (top left) in the grid is located at address 0, the last cell (bottom right) at address gMapWidth * gMapHeight - 1. As gMapWidth (width of the grid in columns) and gMapHeight (height of the grid in rows) are expressed in cells, we can increment the address of a cell by 1 to get the address of its right neighbor, by gMapWidth to find the neighbor below, -1 for the left neighbor, and -gMapWidth for the neighbor above. We have to be careful though: cells located on the first and last row/column only have at most two direct neighbors, not four. It means that we'll have to make sure the address we're trying to reach is, in fact, part of the grid. It's only a formality and we'll get to it shortly. Just thought I would mention it now.

Before we move on, let's write a routine to load our data statements into the array. If you store your level data into external files (as you probably will,) this is where you would load the data into RAM.

''
'' Setup the world via DATA statements.
''
SUB mapFromData
  DIM iR AS INTEGER, iC AS INTEGER
  DIM sDta AS STRING, iRow AS INTEGER

  ' Read map width and height in cells. If you use custom
  ' values, make sure they do not overflow the buffer we
  ' allocated for the map data earlier.
  READ gMapWidth, gMapHeight

  ' Start reading DATA statements. If you use custom values,
  ' make sure there's enough data available to fill the map or
  ' this will crash.
  FOR iR = 0 TO gMapHeight - 1

    ' Read one row.
    READ sDta

    ' Get the writing offset to the 1st cell of the row.
    iRow = iR * gMapWidth

    ' Decode each cell and write to gMapData(). If you use
    ' custom values, make sure each DATA statement contains the
    ' proper number of cells or this may crash.
    FOR iC = 0 TO gMapWidth - 1
      gMapData(iRow + iC) = VAL(MID$(sDta, 1 + iC, 1))
    NEXT iC

  NEXT iR
END SUB

One last thing: let's display the map on screen. Simply go through each cell, get their block index, look at the matching block in gBlock() and follow its specifications:

''
'' Read data off gMapData() and display on-screen. The top-left
'' corner of the map is located at 0, 0 with positive values
'' going right and down.
''
SUB mapDraw
  DIM iR AS INTEGER, iC AS INTEGER
  DIM iX AS INTEGER, iY AS INTEGER
  DIM iRow AS INTEGER
  DIM uBlock AS blockType

  ' Read map data.
  FOR iR = 0 TO gMapHeight - 1

    ' Get the reading offset in gMapData() to the 1st cell of
    ' row iRow.
    iRow = iR * gMapWidth

    ' On-screen vertical offset.
    iY = iR * cCellHeight

    FOR iC = 0 TO gMapWidth - 1
      ' On-screen horizontal offset.
      iX = iC * cCellWidth

      ' Get block type.
      uBlock = gBlock(gMapData(iRow + iC))

      ' Draw the cell.
      LINE (iX, iY)-STEP(cCellWidth - 1, cCellHeight - 1), uBlock.iColor, BF

      ' If the block is solid, draw a cross on it.
      IF (uBlock.iFlags AND cBlockIsSolid) THEN
        LINE (iX, iY)-STEP(cCellWidth - 1, cCellHeight - 1), 0
        LINE (iX + cCellWidth - 1, iY)-STEP(-(cCellWidth - 1), cCellHeight - 1), 0
      END IF
    NEXT iC

  NEXT iR
END SUB

Cell-bound movement

If action games are not your thing and you're more of a classic RPG kind-of-guy, a puzzle game enthusiast (Sokoban, Adventure of Lolo, Boulder Dash, etc.) or a cinematic platformer aficionado (Prince of Persia, Flashback) then you're in luck because cell-based movement is super easy to implement and this chapter is going to tell you all about it! If you have no interest in such things, feel free to skip ahead because this chapter won't be mentioned again.

First, let's write a custom type for actors (this type is used by world objects such as enemies, collectables, and even the player.) For this type of movement, actors are placed inside a specific cell and can only move to adjacent cells. Thus, our actor type only needs a set of X and Y coordinates expressed in cells (not in pixels or world units.)

TYPE ActorType
  iX AS INTEGER       ' Horizontal (column) and vertical (row)
  iY AS INTEGER       '   coordinates, expressed in cells.
END TYPE

DIM SHARED gActor(0) AS actorType

' Set actor's current location (in cells.)
gActor(0).iX = 3
gActor(0).iY = 1

Alright. Now onto the collision stuff. There are two ways of handling cell-based collisions: solid blocks and solid edges.

Option 1, solid blocks

Let's begin with the solid block method because it's the simplest. We predict the destination cell of the actor and look at the block type in the target cell. If it is solid, the actor doesn't move; otherwise the actor is transported to the desired cell. The function will return the address of the cell if the move can be processed, or -1 if the actor is not allowed there.

CONST cMoveUp = 0
CONST cMoveRt = 1
CONST cMoveDn = 2
CONST cMoveLf = 3

''
'' This function returns the address of the cell the actor may
'' move to, or -1 if the actor is not allowed to go there.
''
FUNCTION actorMoveTarget% (iActor AS INTEGER, iDirection AS INTEGER)
  DIM iTargetX AS INTEGER, iTargetY AS INTEGER
  DIM iOffsetX AS INTEGER, iOffsetY AS INTEGER
  DIM iTargetAdr AS INTEGER, iIsSolid AS INTEGER

  ' Get the coordinates of the destination cell. If you don't
  ' like the conditional branching, consider replacing it with
  ' an array of 4 movement vectors (one entry per direction.)
  SELECT CASE (iDirection)
  CASE cMoveUp
    iOffsetX = 0
    iOffsetY = -1
  CASE cMoveLf
    iOffsetX = -1
    iOffsetY = 0
  CASE cMoveDn
    iOffsetX = 0
    iOffsetY = +1
  CASE cMoveRt
    iOffsetX = +1
    iOffsetY = 0
  END SELECT
  iTargetX = gActor(iActor).iX + iOffsetX
  iTargetY = gActor(iActor).iY + iOffsetY

  ' Out of bound check: return -1 if the cell is out of bounds.
  IF (iTargetX < 0) OR (iTargetX >= gMapWidth) OR _
     (iTargetY < 0) OR (iTargetY >= gMapHeight) THEN
    actorMoveTarget% = -1
    EXIT FUNCTION
  END IF

  ' Convert X, Y coordinates to address.
  iTargetAdr = iTargetX + iTargetY * gMapWidth

  ' Read the cell value to get the block type. If the block is
  ' solid, iIsSolid is True. Kind reminder: True is -1.
  iIsSolid = ((gBlock(gMapData(iTargetAdr)).iFlags AND cBlockIsSolid) <> 0)

  ' Return the address of the cell within the world if the actor
  ' can move there (iIsSolid is 0,) or -1 if it cannot (iIsSolid
  ' is -1.)
  actorMoveTarget% = iTargetAdr OR iIsSolid
END FUNCTION

The rest of the code is boring fluff: catch and process user input, update the screen, etc. It's beyond the scope of the article so I won't copy it here, but you can get the whole code here if you want to.

One last tip for the road: some navigation systems allow individual maps to be connected by their edges and levels are designed in such a way the player is allowed to move out of bounds, which triggers a map change. This can be done by modifying the "out of bound check" to return a different value for each boundary (use negative values.) Then, while processing the actual move, catch the return value and load the next map accordingly.

Option 2, solid edges

The second way of doing things unlocks a whole bunch of possibilities for shaping our world: each edge of the cell has a practicability flag that allows (or not) actors to cross it. If the overlapping borders of the origin and target cells both allow to be crossed, then the actor may cross the border. If either border denies crossing, then it cannot. This kind of design lets us create cliffs and slopes (it's just a visual trick, but it's pretty neat with proper graphics.)

The collision detection code requires some changes, and we're also going to need a few more blocks and fresh map data for this demo...

CONST cBlockWallUp  = &h1     ' Top edge cannot be crossed.
CONST cBlockWallLf  = &h2     ' Left edge cannot be crossed.
CONST cBlockWallDn  = &h4     ' Bottom edge cannot be crossed.
CONST cBlockWallRt  = &h8     ' Right edge cannot be crossed.
CONST cBlockWallAll = &hF     ' Shorthand for all edges blocked.

' Grass
gBlock(0).iColor = 2
gBlock(0).iFlags = 0

' Dirt path
gBlock(1).iColor = 6
gBlock(1).iFlags = 0

' Left cliff
gBlock(2).iColor = 7
gBlock(2).iFlags = cBlockWallLf

' Bottom left cliff
gBlock(3).iColor = 7
gBlock(3).iFlags = cBlockWallLf Or cBlockWallDn

' Bottom cliff
gBlock(4).iColor = 7
gBlock(4).iFlags = cBlockWallDn

' Bottom-right cliff
gBlock(5).iColor = 7
gBlock(5).iFlags = cBlockWallRt OR cBlockWallDn

' Right cliff
gBlock(6).iColor = 7
gBlock(6).iFlags = cBlockWallRt

' Cliff front (solid)
gBlock(7).iColor = 7
gBlock(7).iFlags = cBlockIsSolid

' Stone top (walkable)
gBlock(8).iColor = 7
gBlock(8).iFlags = 0

' Sloped dirt path (walkable)
gBlock(9).iColor = 114
gBlock(9).iFlags = 0

' New world data.
DATA "88888888888888888600"
DATA "11111118888844444500"
DATA "88188818888677777700"
DATA "45928888888677777700"
DATA "77928888888677777700"
DATA "77928444444500000000"
DATA "77135777777700000000"
DATA "00177444457700011111"
DATA "00177777770000010000"
DATA "00111111111111110000"
DATA "00000000000000000000"
DATA "00000000000000000000"

We're going to tweak the map display routine just a tiny bit so it can show us where solid borders are located.

''
'' Read data off gMapData() and display on-screen. This time the
'' routine outlines solid edges if there's any.
''
SUB mapDraw
  DIM iR AS INTEGER, iC AS INTEGER
  DIM iX AS INTEGER, iY AS INTEGER
  DIM iRow AS INTEGER, iClr AS INTEGER
  DIM uBlock AS blockType

  ' Read map data.
  FOR iR = 0 TO gMapHeight - 1

    ' Get the reading offset to the 1st cell of the row.
    iRow = iR * gMapWidth
    ' On-screen vertical offset.
    iY = iR * cCellHeight

    FOR iC = 0 TO gMapWidth - 1

      ' Get tile info.
      uBlock = gBlock(gMapData(iRow + iC))

      ' On-screen horizontal offset.
      iX = iC * cCellWidth

      ' Draw cell, use tile-defined color.
      LINE (iX, iY)-STEP(cCellWidth - 1, cCellHeight - 1), uBlock.iColor, BF

      ' If the block is solid, cross it.
      IF (uBlock.iFlags AND cBlockIsSolid) THEN
        LINE (iX, iY)-STEP(cCellWidth - 1, cCellHeight - 1), 0
        LINE (iX + cCellWidth - 1, iY)-STEP(-(cCellWidth - 1), cCellHeight - 1), 0

      ' Draw solid edges.
      ELSEIF (uBlock.iFlags AND cBlockWallAll) THEN
        iClr = uBlock.iColor + 1
        IF (uBlock.iFlags AND cBlockWallUp) THEN
          LINE (iX, iY)-STEP(cCellWidth - 1, 0), iClr
        END IF
        IF (uBlock.iFlags AND cBlockWallLf) THEN
          LINE (iX, iY)-STEP(0, cCellHeight - 1), iClr
        END IF
        IF (uBlock.iFlags AND cBlockWallDn) THEN
          LINE (iX, iY + cCellHeight - 1)-STEP(cCellWidth - 1, 0), iClr
        END IF
        IF (uBlock.iFlags AND cBlockWallRt) THEN
          LINE (iX + cCellWidth - 1, iY)-STEP(0, cCellHeight - 1), iClr
        END IF
      END IF

    NEXT iC

  NEXT iR
END SUB

The collision function is also going to be adjusted to handle solid edges. Note that we kept the solid block flag in place; just in case... although we could replace cBlockIsSolid by cBlockWallAll and get the exact same result. If you desperately need to save a bitflag, that's one you can use.

''
'' This function returns the address of the cell the actor may
'' move to, or -1 if the actor is not allowed to go there.
''
FUNCTION actorMoveTarget% (iActor AS INTEGER, iDirection AS INTEGER)
  DIM iTargetX AS INTEGER, iTargetY AS INTEGER
  DIM iOffsetX AS INTEGER, iOffsetY AS INTEGER
  DIM iSourceAdr AS INTEGER, iTargetAdr AS INTEGER
  DIM iMaskExit AS INTEGER, iMaskEntry AS INTEGER
  DIM iIsSolid AS INTEGER

  ' Get the coordinates of the destination cell and the proper
  ' wall bitflag; the actor is going to cross two borders (one
  ' is the exit of the starting cell, the other is the entry of
  ' the target cell.) We could use bitshifting to make the
  ' process smoother, but is it really worth it?
  SELECT CASE (iDirection)
  CASE cMoveUp
    iOffsetX = 0
    iOffsetY = -1
    iMaskExit = cBlockWallUp
    iMaskEntry = cBlockWallDn
  CASE cMoveLf
    iOffsetX = -1
    iOffsetY = 0
    iMaskExit = cBlockWallLf
    iMaskEntry = cBlockWallRt
  CASE cMoveDn
    iOffsetX = 0
    iOffsetY = 1
    iMaskExit = cBlockWallDn
    iMaskEntry = cBlockWallUp
  CASE cMoveRt
    iOffsetX = 1
    iOffsetY = 0
    iMaskExit = cBlockWallRt
    iMaskEntry = cBlockWallLf
  END SELECT
  iTargetX = gActor(iActor).iX + iOffsetX
  iTargetY = gActor(iActor).iY + iOffsetY

  ' Out of bound check: return -1 if the cell is out of bounds.
  IF (iTargetX < 0) OR (iTargetX >= gMapWidth) OR _
     (iTargetY < 0) OR (iTargetY >= gMapHeight) THEN
    actorMoveTarget% = -1
    EXIT FUNCTION
  END IF

  ' Get the target cell address.
  iTargetAdr = iTargetX + iTargetY * gMapWidth

  ' If the target block is solid, abort right away.
  IF (gBlock(gMapData(iTargetAdr)).iFlags AND cBlockIsSolid) THEN
    actorMoveTarget% = -1
    EXIT FUNCTION
  END IF

  ' Get the source cell address.
  iSourceAdr = gActor(iActor).iX + gActor(iActor).iY * gMapWidth

  ' If either edge is blocked, iIsSolid is True.
  iIsSolid = (((gBlock(gMapData(iTargetAdr)).iFlags AND iMaskEntry) OR _
               (gBlock(gMapData(iSourceAdr)).iFlags AND iMaskExit)) <> 0)

  ' Return iTargetAdr (the address of the cell within the world)
  ' if the actor can move there, or -1 if it cannot.
  actorMoveTarget% = iTargetAdr OR iIsSolid
END FUNCTION

It doesn't seem like much but it can look (and feel) pretty cool with slightly better graphics. Notice the actor in the top left being all red and square and stuff.

Here's the full source code if you need it.

Smooth moves

"But-but-but," I hear you plead, "can't we have smooth transitions when the actor is moving from one cell to the other?" And the answer is: yes, we can. It's only a visual trick: we move the actor to the target cell as usual, but we make it look like it is still at its starting position by introducing an X and Y drawing offset:

TYPE ActorType
  iX AS INTEGER       ' Horizontal (column) and vertical (row)
  iY AS INTEGER       '   coordinates, expressed in cells.
  iOffsetX AS INTEGER ' Display offset in pixels for the X and Y
  iOffsetY AS INTEGER '   axis of the actor's actual position.
  iWait AS INTEGER    ' Game ticks betwen updates.
END TYPE

These two values are added to the drawing coordinates of the actor on screen. If we set those values to the difference between the current and previous location in pixels (for instance, iOffsetX would be -cCellWidth and iOffsetY would be 0 if the actor's previous location was one cell to the left,) then it looks like the actor hasn't moved an inch:

' I know we have not been using PUT() since the beginning of
' this article; it's just an example:
PUT(gActor(0).iX * cCellWidth + gActor(0).iOffsetX, _
    gActor(0).iY * cCellHeight + gActor(0).iOffsetY), actorGfx

To recap: we remember the starting cell and get the target cell. If the move is valid, we place the actor into the target cell then compute the drawing offset between the source and target cell so that the actor looks like it's still standing in the starting cell. We gradually bring both offset values toward 0, making the actor look like it's walking toward the destination cell. Until it is at rest, we must prevent the actor from moving to another cell because that would break the effect.

' Get the next location of the actor:
iAdr = actorMoveTarget% (0, cMoveUp)
iNewX = iAdr MOD gMapWidth
iNewY = iAdr \ gMapWidth

' Get the display offset, in pixel.
gActor(0).iOffsetX = cCellWidth * (gActor(0).iX - iNewX)
gActor(0).iOffsetY = cCellHeight * (gActor(0).iY - iNewY)

' Move the actor to the next location.
gActor(0).iX = iNewX
gActor(0).iY = iNewY

' The actor is walking: get one step closer to the target.
IF (gActor(0).iOffsetX OR gActor(0).iOffsetY) THEN
  ' If the offset is less than 0, we "subtract -1" (add 1) and
  ' if the offset is greater than 0, we "add -1" (subtract 1.)
  ' Alternatively: iOffset = iOffset - SGN(iOffset)
  gActor(0).iOffsetX = gActor(0).iOffsetX - (gActor(0).iOffsetX < 0) + (gActor(0).iOffsetX > 0)
  gActor(0).iOffsetY = gActor(0).iOffsetY - (gActor(0).iOffsetY < 0) + (gActor(0).iOffsetY > 0)
ELSE
  ' Both offsets are 0. It looks like the actor just reached the
  ' target cell. It is now allowed to move to another cell.
END IF

The reason why you want to place the actor on the target cell as early as possible is because another actor may try to go there too. If they are both physically walking there, it becomes harder to determine which one should reach the target first, and what should be done with the loser of the race... By placing the actor right there immediately, we know the cell is reserved and there's no battling over its ownership. Of course, if you allow multiple actors to stand on the same cell, this isn't really a concern.

Here's some test code to give you an idea.

Free movement

Plain bounding box (with gravity)

If you went through the cell-based movement chapter, forget everything you just read. If you forgot your name or what you're doing here, you forgot too much, try to remember. Good? Good.

A bounding box is a fancy rectangle that represents the body of the actor: when something solid overlaps with the bounding box, there's collision. Rather than "fix" collision by pushing things away after the fact, we're going to predict the future location of the actor and course-correct before moving the actor. It's simple, I swear.

First let's design a custom actor type.

CONST cActorOnGround = &h1 ' If set, the actor is on the ground.

TYPE ActorType
  iFlags AS INTEGER   ' Special flags.
  fX AS SINGLE        ' Actor's origin, located in the bottom
  fY AS SINGLE        '   center of the bounding box.
  fVelX AS SINGLE     ' Velocity, added to the origin every game
  fVelY AS SINGLE     '   tick, influenced by body type.
  iBBoxW AS INTEGER   ' Bounding box half width and height,
  iBBoxH AS INTEGER   '   relative to the origin.
END TYPE

The actor is given a special flag. Currently, it is used to remember if the actor is on the ground or not. Being on the ground means that gravity shouldn't be applied and the actor is allowed to jump. Rather than directly manipulate the actor's origin, we're using fVelX and fVelY to set its horizontal and vertical velocity. Those values can be set to 0 by the collision detection routine to stop the actor in its track. Positive velocities push the actor to the right and down, negative velocities left and up.

The bounding box is built relative to the actor's origin (fX, fY:) as it moves around, so is the bounding box. It may sound very limiting but it's going to be super handy later. The bounding box size is defined with iBBoxW and iBBoxH:

' Get the absolute (in-world) coordinates of all four corners of
' the bounding box for actor 0. Kind reminder that the origin of
' the actor is ALWAYS located in the bottom center of the
' bounding box (this will be VERY handy later.)
iLf = INT(gActor(iActor).fX) - gActor(iActor).iBBoxW
iRt = INT(gActor(iActor).fX) + gActor(iActor).iBBoxW
iUp = INT(gActor(iActor).fY) - (gActor(iActor).iBBoxH - 1)
iDn = INT(gActor(iActor).fY)

By computing the absolute (in-world) coordinates of the box, it becomes possible to test actor against actor collisions, which is useful to determine when an item is picked up, when a projectile reaches its target, etc:

''
'' This function returns True if actor uOne overlaps actor uTwo.
''
FUNCTION actorCollide%(uOne AS ActorType, uTwo AS ActorType)
  IF (uOne.fX - uOne.iBBoxW <= uTwo.fX + uTwo.iBBoxW) THEN
    IF (uOne.fX + uOne.iBBoxW >= uTwo.fX - uTwo.iBBoxW) THEN
      IF (uOne.fY - (uOne.iBBoxH - 1) <= uTwo.fY) THEN
        actorCollide% = (uOne.fY >= uTwo.fY - (uTwo.iBBoxH - 1))
      END IF
    END IF
  END IF
END FUNCTION

Collisions against the world are processed differently. For starter, we won't test the whole actor's body against any and all surrounding tiles: we're only going to test blocks ahead of the actor. If the actor is moving left, we test tiles directly to the left. If the actor is moving down, we only test tiles below its feet. To simplify the process even further, we will test each axis separately, beginning with X (moving left or right, colliding with vertical edges) and then with Y (moving up or down, colliding with horizontal edges.) In our design, the bounding box is allowed to overlap the edges of solid blocks by one unit. It may sound counter-intuitive but it's easier to poll whether the actor is standing on ground or airbound. Look at it the other way: the actor is actuall INSIDE the bounding box, meaning that a 18-unit tall bounding box holds a 16-pixel tall actor, which explains why it can fit through 16-pixel tall gaps (while the bounding box visibly overlaps.)

There's a catch though! If the bounding box is inside solid tiles, then testing for collisions against vertical edges will always trigger when the actor moves left or right, because the left edge of the bounding box is just tall enough to scrape the floor cells. Thankfuly, the solution is super simple: just reduce the vertical edges of the bounding box by two units:

Alright. So: if the actor is moving horizontally (left or right) then we compute the absolute coordinates of the bounding box corners, get all tiles located from the top to bottom of the bounding box, and see if any solid block collides with the would-be location of the actor. If there's collision, we adjust the ideal (would-be) coordinate so it overlaps with the edge of the solid blocks by only one unit.

The following routine predicts the new origin point of the actor according to its velocity, and adjusts the output if a collision occurs. Please note that we do not check for out-of-bounds coordinates, meaning that the program will crash if the actor is located outside the world.

''
'' Adjust the actor's coordinates using its horizontal and
'' vertical velocity (fVelX, fVelY.) Test for collisions against
'' vertical edges first (left/right moves) and then against
'' horizontal edges (up/down moves.)
''
SUB actorMove (iActor AS INTEGER)
  DIM fIdealX AS SINGLE, fIdealY AS SINGLE, iAdr AS INTEGER
  DIM iCol AS INTEGER, iColLf AS INTEGER, iColRt AS INTEGER
  DIM iRow AS INTEGER, iRowUp AS INTEGER, iRowDn AS INTEGER
  DIM iLf AS INTEGER, iUp AS INTEGER
  DIM iRt AS INTEGER, iDn AS INTEGER

  ' Test collisions with vertical edges first.
  IF (gActor(iActor).fVelX) THEN

    ' Compute the would-be target coordinates.
    fIdealX = gActor(iActor).fX + gActor(iActor).fVelX
    fIdealY = gActor(iActor).fY

    ' Compute the would-be bounding box.
    iLf = fIdealX - gActor(iActor).iBBoxW
    iRt = fIdealX + gActor(iActor).iBBoxW
    iUp = fIdealY - (gActor(iActor).iBBoxH - 1)
    iDn = fIdealY

    ' Select the proper column of tiles (either on the left or
    ' right side of the actor, depending on its direction.)
    IF (0 < gActor(iActor).fVelX) THEN
      iCol = iRt \ cCellWidth
    ELSE
      iCol = iLf \ cCellWidth
    END IF

    ' If we use the FULL height of the bounding box, we will
    ' always trigger a collision against the vertical seams of
    ' the cells that make up the floor when the actor is on the
    ' ground. We offset the values because we don't want to test
    ' against the floor: only against solid blocks directly to
    ' the left or right.
    iRowUp = (iUp + 1) \ cCellHeight
    iRowDn = (iDn - 1) \ cCellHeight
    iAdr = iCol

    ' Test right/left collision. If we got a collision, adjust
    ' the ideal X coordinate and exit the loop.
    FOR iRow = iRowUp TO iRowDn
      IF (gBlock(gMapData(iAdr + iRow * gMapWidth)).iFlags AND cBlockIsSolid) THEN
        IF (0 < gActor(iActor).fVelX) THEN
          fIdealX = (iCol * cCellWidth) - gActor(iActor).iBBoxW
        ELSE
          fIdealX = ((iCol + 1) * cCellWidth) - 1 + gActor(iActor).iBBoxW
        END IF
        ' Cancel horizontal velocity.
        gActor(iActor).fVelX = 0
        EXIT FOR
      END IF
    NEXT iRow

    ' Update X coordinate.
    gActor(iActor).fX = fIdealX
  END IF

  ' Test collisions with horizontal edges. In theory, if the
  ' world layout never changes, this can only happen if the
  ' velocity is not zero (actor moved left or right, but also if
  ' it is currently falling or jumping.) We're going to do it
  ' all the time, just to make sure its feet are still on the
  ' ground.

  ' Compute the would-be target coordinates.
  fIdealX = gActor(iActor).fX
  fIdealY = gActor(iActor).fY + gActor(iActor).fVelY

  ' Compute the would-be bounding box.
  iLf = fIdealX - gActor(iActor).iBBoxW
  iRt = fIdealX + gActor(iActor).iBBoxW
  iUp = fIdealY - (gActor(iActor).iBBoxH - 1)
  iDn = fIdealY

  ' Select the proper row of tiles (either above or below the
  'actor, depending on its direction.)
  IF (0 > gActor(iActor).fVelY) THEN
    iRow = iUp \ cCellHeight
  ELSE
    iRow = iDn \ cCellHeight
  END IF

  ' Same problem as above: we cannot use the full width of the
  ' bounding box as the actor will get stuck at the horizontal
  ' seams of the cells that make up the walls.
  iColLf = (iLf + 1) \ cCellWidth
  iColRt = (iRt - 1) \ cCellWidth
  iAdr = iRow * gMapWidth

  ' Clear the "onground" flag. If we get a collision while
  ' going down, we'll set it back.
  gActor(iActor).iFlags = gActor(iActor).iFlags AND NOT cActorOnGround

  ' Test bottom/top collision. If we got a collision, adjust
  ' the ideal Y coordinate and exit the loop.
  FOR iCol = iColLf TO iColRt
    IF (gBlock(gMapData(iAdr + iCol)).iFlags AND cBlockIsSolid) THEN
      IF (gActor(iActor).fVelY < 0) THEN
        fIdealY = ((iRow + 1) * cCellHeight) - 1 + (gActor(iActor).iBBoxH - 1)
      ELSE
        fIdealY = (iRow * cCellHeight)
        gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGround
      END IF
      ' Whether the actor bumped its head against a block or
      ' fell on the ground, cancel its vertical velocity.
      gActor(iActor).fVelY = 0
      EXIT FOR
    END IF
  NEXT iCol

  ' Update Y coordinate.
  gActor(iActor).fY = fIdealY
END SUB

This should work as long as the delta is not equal or greater than the width/height of a cell (whichever is the shortest.)

Tweaking the bounding box

It works but feels a little stiff. Granted it is partially due to using INKEY() for keyboard controls, but it's also due to the bounding box itself. Here are a few tweaks we can use be more lineant toward "intelligent" actors (shouldn't apply to debris and projectiles.)

Jumping up to a ledge requires the actor's feet to be exactly above the top surface of the cell, and not a pixel short, or it will stumble the tip of its toe against the corner and miserably slide along the edge of the block, falling down to its doom.

The first thing we can do is reduce the height of the left and right edges of the bounding box when testing vertical collisions: by moving the lower point from the feet to the ankle, we may not always detect collision with the vertical edges of solid cells, meaning that the horizontal coordinate of the actor may update in such a way it is now clipping inside a solid cell. It sounds like a horrible idea, but the next (horizontal) collision test will look at the feet and catch that the actor is indeed in a solid cell, nudging it back up on the platform.

To do that, we only have to replace two lines in ActorMove():

' Old code: the offset is sufficient to skip the floor cells but
' it still requires pixel-perfect leaps.
iRowUp = (iUp + 1) \ cCellHeight
iRowDn = (iDn - 1) \ cCellHeight

' New code: if the actor is close enough to the edge of the cell
' then the jump should be valid.
iRowUp = (iUp + 4) \ cCellHeight
iRowDn = (iDn - 4) \ cCellHeight

We could also reduce the width of the top edge of the bounding box to prevent head bumping in narrow hallways but it's a lot trickier to pull off (we won't even try,) partly because the bottom of the bounding box may have the opportunity to catch a collision and "suck" the actor up through the top block when it really shouldn't. By the way, Super Mario Bros on the NES allows partial overlap of actors and blocks when going up:

The best illustration of how SMB attempts to solve collisions by gently nudging actors out of the way (gradually adjusting their position rather than correcting it right away) is seen when people go to world minus 1 by jumping in-between bricks in the first underworld level to reach the warp zone.

The very last tweak requires actors to be no wider than one tile (which is a perfectly sensible requirement: after all, the size of the world should be proportional to the dimensions of the actors living in it.) Rather than test a whole bunch of tiles below the bounding box, we're only going to test (at most) two, for the left and right foot. As long as one foot is located in a solid tile, then the actor is on the ground. If both feet are in the air, the actor should fall.

One more thing: we're going to define two new flags: cActorOnGroundLeft and cActorOnGroundRight to know which feet is still on the ground; then we're going to create a mask to know if the actor is in the ground (implied by the two previous bitflags.)

CONST cActorOnGroundLeft = &H1    ' Left foot on the ground.
CONST cActorOnGroundRight = &H2   ' Right foot on the ground.
CONST cActorOnGround = &H3        ' Actor is on the ground.

And now, let's adjust ActorMove() accordingly.

''
'' Adjust the actor's coordinates using its horizontal and
'' vertical velocity (fVelX, fVelY.) Test for collisions against
'' vertical edges first (left/right moves) and then against
'' horizontal edges (up/down moves.)
''
SUB actorMove (iActor AS INTEGER)
  DIM fIdealX AS SINGLE, fIdealY AS SINGLE, iAdr AS INTEGER
  DIM iCol AS INTEGER, iColLf AS INTEGER, iColRt AS INTEGER
  DIM iRow AS INTEGER, iRowUp AS INTEGER, iRowDn AS INTEGER
  DIM iLf AS INTEGER, iUp AS INTEGER
  DIM iRt AS INTEGER, iDn AS INTEGER

  ' Test collisions with vertical edges first.
  IF (gActor(iActor).fVelX) THEN

    ' Compute the would-be target coordinates.
    fIdealX = gActor(iActor).fX + gActor(iActor).fVelX
    fIdealY = gActor(iActor).fY

    ' Compute the would-be bounding box.
    iLf = fIdealX - gActor(iActor).iBBoxW
    iRt = fIdealX + gActor(iActor).iBBoxW
    iUp = fIdealY - (gActor(iActor).iBBoxH - 1)
    iDn = fIdealY

    ' Select the proper column of tiles (either on the left or
    ' right side of the actor, depending on its direction.)
    IF (0 < gActor(iActor).fVelX) THEN
      iCol = iRt \ cCellWidth
    ELSE
      iCol = iLf \ cCellWidth
    END IF

    ' If we use the FULL height of the bounding box, we will
    ' always trigger a collision against the vertical seams of
    ' the cells that make up the floor when the actor is on the
    ' ground. We offset the values because we don't want to test
    ' against the floor: only against solid blocks directly to
    ' the left or right.
    iRowUp = (iUp + 4) \ cCellHeight
    iRowDn = (iDn - 4) \ cCellHeight
    iAdr = iCol

    ' Test right/left collision. If we got a collision, adjust
    ' the ideal X coordinate and exit the loop.
    FOR iRow = iRowUp TO iRowDn
      IF (gBlock(gMapData(iAdr + iRow * gMapWidth)).iFlags AND cBlockIsSolid) THEN
        IF (0 < gActor(iActor).fVelX) THEN
          fIdealX = (iCol * cCellWidth) - gActor(iActor).iBBoxW
        ELSE
          fIdealX = ((iCol + 1) * cCellWidth) - 1 + gActor(iActor).iBBoxW
        END IF
        ' Cancel horizontal velocity.
        gActor(iActor).fVelX = 0
        EXIT FOR
      END IF
    NEXT iRow

    ' Update X coordinate.
    gActor(iActor).fX = fIdealX
  END IF

  ' Test collisions with horizontal edges.

  ' Clear the "OnGround" flags. We may set it back later...
  gActor(iActor).iFlags = gActor(iActor).iFlags AND NOT cActorOnGround

  ' Compute the would-be target coordinates.
  fIdealX = gActor(iActor).fX
  fIdealY = gActor(iActor).fY + gActor(iActor).fVelY

  ' Compute the would-be bounding box.
  iLf = fIdealX - gActor(iActor).iBBoxW
  iRt = fIdealX + gActor(iActor).iBBoxW
  iUp = fIdealY - (gActor(iActor).iBBoxH - 1)
  iDn = fIdealY

  ' If the actor is going up, check tiles above.
  IF (0 > gActor(iActor).fVelY) THEN
   iRow = iUp \ cCellHeight

    ' Same problem as above: we cannot use the full width of the
    ' bounding box as the actor will get stuck at the horizontal
    ' seams of the cells that make up the walls.
    iColLf = (iLf + 1) \ cCellWidth
    iColRt = (iRt - 1) \ cCellWidth
    iAdr = iRow * gMapWidth

    ' Test top collision. If we got a collision, adjust the
    ' ideal Y coordinate and exit the loop.
    FOR iCol = iColLf TO iColRt
      IF (gBlock(gMapData(iAdr + iCol)).iFlags AND cBlockIsSolid) THEN
        fIdealY = ((iRow + 1) * cCellHeight) - 1 + (gActor(iActor).iBBoxH - 1)
        gActor(iActor).fVelY = 0
        EXIT FOR
      END IF
    NEXT iCol

  ' If the actor is NOT going up, it is either falling or
  ' walking; check both feet.
  ELSE
    iRow = (iDn \ cCellHeight)

    ' Left foot.
    iAdr = iRow * gMapWidth + ((iLf + 1) \ cCellWidth)
    IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSolid) THEN
      fIdealY = (iRow * cCellHeight)
      gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGroundLeft
      gActor(iActor).fVelY = 0
    END IF

    ' Right foot.
    iAdr = iRow * gMapWidth + ((iRt - 1) \ cCellWidth)
    IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSolid) THEN
      fIdealY = (iRow * cCellHeight)
      gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGroundRight
      gActor(iActor).fVelY = 0
    END IF
  END IF

  ' Update Y coordinate.
  gActor(iActor).fY = fIdealY
END SUB

By using two collision points for feet, we can determine when an actor is about to fall off a platform (one of its feet is in the air.) This marker can be used to force actors to change their walking direction when they're about to fall, to create Zoomers (the spiked enemies found in Metroid on the NES,) or show a special animation to inform the player he's about to fall off a ledge.

You can get the tweaked bounding box code here!

Before we move on, I'd like to remind you that many great NES games only worked with simple solid tiles: Super Mario Bros, Power Blade 1 & 2, Shatterhand, Mega Man 1 thru 6, Duck Tales 1 & 2, Kid Icarus, Metroid, Little Samson, Blaster Master, Bionic Commando, Batman, Trojan, Contra, Wally Bear & The NO Gang... none of these games used slopes! Isn't that amazing? Who needs slopes anyway? You? Me? Ah ah... no but really, do you absolutely NEED slopes?

Slopes

Implementing slopes is an uphill battle [canned laughter] Thank you! Thank you! I'll be here all week. Seriously though, enjoy the laugh because it's all going downhill from here [canned laughter again.] Ah ah, jokes aside folks, remember there are plenty of ways to program slopes, and they all suck. You may think that I'm being hyperbolic when I say "slopes are the holy grail of platformers" but if I really wanted to be hyperbolic, I would have said "Less than 1% of people get THIS one single thing right [red arrow pointing at nondescript blob], and here's the REAL reason NOBODY talks about: it's WORSE than you think and here's why they LIED to YOU (the answer left me SPEECHLESS as it CHANGED EVERYTHING!)" but I have more self-respect than a common whore. Wow, that came out of nowhere. See Mike, that's why nobody ever shares your articles. Anyway, enough procrastinating desguised as unhinged psychotic rambling: let's get down to business!

For those who didn't notice, this chapter is not a sub-chapter of Free Movement, which was all about bounding boxes. That's because slopes do not use the bounding box (although we will still use it for wall collisions:) slopes allow actors to walk through them as if they were non-solid blocks, but they also automatically adjust the vertical position of the actor to match their shape. Following that curve is not going to be possible with a plain bounding box...

That being said, first, we create a new flag for our blocks: cBlockIsSlope. Then, we're going to create separate slope shapes that we will refer to by index (just like one would do with graphics.)

CONST cBlockIsSlope = &h4000 ' Block is a slope.

TYPE blockType
  iColor AS INTEGER
  iFlags AS INTEGER
  iShape AS INTEGER          ' Index (divided by cCellWidth) in gSlope()
END TYPE

Since our cells are 16 columns wide, each shape will be an array of 16 entries in which each entry represents the floor elevation from the bottom of the cell (a value between 15 and 0 included.)

CONST cNumSlopes = 6         ' Number of slope Types

DIM SHARED gSlope(cCellWidth * cNumSlopes - 1) AS INTEGER

' Slope 0, going down (1 step right = 1 unit down)
' Slope 1 & 2, going down (2 steps right = 1 unit down)
' Slope 3 & 4, going up (2 steps right = 1 unit up)
' Slope 5, going up (1 step right = 1 unit up)
DATA 15,14,13,12,11,10,09,08,07,06,05,04,03,02,01,00
DATA 15,15,14,14,13,13,12,12,11,11,10,10,09,09,08,08
DATA 07,07,06,06,05,05,04,04,03,03,02,02,01,01,00,00
DATA 00,00,01,01,02,02,03,03,04,04,05,05,06,06,07,07
DATA 08,08,09,09,10,10,11,11,12,12,13,13,14,14,15,15
DATA 00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15

''
'' Setup slope types via DATA statements.
''
SUB slopeFromData
  DIM iSlope AS INTEGER, iFloor AS INTEGER, iIndex AS INTEGER

  ' Read the floor offset of each slope.
  FOR iSlope = 0 to cNumSlopes - 1
    iIndex = iSlope * cCellWidth
    FOR iFloor = 0 TO cCellWidth - 1
      READ gSlope(iIndex + iFloor)
    NEXT iFloor
  NEXT iSlope
END SUB

Then, we define a bunch of blocks:

' Setup block types.
gBlock(0).iColor = 0
gBlock(0).iFlags = 0

gBlock(1).iColor = 3
gBlock(1).iFlags = cBlockIsSolid

gBlock(2).iColor = 2  ' dark green
gBlock(2).iFlags = cBlockIsSlope
gBlock(2).iShape = 0

gBlock(3).iColor = 5  ' dark purple
gBlock(3).iFlags = cBlockIsSlope
gBlock(3).iShape = 3

gBlock(4).iColor = 13 ' bright pink
gBlock(4).iFlags = cBlockIsSlope
gBlock(4).iShape = 4

gBlock(5).iColor = 10 ' light green
gBlock(5).iFlags = cBlockIsSlope
gBlock(5).iShape = 5

gBlock(6).iColor = 1  ' dark blue
gBlock(6).iFlags = cBlockIsSlope
gBlock(6).iShape = 1

gBlock(7).iColor = 9  ' light blue
gBlock(7).iFlags = cBlockIsSlope
gBlock(7).iShape = 2

And of course, new map data:

' This is our world data. We got a whole set of blocks: solid,
' non-solid, and several slopes (indices 2 to 7.)
DATA "11000000000000000011"
DATA "11000000000000000011"
DATA "11000000000051111011"
DATA "11000000000011110011"
DATA "11120000000000000011"
DATA "11112003411200000011"
DATA "11111111111110000011"
DATA "11000001100000001111"
DATA "11000001100000051111"
DATA "11167000000000511111"
DATA "11111670000005111111"
DATA "11111111111111111111"

So essentially, this is what we got:

Functionally, we compute the difference between the actor's horizontal coordinate and the cell's horizontal coordinate to obtain the actor's location inside the tile, then lookup the matching floor value in the shape array and adjust the vertical offset of the actor. Of course, if the actor is located above the crosshatched section of the illustration, we shouldn't be changing anything (more about that later.)

' Assuming iCellBottom is the vertical position of the bottom
' row of the slope tile, iCellLeft is the horizontal position of
' the left column of the slope tile, iSlopeType is the slope
' type index, and the coordinate at (gActor(iActor).iX,
' gActor(iActor).iY) points to the slope surface, this works:
gActor(iActor).fY = iCellBottom - gSlope(iSlopeType * cCellWidth + (iCellLeft - gActor(iActor).fX))

That sounds simple! Is it really all we have to do? Yes! But also no... mostly "no" in fact.

To really hammer the point home: so far we only tested the edges of cells (the very narrow space in-between the squares of our grid,) against the bounding box to determine if there was collision. Slopes are more difficult because we have to test elevation within the cell itself using a single point. Because we use two different metrics (a 2D box and a "non-dimensional" point,) the two collision systems may often provide contradictory information. A good part of our job now is to decide which process gets the priority (edge or slope detection,) and when.

Revisiting cActorOnGround

So far, we half-assed the "on ground" detection because it didn't really matter that much to us: we used the flag to determine if the player was allowed to jump and that was it. We might as well not have the flag at all and check before jumping if the actor is standing on something. The problem is that now, we DO need to know if the actor is STILL on the ground because we need a separate set of rules when handling horizontal movement for walking actors, and when the actor is in the air (either jumping or falling.) Let's go back to ActorMove().

First, we can be sure that the actor is not on the ground if its vertical velocity is not Null.

' The actor is moving vertically. It cannot be on the ground.
IF (gActor(iActor).fVelY) THEN
  gActor(iActor).iFlags = gActor(iActor).iFlags AND NOT cActorOnGround
END IF

Next, if there's horizontal movement, we have to check vertical wall collisions like we've done before. However, if the actor is on the ground, we have to also check if it didn't walk off a ledge.

' Note: we just validated the horizontal coordinate and we're
' still in the conditional block for horizontal velocity.

' The actor was on the ground last time we checked and the
' horizontal velocity is not Null, we have to make sure the
' actor's feet are still on the ground.
IF (gActor(iActor).iFlags AND cActorOnGround) THEN

  ' Compute the bounding box with the updated coordinates.
  iLf = fIdealX - gActor(iActor).iBBoxW
  iRt = fIdealX + gActor(iActor).iBBoxW
  iUp = fIdealY - (gActor(iActor).iBBoxH - 1)
  iDn = fIdealY

  ' Feet are located on the same tile row.
  iRow = (iDn \ cCellHeight)

  ' Left foot.
  iAdr = iRow * gMapWidth + ((iLf + 1) \ cCellWidth)
  IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSolid) THEN
    gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGroundLeft
  ELSE
    gActor(iActor).iFlags = gActor(iActor).iFlags AND NOT cActorOnGroundLeft
  END IF

  ' Right foot.
  iAdr = iRow * gMapWidth + ((iRt - 1) \ cCellWidth)
  IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSolid) THEN
    gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGroundRight
  ELSE
    gActor(iActor).iFlags = gActor(iActor).iFlags AND NOT cActorOnGroundRight
  END IF
END IF

We used to systematically test up-down collisions. Now, we will only test collisions if the vertical velocity is not Null. We will test for head bumps if the velocity is lower than 0, or for possible landing if the velocity is greater than 0.

' The actor's vertical velocity is not Null, we may test for
' jump or drop.
IF (gActor(iActor).fVelY) THEN

  ' Compute the would-be target coordinates.
  fIdealX = gActor(iActor).fX
  fIdealY = gActor(iActor).fY + gActor(iActor).fVelY

  ' Compute the would-be bounding box.
  iLf = fIdealX - gActor(iActor).iBBoxW
  iRt = fIdealX + gActor(iActor).iBBoxW
  iUp = fIdealY - (gActor(iActor).iBBoxH - 1)
  iDn = fIdealY

  ' If the actor is going up, check head bump.
  IF (0 > gActor(iActor).fVelY) THEN
    iRow = iUp \ cCellHeight

    ' Same problem as before: we cannot use the full width of
    ' the bounding box as the actor will get stuck at the
    ' horizontal seams of the cells that make up the walls.
    iColLf = (iLf + 1) \ cCellWidth
    iColRt = (iRt - 1) \ cCellWidth
    iAdr = iRow * gMapWidth

    ' Test top collision. If we got a collision, adjust the
    ' ideal Y coordinate and exit the loop.
    FOR iCol = iColLf TO iColRt
      IF (gBlock(gMapData(iAdr + iCol)).iFlags AND cBlockIsSolid) THEN
        fIdealY = ((iRow + 1) * cCellHeight) - 1 + (gActor(iActor).iBBoxH - 1)
        gActor(iActor).fVelY = 0
        EXIT FOR
      END IF
    NEXT iCol

  ' The actor is falling. Reminder: cActorOnGround is clear
  ' because the vertical velocity is not Null. We did that early
  ' in the routine. This means we don't have to clear the flag
  ' if neither foot is on the ground.
  ELSE

    ' Feet are located on the same tile row.
    iRow = (iDn \ cCellHeight)

    ' Left foot.
    iAdr = iRow * gMapWidth + ((iLf + 1) \ cCellWidth)
    IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSolid) THEN
      fIdealY = (iRow * cCellHeight)
      gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGroundLeft
      gActor(iActor).fVelY = 0
    END IF

    ' Right foot.
    iAdr = iRow * gMapWidth + ((iRt - 1) \ cCellWidth)
    IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSolid) THEN
      fIdealY = (iRow * cCellHeight)
      gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGroundRight
      gActor(iActor).fVelY = 0
    END IF
  END IF

  ' Update Y coordinate.
  gActor(iActor).fY = fIdealY
END IF

The mysterious third leg

Until now, we've been using two points to determine if the actor is on the ground or not. It's cool and all, but it doesn't work with slopes. Let's put it this way: which foot should be used to determine if the actor is on a slope? Yeah, that doesn't sound like a question you'd like to hear in a game of Trivial Pursuit.

The secret is a third point, located right between both feet, at the base of the bounding box; which happens to be the exact location of the actor's origin (I told you I put it there for a reason.) If that point is in a slope tile, then the actor is on a slope. Even if most of the actor is located on a flat-top tile, its vertical coordinate should be adjusted to follow the slope shape. This check always has the highest priority if the actor is on the ground. In my head, it looks like this:

The third schematic looks kind of scary, but it's not. When the actor is on the ground, we never test for ceiling and floor collisions, thus it will be able to move from cell 1 to cell 2 without bumping against the top edge of cell 1. However, walking actors still test against left and right wall collisions, and moving from cell 2 to 1 will trigger a collision with the right side of cell 1.

We could solve the issue by clipping a few extra units off the left edge of the bounding box (so collisions are only caught from the waist-up,) but I have the feeling it's going to come back and bite us in the ass later. The alternative is equally simple: we do NOT test cells located on the same row (or below) a slope block. Since the origin of the actor is always one unit deep into a solid block or slope (when it's on the ground,) we just compute the row the actor is in, minus 1.

The other major problem we're going to face is that when we move from cell 4 to 2, the origin point will not actually enter cell 2: it will enter cell 3. The obvious solution is to test both the orign point and one unit higher to check if the actor is entering a slope.

Okay, we got enough ideas to start writing something. It's not going to be pretty and it will require some adjustements, but it should give us a good idea of what to do next:

''
'' Adjust the actor's coordinates using its horizontal and
'' vertical velocity (fVelX, fVelY.) Test for collisions against
'' vertical edges first (left/right moves) and then against
'' horizontal edges (up/down moves.)
''
SUB actorMove (iActor AS INTEGER)
  DIM fIdealX AS SINGLE, fIdealY AS SINGLE, iAdr AS INTEGER
  DIM iCol AS INTEGER, iColLf AS INTEGER, iColRt AS INTEGER
  DIM iRow AS INTEGER, iRowUp AS INTEGER, iRowDn AS INTEGER
  DIM iRelX AS INTEGER, iRelY AS INTEGER
  DIM iCelX AS INTEGER, iCelY AS INTEGER
  DIM iLf AS INTEGER, iUp AS INTEGER
  DIM iRt AS INTEGER, iDn AS INTEGER

  ' The actor is moving vertically. It cannot be on the ground.
  IF (gActor(iActor).fVelY) THEN
    gActor(iActor).iFlags = gActor(iActor).iFlags AND NOT cActorOnGround
  END IF

  ' Test collisions with vertical edges first.
  IF (gActor(iActor).fVelX) THEN

    ' Compute the would-be target coordinates.
    fIdealX = gActor(iActor).fX + gActor(iActor).fVelX
    fIdealY = gActor(iActor).fY

    ' Compute the would-be bounding box.
    iLf = fIdealX - gActor(iActor).iBBoxW
    iRt = fIdealX + gActor(iActor).iBBoxW
    iUp = fIdealY - (gActor(iActor).iBBoxH - 1)
    iDn = fIdealY

    ' Select the proper column of tiles (either on the left or
    ' right side of the actor, depending on its direction.)
    IF (0 < gActor(iActor).fVelX) THEN
      iCol = iRt \ cCellWidth
    ELSE
      iCol = iLf \ cCellWidth
    END IF

    ' If we use the FULL height of the bounding box, we will
    ' always trigger a collision against the vertical seams of
    ' the cells that make up the floor when the actor is on the
    ' ground. We offset the values because we don't want to test
    ' against the floor: only against solid blocks directly to
    ' the left or right.
    iRowUp = (iUp + 4) \ cCellHeight
    IF (gActor(iActor).iFlags AND cActorOnGround) THEN
      iRowDn = (iDn \ cCellHeight) - 1
    ELSE
      iRowDn = (iDn - 4) \ cCellHeight
    END IF
    iAdr = iCol

    ' Test right/left collision. If we got a collision, adjust
    ' the ideal X coordinate and exit the loop.
    FOR iRow = iRowUp TO iRowDn
      IF (gBlock(gMapData(iAdr + iRow * gMapWidth)).iFlags AND cBlockIsSolid) THEN
        IF (0 < gActor(iActor).fVelX) THEN
          fIdealX = (iCol * cCellWidth) - gActor(iActor).iBBoxW
        ELSE
          fIdealX = ((iCol + 1) * cCellWidth) - 1 + gActor(iActor).iBBoxW
        END IF
        ' Cancel horizontal velocity.
        gActor(iActor).fVelX = 0
        EXIT FOR
      END IF
    NEXT iRow

    ' Update X coordinate.
    gActor(iActor).fX = fIdealX

    ' The actor was on the ground last time we checked and the
    ' horizontal velocity is not Null, we have to make sure the
    ' actor's feet are still on the ground.
    IF (gActor(iActor).iFlags AND cActorOnGround) THEN

      ' Compute the bounding box with the updated coordinates.
      iLf = fIdealX - gActor(iActor).iBBoxW
      iRt = fIdealX + gActor(iActor).iBBoxW
      iUp = fIdealY - (gActor(iActor).iBBoxH - 1)
      iDn = fIdealY

      ' Feet are located on the same tile row.
      iRow = (iDn \ cCellHeight)

      ' Slopes have the priority for this test again. If the new
      ' origin is NOT in a slope tile, test the tile just above:
      ' the actor may come from a solid tile and onto a slope.
      iAdr = iRow * gMapWidth + (fIdealX \ cCellWidth)
      IF ((gBlock(gMapData(iAdr)).iFlags AND cBlockIsSlope) = 0) THEN
        iAdr = iAdr - gMapWidth
      END IF

      ' If the actor is walking on a slope, we have to adjust
      ' the vertical coordinate. We don't care where its feet
      ' are at all.
      IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSlope) THEN

        ' Get the left and bottom coordinates of the slope cell.
        iCelX = (iAdr MOD gMapWidth) * cCellWidth
        iCelY = (iAdr \ gMapWidth) * cCellHeight + (cCellHeight - 1)

        ' Get the horizontal location of the actor, relative to
        ' the left edge of the tile.
        iRelX = fIdealX - iCelX

        ' Get the floor elevation.
        iRelY = iCelY - gSlope(gBlock(gMapData(iAdr)).iShape * cCellWidth + iRelX)

        ' Set the actor's vertical location.
        gActor(iActor).fY = iRelY

      ' The actor is not on a slope, check both feet.
      ELSE
        ' Left foot.
        iAdr = iRow * gMapWidth + ((iLf + 1) \ cCellWidth)
        IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSolid) THEN
          gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGroundLeft
        ELSE
          gActor(iActor).iFlags = gActor(iActor).iFlags AND NOT cActorOnGroundLeft
        END IF

        ' Right foot.
        iAdr = iRow * gMapWidth + ((iRt - 1) \ cCellWidth)
        IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSolid) THEN
          gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGroundRight
        ELSE
          gActor(iActor).iFlags = gActor(iActor).iFlags AND NOT cActorOnGroundRight
        END IF
      END IF
    END IF
  END IF

  ' The actor's vertical velocity is not Null, we may test for
  ' jump or drop.
  IF (gActor(iActor).fVelY) THEN

    ' Compute the would-be target coordinates.
    fIdealX = gActor(iActor).fX
    fIdealY = gActor(iActor).fY + gActor(iActor).fVelY

    ' Compute the would-be bounding box.
    iLf = fIdealX - gActor(iActor).iBBoxW
    iRt = fIdealX + gActor(iActor).iBBoxW
    iUp = fIdealY - (gActor(iActor).iBBoxH - 1)
    iDn = fIdealY

    ' If the actor is going up, check head bump.
    IF (0 > gActor(iActor).fVelY) THEN
      iRow = iUp \ cCellHeight

      ' Same problem as before: we cannot use the full width of
      ' the bounding box as the actor will get stuck at the
      ' horizontal seams of the cells that make up the walls.
      iColLf = (iLf + 1) \ cCellWidth
      iColRt = (iRt - 1) \ cCellWidth
      iAdr = iRow * gMapWidth

      ' Test top collision. If we got a collision, adjust the
      ' ideal Y coordinate and exit the loop.
      FOR iCol = iColLf TO iColRt
        IF (gBlock(gMapData(iAdr + iCol)).iFlags AND cBlockIsSolid) THEN
          fIdealY = ((iRow + 1) * cCellHeight) - 1 + (gActor(iActor).iBBoxH - 1)
          gActor(iActor).fVelY = 0
          EXIT FOR
        END IF
      NEXT iCol

    ' The actor is falling. Reminder: cActorOnGround is clear
    ' because the vertical velocity is not Null. We did that early
    ' in the routine. This means we don't have to clear the flag
    ' if neither foot is on the ground.
    ELSE

      ' Feet are located on the same tile row.
      iRow = (iDn \ cCellHeight)

      ' Slopes have the priority, check now.
      iAdr = iRow * gMapWidth + (gActor(iActor).fX \ cCellWidth)
      IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSlope) THEN

        ' Get the left and bottom coordinates of the slope cell.
        iCelX = (iAdr MOD gMapWidth) * cCellWidth
        iCelY = (iAdr \ gMapWidth) * cCellHeight + (cCellHeight - 1)

        ' Get the horizontal location of the actor, relative to
        ' the left edge of the tile.
        iRelX = fIdealX - iCelX

        ' Get the floor elevation.
        iRelY = iCelY - gSlope(gBlock(gMapData(iAdr)).iShape * cCellWidth + iRelX)

        ' If the actor's origin is below the floor level, adjust
        ' the ideal Y coordinate.
        IF (gActor(iActor).fY >= iRelY) THEN
          fIdealY = iRelY
          gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGround
          gActor(iActor).fVelY = 0
        END IF

      ELSE
        ' Left foot.
        iAdr = iRow * gMapWidth + ((iLf + 1) \ cCellWidth)
        IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSolid) THEN
          fIdealY = (iRow * cCellHeight)
          gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGroundLeft
          gActor(iActor).fVelY = 0
        END IF

        ' Right foot.
        iAdr = iRow * gMapWidth + ((iRt - 1) \ cCellWidth)
        IF (gBlock(gMapData(iAdr)).iFlags AND cBlockIsSolid) THEN
          fIdealY = (iRow * cCellHeight)
          gActor(iActor).iFlags = gActor(iActor).iFlags OR cActorOnGroundRight
          gActor(iActor).fVelY = 0
        END IF

        ' TODO: if we're on the floor, it's possible that the
        ' tile above is a slope. In that case we must push the
        ' actor up!
      END IF
    END IF

    ' Update Y coordinate.
    gActor(iActor).fY = fIdealY
  END IF
END SUB

Here's the whole code for our sloppy slope implementation, give it a try. We can tell it's getting there, but some things are not acting quite right.

Limitations of a sloppy slope implementation

Earlier we agreed that if the actor was inside a slope block and its vertical position was above the floor surface, then we wouldn't adjust said coordinate (it can happen when the actor is falling down and into a slope block.) The problem with that logic is that the few first (or last) columns of the shape may be so close to the bottom of the tile that the collision system may not register the landing.

This shouldn't be an issue IF levels are designed in such a way slope blocks are always located above at least one solid tile AND if we check for in-slopes location (and adjust the vertical offset) immediately after landing: then we WOULD register the landing on the block below the slope, test the origin (and one unit higher,) catch that the actor is actually in a slope, then adjust the vertical offset accordingly.

We also agreed that it the origin point is in a slope block, then the actor is on a slope. It's only sort of true because there's one nightmare scenario where the level designer may throw a monkey wrench in our logic (it's also related to falling:)

Thus, we shouldn't put a vertical wall directly after a slope, unless it's at least two tiles high: in that case the actor's horizontal position would be correct by the time its origin point reaches the slope.

There's another annoying issue we have to solve when going downhill. When on the ground, the actor's origin is always one unit into a solid block. When we move toward a downward slope, the origin is one unit deep into the slope block. So far so good. But when we are standing on the rightmost column of a downward slope block, the origin point is placed inside the bottom row of the slope. The problem is that as soon as the actor gets off the slope, its origin ends up in the bottom row of a non-solid cell, hovering one unit above the solid (or slope) block it is meant to be in. This means that for a short moment, the actor is no longer walking on the ground, but falling down. As the "falling physics" kick in, the actor is now made to stand on top of the flat solid block beneath the slope, meaning that it will be hovering with one feet on solid ground, the other above the void until the origin catches up into the hill. This results in a jarring effect as the actor is bumping against the floor hidden beneath the hill.

Similarly, those solid blocks beneath slopes can trigger vertical wall collisions when the actor jumps into (or worst: off) hills: when the collision is processed, the actor is not on the ground, meaning solid tiles beneath slopes are not discarded, and since slopes are non-solid until the actor is on the ground, the code detects an unwanted collision with a vertical edge. We could solve this issue without extra code by placing special slope blocks that push the actor higher than its boundaries, and into the top tile. Since it's a slope, there's no vertical wall collision, and we also wouldn't need to check the point right above the actor's origin, since the slope tile would push it up for us. Of course, that would require more attention when designing levels.

Wow. I can't believe you read it this far. Here's a corrected version of the previous code, featuring an example of irregular terrain that uses the slope collision code at no extra cost! Welcome to the Panic Restaurant, Kirby's Adventure, Felix The Cat, and Mr. Gimmick Club of Sloppy Friends! Wait, that came out wrong.