The Allegro Wiki is migrating to github at https://github.com/liballeg/allegro_wiki/wiki

Collision detection

From Allegro Wiki
Jump to: navigation, search

Introduction

Arguably the most important aspect of incorporating a system for collision detection into a design document or product is choosing the technique that best suits your particular project. Collision detection is a vast and often confusing topic. While one particular method may suit a project perfectly, it can also be entirely illogical for another. After all, a roguelike isn't likely to need a pixel-perfect implementation, while a game incorporating an advanced physics engine may well require something slightly more precise. At the end of the day, choosing a method for collision detection involves considering the key aspects of your projects gameplay and weighing them against your various computational constraints. This is kind of a broad question; depending on what kind of game you make, there are various kinds of collision detection and collision response.

First thing first, though; you don't do collision detection on "sprites". A sprite is a bitmap, you use those for drawing, while collision detection is part of the game logic, that means that you could create a complex collision detection system without seeing not even one image. In case you haven't heard the mantra before, here it is: "Separate logic from drawing".

That said, it depends on what kind of game you're making and how you represent the colliding objects. The most straightforward way of doing collision checks is bounding boxes and bounding spheres. It should be fairly easy to find examples and explanations of both using google. These are probably good enough for any game you can handle now (bounding boxes were good enough for most of the Super Mario series); but if you want to go deeper, you can look into the Separating Axes Theorem, represent your entities as more complex shapes such as polygonal outlines, pixel masks, or combinations of multiple boxes or spheres. For any of these more complicated checks, it is best to do a simple sphere or box test first to rule out obvious non-collisions.

There's also the problem of algorithmic complexity. Using a brute force approach, you have to check every possible pair of entities against each other, which means the number of checks you have to do grows quadratically with the number of entities - for 10 entities, you have to do 100 checks, for 20 you have to do 400, for 100 you have to do 10,000. This is often expressed in 'Big O Notation', as O(n²). If you have only a handful of entities, this is no problem, but usually, you want to support more than a dozen. Here's what you can do about it:

  • If you are checking against a tilemap, there are only very few positions on the tile grid that any freely moving entity can occupy at the same time - if the entity is not larger than a tile, then that number is 4, and finding these 4 tiles is pretty easy (top-left position in tile space, plus zero or one in any direction)
  • A simple way of weeding out trivial non-collisions is axis sort: Sort all your entities along one axis, e.g. the x-axis; to check for collisions for any entity, walk the list to the left and to the right until you find an entity that is farther away than the maximum size of any entity.
  • More complicated approaches are sector-based collision detection and quadtrees. They are harder to implement, but also way more efficient. You should only worry about these if the above don't give you good enough results.

Bounding Box

Main article: Bounding Box

While not the fastest method of collision detection (and not technically even a method for collision detection), Bounding Box (BB) is often a favourite among many developers. Put simply, this technique involves checking whether an object has intercepted (overlapped) an invisible square boundary that is usually placed over, and often remains relative to, a game object.

Separating Axis Theorem (SAT)

This method of collision detection provides collision detection between convex shapes. The SAT method takes much more computing power than the bounding box method, and is much more complex. This is useful in games which require slanted surfaces, which BB colision detection fails to accomplish. An article is yet to be written about impementing SAT on this wiki, as far as I know (September 6th, 2008).

Pixel Perfect

Stub.