We’ve got a physics engine to build.

Would you like some science with your game?

Not too much science now, since we are focusing today on physics only. And within physics, on mechanics only. Of the classical kind only. With a focus on dynamics only. And within this, of rigid bodies only. And all that in 2D only. This is a very tiny bit of science so we should have it implemented and tested by Monday, right? Right… -_-

Classical dynamics describes and predicts the motion of bodies under the influence of forces. If we model the legs of your in-game character by a ‘walk force’, then you can change the amplitude and direction of this force by pressing the WASD keys and see your character respond to it. If you’ve had a look at the code pushed on GitHub you might have noticed that the MoveCommand event has a force parameter. It is properly generated by the PygameController, but it is stupidly used because there is no physics engine:

class EntityModel(......):
    ...
    def moveTo(self, pos)
        """Set the position of the entity."""
        self._pos.icopy(pos)
        self.post(events.EntityMovedEvent(self.entity_id, self._pos))
    def onMoveEntityRequest(self, event):
        if event.entity_id == self.entity_id:
            self.moveTo(self._pos + event.force)

So what we are doing here is x_{t+dt} = x_t + a, which is as far from the Newton equations of motion as you can get while still kinda move in the right direction.

Introducing the time step.

If we try to copy-paste the equations of motion into our code we hit a wall: physics is continuous, but our simulation is limited to using a time step. The time step is the dt in the equation above. In real life, that time step is tiny, so tiny we can say it is infinitely tiny and we can use calculus to solve the equations of motion exactly, at least in simple cases.

But a game is not simple: there are many bodies moving around at the same time, many forces applied on them at the same time, plus all the collisions that can occur. Solving the equations exactly is out of the question so we have to satisfy ourselves with an approximation that we can compute with numerical analysis.

The smaller our time step, the better the approximation. There are at least two limits to that statement:

  • The precision of the floating point calculations is not infinite. A tiny time step can lead to differences in position or velocity that can hardly be represented (if at all) by a 64-bits float. Then your simulation explodes.
  • The smaller the time step, the more computations we need to make. If you divide the time step by 10, you have to run your physics engine 10 times more to get to the same time. There is a limit to the number of computations that our computers can do in one second and if we use small time steps then our simulation is going to run late. If it takes you 0.02 seconds to compute the equations with a time step of 0.01 you’ll never catch up and the game will look super slow.

Euler integration.

What do the equations of motion look like when we discretize them with a time step ? Well, there are a bunch of possibilities. They are all equivalent with an infinitesimal time step but they won’t be equivalent for us:

# Possible implementation:
position += velocity * dt
velocity += acceleration * dt
# Another implementation:
velocity += acceleration * dt
position += velocity * dt
# Yet another one:
position += velocity * dt + 0.5 * acceleration * dt * dt
velocity += acceleration * dt

These are all variations of what many people call “Euler integration”. I don’t know why it’s called after Mr Euler since anyone who starts writing his/her first physics engine comes up with one of these. They just feel very straightforward and natural.

Euler integration works decently in some cases. However, it depends a lot on the choice of the time step. Indeed, with that integrator, the acceleration and the velocity are considered constant during the whole time step. That does not make sense: if the acceleration is constant (and not null), then the velocity CANNOT be constant during the time step. That’s the very definition of accelerating. Different time steps will give very different results and you are forced to use a small time step in order to have the best predictions you can. Which is bad, because small time steps force you to compute more.

Verlet and Runge-Kutta integrators.

Fortunately there are other integrations methods around. They are more complex, less straightforward, but not more complicated. For example, Minecraft uses a Verlet integrator. Another popular integrator is Runge-Kutta. There is a bit of a holly war on teh tubes about which one is better and it’s a bit hard to choose. So let’s apply science, shall we?

Therefore Runge-Kutta is better than Verlet :D.

Both Verlet and RK come in several flavors. However, from what I’ve seen around the tubes, what people often mean by “Verlet” is Position-Verlet, and “Runge-Kutta” is most of the time referring to Runge-Kutta-4.

You can have a look at the following articles:

The idea behind position-Verlet is to not use a velocity vector at all. Instead, the velocity is implicit: that’s the distance between the last two positions divided by the last time step. This has the enormous advantage of keeping velocity and position in sync. The algorithm is also very light, it’s almost as light as Euler from a computational point of view. Verlet also lets you rewind a trajectory; that time-reversal symmetry is a nifty thing that has its uses in particle physics but I can’t think of a use-case in a game. Also Verlet is good at conserving the energy of the system, which is cool for serious simulations but we don’t care about it in games where external forces (those damn players keep wanting to move their characters) apply all the time.

The idea behind RK4 is to sample the velocities and accelerations at different times within the time step and make use of Newton series for doing its magic. It’s way less easy to grasp, and there are many more computations involved.

Yeah, Verlet is cool. However, I find it a bit weird. Indeed, how do you start it? You need at least two positions to begin with. Of course you can always say that they are equal, that’s easy, but then all your objects are created at rest which may not be what you want. Perhaps it’s enough: the arrow is at rest in the bow and the force of the string is applied only once when the arrow is fired. You’ll have to tweak the force using your time step to ensure that the arrow achieves the same speed regardless of the time step. Another possibility is to use Euler to define the second point. The example of the bow and arrow also illustrates the lack of impulses. An impulse is an instantaneous change of the velocity. Bouncing on a wall creates an impulse: your velocity is mirrored on the wall. With Verlet, just changing the position is not enough to simulate the impulse because your body won’t bounce in the right direction ; instead you have to create a one-time pseudo force that takes the time step into account. Messy.

On the other hand, RK4 lets me do my physics the way I am used to: I have both my position and my velocity. RK4 is very resistant to a change in time step. So even though RK4 is heavier from a computation point of view, I can call it less often. I choose RK4. It’s not even that hard to implement : Integration basics, by Glenn Fiedler on gafferongames.com.

Once I have implemented the integrator, I will have to start the serious business: collisions.

Demotivator: Physics, resistance is futile.

Deformable bodies won't be part of my simulation. Phew!

Edit: One hour later…

Wow, that went pretty well. I spent more time writing the post than actually implementing the thing. The version v0.0.4 is pushed on Github, you can pull or and download it already. See my previous post to know how.

Now, I’ll write something about how I implemented it. So little code has changed ! Have a look:
https://github.com/Niriel/Infiniworld/commit/4ae2d4125899fe738fc4421697e79c954ffbeb4b

Advertisements

About Niriel

Cynical utopist who likes red wines from Languedoc and playing Minecraft instead of working on his own game.

Posted on 13/08/2011, in Infiniworld and tagged , , , , , , , , . Bookmark the permalink. 2 Comments.

What do you think about it?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: