Fixing My Xbox Performance Problem

The Symptoms
Most of the time I tested my game on my PC because I simply had no Xbox available. Now that I have one, I tested my game on the Xbox and had really bad results. It ran only at average 40-50 frames per second. So I looked at my scheduling visualizer to search for the bottleneck (see this blogpost from march for a description of the visualizer):

Task execution times Xbox 360

In the test scene there were ca. ten missiles and 15 space-crafts (enemies + own ships) and the framerate was down to ca. 35 fps. Very bad! The bottleneck was the physics task (blue bar). It took average 31ms per frame. The graphics task (green bar) had always to wait for the physics task. So I had to search there for my problem.
And just for fun the same scene on my PC (Intel Quadcore 2.5 GHz + Radeon HD 6700):

Task execution times PC (Intel Quadcore 2.5 GHz + Radeon HD 6700)

You can see, there is absolutely no performance problem on the PC! Further you can see that the Xenon CPU used in the Xbox is really really slow. The physics calculations take over a hundred times longer. Ok, its a unfair comparison, the Xenon is from the year 2005 and my Core 2 Quad Q9300 is from 2008. Additionally there must be some other problems. Factor 100 is just too much. This can't be all reduced to the hardware. Maybe some specific Xbox .Net compact framework problems.
I learned from this, that you have to test all the time on the hardware your game is targeted for.

The Problem

Searching for the problem I had a closer look at the Jitter Physics source code for the first time. The engines debug timers showed that the engine spent 95% of the time in the collision detection system, which uses the Sweep and Prune algorithm. A very good description of this algorithm and its implementation can be found on the Jitter homepage. The core idea behind this and most other collision detection algorithms is, to figure out which of the possible collisions can actually happen and put them into a list. This step is called the broadphase. In the next step (the narrowphase), only those object pairs in the list are actually tested for collision, using a more complex collision check which also calculates things like the collision points.
After reading the article about Sweep and Prune I had an idea what the reason for my performance problems could be.
I've put the perception for AI (also used for the player's radar) in the physics system. Perception means, figuring out which other game entities the AI can see right now. So every physics object carried a sensor collision shape around to "see" surrounding objects. Every game entity inside the shape can be seen by the AI. This is illustrated in the picture below:

I have drawn circles into the radar on the screenshot to show the approximated shape of the sensor. Doing perception inside the collision system doubled the number of objects that need a broadphase collision check. Also there are many completely useless broadphase collision checks between two sensors. Putting the perception into the physics systems was just a very bad idea! But the main CPU cycle wastage came from gathering perception data in EVERY FRAME. Thats just not necessary.

The Solution
The solution is easy. Move the perception gathering out of the collision system and don't gather every frame. It took me a few hours to move perception into the AI system. Have a look at the nice result:

Good Performance (Xbox): Perception in AI system, gathering interval one second

For comparison - Bad Performance (Xbox): Perception in physics system

Now I have frame rates between 70 and 80 and all tasks have to wait for the graphics system. This means I have now plenty of CPU cycles left to increase the number of enemies, implement new cool weapons or improve my AI.

Hitting a moving target with an accelerating missile

The last few days I spent quite some time solving this problem. My first idea was, that I could just calculate the time the missile needs to travel to the target at maximum acceleration. With this time I can predict the new position of the target and aim toward that point with the missile. It is clear that this is not very accurate, but I thought that it is accurate enough.  Have a look how this worked:


Hitting a moving target with an accelerating missile on Vimeo.

The stupid missile in the first part of the video uses the approach I described. On the moving target it performs well, if the missile has no start velocity. But if you do add a start velocity, it gets really bad. You can see this better on the none moving target. The missile does move in an orbit around its target, because it will always accelerate towards the target.
So how does the smart missile work? Luckily I have a brother who studies physics and he explained me patiently how I can solve this (if you are not interested in the math you can download the code here and use it as a black box in your game or what ever you are programming).

The Math behind it:
In 2D space the target is at position X at the time t (d = distance to missile, v0 = velocity of the target):

For the missile the equation looks like this (w = start velocity missile, a = acceleration missile):

The missile hits the target if both equations return the same position in space x:

To get a solution that fulfills the equation we have to use the quadratic formula (replaced vectors with the vector components - index i can be set to x or y) :


The missile and target are at the same position if :



(k = length of acceleration vector)
Now we want to know which value of the angle alpha fulfills the equation. Sadly, we cant easily calculate the angle, but have to use an approximation method. I used Newton's method because I knew it already from school. The problem is, that we have four equations that have to be checked (plus-plus, plus-minus, minus-plus, minus-minus). So we have to use newton four times and look which of the four solution is the best. For newtons method you also need to derive the above equation (used wolfram alpha for this). Writing the derivate down in code was a pain. Newtons method on the other side is very easy to implement:

delegate float Function(Vector3 velocityDiff, Vector3 distance, 
                        float acceleration, float phi);

static float SolveWithNewton(Function function, Function derivative, 
                             Vector3 v, Vector3 d, float a, 
                             float startPhi, int numIterations)
{
    float phi = startPhi;
    for (int iteration = 0; iteration < numIterations; iteration++)
    {
        // precalculate values that are needed in the function and the derivative, 
        // so that we calculate them only once
        cosPhi = (float)Math.Cos(phi);
        sinPhi = (float)Math.Sin(phi);
        tanPhi = (float)Math.Tan(phi);
        vxQuad = v.X * v.X;
        vyQuad = v.Z * v.Z;
        insideRootVx = vxQuad + 2 * a * d.X * cosPhi;
        insideRootVy = vyQuad + 2 * a * d.Z * sinPhi;
        if (insideRootVx > 0) rootVx = (float)Math.Sqrt(insideRootVx);
        if (insideRootVy > 0) rootVy = (float)Math.Sqrt(insideRootVy);

        float functionValue = function(v, d, a, phi);
        float gradient = derivative(v, d, a, phi);
        phi = phi - functionValue / gradient;

        if (float.IsNaN(phi) || Math.Abs(functionValue) < Epsilon) break;
    }
    return phi;
}

Performance:
Right now I calculate the angle for the missile every frame and use maximal eight iterations in Newton's method. Worst case this means 24 iterations, because we have to test all four possible sign combinations. In every iteration we have at least one Sin, Cos, Tan, Sqrt and a few multiplication/division calculations. On my machine (Quad Core Q9300) this works fine (tested with circa 40 missiles). But I cant recommend this, especially on the Xbox with XNA where the floating point performance isn't that great (but I haven't tested it). The good news is, that you don't have to calculate the angle every frame. Its enough to calculate it every time the velocity of the target changes.