Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question

migrated from stackoverflow.com Feb 9 '11 at 16:25

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

58  
+1 for making me nostalgic –  Mike Feb 9 '11 at 15:35
4  
See also this possibly-related question: gamedev.stackexchange.com/questions/7305/… –  Josh Petrie Feb 9 '11 at 16:56
1  
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
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 Jul 11 '11 at 20:54
1  
If you look at my answer below, you will see how it is actually done. Cheers! –  James May 25 '13 at 1:56
show 1 more comment

9 Answers 9

up vote 59 down vote accepted

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).

share|improve this answer
    
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
3  
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
1  
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
1  
@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
show 8 more comments

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.

share|improve this answer
    
so it's a pixel-perfect collision detection with the tiles? –  Jari Komppa Feb 9 '11 at 20:42
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 Feb 9 '11 at 22:01
2  
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
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. Feb 20 '11 at 21:02
    
That makes the top voted answer.. wrong –  bobobobo Jun 12 '13 at 13:40
show 1 more comment

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.

share|improve this answer
add comment

I found this article some time ago about the movement mechanics in Zelda. I think it answers your question:

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

share|improve this answer
2  
thanks, pretty interesting article. –  Restart Feb 10 '11 at 12:42
add comment

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.

share|improve this answer
    
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
12  
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
This does not add anything that hasn't already been covered. –  Josh Petrie Jun 12 '13 at 15:22
add comment

Let’s start our deconstruction with the most basic feature of the player’s character, Link: his movement. Link’s movement displays a surprising amount of subtlety. If you play The Legend of Zelda for a while, you’ll notice that Link doesn’t ever get hung up on obstacles due to unexpected collisions, nor do you ever just miss a bad guy by a pixel or two when attacking him. Yet at the same time, you’ll notice that Link moves fluidly through the gameworld; even tough the environment is tile-based, you can tap the directional pad and link will move a single pixel in that direction. If you’re moving to the left and decide to go up, down or right, Link instantly moves in that other direction when you change directions on the gamepad

What’s happening here is a very neat trick. While Link can move a single pixel at a time, in any direction, the longer he continously moves in any direction the more he gravitates toward aligning himself with the underlying grid of the screen. The tile grid for LoZ is 16 tiles wide by 14 tiles high (including 3 tiles for the status display at the top of the screen). Each tile is 16×16 pixels. Link operates on a half-tile grid, though (32×28 tiles, 8×8 pixels each). As Link moves, if he’s not currently aligned with the half-tile grid, he is adjusted, one pixel at a time, toward the closest correction. As a result, if Link is 4 pixels off alignment he’ll line back up with the grid after moving 4 pixels.

share|improve this answer
add comment

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

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.