# How did LoZ: A Link to the Past handle sub-tile collisions?

The Legend of Zelda: A Link To The Past is rendered with 16×16 tiles. How did they implement collision with tiles where only a quarter or half is occupied?

You can see such tiles in the cliff corners here:

Did they use a finer grid for collision detection, like four 8×8 tiles? If so, how do the diagonally cut tiles work?

The corners of the tiles also seem "round": if Link walks into a tile's corner, he can keep on walking and automatically moves around it. How is that done?

-

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

This question came from our site for professional and enthusiast programmers.

+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
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
If you look at my answer below, you will see how it is actually done. Cheers! – James May 25 '13 at 1:56

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 (2016 edit: http://www.gamasutra.com/view/feature/3938/the_pacman_dossier.php - the section on "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
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
The link is dead, no pun intended – Vince Emigh Dec 11 '15 at 4:48

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.

-
What exactly is `Link's hotspot offset`? – Chiru Jun 3 '15 at 11:35
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 Jun 3 '15 at 20:24

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
That makes the top voted answer.. wrong – bobobobo Jun 12 '13 at 13:40

http://troygilbert.com/deconstructing-zelda/movement-mechanics/

-
thanks, pretty interesting article. – Restart Feb 10 '11 at 12:42
@OmarKooheji You should add the overview of how that works, link-only answers are worthless if the link dies. – akaltar Mar 21 '15 at 21:04
On phone now, will try to give a summary when I'm next at a PC. Also had a wee chuckle at "if the link dies" – Omar Kooheji Mar 21 '15 at 21:07
@OmarKooheji Did you forget? :) – Chris Cirefice Jul 13 at 16:37

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. – user744 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.

-

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.

-
This does not add anything that hasn't already been covered. – Josh Petrie Jun 12 '13 at 15:22

## protected by Josh Petrie♦Jun 12 '13 at 15:22

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).