Tile Collisions

Last Modified:

This post details the tile collision subsystem for my Super Nintendo game engine.

The goals of the tile collision subsystem is for it to handle:

  • A variety of map sizes
  • 45° and 30° slopes on the floors and ceilings
  • Upwards and downwards gravity

I initially budgeted 10% of the CPU time for handling entity-tile collisions, with 8 active entities (1 player character and 7 enemies), that gives me a target of 3.275 scanlines per entity. On a SlowROM cart that comes out to ~542 CPU cycles, which isn't much, forcing me to be clever in the design of the tile collisions if I want to stay in budget.

X-Axis Movement

For simplicity's sake the X and Y axis movement and collision tests are handled separately. In order to make slope movement easier, the X-Axis is processed first.

The first thing my code does is add the entity's X-velocity to its X-position. What happens next depends on the direction of movement.

If the entity is moving right, the code calculates:

  • The hitbox's top-right position.
  • The tile index of the top-right position.
  • The number of tiles from the top to the bottom of the hitbox (inclusive).

The system will then test all the tiles touching the right edge of the hitbox. If any of the tiles are SOLID, we have an X-Axis collision and the entity will be moved leftwards until the hitbox no-longer touches the tile. Left movement is same as right movement, except we test the left edge.

X-Axis movement only tests for a SOLID tile, all other tile types are ignored. This makes X-axis collision testing fast as I deliberately gave TileCollisionState.SOLID a value 0, eliminating the need for any cmp instructions in X-Axis loop.

The tiles tested in the X-Axis collision tests
X-Axis Collision Test (when moving right)

END_SLOPE Tiles

When walking up a slope, followed by a SOLID tile, we encounter a problem. The SOLID tile at the end of a slope is treated as a wall, impeding movement.

Animation showing how an X-Axis collison impeeds slope movement
X-Axis collision preventing an entity from walking up a slope

My solution to this problem was inspired by Super Metroid, the END_SLOPE tile. This tile has no collision in the X-Axis, but is solid in the Y-Axis. By placing this tile on the tall side of a slope tile the entity can now walk up slopes unimpeded.

Animation showing how END_SLOPE tile allows the entity to walk up slopes
Walking up a slope with an END_SLOPE tile

A Small Caveat

There is one major downside to this design. All slopes must be a part of the floor or ceiling. There must be a SOLID tile above/below the short end of a slope and the far end of a slope must be followed either by a slope tile or an END_SLOPE tile. Additionally, there must not be an EMPTY tile to the left or right of an END_SLOPE tile. Failure to meet these conditions can result in the entity either clipping or zipping through the slope and potentially getting stuck inside a wall.

A digram of a multi-tile slope and a list of tile restriction necessary to prevent a clip or zip
These restrictions must be met to prevent a clip or zip

Y-Axis Movement

An entity will only collide with a slope tile at the entity's X-Position. Besides the simplicity, this will allow an entity on top of a slope to suddenly reverse direction without changing their Y-Position.

Determining the height of a slope at a given position is accomplished using a lookup table and the following code:

    tileIndex = yPos / 16 * map.bytesPerRow + xPos / 16
    tileId = map.data[tileIndex]
    heightTableIndex = (xPos & 0xf) | collisionMap[tileId]
    tileHeightAtXposition = TopHeightTable[heightTableIndex]

I have carefully selected the collisionMap values to confine 17 tile types * 16 height values inside 256 bytes of data (allowing it it to be accessed with a 8 bit index register). The hi-nibble is the tile type and the lo-nibble is the entity's X-Position.

An exception occurs for the END_SLOPE tile (0x08), which shares a hi-nibble value of the SOLID tile (0x00). By logical or-ing the 0x08 with xPos & 0xf the hi-nibble is always 0, and the slope test code will treat END_SLOPE tiles as if they are SOLID.

Table of tile types and their collisionMap values
Tile Collision values for various tiles that my engine supports

Another advantage of this design is that I have 4 bits (3 for END_SLOPE tiles) of unused space to store future metatile properties.

Falling

When the entity is falling downwards, the engine will add the entity's Y-Velocity to its Y-Position and then preform a series of tile tests.

The bottom-center tile, located at position (entity->xPosition, tileHitbox.bottom), is tested first to give slope tiles priority over all other tiles. Secondly the bottom-left and bottom-right tiles are tested to see if the entity has landed on the edge of the floor. Finally the top-center tile is tested to see if the entity's head has collided with the ceiling.

Due to the tile restrictions I described earlier, there is no need to preform a slope test on the left/right tiles. We only need to check if the left/right tiles are a SOLID or PLATFORM tile, which replaces a series of costly lookups with some simple comparisons.

Tiles tested when Falling
Tiles tested when falling

Whenever a collision is detected the engine will move the entity so it is one pixel above (or below) the tile's collision area, set the entity's standing flag, and skip the remaining tile tests.

The tiles tested for upwards movement are the same as downwards movement, only flipped vertically.

Platforms

A one way platform tile is a tile an entity can when stand on, but also jump onto from above/below. As my engine will support upwards and downwards gravity I have provided two types of platforms, an UP_PLATFORM and a DOWN_PLATFORM.

Platform tiles have no collision in the X-axis and only have collision upon certain conditions.

For an UP_PLATFORM, a collision only occurs when moving downwards and the bottom of the hitbox touches or crosses a tile boundary.

For a DOWN_PLATFORM, a collision only occurs when moving upwards and the top of the hitbox touches or crosses a tile boundary.

What if we're falling too fast?

Animation of an entity clipping through a Slope by falling too fast
Clipping through a slope when Y velocity > slope height.

Whenever an entity's Y velocity is >= 2 pixels/frame it is possible for an entity to clip through a slope tile.

It's possible to fix this clip by testing if an falling entity crosses a tile boundary, and if it does, test if the tile above is a slope tile. Unfortunately my code is already close the limit of my CPU time budget and adding one more tile test would break it.

Luckily there is a clever hack to prevent slope clips. Just add a SOLID or END_SLOPE tile below all slope tiles. When an entity clips through a slope tile, the tile below will stop the fall and it will be placed one pixel above the tile boundary. On the next frame the entity will collide with the slope, and move the entity to the correct position above the slope.

Diagram showing how a SOLID or END_SLOPE tile prevents a slope clip
Placing a SOLID or END_SLOPE tile below a slope prevents slope clipping

As a downside this trick will show a single frame of the entity being below the slope. I do not believe this impair the gaming experience, but if it does I think I could hide it with a long fall squash animation or possibly a cloud particle effect.

Why do I test the top-center tile?

While testing the tile collision code I quickly discovered an entity could clip through a slope tile when it is moving with an angle < 45°.

Animation of an entity clipping through a DOWN_RIGHT_SLOPE when jumping up-right at a angle < 45°
Clipping through a DOWN_RIGHT_SLOPE when preforming a weak running jump

Eliminating the clip required me to test the top-center tile when falling downwards and test the bottom-center tile when falling upwards.

Animation showing no slope clip when jumping through a DOWN_RIGHT_SLOPE when jumping up-right at a angle < 45°
No more jump clipping

Standing

My engine uses separate logic for standing and falling to prevent the entity from bouncing down slopes.

Animation of an entity bouncing down a slope when X-Velocity is > Y-Velocity
The slope dilemma.

This bouncing occurs due to the game's weak gravity. The X-Velocity will move the entity off the slope and it takes a while for gravity to catch up and pull the entity back onto the slope.

Now there are a number of ways to handle the slope dilemma, but I have picked the simplest. The engine will ignore the entity's Y-Velocity whenever it is in a standing state. The only way a standing entity's Y-Position can change is by slope collision.

When an entity is in a standing state the engine first tests the bottom-center tile to see if the entity is walking up a slope. Then the tile below the bottom-center is tested to check if the entity is walking down a slope. Finally the bottom-left and bottom-right tiles are tested to see if the entity is on a ledge.

When a collision occurs, the entity's Y-Position will be moved so it is above the slope/tile. If there is no collision, the entity's standing flag is cleared and the entity will start falling on the next frame.

The four tiles tested when standing
Tiles tested when standing
Tiles tested when walking up a slope
Walking up a slope
Tiles tested when walking down a slope
Walking down a slope


As an optimisation I have eliminated the slope and platform position tests from the MovingDown_Standing code. While this does speed up the code considerably, it causes the entity to zip if it walks into the tall side of a slope tile.

Animation of an entity zipping when walking into the tall side of a slope
Walking into the tall side of a slope causes zips

Another zip involves the entity walking off a SOLID tile into the narrow side of a slope tile.

Animation of an entity zipping when walking off a SOLID tile into a slope
Walking off a SOLID tile onto a slope tile causes zips

I could add a some checks into the tile collision routines to handle these zips, but that's slow. Instead I've decided to prevent these zips from ever occurring by forbidding them in untech-editor. If any of these forbidden tile patterns are found the editor will refuse to compile the map, preventing the entities from zipping or clipping into slopes.

Closing Remarks

Did I meet my CPU budget? I'm a hair's breath over the limit. For a 12x24 hitbox the Tile Collision code uses an average of 3.30 scanlines when falling and 2.96 scanlines when standing. Luckily the CPU budget is just a guideline and contains a bit of wiggle room.

Could I make the collision code any faster? Yes. The main bottleneck is converting a position to a tile index. By switching the room size to a fixed width or height I could eliminate some slow multiplications, possibly improving the speed of the code by about 20%. I'm not sure if I'm going to implement this speedup, as I would like my engine to support a wide variety of room sizes.

My next task is to figure out an efficient way to link the Joypad input, MetaSprite Animation subsystem and the Tile Collision subsystems together.