I come back from the land of game programming as a lost wanderer. And I have come with news: if you are interested in algorithms and/or 3D, it'd be in your best interest to remember all your math from high school.

I liked to build my understanding of new knowledge off of my existing foundations of knowledge. And while I understood nearly everything I came across in the world of math, some things I just took for granted. Like vectors. I thought it was just a different way of looking at the world of math, and that for practical purposes I could just geometry and trigonometry my way out of anything. Calculus will be calculus.

And it worked. For a while anyways.

But during the whole time, we were told that there were certain ways to calculate some things, such as the reverse of square power, square root. Or sine and cosine. If we knew the values, great. Otherwise, we resort to our trusty tool: calculators (or if you're really old, the slide rule). Of course, we were told that certain values would always evaluate to something, such as the square root of 4 being 2, sin(30) is 1/2, and so on. But other than that, we were clueless.

How does one really calculate the square root of 7? Or the tangent of 67 degrees? As far as I know, if the value isn't known before-hand, the only way to find out is by trial and error. Even calculators and computers have to do this. Of course, we don't do this blindly. With every guess we make, we make a better educated guess based off of how inaccurate we were, and we get closer to the actual value.

Fast forward a few years, and I'm sitting at my computer desktop wondering what's the best way to teach a computer how to tell whether two rectangles are touching each other. From testing, I have discovered that calling Math.sqrt(n) is almost 20 times slower than simple mathematical operations. Math.sin(n) and the like are slightly worse. Obviously, I would have to do this with as few operations as possible, and I should especially avoid using sqrt or sin/cos/tan, all of which are incredibly helpful when dealing with shapes floating in a vacuum.

But wait, wouldn't it be so much nicer if I didn't have to use those expensive functions at all? Turns out this is possible, thanks to the magic of vectors. As long as you knew the location of the vertices of the rectangles, it is possible to determine if one rectangle is colliding with another rectangle, regardless of orientation, size or location. The same is possible with any polygon, although complexity obviously slows down the process. If you're using a shape that has a curve in it, that's when the nightmare begins. Circles are an exception due to their mathematical properties, but for any other curved shape, I have yet to find an algorithm that doesn't use sin/cos/tan. Still, it's easy enough to define a psuedo curve constructed out of vectors, but even better yet, why pay this much attention to detail when the users won't notice such small things? If something is roughly a rectangle, just use a rectangle collision shape.

Some of you may be wondering why I would bother with speedy algorithms when calculators can spit out the cosine of x squared at the speed of light. Well, it may be fast enough for you guys, but the scope here is on an entirely higher level. Computers are dumb. Yes, that's right, computers are dumb. They can't just watch two rectangles speed at each other until a collision happens. They have to decide whether they are colliding or not, and they can only do it every several nanoseconds or so. Not convinced that speed is still an issue? Hold on, let us set the stage for a bit....

So let's assume that your computer was designed to play a shooter game, and there is nothing else that will grab its attention. On a normal computer, there's several other programs that will compete for the computer's attention, and it can only do so much. But this computer will not give a shyt about any of that. It will only care about the shooter game you're playing. (In reality you'd probably be willing to close down programs to get the best performance out of your gaming experience anyways.) After playing your game for a while, you get to a particularly intense level, and pause the game. You're shocked at the fact that there's literally a bullet every 5 pixels on the screen, dozens of enemies, and you're just spraying tons of plasma weaponry back at them. You unpause, and continue with the onslaught. Then you notice that your game seems to be slowing down. Why?

What the computer is doing is doing is tracking the locations of everything: enemy bullets, your bullets, enemy locations, your location, environmental objects, bonus items, etc. And in all of that, it has to figure out if you're trying to do something. And if you are, what exactly your action does, such as moving forward with a velocity of 35. It also has to figure out what stuff is colliding with what, and whether the computer should do anything about it if x and y suddenly are in love. But that's not all. The computer has to dedicate its time to drawing everything (that it is told to draw), which is incredibly time-consuming. And we're not done yet. The computer has to do all of this as fast as possible. For flash games, this is every time a frame is introduced. And this can be anywhere from 15 to 60 frames per second (fps).

All this chaos can be crunched down and reduced to quantifiable numbers. But how precise you want to be depends on what your goals are. Since this post is about collision detection, we'll talk about collision detection. In my case, I want to ballpark doing 5000 collision calculations at 60 fps, which I guesstimate to be close to the most extreme cases (7500?) while still being practical. It's no exact science, but it's good enough for our purposes. Using various tests, I have to decide what is good enough and what isn't. But we can't just simply devote all of our time per frame (16.667 milliseconds) to collision calculations. Realistically, we'd probably have only 40% or less. It's hard to know. But at the very end, if the game runs at the desired fps, then all is well.

In the vast majority of collision calculations, there will be no collision, unless you're playing with few elements, which a shooter game isn't. Therefore, it is smart design to conduct tests that return negative really fast. So we do a stress test that runs our collision detection algorithms. For my basic level of detection, I do the incredibly fast circle vs. circle comparison. My budget gaming desktop is capable of completing 500,000 basic detection calculations within less than 0.65 seconds. If we were to do only 5000 calculations, then it's reasonable to assume it would take 0.0065 seconds, or 6.5 milliseconds, to do it all. This is well within feasible territory. But if we run the more expensive rectangle vs. rectangle collision detection test (using only basic math), it takes ... 27 seconds to run 500,000 times. Ouch -_-;

But fear not! That was only with my original attempt at the algorithm, and is not optimized. And that test was done with FlashDevelop's debug mode (which runs 5x slower than if Flash was on it's own in a browser or as stand-alone). And such a calculation would only happen if the extremely fast algorithm determined there was a collision. Still, why leave this as slow as it is? Using some tricks that I know and some trial and error, I managed to reduce the time down to 6.9 seconds (in debug mode). It's still miles behind the basic detection speed, but this isn't the end. I refrained from optimizing the code to the point of unreadable (to humans), so it's incredibly likely I can reduce the time even further.

Why did I do all of this when there exists free collision detection kits on the internet? I did it so I would know the fundamentals and learn some tricks. That's mostly what it comes down to. But there's also the bonus that I can tailor the collision detection for maximum performance with my own code and design specs. Kits that are made to be general-purpose typically aren't tuned to be as fast as possible for specific applications. And, to be honest, if my algorithms aren't actually on par or faster than the free kits, then I consider my efforts a failure, and that I can do better.

A few other things I took away from this adventure:
-- Write up and test for a ridiculous amount of cases. Circles won't teach you this, but rotated rectangles will. It's not fair, but if your algorithm works correctly except for a very specific niche case, it can be considered a failure. A friend of mine had a couple of alternative proposals to my algorithm, but none of them passed the case where both rectangles crossed each other.
-- Don't delete complex code once you've written it! If for some reason what you're doing doesn't work out, you still can go back to square 2 since you kept a copy of the code.
-- Optimization takes away readability of code. Save optimization for after you're done laying out all the things. If you don't, you risk losing a lot of time optimizing for something that won't get used anyways.