# How was collision detection handled in The Legend of Zelda: A Link to the Past?

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.

-
+1 for making me nostalgic – Mike Feb 9 '11 at 15:35
See also this possibly-related question: gamedev.stackexchange.com/questions/7305/… – Josh Petrie Feb 9 '11 at 16:56
I always wondered how they did the original Zelda's collision. It felt more pixel perfect than LttP's – Jeff Feb 10 '11 at 13:14
Just curious... why is there a 40 in the graphic on the front door? – Corey Ogburn Jun 21 '11 at 17:00
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 Jul 11 '11 at 20:54

## migrated from stackoverflow.comFeb 9 '11 at 16:25

Given the memory limitations of the SNES, the solution must be very simple.

My guess is that they have another 16*16 grid that tells you how to handle collision in the tile. A tile can be:

• Empty
• Full (i.e. a square block collision)
• Half-full-1 (a diagonal top-left to bottom-right line collision)
• Half-full-2 (a diagonal top-right to bottom-left line collision)

So, when Link moves, the game engine checks the surrounding tiles and applies the collision logic for them, according to the collision grid.

Of course, I didn't disassemble the Zelda sources, I'm just saying how I would do it.

And the "roundness" of the corners is just an illusion - some special code written to make them feel that way. Developers have been doing it since the Pac-Man years:
http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#CH2_Cornering

As you see, even though the maze's topography is both tiled and super simple (only squares), a technique like smooth turning can be simulated by creating an optical illusion (square tiles with round textures) and some clever code (beginning a turn before the end of the tile).

-
I see but if you look at the picture above, the bottom right of the hill should exist out of Half-full-2 tiles. but how did they make the fence? it's somewhat diagonally but it's like the tile is split in 4 and 1/4 is free to walk in, the rest is occupied – Restart Feb 9 '11 at 15:49
It's possible they have more types of collision tiles. Like "left-half is full", "top-left, top-right and bottom-left is full". Or, they have only 4 types of collision tiles but the collision grid has an 8*8 resolution, instead of 16*16 – x10 Feb 9 '11 at 15:53
would it be possible to make diagonally half 16x16 tile collision when using an 8x8 grid? – Restart Feb 9 '11 at 15:57
Yeah, just make an 8*8 Half-full-2 tile at (x,y) and then another Half-full-2 tile at (x+1,y+1). Possibly a Full tile at (x, y+1) – x10 Feb 9 '11 at 15:59
@Restart OGMO Editor supports tiles with different sizes: ogmoeditor.com. The getting started tutorial explains things rather well: ogmoeditor.com/help/getting_started/index.html – bummzack Feb 10 '11 at 8:18

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 Feb 9 '11 at 20:42
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 Feb 9 '11 at 22:01
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. Feb 20 '11 at 20:59
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. Feb 20 '11 at 21:02

http://old.troygilbert.com/2006/10/the-movement-and-attack-mechanics-of-the-legend-of-zelda/

-
thanks, pretty interesting article. – Restart Feb 10 '11 at 12:42

This is how it is actually done:

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.

-

The map grid has large (apparently 16x16 pixel) elements, probably so that it can be stored efficiently on the limited ROM cards of the SNES/Super Famicom by reusing tiles. But if you observe the game closely, you'll notice the sprites move on a much more fine-grained grid. (Try sticking your sword out and notice that an enemy can bump into it and get hit, even when it's on the border of two tiles.) This was already true in the original Legend of Zelda.

-
That's not necessarily true. Even most of the games today have imprecise collision detections, but visual tricks cause you to think they are pixel-perfect. Given the amount of RAM in a SNES, I don't think pixel-perfect collision would even be possible. – x10 Feb 9 '11 at 15:51
Pixel-perfect collision detection was actually far more common on NES/SNES/etc era hardware because the framebuffer, as it was, was more closely linked to the game logic, and sprites were a hardware primitive rather than one application of quad texturing. The equivalent approach today would be using occlusion queries. – Joe Wreschnig Feb 9 '11 at 18:45

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.

-