Ordinarily I wouldn’t recommend writing your own physics engine. There are plenty of good, free ones and it would take years to achieve the same quality and feature set.

However, I don’t like having a dependency on a big, complex piece of code if you don’t need it. My requirements for physics are limited; I can probably fulfil them in no more time than it would take to learn and integrate a new library. And as a bonus I will understand and be able to tweak the code at any level.

First stop is collision detection. And here I have a head start: the navigation zones built for the pathfinding are ideal. Intersection tests and ray casting fall out in no time. Perhaps this shouldn’t be surprising. A pathfinding data structure must necessarily be able to determine whether a path is valid or not.

Beyond that my main requirement is to constrain moving objects against each other and the world. The algorithm goes something like this:

1. Update object positions.
2. Find pairs of intersecting objects and objects intersecting with the world.
3. Put all the intersections in a matrix.
4. Solve the matrix equation.
5. Move the objects to the constrained positions.

Note that one object can push another which in turn pushes a third and so on. This is why the constraints must be solved together.

Now, there are a few implementation details. Finding intersecting pairs is O(N^2) using brute force; it needs a spatial data structure for acceleration. You don’t want all intersections in the same matrix, only the ones that affect each other. So the world needs to be split up into islands. Matrix maths can get pretty complex but in this case a simple iterative method works. I might also want to constrain velocities. It’s much the same process.

A lot of typing and a few division-by-zero bugs later it’s all working. Was all that worth it? Well, it was fun and I learned some new things. So yes then.

Advertisements