I would like to know how the collision detection was done in The Legend of Zelda: A Link To The Past.
The game is 16x16 tile based, so how did they do the tiles where only a quarter or half of the tile is occupied? Did they use a smaller grid for collision detection like 8x8 tiles, so four of them make one 16x16 tile of the texture grid?
But then, they also have true half tiles which are diagonally cut and the corners of the tiles seem to be round or something. If Link walks into tiles corner he can keep on walking and automatically moves around it's corner. How is that done?
I hope someone can help me out here.
This is how it is actually done:
[NOTE: I have reverse engineered this game]
For collision detection, on a given screen in the Overworld, Link's hotspot offsets are used to calculate which 32x32 block(s) he occupies. Each block is defined by four 16x16 blocks. Likewise, each hotspot offset is further divided to determine which of these 16x16 blocks each hotspot occupies.
Each 16x16 block comprises of 8x8 blocks that reference actual graphic cells in VRAM. A reference table exists that maps each available 8x8 block to a collision type. The collision type is a single byte value that defines both how to handle collisions with the tile (stop movement, allow jump down, allow lifting, ladder, etc.) This byte also defines which portion of the tile is traversable. A simple height map is used to define each shape. The height map defines a single one-way solid area as 8 bytes from 0 to 8. While not space efficient, it is speed efficient.
In summary, collision is handled at the 8x8 cell level, where each 8x8 cell has a collision type and shape defined for it that matches it's traversable area and actions that can be taken upon it. Collision shapes are handled with simple, reusable 8 byte height maps.
Link's hotspot offset
? - Chiru
I actually know this. It's common in all SNES games.
The hardware framebuffer redraws all of the sprites on every frame. If, while redrawing, a sprite draws over another sprite's pixel, if results in an event. The sprite quadtree is then scanned to figure out which one was actually impacted.
A suggestion to do pixel based collision detection:
Sprites are rectangular right? it's the drawing minus the alpha in a rectangular image. So the first check is to see if any 2 rectangle sprites overlap any number of pixels in the screen area, which is fairly simple.
If this is true: Do a check for each non-alpha pixel of sprite 1, to see if it is sharing the the same (X,Y) coordinate of the screen with of any other non alpha pixel from the colliding sprite B.
A faster method of detecting collision would be hardware per-pixel collision detection. I am sure that the graphics chip of the SNES can detect per-pixel collision between any sprites, like the old 8 bit consoles. So an efficient method would be to create a sprite, make it look like the tile(s) Link is heading towards and check the sprite collision detected by the graphics chip. A disadvantage of that method is that SNES doesn´t have endless sprites. But that would be super fast per-pixel collision detection.
The collision was probably defined in 8x8 blocks - each 16x16 tile containing 4 such blocks. The blocks may have selectable shapes besides "all non solid" and "all solid" such as diagonals and "can jump down from" to implement ledges, from all 8 directions. The game certainly maintained a separate invisible layer for collision tiles rather than doing any kind of pixel-perfect collision - the SNES had no hardware provisions for sprite collisions besides being definitely too much for its ~3mhz CPU to handle.