Edit (19/01/2013)
I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.
Firstly
The post is not going to explain how the chosen algorithm works, although I might cover the basics. I’m going to leave understanding of the algorithm and code up to the reader. Hopefully it’s not that complex, though.
Why Re-Write It?
I re-installed Visual Studio today, and started itching for something to code. Then I remembered that a friend had recommended that I write a program containing my collision detection code to show it off.
Apparently, the pseudo-code and explanation I’d produced for it was quite good.
So, I decided to turn the pseudo-code into actual code. Thinking it wouldn’t take too long, I sat down at my pc and started coding. Providing the background music was Miles Davis (specifically the album ‘Sketches of Spain’, which I recommend to anyone).
I decided that I’d produce some code in C. But Visual Studio doesn’t have support for C, so I decided to give it a go in C++ instead.
Seeing how C++ is just an extension of C (clever naming convention, eh?), it shouldn’t be that different. Especially since I didn’t use any custom objects.
Two hours later, I emerged from my coding “deluge” with a a whole slew of twitter/facebook messages (I tend to zone out when coding) and some working code… sort of.
The Algorithm
It worked, but not entirely as expected. There was a problem with the internal logic, which I quickly fixed (more on this can be found in the change log, linked at the end of this post). Firstly, though, the algorithm.
When we look at a graph with 2 straight lines plotted on it, we can see instantly if the lines intersect (if they cross over each other) at some point. For instance:
Lines 1 and 2 intersect at the point (3,2), we can see this by looking at the image
Looking at the image, we can see that lines 1 and 2 intersect at the point (3,2). We can see that, because we humans have a power that a computer doesn’t: We can see the image as a whole, whereas the computer would see that image as a collection of pixel locations. So how do we get the computer to look for an intersection?
Firstly, we must decide if there is an intersection. There’s no point checking all of the individual locations if we don’t know whether there is a collision or not, as this is very costly (in CPU time); especially since the image area is likely to be rather large. After we’ve decided that there’s a collision, we’ll look for a point of collision.
There are lots of different ways to do this and each has their own benefit. A simple system, for instance would be to check the x value of some point against the x value of some other point. If those points match, check the y values. If they match, then there has been a collision. This is really simple to write, and very simple to read.
[sourcecode language=”cpp”]
bool checkForCollision () {
if (myXValue == someOtherXValue) {
if (myYValue == someOtherYValue) {
//a collision has occured
}
}
}
[/sourcecode]
The problem with this is that every single x value position needs to be checked, at least, once.
Another way would be to create a bounding box. This is slightly less simple, but easier on the cpu. Basically the idea here is to create a list of points around your object and check those against the positions around the other objects. Here is an article on wikipedia about bounding boxes.
The method I chose was to think of the entire screen as a graph. Working with a start and end position for my objects instead of a single set of x and y values, I can create a virtual line that goes through the space each of the objects takes up. Then, by using some, high level, maths we can find out whether any of these lines have crossed.
Look again at these lines
Line 1 consists of two sets of points, (1, 1) and (4, 3) and Line 2 consists of the points (1, 4) and (4, 1). by taking these points and throwing them at a mathematical formula, we can tell if they intersect. By the way, there are 4 formulae to work this out.
- x intersection point = x1 + ua (x2 – x1)
- y intersection point = y1 + ua (y2 – y1)
- ua = (x4 – x3)(y1 – y3) – (y4 – y3)(x1 – x3) / (y4 – y3)(x2 – x1) – (x4 – x3)(y2 – y1)
- ub = (x2 – x1)(y1 – y3) – (y2 – y1)(x1 – x3) / (y4 – y3)(x2 – x1) – (x4 – x3)(y2 – y1)
The format for the points are thus:
Line 1 = (x1, y1) to (x2, y2)
Line 2 = (x3, y3) to (x4, y4)
How Does I Use It?
The first thing we have to do is find out if there is a collision anywhere between these two lines. We do this by working out formulae 3 and 4.
Both formulae 3 and 4
As long as the answers to both of these formulae are greater than 0, then we can say that there is a collision happening. Using the values for ua and ub, we can find out the position of the collision by feeding these values back into formulae 1 and 2.
I Get Ya… Sort Of
Now that I’ve discussed a little about how it works (I, intentionally didn’t cover it all because there are tonnes of websites out there that explain the maths better than I can), I’ll post the code.
A quick note: I’ve intentionally made this code a little hard to read. This is so that anyone who block copies this code wont be able to explain how it works without some intense study of the code.
Until next time, have fun,
J
