|December 13th, 2011|
In developing Cannonade and Invader Zurp I’ve invested a fair amount of time becoming familiar with the Bullet Physics Library and trying to milk every bit of performance I can out of it. Realistic physics simulation plays a crucial part in both games, and is also the performance bottleneck in the majority of gameplay scenarios for both. When trying to optimize for performance, I generally find myself using two kinds of approaches. One is a higher level algorithmic approach that tries to find ways to create less work or avoid work in order to keep things going fast. Once I’ve nailed down the minimum set of work that absolutely must be done, then comes the work of getting down and dirty to speed up the routines that actually do that work. When I first approached the problem of speeding up Bullet, I simply treated it as a black box (work that I wouldn’t be able to avoid) and explored what kinds of compiler configurations I could leverage to create the fastest possible execution of the physics simulation work. Later, after I had nailed down the gameplay mechanic for Invader Zurp, I was able to start specifically attacking the set of physics simulation work needed for the game, and whittled it down to a much smaller amount using some simplifications, accuracy compromises and psychology.
Work, work… More work?
A basic description of the gameplay in Invader Zurp is that you, the player, are flying in 1st person over a planet surface towards structures made up of variously shaped and sized blocks. The player taps the screen to fire missiles at the structures, which then explode. This explosion destroys some blocks and sends other blocks flying through the air. There are also some special blocks (called turrets) that shoot missiles back at the player, which must be intercepted else the player takes damage. In the next couple of sections, I’m going to step through the procedures I go through in order to make sure that my physics simulation work is as small as possible, while still giving the player a good gameplay experience.
Less Stuff, Less Work
First things first. The player is constantly moving forward and “blocky” structures are regularly being brought into the simulation at the horizon as the player plays the game. Obviously more blocks means more work, so minimizing the amount of blocks in the simulation is imperative. Because the direction the player is moving never changes, it only seems natural that once a block has moved behind the player’s viewpoint, it should be removed from the simulation. In this game, a block behind the player can no longer be interacted with (usually) and so it’s simple enough to just remove them from the simulation. I also thought about removing blocks once they have left the player’s view frustum but eventually decided that I should still keep those blocks in play in case a missile has already targeted and started homing in on it. The player might be really disappointed to have successfully targeted a special bonus block, only to have it lifted from their grasp as it leaves their view. In addition to removing blocks behind the player viewpoint, I also remove blocks that have been pushed too far into the background.
Shh… Don’t move. Its CPU Load’s Based On Movement
Another very basic performance concept in physics simulation is that if objects are not moving (or are moving so slowly as to not be perceived as moving) we can skip over a large part of their simulation computation. You can set a movement threshold that causes blocks to become inactive from the majority of the simulation once their velocity falls below it. This functionality is built in to Bullet (
btRigidBody::setSleepingThresholds()) and most other physics engines. In Invader Zurp, I chose to bump up that threshold higher than normal so blocks would become inactive sooner. I also set the friction coefficients of the blocks and the ground such that blocks would slide around less and fall under the inactivity threshold quicker (
btRigidBody::setFriction()). Because the player is constantly moving, there’s not a lot of perceived difference to the player between a block that is sliding around a little bit, and one that is stationary. Thus, aggressively changing these values didn’t result in a very different experience for the player. In addition, when new block structures are added to the simulation, every block is initially flagged as inactive (
btRigidBody::setActivationState(ISLAND_SLEEPING)). This is because in Invader Zurp, it is assumed that the structures are all initially standing still. This does have the interesting side effect of allowing for structurally unsound buildings. Blocks can be suspended in the air and blocks can also occupy the same space at the same time indefinitely. Of course, the instant a moving block collides with it, the entire thing falls apart. I eventually decided that the charm of having interesting (but structurally insufficient or conflicting) building designs, outweighed the realistic depiction of the structure.
Accuracy Is In The Eye Of The Beholder
There’s an interesting problem in traditional realtime physics simulation called “tunneling” which I describe in depth in another blog post. In that post, I describe some techniques to deal with the problem of relatively small objects tunneling through others, and different ways of dealing with it. In Invader Zurp, the fastest moving objects are (usually) the missiles that the player shoots at the oncoming structures and incoming enemy missiles. The missiles travel quite quickly (especially when they are completely leveled up) and at a normal simulation granularity, they can easily tunnel through the blocks. I considered special-casing them and simulating their movement and collision myself, but I eventually decided to have them remain as Bullet simulation objects and keep (most) collision detection for them inside the physics engine. Taking some cues from the solution I came up with for Cannonade (“Convex Sweep Collision Based Time Slicing“, discussed in the tunneling blog post), I decided to start from there. To ensure that the missiles do not tunnel through blocks even at their high rate of speed, I decided to increase the granularity of the simulation high enough so that they could not completely tunnel through an individual block. Because doing so increases the computational power need substantially, I had to make sure that I only did it when absolutely necessary. So every frame I would spend some CPU cycles performing convex sweep collision queries (
btCollisionWorld::convexSweepTest) for the fast moving missiles to see if the’re likely to hit a block within the next simulation frame. If it seems like a collision is likely, then I lookup the fastest velocity of any missile that will likely hit a block during that frame. I use that velocity to determine just how much more accuracy (and in turn, granularity) my simulation needs to ensure that the fastest moving missile will not tunnel. The cost of performing convex sweep collision queries is expensive, but in the long run they save much more time by keeping the simulation runs at a lower accuracy level when missiles aren’t going to tunnel. Those convex sweep queries can still get quit expensive though. I started looking for ways to avoid performing it. I looked very closely at the specifics of the missile’s role, and player perception in my game and got an insight. When you tap on the screen, an algorithm determines which block or enemy missile you most likely intend to hit with your missile. Your missile is entered into the simulation, and undergoes forces that cause it to home into its target until either it, or its target is destroyed. Because of that strong homing force, I noticed that 9X% of the time, the only collision that a missile would ever experience in its lifetime is with its target. I figured that if I only performed the convex sweep query for a missile when it was getting close to its target, I could forego performing a ton of queries when the missiles are not close to their targets, or much less, when they aren’t even close to any block at all. It’s substantially less expensive to simply calculate the straight-line distance between a missile and its target, and then check if that distance is within a certain threshold. If it was indeed within the threshold, only then would I actually perform a convex sweep query to determine if I really needed to increase the simulation granularity. A side effect of this was that occasionally, missiles will tunnel through blocks that they are not targeting. In practice though, I’ve only actually noticed this happening two or three times. The computation savings were well worth the compromise in this specific application. I took this optimization one step further and also decided to sort the missiles per frame in order of how close they were to their targets. This meant that the missiles which were more likely to come up with a positive collision as a result of the convex sweep query were examined first. This meant that contenders for the fastest moving collision during the frame were calculated earlier, and thus increased the likelihood of being able to forego convex sweep queries on missiles that had less of a chance of coming back with a positive collision. All of these optimizations led to a significant performance boost without sacrificing significant user perceived accuracy. Occasionally, when there’s a lot going on, you can see individual frames take longer as the simulation granularity gets spiked, but it’s usually only for a few individual frames. For the most part, the player taps, sees a missile shoot out towards the structure, and then watches it blow up. All with a fairly regular frame rate.
They’re So Small Anyway…
In that same strain of missile collision performance, I devised another slight performance win, but it was instead born out of player experience rather than an egregious slowdown. In addition to targeting structural blocks, your missiles can also target the enemy’s defense missiles, which are constantly homing in on you. Unfortunately, because of the missile’s speeds relative to their sizes, what usually happened was that the player’s missile would speed towards the enemy missile very quickly, and then violently hover around it for a bit before finally colliding with it and exploding them both. This was not a very fun player experience, and was also perceived as being a very erratic result. So I decided to pull missile to enemy-missile collision into my own code, instead of using the physics engine. So instead, I calculate the straight-line distance between the two missiles, and when the distance falls below a certain threshold, the player missile explodes and takes the enemy missile with it. This makes for a much more satisfying player experience. The player sees their missile heading toward its target, and then both explode when they appear to intersect. In addition to being a better game experience, it saves on collision computation as well. In fact, we can probably say that we don’t even need to compute collision between a player missile and an enemy missile in the physics engine at all! Using collision flags (
btBroadphaseProxy::m_collisionFilterGroup) I separated the missiles into specific groups that would only collide with the ground and blocks. The likelihood that two missiles would collide with each other when out in play area, away from the ship was somewhat small (much less, have a user even notice that it should have happened, but didn’t). Thus, pulling those objects out of collision computation with each other turned out to be a significant win. I also found that doing this was necessary when the player got to higher levels of the game and started to fire missiles much more rapidly. The player’s own missiles actually WOULD collide with each other (fairly often actually) and quickly explode after being fired because of the missile density around the area they were being fired from. This was also a bad player experience that was solved simply by taking the missiles out of collision tests with other missiles.
At one point I experimented with extending Bullet itself to allow for more specialized control over it’s execution. I added some flags to collision bodies that allowed me to selectively control which bodies were fully put through the collision detection and contact resolution systems. My aim was to lower the hit of increasing the simulation granularity by keeping most of the simulation progressing forward at the rate of one full frame and instead, only allow the speedy missiles that were likely to tunnel, undergo multiple sub-frame physics passes. That way, the only increased performance hit would be involving the additional physics calculations associated with objects that I’d determined were likely to tunnel. This, would of course, also sacrifice some accuracy because not all of the objects involved in a high granularity collision will be progressing forward like they normally would. But the potential performance gain was too high to ignore. I took about a day to investigate this avenue and got things up and running, but they didn’t quite work correctly. There were clearly many peripheral effects to my modifications that I didn’t yet fully understand. So I decided to instead, keep treating Bullet as an unmodified black box for Invader Zurp version 1.0 and planned to re-visit the idea again when I had more time to dig into Bullet’s internals.
Other small things I did to try and milk more performance was to keep my landscape geometry as simple as possible (in the case of Invader Zurp it’s just one simple plane). I also read that adding the
SOLVER_ENABLE_FRICTION_DIRECTION_CACHING flag to
btContactSolverInfo and lowering the
btContactSolverInfo (I lowered mine down to 2 down from the default 10) you could possibly gain some performance at the cost of simulation accuracy. Because of the quick gameplay pace and constant movement of Invader Zurp, I felt like it was a fairly tolerable amount of accuracy loss and so I added those settings into my configuration. I didn’t do any formal or extensive testing to see if this had any effect, but to the naked eye, I couldn’t discern any significant performance gain (or loss, or accuracy loss for that matter) and so I decided to leave the changes in.
Well, that’s about all the ones I could remember. I’m sure that as time goes on, I’ll be able to figure out more ways to squeeze the most out of Bullet. The grand takeaway is that in your application (especially games), it helps to look at your own specific situation and perform very narrow, situation-specific optimizations. Are any of these optimizations applicable in your game/application? Any other ideas on getting more physics bang for your buck? Let me know in the comments.