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.
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
TileCollisionState.SOLID a value 0, eliminating the need for any
cmp instructions in X-Axis loop.
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.
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.
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.
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
xPos & 0xf the hi-nibble is always
0, and the slope test
code will treat END_SLOPE tiles as if they are SOLID.
Another advantage of this design is that I have 4 bits (3 for END_SLOPE tiles) of unused space to store future metatile properties.
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
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.
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
standing flag, and skip the remaining tile tests.
The tiles tested for upwards movement are the same as downwards movement, only flipped vertically.
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.
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.
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.
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°.
Eliminating the clip required me to test the top-center tile when falling downwards and test the bottom-center tile when falling upwards.
My engine uses separate logic for standing and falling to prevent the entity from bouncing down slopes.
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
flag is cleared and the entity will start falling on the next frame.
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.
Another zip involves the entity walking off a SOLID tile into the narrow side of a slope tile.
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.
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.