## Underlying Mechanics: Collision DetectionDuring 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. |