|June 1st, 2011|
Did you know that bullets (and other quick moving objects) in video games sometimes exhibit magical properties if they move too fast? If they gain enough speed, sometimes they can even pass completely through other objects without leaving a scratch or affecting them at all! You might have seen this happen occasionally in games that have a lot of complicated physics simulation. Sometimes fast moving objects just seem to pass through the ground or other objects. Unfortunately this is not a desirable user experience and it quickly breaks the illusion the game is trying to convey. This phenomenon is called “tunneling” and game developers attempt to deal with it in a variety of different ways. I thought I would share my unique combination of techniques to deal with it that I used in Cannonade. I have not seen this specific combination of techniques explained or suggested anywhere and so I thought it might be beneficial to share what I have learned with others who might also be suffering from object tunneling woes. First lets explain how most modern game physics simulation works and investigate why this problem crops up.
Physics Simulation 101
Realtime physics simulation used in games has a very tall order to fulfill. It has to deal with all sorts of complicated collision detection and constraint resolution and has to do it all within a reasonably low amount of computation time. To accomplish this task, things like simulation accuracy and correctness tend to take a hit because most games don’t need a very high level of either of those. As a consequence, many realtime physics simulation libraries roughly go about their task like this (many portions omitted and glossed over):
The problem of tunneling comes up when an object is going so fast that the new updated position does not intersect with the object it was heading towards. The object didn’t intersect the target object at all before the frame was simulated and it wasn’t intersecting at its new position either. So as far as the simulation is concerned it never hit the object and so it just keeps on going. An interesting side note regarding tunneling is that people who become proficient at creating video game time attacks will sometimes use tunneling as a time shortening technique.
There are physics simulation libraries that perform continuous collision detection (CCD) which will figure out if two objects collided at any point within the simulation frame. Usually this is accomplished by creating a new collision shape that has a volume which contains all the space that the moving object occupied throughout the time quantum. It then tries to figure out the intersection of the movement volumes with other objects and then looks even closer to see if the both objects existed at the intersection of their collision volumes at the same time. Performing CCD is more involved and computationally expensive than the traditional method although it does help to prevent the tunneling problem. At the time of this writing most game-suitable physics libraries do not fully support CCD. More likely than not you will probably be using the more traditional collision detection techniques in your game. So what is a developer to do? Here are some of the methods I know about to mitigate or otherwise deal with tunneling:
1. Avoid The Problem With Universe Constraints
People most often encounter the tunneling problem when they have a relatively small object (like a bullet) going really fast. But it can affect large objects as well if they are going fast enough. It is all really about scale. Tunneling will only occur if an object is moving fast enough so that it can move the complete length of the shortest width of another object in the time quantum of the simulation. Thus you can constrain your universe to limit the velocity of objects so that they can never move fast enough to completely tunnel through other objects (or maybe just the objects you care about preventing tunneling through). You could also make sure that all the objects you care about preventing tunneling through are large enough such that the fastest moving objects could never completely tunnel though them. Unfortunately, putting these kinds of restrictions on your universe is often not a viable solution because the limits of what kind of scenarios you can simulate is greatly reduced.
2. Avoid The Problem With Time Quantum Reduction (AKA Time Slicing)
This is the most proscribed remedy to the tunneling problem. Time slicing is when you increase the granularity of the simulation by reducing your simulation time quantum. What this does is it increases the accuracy and correctness of your simulation and shortens the potential distance that any object can travel within the simulation time. For example, if you cut your time quantum in half then the distances objects travel in a simulation frame are also cut half. This lowers the potential for objects to tunnel through each other at the cost of increased simulation processing. So you could make your time quantum really small such that tunneling doesn’t happen often anymore but your simulation time might rise dramatically. This can be especially wasteful if 9X% of the time objects are moving relatively slowly and you don’t need the extra simulation granularity.
3. Special-case Really Fast Moving Objects As Raycasts
This is what a lot of games do to simulate bullets and the like. Instead of actually creating an object in the physics simulation you simply cast a ray from the end of the gun and calculate which objects the ray intersects. Once you have found the first object that the ray hits you deal with the event of the bullet hitting the object. In a sense you are manually performing CCD with a collision volume of a ray. This is very effective for very small objects that can be reasonably approximated by a ray for collision purposes but will not work as well for objects that are larger relative to the rest of the world. Also, you usually don’t get the benefits of the physics simulation library that your other objects which are in the simulation have. You have to roll any physics simulation associated with your raycast objects yourself. This still leaves a fairly large middle ground of objects that have the real potential to tunnel but cannot be reasonably simulated as a ray.
4. Convex Sweep Collision Based Time Slicing (My Cannonade Solution)
For the kinds of simulations I have been running in Cannonade, none of the above solutions quite fits the bill. I simulate lots of objects of all sorts of sizes, almost all of which have the realistic potential to be moving very fast in the course of the game. What I came up with is a variation of solution #2 above and my implementation is specific to the bullet physics library. At the moment I don’t know about the portability of this solution to other physics libraries. What I do is that for every potentially fast moving object, I calculate the radius of a sphere such that the sphere is the smallest sphere that could completely enclose the object. Then in every event loop right before I invoke the simulation of the physics frame, I inspect all the objects in the universe and find which ones are going faster than a specific threshold. For each of those objects I perform a convex sweep test using the aforementioned sphere moving at the same velocity as the object and the in the same direction as the object. What a convex sweep test does is it creates a movement volume as described above when you use CCD. It then checks to see if that movement volume volume intersects any objects as they reside in their current positions. If the query reports back that there was a collision, it checks to see if the collision was with a convex object or if it was the terrain (implemented as a
btHeightfieldTerrainShape). It then calculates a whole number (based on the thinnest portion of the moving object and the speed at which it is moving) which represents the number of times I would need to slice up my time quantum to prevent tunneling. If the terrain was among the objects that collided with sweep volume then that calculated slice number is significantly higher because currently
btHeightfieldTerrainShape is not simulated with any thickness to its surface (some other physics libraries do have thickness options to their terrain heightfields) so an object simply has to pass through the thin surface of the terrain to tunnel instead of passing through an entire object. My code finds the highest number of time slices required for all the fast moving objects, divides my fixed time step by that number and passes it to
btDiscreteDynamicsWorld::stepSimulation() making sure
maxSubSteps is greater than the time slice number. What this amounts to doing is that the game spends a little more work every frame inspecting every object’s velocity, performing a convex sweep query for fast moving objects and then increasing the simulation granularity (and in turn, the required computation) during those frames when a fast moving object actually hits something.
In practice this has produced a very pleasing result because the simulation runs at full speed almost all the time and only has these very brief moments of slowdown when projectiles or fast moving blocks hit something. In most cases when a fast moving object hits something else the resulting object collision significantly slows down the moving object. Thus the number of frames in which a lot of extra computation time is needed (due to time slicing) is usually very small. It is of important note that whenever you increase the number of slices you divide your fixed time step into you also need to divide and reset your error reduction parameter (ERP) like this:
myDynamicsWorld->getSolverInfo().m_erp = 0.2/numberOfTimeSlices (assuming that your default value for the ERP is 0.2). The ERP is the basis for the force that moves intersecting objects so that they no longer intersect each other. If you don’t set your ERP accordingly you will see intersecting objects bounce out and away from each other with much more force than usual during times that you do simulation time slicing. It should also be noted that this solution is not perfect and will not catch scenarios such as when two objects traveling in say perpendicular directions to each other, should collide in the course of a simulation frame. However, I have found that it covers about 98% of the scenarios that I care about and without significant cost to the framerate.
Got any other anti-tunneling techniques that I didn’t mention? Any other things to consider that I might have missed? Let me know about them in the comments below!