Tag Archives: algorithms

Awesome Efficient MMD

I’m currently implementing Class::Abstract, which will become my Perl 6 multimethod proposal. I pounded my head against a wall for a couple hours, and I came up with a really awesome multimethod dispatch algorithm. It isn’t Manhattan distance, of course, because I hate Manhattan distance. Actually, it’s more general: it’s an algorithm for quickly finding all possible candidates, without using any algorithm to disambiguate which ones. It is Θ(a m t) (where a is arity, m is number of methods, and t is number of types) in space, which beats the hell out of Parrot’s current Θ(t a), especially since t is usually much larger than the other parameters. It’s also fast-O(a+m) in time, where fast-O is technically O(a+m), but the bounding constant is quite small relative to most asymptotic measures. That is, it can be implemented in a really tight, CPU register-only loop, on top of the fact that a and m are generally small.

Continue reading Awesome Efficient MMD

Efficient Inheritance Relationship Checking

I’m working on a team making an RPG, and the lead designer needed a way to quickly check whether some class A (on the data level, not the code level) is derived from another class B. Here is the solution. This is actually a solution for mapping any partially ordering relation into pairs of real numbers.

Static Forward-Reverse Order

This is the best way if you know your entire hierarchy at compile time. Assign each class two numbers as follows: The base of the hierarchy gets the pair <0,0>. From there, do a leftmost preorder depth-first traversal and assign the first element of the tuple increasing natural numbers. For example:

                <0,0>
                /    \
             <1,>   <3,>
             /
           <2,>

Now start at the top again, and do the same thing for the right element of the tuple, starting at zero, and doing a rightmost traversal. So this hierarchy becomes:

                <0,0>
                /    \
             <1,2>  <3,1>
             /
           <2,3>

And now, a class with the tuple <a,b> is derived from <c,d> iff a ≥ c and b ≥ d. If a<c and b<d, then <a,b> is a parent of <c,d> If neither of these cases hold, then the two classes are siblings.

Continue reading Efficient Inheritance Relationship Checking

Game Loops

IPC is getting so nice that we have to start tackling the hard problems like user interaction and the Canonical Game Loop.

Don’t know what the Canonical Game Loop is? Well you’re in the right place. I’ll start by talking about integrator step, then I’ll contrast variable with fixed step, and finally I’ll introduce the happy medium that is the Canonical Game Loop.

Integrator Step

Say you have a ball (in a one-dimensional space) with mass 1 kg, going at speed +3 m/s, at position 0 m, with a force acting on it of -1 N, at time 0 s. You want the integrator to find its position at time 1 s.

The way you’d do this in Physics class is to take ∫01(3-1t)dt, giving the result 2.5 m. But the typical game simulation is far too complex to solve analytically, so the integrator has to do it numerically.

With a timestep of 0.25 each time, it steps the simulation Newtonianly by 0.25 s, recomputes the forces, steps again, until it has covered a whole second. This gives:

Time Position Velocity
0.0 0.0 3.0
0.25 0.75 2.75
0.5 1.44 2.5
0.75 2.06 2.25
1.0 2.63 2.0

Not quite 2.5 m, but close. If, on the other hand, an integrator step of 1 s is used, then it computes the final position as 3 m. That’s pretty bad. In summary, bigger integrator step ⇒ bigger error. Most of you probably already knew that.

Fixed & Variable step

There are two obvious ways your game can integrate, using a variable and using a fixed time step. A variable time step measures the time that it took to draw the last frame and uses that as the time step for the next frame. This way your simulation always runs in real time, no matter what your frame rate. A fixed time step uses the same step no matter how long it took to draw the frame. In order to keep this in real time, a sleep can be issued if the drawing time was shorter than the time step.

At first glance, variable time step seems like a big win. You’re always maximizing the potential of the computer, getting the most accurate results that are possible to calculate in real time. There are big problems with that, though. First, since the computer doesn’t run at the same speed all the time (background processes, temperature, etc. play in), your simulation doesn’t come out the same if run two different times with the exact same input. This is obviously something that we don’t want to happen for a game like the incredible machine. Another problem is that if you move the window, suspend the process, do anything that takes more than a small amount of time in which the program doesn’t get to run, you get a huge time step, and thus big error and instability in the system. This latter issue is correctable, though.

On the other hand, a fixed time step will always give you the same result for the same input. Many games want this, IPC in particular. But, not surprisingly, it too has issues. If your computer’s faster than the pre-chosen time step, your frame rate suffers. You might only get 24 frames per second when your machine is capable of hundreds, because of the sleeping involved. If your computer is too slow, the game’s time slows down and you’re no longer running in real time. Although if you want a stable system, this latter problem is uncorrectable. Thus “minimum system requirements.”

Enter The Canonical Game Loop

The Canonical Game Loop is a way of using a fixed time step while not making fast computers’ frame rates suffer. The first thing you have to do is separate the drawing pass from the integration/computation pass. Fortunately, this is something that IPC has done from the beginning (yay design choices!). The game loop looks something like this:

    num time = 0;
    loop {
        time += timer.tick();     // Get the time since the last tick()
        while (time > TIME_STEP) {
            Integrate();
            time -= TIME_STEP;
        }
        TIME_ERROR = time;
        Draw();
    }

Not surprisingly, this is almost the exact code used in game.cpp from IPC.

When you’re drawing your objects, you fetch the position and rotation first, right? So when you fetch the position, add the velocity times TIME_ERROR. Likewise when you fetch the rotation, add the rotational velocity times TIME_ERROR. This is extrapolating, so your results will be slightly non-physical. But if you have your TIME_STEP sufficiently low, this isn’t a problem, as nobody will notice.

The way I did it in IPC is made a wrapper around the ODE dBodyID, and added the velocity time TIME_ERROR in the pos() method. That’s all there is to it, but to do it right, you kind of have to know that you’re going to do this from the beginning, as it effects your design.

You can also interpolate, so that your results will never be non-physical (no penetrating bodies, etc.), but that is more computationally expensive, and requires one timestep of visual lag. For IPC that’s fine, but for a more real time game, that might take away from the responsiveness too much. I encourage extrapolating, because of its algorithmic simplicity.

Now the next time you write a game, you’ll know what to do so that you can implement the canonical game loop.