NDS/Tutorials Collision Detection
From Dev-Scene
There are most probably other, more advanced ways to detect collisions than the ones listed here. If you know of any, please add them!
Contents |
[edit] 2-D Collision Detection
[edit] Intersecting Rectangles
This method encloses two objects in rectangles and tests to see if the rectangles intersect. This works most perfectly for objects that are actually rectangular, but because this is one of the simplest (and fastest) ways to do collision detection, game programmers often use this for non-rectangular objects as well, where perfect accuracy is not required.
There are two cases where two rectangles could collide:
- A point from one rectangle is contained in the other.
Figure 1
A way that rectangles can intersect. Note that a corner point of Rect A is
inside Rect B, and vice versa.
+-------------+
| Rect A |
| |
| |
| +-----|--------------------+
| | | Rect B |
| | | |
+-------------+ |
| |
| |
+--------------------------+
- Adjacent points on one rectangle flank the other rectangle, so that a border from one rectangle crosses completely over the other rectangle.
Figure 2
Another way that rectangles can intersect. Note that although none of the
corner points are enveloped by another rectangle, each rectangle has corner
points on two opposite sides of the other rectangle. However, if just one
border breaks one border of the other rectangle, that is sufficient to show
that the rectangles intersect.
+------------------+
| Rect A |
| |
| |
| |
+------------------------------------+
| Rect B | | |
| | | |
| | | |
+------------------------------------+
| |
| |
+------------------+
The only case where the second case could be triggered and not the first is a situation similar to that of Figure 2, where the rectangles from something like a plus sign (+). If the rectangles are too wide or tall for one rectangle to completely cross the other like Figure 2 in one animation frame, type 2 checking could possibly be ignored because it would never be triggered without already triggering type 1. However, for the sake of portable code, it may be best to include type 2 checking because even with its inclusion, checking two rectangles for intersection is trivial.
Rectangle intersection can also be used to "short-circuit" algorithms for more CPU-intensive collision detection. That is, you could have your program check potential intersections using more advanced algorithms *only if* this simpler rectangle intersection algorithm returns true. For example, you could have a function like this:
bool intersect(Sprite a, Sprite b) { if (simpleRectanglesIntersect(a, b)) return moreComplexIntersect(a, b); else return false; }
Or, more simply:
bool intersect(Sprite a, Sprite b) { // let the && operator do the short-circuiting return simpleRectanglesIntersect(a, b) && moreComplexIntersect(a, b); }
Since most game objects only collide for one frame before disappearing, this short-circuiting method can make the game run much faster.
[edit] Pixel Collision
This method individually checks every pixel in both objects to see if they occur at the same point.
In general, don't ever use this brute-force method if you can help it. While it is perfectly accurate, it is *extremely* *slo-o-ow*. There are usually better, similarly accurate methods like row-rectangle intersection.
[edit] Row-Rectangle Intersection
Usually, an image can be split into one-pixel-high rectangles traversing the object horizontally, as in Figure 3:
Figure 3
A shape can usually be reduced to a bunch of thin, horizontal rectangles.
###### ======
############ ============
############## \ ==============
################ ========\ ================
################ ========/ ================
############## / ==============
############ ============
##### ======
Most frequently, there is only one such rectangle per image row. If each of these rectangles are checked instead of individual pixels, the algorithm could be much faster. This is because entire rows are checked at the same time.
Figure 4
A rocket collision with a ball. Using row-rectangle intersection, the collision
would be detected at the balls' second row from the top or at the rocket's
fourth row.
==
==
====== ==
=======#####========================
======########=======================
=========#######======================
================ ==
============== ==
============ ==
======
This algorithm can be very efficient, as far as pixel-perfect algorithms go. Don't make it complicated; checking each row in ballSprite against each row in rocketSprite is horribly inefficient, taking ballSprite->size.y*rocketSprite->size.y row checks to complete. Instead, by using ballSprite->origin.y - rocketSprite->origin.y, you can do one-to-one comparisons between the rows. This is much more efficient; the number of row checks necessary is min(ballSprite->size.y, rocketSprite->size.y) at maximum.
The simple row-rectangle method, however, is not able to check for "armpits" in the image or interior gaps. If such detection is necessary, a more advanced version of this algorithm could check multiple rectangles per row to account for such interior gaps.
In any case, due to the tediousness of hand-coding collision maps for each image (suppose the image is changed?) it is recommended to have your program generate these collision maps automatically from the image files before before collision detection is necessary (like at game load, or even at compilation time using a specialized program to generate header files containing this information).
[edit] Rectangle Subdivision
Here, each image is separated (preferably by an algorithm; I wouldn't want to do this by hand) into major rectangular components:
Figure 5 Sometimes, a shape can be divided into a few large rectangles. ### +-+ ### | | ### +-+ ###### \ +----+ ###### ========\ | | ###### ========/ +----+ ############# / +-----------+ ############# +-----------+
Each of the rectangles in each shape are then checked against each other using plain vanilla rectangle intersection. If shape A has n subrectangles, and shape B has p subrectrangles, this operation requires n*p rectangle intersection checks.
Depending on the number of subrectangles (like if n*p is more than A->size.y or B->size.y), it may eventually be more efficient to use row-rectangle intersection instead, because fewer checks would be required, and each check is simpler to execute.
[edit] R-Squared Method
If primarily circular objects are being tested (as in a billiards game), it is possible to check for collisions using inequalities derived from the Pythagorean Theorem, which is:
(1) x2 + y2 = r2
Where r is the radius of the circle, and (x,y) is some point exactly on the circle's circumference.
A point P(x,y) is inside the circle if this inequality is true:
(2) Px2 + Py2 ≤ r2
Since taking the square-root of a number is very computationally expensive, we can get away with simply comparing the squares of the numbers as shown above in (2). This check can test a circle for collisions with rectangles, points, and other circles.
For rectangles, it is necessary to check the nearest border and corner point for intersection. The inequality for checking the corner point was related in (2). For checking the closest rectangle border ( (rx, y) or (x, ry) ) if the circle center is (cx,cy) the inequality is:
(3a) rx2 + cy2 ≤ r2 -- if the border is vertical
(3b) cx2 + ry2 ≤ r2 -- if the border is horizontal
On an ARM9 processor, integer multiplies take between 2-7 times as long as addition, which is not too bad. I wouldn't be afraid to check all the corners and borders for intersection.
For two circles A and B, the inequality is:
(4) (Ax - Bx)2 + (Ay - By)2 ≤ (Ar + Br)2