So about a month ago I was inundated with a stream of emails informing me that a tweet I made back in November had suddenly started recirculating. November was the Concentric Game Jam, in which I succeeded only in failing spectacularly, partly because I was trying to to use an engine I'd been working on and it wasn't ready by a long shot, and partly because I got hung up, as I often do, on getting reliable collision detection working. That prompted me to tweet this:
I think it resurfaced because I barely tweet at all these days, so when I announced I was updating this blog again last month, this relic was the most recent tweet before it. And at 7 retweets and 2 favourites, this is easily the most traffic I've gotten on twitter, or even the web at large. Admittedly I'm still a bit shy of internet famous, but it's a a start.
But I didn't come here to advertise a tweet. God help me if I ever do. I just thought it was an odd coincidence, since that collision problem has continued to gnaw at me, and since I was getting back into the habit of working, I set about fixing it.
Side note, throughout this post, some of my fellow developers will be screaming "VECTORS! VECTORS! VECTORS!", and they're not wrong. In the later part of development of this library and the writing of this post, I came up with a 3 box check that can solve the whole problem and many other problems relating to angular collisions. Should I need it, I will probably code that library up too, but most of the times i have found myself in need of collision detection, I was just using simple x, y, width, height hit boxes (Henceforth WHYX hit boxes) and so that is what this program and post concentrate on.
So in simple platformers, the easy solution to collision detection is to ask 4 questions of each object in the scene. Is it above me? Below me? To my left? To my right? If the answer to all of these is no, the object must be inside you. This method easily tells you if you are colliding with something in your current position. Of course if you're moving, things get more complicated. If an object is 20 pixels by 20 pixels and is fall down at 10 pixels at a time, it will always detect the the ground beneath it by checking if its new position is hitting the ground. But if it's falling at 40 pixels at a time and the ground is only 2 pixels thick, then the objects new position underneath the ground is clear so it will proceed as if the ground isn't there and fall forever. Very sad.
To solve this problem, most tutorials I've read suggest using a super simple technique. Instead of moving all at once, we move in even increments, say 20 pixels at a time, and detect collisions as we go. This solves the first problem, but there are two other important problems it doesn't solve. Suppose the object is falling toward a deadly spike, but above that spike is a thin platform. It is possible that the same collision check of a 20 by 20 pixel box that first detects the platform also detects the spike. So now you need to know which was hit first. In this case we were going down so the object that is higher is hit first. But if it's moving up then this is all backwards and if we move diagonally, it introduces a whole bunch of new possibilities. So should you resolve the x first or the y? Either way you will slightly favour the player in some situations and hurt them in others. A player trying to avoid falling down a pit stands a better chance of snagging a ledge if the x is resolved first, while a player trying to just barely jump over a spike will find it a lot easier if the the y is resolved first. You could resolve both first, but now an object might move through a diagonal hole much smaller than the object because the two object sized check regions are on opposite sides of the whole with an overlapping region in the middle that does fit. (Think of how the overlapping section of a venn diagram isn't as long as the full diameter of either circle.)
You can solve most of these problems for a simple game by moving the object one pixel at a time. This way you hit the first object first and if you balance your x and y changes you can move in approximately the right diagonal shape. with slips only ever being by one pixel, which the user is unlikely to notice. The problem here is one of scalability. Checking every object against every other project for every pixel traveled is painfully inefficient once there are more than a hand full of objects.
And this is the meat of the problem and the point I wanted to make with that tweet. Collisions are n squared no mater how you handle them. Every object against every other object. Almost all the well known techniques are made to make the check simpler, or reduce the number of objects considered: only check the collisions with moving objects, combine walls in a row or column into a contiguous object, only collide with certain types of objects, narrow the field with quad trees (or oct trees in 3D), all just reducing n. Nothing can really fix the complexity of it. No matter how you slice it, it's going to make you cry.
And what I've ben working on doesn't really do much better, but it does aim to be an improved version of the simple iterative method, only checking the space at the necessary level of detail. It's gone through a couple revisions since the original idea of expanding the above, below, left of, right of test, (henceforth ABRL) breaking each line into a combination of a sloped line and a vertical or horizontal section as shown below.
I briefly hit upon the idea of using vector math to rotate all objects about the origin until the situation mirrored the one case with a positive x and y shown above, this may still be a viable idea, but the process of rotating all the objects changes the relation between their width and height and the origin of the object, since that origin may be in a corner other than the top left. There may be a smart way to deal with that, but I was starting to see another giant if tree forming and decided to back up and rethink the entire strategy.
Having shelved this for a while, I looked it over again after my last post, vowing to complete a project, any project, and a good collision library has been a sorely missed asset in my various jam projects, so it seemed like a good choice to get myself up to speed with again. (Yes I do realize that almost 2 months have passed and I really need to focus on that speed part.)
I went back to the iterative solutions and came up with a three level collision check. On the first level, I check one box containing the initial position in one corner, the final position in the opposite corner, and everything in between. This is over checking by a lot, but it is only here for two reasons: one, find out if more detailed collision checking is necessary, and two, narrow the list of objects that might be crashed into to only those which collide with this box. This way, later checks with very little movement between checks, will compensate by having very small lists of candidates.
The second level moves the object moves the object by unit differently depending on its velocity. If the velocity has an x component of greater magnitude, the object moves based on its width, otherwise it moves based on the objects height. Whichever is chosen is considered the primary length, while the other is the secondary length. The idea is to define a series of boxes with the original position once again in one corner with the opposite corner containing a new position that is moved one primary length forward in the primary dimension, and an appropriate distance in the secondary dimension according to the velocity. This way the box encompasses this step's actual covered area and the box around it the same way the first level did for the entire trip. If there is no object in the box to collide with, the destination becomes the new origin, and the process repeats.
If a collision was detected, the method goes back to the tried and true, move the object along its course one pixel at a time until a collision is detected. If no collision, go back to level 2, if there is a collision, then there was a collision and the object, or objects detected are returned as the result.
I could go into more detail about the inner workings, but I think it's all better explained by this visual debugging program which I build to develop it. The blue box is the subject. Move the mouse and click to test a final position. The box moving with the mouse is the intended final position will be green if it made it there without colliding, and red if it did not. The pink sections are the collision boxes used in the section of code that returned the result. Level one collision boxes are not shown. The lines that can be collided with will turn red if they were considered in the deciding check.
Download test page at:
https://github.com/Lambwatt/CollisionSys/blob/master/debugCollisionDemo.html
As you can see, the last collision box in level two can actually extend beyond the final position. I intended to specially handle this edge case, but it turned out to be rather problematic, and it didn't seem to be having problems with it anyway. The reason no new problems emerge is that the level 2 checks only check the results from the level 1 check, not the global list of objects. This means that an object colliding with a level 2 check but not a level 1 check is actually invisible to the level 2 check so it doesn't cause any errors.
It's not a pretty algorithm. It's a bit more convoluted than I intended and it uses a lot of complex return values, (objects sent back with companion data to the intended return value), and it isn't sophisticated enough to handle hit boxes being on an angle. But for most of the games I would be making at jams, this is sufficient without requiring any new infrastructure around it, like a quad tree implementation, and works well enough even with a huge number of objects flying around the screen. And my real criteria for success was to be able to hold a bunch of objects with 1 pixel thick walls. As shown in the demo below (press and hold the left mouse button to advance time.), I believe I've done that*.
Download demo at:
https://github.com/Lambwatt/CollisionSys/blob/master/stressTestDemo.html
All code related to this project can be found at https://github.com/Lambwatt/CollisionSys.git
I'm Michael Pattie, and this day <checks calendar> 53.... damn.
*The demo piece hit some weird cases with particles below about 6 pixels by 6 pixels and completely breaks for 1 x 1 particles, however these seem to be more related to the less well thought out way in which I resolve collisions than a failure to detect them. I decided what I had was good enough for me to move on. It's time I got back to a certain other project.
