share
Game DevelopmentHow was collision detection handled in The Legend of Zelda: A Link to the Past?
[+171] [5] Restart
[2011-02-09 15:20:09]
[ 2d collision-detection nintendo ]
[ https://gamedev.stackexchange.com/questions/8336/how-was-collision-detection-handled-in-the-legend-of-zelda-a-link-to-the-past ] [DELETED]

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.

enter image description here

(4) See also this possibly-related question: gamedev.stackexchange.com/questions/7305/… - Josh
I found this article some time ago about the movement mechanics in Zelda. I think it answers your question: troygilbert.com/deconstructing-zelda/movement-mechanics - Omar Kooheji
(2) I always wondered how they did the original Zelda's collision. It felt more pixel perfect than LttP's - Jeff
Just curious... why is there a 40 in the graphic on the front door? - Corey Ogburn
(1) I found this map in google: zs.ffshrine.org/link-to-the-past/maps/light_world-1.png. All the doors are numbered, I guess it's to specify locations or something. I just needed textures, didn't really paid attention to the numbering on the doors. :) - Restart
(1) If you look at my answer below, you will see how it is actually done. Cheers! - James
[+93] [2012-09-07 05:04:25] James

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.


(4) What exactly is Link's hotspot offset? - Chiru
(4) Hotspots are single pixels that are tested for collision instead of using collision rectangles. The hotspot offset is the number of pixels along each axis that the collision point is offset from the center of the character. - James
1
[+40] [2011-02-09 20:12:44] Bryan Elliott

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.


so it's a pixel-perfect collision detection with the tiles? - Jari Komppa
(1) ok so that's for sprite collisions right? and then background collisions are presumably checked through an 8x8 collision grid on top of the 16x16 tile grid right? that would cover about all collisions in the game right? - Restart
(5) This was very true for the C64, which had sprite collision interrupts. The NES had a Sprite0 Hit Flag, but I'm under the impression it was very limited, and the SNES and GBA had no hardware collision detection. Blargg on nesdev brings up that this is likely because tile layers can overlap sprites. - T.R.
(1) Nesdev collision detection discussion - nesdev.parodius.com/bbs/… NES hardware specification (search "collision" to find relevant parts) - nocash.emubase.de/everynes.htm C64 collision detection - c64-wiki.com/index.php/Sprite#Interrupt_on_collision - T.R.
(1) That makes the top voted answer.. wrong - bobobobo
Sorry :) Back then I didn't know how the SNES handles sprite overdraw on the hardware level. Although, looking at the other answers in this thread - it seems my educated guess was in fact a fairly decent approximation of what the developers did(i.e. they didn't actually use pixel-perfect collision, but 8x8 grids). - x10
2
[+1] [2011-02-09 21:55:39] user5304

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.


3
[+1] [2013-06-08 08:17:41] a_guest

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.


4
[+1] [2013-06-11 18:15:49] Roger Levy

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.


This does not add anything that hasn't already been covered. - Josh
5