Just out of pure curiosity, I'm wondering how classic 2D games of the 80s/90s (The Legend of Zelda, Super Mario, Warcraft, ...) approached collision detection/resolution.

For some reason I can't picture them doing things like a separating axis test, or using lots linear algebra anyway. Do correct me if I'm wrong, but all that seems to have appeared with 3D graphics.

The alternative I can come up with is the kind of algorithm I came up with in my earlier games; basically some home-grown AABB test. I wouldn't get any information about the time of impact, so to resolve collisions, I had to write some rather fiddly, bug-prone code.

(Thinking a bit about it, I could have made my characters move in fixed step sizes and position all objects as multiples of that, I suppose. Resolving a collision would simply be a matter of undoing the last step. But that seems quite limiting, and a bit difficult to implement with dynamic frame rates.)

Does anybody know how collision detection/resolution was commonly done back in the day?

Edit: Came across this, it's quite interesting: http://higherorderfun.com/blog/2012/05/20/the-guide-to-implementing-2d-platformers/

  • \$\begingroup\$ I recently wrote a clone of Atari's classic Breakout game using exclusively assembly language, and the collision detection was simple pixel based bounding box tests. Due to the simplicity of bounding box sat algorithms, it would make more sense to implement something like that, than it would per pixel collision detection for convex shapes. \$\endgroup\$ – Evan May 7 '13 at 3:14
  • 1
    \$\begingroup\$ This is not an answer, but I'd like to point out that using a bounding box is functionally the same as writing a separating axis test. Linear algebra works in two dimensions just as well as in three. It didn't appear with the advent of 3D (or any other videogame generation), it appeared because math is supposed to make things easier. In my opinion, using it in 2D is simpler than individually fiddling with both dimensions. \$\endgroup\$ – Seth Battin May 7 '13 at 3:28
  • \$\begingroup\$ heh, yeah. the math came later :p \$\endgroup\$ – GameDev-er May 7 '13 at 18:36

First of all, let me say that most calculations were done with integer maths because without FPUs real values were slooooooow.

I'd say that in the vast majority of cases it would be axis aligned rectangles, simply because that is the fastest way, which as Seth pointed out, is just a special case of separate axis testing.

In some cases collisions would be with circles, but when doing that the square of the distances were used to avoid square roots. These were very slow back in the day, and although it's not such an issue today, it's still done this way because why do unnecessary work?

A faster but far less accurate distance measure is using 'manhattan distance', which is simply abs(dx)+abs(dy). This might be used for coarse collsion detection before a more expensive version.

I doubt per pixel testing was ever used since it is very costly, except for simple sampling, such as the ground beneath rodent feet in Lemmings.

  • \$\begingroup\$ And how about collision resolution/response? \$\endgroup\$ – futlib May 7 '13 at 5:34
  • \$\begingroup\$ It highly depends on the type of game. I'd say that is pretty similar to today, separate for no penetration and then modify velocity. Although many games didn't use velocity, just update position directly. \$\endgroup\$ – DaleyPaley May 7 '13 at 5:40
  • \$\begingroup\$ @futlib forums.nesdev.com/viewtopic.php?t=8984 \$\endgroup\$ – Sidar May 7 '13 at 8:11
  • \$\begingroup\$ @DaleyPaley But how to separate for no penetration? That's the tricky part if there wasn't a standard way to calculate the time of impact (which seems to have come up in the 2000s from what I see). \$\endgroup\$ – futlib May 7 '13 at 12:09
  • \$\begingroup\$ penetration.x = abs(position1.x-position2.x)-(size1.x+size2.x)/2 If the value is negative you have penetration. You need to check which side it's on (if(position1.x>position2.x)) And the same with the y (choose the axis with the largest penetration) Finally, separate by moving them away from each other a distance of penetration/2 \$\endgroup\$ – DaleyPaley May 7 '13 at 12:52

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