I needed a method of collision detection for shooting bullets that worked very fast. Rely on checking every movie clip between lots of other movie clips (such checking a small bullet object moving Every Frame of the bullet’s existence) wouldn’t have worked as there would have been gaps where the bullet moved too fast between frames.
It would have also been nice to ‘shoot’ and get a reference to either ‘null’ if I had hit nothing, or a reference to the object I hit directly, instead of just a true or false.
There are lots of methods to do this, but what I decided to go with was by using ray-casting to solve my problem. This site is useful in showing the concept and theory behind it: http://www.permadi.com/tutorial/raycast/index.html
There are many articles on ray-casting for rendering purposes (such as the one above), however I was interested in it for collision detection purposes only (in retrospect I can see that collision detection plays a large part of the rendering algorithm and extends off it). As a result, I had to figure out and pick my way through the articles and trim out the rendering/drawing algorithms and figure out just the collision detection part.
The following here is what I’ve managed to piece together from various sources as well as some invention on my part. With that said, it may not be 100% accurate, feel free to send in comments, questions, and corrections.
Casting The Ray
Basic idea is you cast a ray out and trace along it until it hits an object or reaches a max defined length/limit. The ray is just a vector on a grid, which is the ‘world’. The world must be split up into a grid/sections to make it easier to process. Collision objects would ideally lie inside 1 or more grid boxes. The goal is to find out, which grid boxes the ray intersects, resulting in a hit.
Recall the equation of a line and calculate it for the ray above: origin is (0,0) and the target is (10, 3)
Line equation: y = mx + b
Calculating ‘m’ (line’s slope): m = (y2 – y1) /(x2 -x1) =(3 – 0) / 10 – 0) = 0.3
Value of b (the y-intercept) is 0, since the origin of the ray above happens to be (0, 0)
(If the origin of the ray was not (0, 0), b can be calculated by plugging in the known numbers so far and calculating for b)
Result: y = 0.3x
Tracing the ray – Which points to look at
From here, the next step would be to ‘trace’ along the ray to determine the points where the ray intersects a grid box. One way to do this can be to step through the ray at predefined intervals/segments, checking to see which grid box the ray is in at that point. However this could result in a near infinite amount of points to check as each segment could be divided by half and again depending on the resolution/accuracy. Also, some points may also lie inside a grid box twice, resulting in the same grid box being checked twice.
Don’t check along a regular interval… as there are too many spots to check. Each spacing between each interval can also be divided over and over resulting in near infinite points to check:
Instead we only need to check the moment a ray hits a grid box’s boundary. This reduces the total points to a much more manageable number and still no grid boxes are missed. A much simpler method would be to only check the point a ray hits/enters a grid box:
At this point you need to know how to calculate the points of intersection on the ray as it hits a grid box. To make it a bit easier, you can separate all the Y intercepts and all the X intercepts.
Tracing the ray – Calculating each point
You can see now that at every single X intercept, Y is an integer. To get the first X intercept, Y is equal to 1. To get the next, Y is equal to 2, etc. Vice versa for the Y intercepts.
Plugging in the known number of each point into the line equation calculated above for the ray will give the exact point of intersection:
The next step is to do this ‘in order’ since you want to know which object/grid box the ray hit first. To do this, you ‘step’ along the ray checking the points in order from the origin.
One way we can do this is to calculate the distance of the first x and y intersection point and comparing the distance fro the origin to see which is smaller. Then which ever one is smaller (the Y or X intersection point), calculate the next intersection point along that same axis then recheck which point’s distance is smaller. Whichever point’s distance is smaller is the next point along the ray.
Recall pythagorean theorem for calculating distances: A * A + B * B = C * C, where A and B are the sides of the right angle triangle and C is the hypotenuse. To get the distance of the right angle triangle formed by the point X, Y, simply go: distance = ?((X * X) + (Y *Y))
Example of calculating the distance for a point. Note the right angle triangle created by the point (in orange):
Stepping/tracing along the ray:
- Calculate the distance of point X1 and Y1 first.
- Note that in the example, X1 is smaller then Y2, so X1 is the first point along the way. Then calculate the distance for the next point ‘X’ point (X2).
- Comparing X2 to Y1, X2 is smaller, so X2 is the next point along the ray.
- Calculate X3 next.
- Comparing X3 to Y1, X3 is still smaller, so X3 is the next point.
- Calculate X4 next.
- This time Y1 is smaller then X4′s distance so Y1 is the next point along the ray. Calculate the next ‘Y’ point now (Y2).
- Comparing X4 and Y2, X4′s distance is smaller then Y2′s distance, so X4 is the next point along the ray.
- Repeat until the end of the ray is reached.
At every point calculated, the coordinates of every grid box intersected by the ray can be found, so at this point, a quick check inside the contents of the grid box can indicate if the ray has hit something. If not, simply keep going until the ray reached some max distance/range, or if the ray hits a ‘wall’ object.
Further note 1
Since taking the square root can be an expensive operation, it can actually be omitted as we only need to know which distance is smaller, we don’t care about the exact precise distance.
Instead of going: sqroot((X * X) + (Y *Y))
It can just be: (X * X) + (Y * Y)
Further note 2
There is 1 further method of calculating the intersection points. Some may notice that point X(n) is equal to X(1) * n, and Y(n) is equal to Y(1) * n.
Thus, an alternative method can be used: instead of calculating each point from scratch and that is to simply treat each point as increments past the first point. To step through each point in order (instead of multiplying), you could additively add on 1 point on top of the other to get the next point: X(n) = X(1) + X(n-1) and Y(n) = Y(1) + Y(n – 1)
Condensed summary of steps
- Cast the ray
- Calculate the formula of the line
- Calculate the distance of the first ‘x’ point and the first ‘y’ point. (X = 1 and Y = 1)
- Step through each point, checking the grid cords if an object exists in that gird square.
Example
(implemented using both notes)
Some algebra
Basic line formulas:
For Y (most common form): y = mx + b
For X (based on the above): x = (y – b) / m
Calculating m (line slope): m = (y2 – y1) / (x2 – x1)
Combine with Pythagorean theorem (C * C = A * A + B * B, where A and B is an X, Y value):
Distance for a ‘y’ intercept point, where y = 1, 2, 3…
distanceY = ((y – b) / m * (y – b) / m) + (y * y)
(ignoring the square root)
Distance for a ‘x’ intercept point, where x = 1, 2, 3…
distanceX = (x * x) + ((mx + b) * (mx + b))
(ignoring the square root)
