I actually got around to writing physics code at last. It was incredibly quick and easy.

Getting it to work right, though, that took nine whole days.

I tend take physics for granted, in the real world and in games. There’s a floor? I can stand on it and won’t fall through. There’s walls? I will collide with them instead of drifting ghostlike through them. Pick up and throw things, and they arc with gravity, bounce of other objects they hit, reach the floor and slide a little, then come to a stop.

In the real world, all of that behaviour comes for free. In a game, none of it does.

I mentioned a while back the possibility of using an existing rigidbody physics library and why I wanted to avoid that route: I don’t actually need most of what they do, and they don’t help much with one of the most crucial features: a first-person camera that will slide along the floor walls under player control. There must be books and articles and papers out there that cover in detail about how to write a good FPS camera, but I couldn’t find any.

Of the three books I had to hand, Physics for Game Developers (Bourg & Bywalec, 2013; O’Reilly) and Game Physics (Eberly, 2004; Morgan Kaufmann) were all about rigidbody simulations and silent on the topic of FPS camera behaviour; and Real-Time Collision Detection (Ericson, 2005; Morgan Kaufmann), as the title promised, focused entirely on collision detection and not response. I later came across Collision Detection in Interactive 3D Environments (van den Bergen, 2004; Morgan Kaufmann), which is also excellent, but also covers only the topic of collision detection.

So everything in this post–right and wrong–comes from scattered sources: the collision detection books above, scattered memories from a failed attempt years ago at writing a physics-driven grappling-hook game for touchscreens, a couple of papers that were both helpful and misleading, and a little digging through the quake source code to see how its player movement worked.

The task:

Given a sphere that represents a moving object–either player or AI controlled, or under the influence of physical forces alone:

  1. Calculate how it will move in response to physical forces;
  2. Determine if it will collide with any other objects as it moves;
  3. If it does collide, alter its movement with a suitable response to the collision.

Part 1 is pretty straightforward: an object has a position, a velocity (the first derivative of position), and an acceleration (the second derivative of position). On each frame: figure out what forces apply to the object; calculate the resulting acceleration (F = m.a); integrate the acceleration to get the new velocity (v += a.dt); then integrate the velocity to get the new position (x += v.dt). That’s using Euler’s method, which I learnt (though without knowing the name or anything about forces, let along integration) back when I was about 10 years old, writing little spaceship games and platform games in Qbasic, for which it works well enough. But it’s not great for realistic, robust physics. There are a multitude of other integration methods, and plenty of literature on them (Game Physics has a whole chapter devoted to them). I don’t really have a good idea of which will work best for my game; but knowing I at least want to have drag forces from air resistance, which is dependent upon velocity, I implemented the ‘velocity Verlet’ integrator which the book assures me will work better for that. But given the nature of my game, where most moving objects are moving through the air–and nary a crate to be seen, let alone to have objects piled upon–and I’m not overly concerned with accuray, I could probably use any method without any real problems.

Well, without any real problems caused by silly mistakes! Game Physics unfortunately uses 𝐲̇ notation to mean the derivative of a vector. And a tiny dot like that is easy to miss! I misread one equation as having just 𝐲 which meant each sphere’s velocity was based on its position the previous frame instead of its previous velocity. Fixed it easily once I actually noticed which part of the code was wrong.

Part 2, detecting collisions, is also extremely well-documented (and I had two whole books on it handy). I read through a number of sections of Real-Time Collision Detection, then implemented two of its pseudocode functions for what looked to be a simple (if brute force) approach: test for intersections between the sphere and every triangle in the mesh. It went pretty smoothly; first I tested against a single triangle:

A red wireframe sphere is intersecting a purple triangle. Red, green, and blue axial arrows show the sphere’s origin and orientation, and a small white line from the triangle’s edge shows the closest point on the triangle to the sphere’s centre.

Then I upgraded: first to a cube mesh with 12 triangles, then to the Sponza mesh with 40,000 of them:

Part 3, responding to collisions, turned out to be fraught. Without a clear idea of what I needed to do or how I needed to do it, I began with something simple and obvious: when a collision is detected, just stop the sphere at the point where it hits the triangle.

Even that turned out to be not so simple and obvious as I thought–I knew the point on the triangle that was closest to the center of the sphere (as it intersected the triangle); but what I needed was the point on the sphere’s trajectory this frame just as (or just before) it touched the triangle. I wrestled with the geometry of the problem, and tried diagramming it, over and over again (below is the first), but I couldn’t make sense of it.

A circle is intersecting an angled line representing a wall. A blue arrow shows the intended movement of the circle; a green arrow is perpendicular to the wall showing the vector between the hit point and the sphere’s origin; and a section of the blue arrow’s path is highlighted and labelled “hit_to_origin • dpos”.

Eventually I decided I needed to a different strategy, and turned to an iterative binary search for the time of impact: position the sphere at the halfway point of the trajectory, and collision test again; if it collides there move it back half of the remaining distance, but if it doesn’t then move it forward half of the remaining distance; and repeat, moving the sphere shorter and shorter distances until I’ve found a precise-enough point of impact. This was refreshingly easy both to write and to get right. As soon as it was in, I decided it was time to start applying collision detection and response to the in-game camera–as I’d need it there soon enough regardless.

This was good progress! Two days of reading up on the problem and coding up a solution, and had got this far already. All I had left was to make the camera slide when it collided instead of stopping dead, and I’d be done, right?