Underlying Mechanics: Collision Detection
NicholasIbarluzea 270005QS76 Visits (1905)
During our initial brainstorming sessions we acknowledged the need to spend some time exploring the physics-related aspects of the game. However, looking back, I think it's fair to say that we underestimated the complexity of the required computations. Naively thinking that our faint recollection of various formulas from old physics classes would suffice, we charged forward and planned to tackle all physics-related requirements as they arose. This resulted in quite a few learning experiences and code refactoring sessions as the overall complexity gradually rose over time. In the end we decided to integrate a robust, third party physics engine into the game. But before arriving at this final conclusion we implemented a number of our own home-brewed solutions.
In this post I will describe our original method for collision detection (such as between two cars). Although we are now using a powerful physics engine to handle much of this work for us, the engine itself also uses this method (among others) underneath the hood. My intention is to perhaps offer some guidance to anyone wishing to implement their own game physics or to just give a quick look at some of the inner-workings of what you see in the game.
At the core of our method of collision detection is the Separating Axis Theorem (Wikipedia link). The theorem simply states that if two convex objects are not intersecting, then there exists an axis for which the projections of the two objects do not overlap. Note that if you wish to test a concave object you must first break it down to multiple convex objects and individually test each one. SAT is an efficient, generic algorithm for detecting overlap between two entities and its ability to execute relatively quickly makes it often ideal for collision detection in games.
To picture this concept of "overlapping projections", take a look at the image below. In diagram a you see two squares which are clearly not intersecting. If you were to project their respective images onto the horizontal axis as pictured, their projections would not intersect either. As soon as you have found an axis in which these projections do not overlap, you can assert that the objects do not intersect. Conversely, the two squares are clearly intersecting in diagram b. For every possible axis, the projections of the two objects will also overlap, allowing you to assert that the objects themselves are overlapping. For any two polygons, the only axes you must test against are the normals of each edge. To obtain the normal of a vector you simply swap the coordinates and negate one (ie. [5,3] becomes [-3,5]).
Unlike the previous image, objects being tested for collision won't usually be simple, un-rotated squares. You might be dealing with a complex polygon with many vertices. You may be wondering then, what the best way to programatically project these polygons onto an axis is. The answer, luckily, isn't very difficult. You would simply loop over all of a polygon's vertices, perform a dot product between the vertex and the normalized axis to be projected on, and store the minimum and maximum result. Remember that there is a difference between a vector's normal and a normalized vector! In simple pseudocode, this would look similar to the foll
We now know enough to be able to assemble a simple function for determining whether or not two objects are intersecting. But in our racing game, we needed more than simply knowing if two cars are colliding. We also wanted to prevent them from simply driving right over the top of each other. For this reason it is beneficial to calculate the Minimum Translation Vector - a vector which tells us the shortest path to push the two objects apart to keep them from intersecting. Your final collision detection code might look similar to the following pseudocode:
Don't forget that the array of axes in the above code would have to consist of both objects' axes needing testing.
This was a very simplistic overview of the algorithm we employed for collision detection in our beginning stages of development. Before using it yourself, you would likely want to spend some time making the algorithm more efficient (such as by not testing parallel axes) and adding additional functionality to handle curved features or to properly handle the case in which one object is completely engulfed by the other.
Collision detection is just one facet of our physics-related computations. Things seem to get exponentially more complex when you begin to account for resultant forces due to a collision, cancelling out a car's lateral movement due to traction, applying the appropriate amount of torque to turn a car just the right amount, etc. In future blog posts we will discuss our move to the JBox2D physics engine, how much easier this made our lives, and all the cool physics stuff we've been able to put into the game.