A new feature that I have been working on recently and that I am very excited about is our new spline based steering system. We wanted to solve the problem of jerky movement and agents occasionally sliding off paths and hitting walls, and to have more natural looking movement. We want agents to take the racing line around corners with minimal loss of speed. To achieve this, instead of treating paths as a series of straight line segments, we now fit a polynomial curve between the points and calculate the actual accelerations needed to stay on the curve.

The paths generated by the Mercuna pathfinder are composed of a series of path points with clear lines of movement between them. Previously we had been using a basic, naive approach of simply moving directly from one point to the next. This approach is commonly used in games, and can work fairly well for character steering. However, this has two major problems for agents with momentum. Firstly, even with some added smoothing, the movement can look very robotic. Agents tend to move in a straight line and then make hard turns close to path points. Secondly, due to the instantaneous velocity changes required at the path points, agents frequently miss the turn and fall off the path, which then can result in collisions with walls. While we had implemented various fixes to mitigate these problems, including dynamic path shortcutting, and raycasting ahead to check for collisions, they had mixed success.

Our new steering approach involves fitting a third order polynomial spline segment between each pair of path points and using a “splinecast” through the navigation octree to check that the segments don’t intersect with any geometry. Fitting a spline to the paths immediately means that agents are following much smoother curves which results in far more natural looking movement. Using third order polynomials allows us to join spline segments at path points and to match the first order derivatives in order to keep the velocity continuous, and avoids the instantaneous velocity change problem of straight line segments. In addition, the second derivative at each point on the spline specifies the exact acceleration required at that point to follow the spline without falling off.

However, just fitting splines and calculating the accelerations isn’t sufficient. If the speed at which an agent tries to follow the spline is too high, then staying on the curve requires a larger acceleration than the simulated agent should be capable of. We therefore constrain the maximum speed at which the spline can be traversed, by finding the points with minimum and maximum curvature on each segment, which correspond to the places where minimum and maximum acceleration perpendicular to the direction of travel must be used to stay on the curve. From this we can calculate the maximum speed at these points given the available acceleration. By then interpolating between these points we can obtain a reasonable approximation to the maximum possible speeds along the entire segment.

Getting all this to work, including regenerating sections of the spline when the destination moves and making the spline generation and update happen asynchronously on a background thread, proved to be slightly more challenging than first anticipated. I had to brush up on numerical integration techniques and restructure the code several times, but I am now very pleased with the results. The movement of agents looks much more natural and perhaps, more importantly, the approach completely eliminates the problem of agents falling off the path and colliding with fixed geometry.