Making believable 3d navigation doesn’t just mean finding straight-line paths for AI to travel on, it also means following them in a realistic way. What we really want to be able to do is make our birds/fish/spaceships/planes/dragons move in ways that seem plausible, and one of the ways we can do this is to set parameters such as pitch and yaw rates that discriminate between say a bird and a submarine. In this post I am going to describe some of the updates I have applied to Mercuna to allow more realistic constraints to our curve-following.
Path following with acceleration and turning rate limits
The first constraint we had in Mercuna was to limit the maximum sideways (or perpendicular) acceleration that an agent could apply. A way of thinking of this type of limitation is like driving a car where the grip of the tires on the road provide a limit on the cornering speed. In Mercuna we follow curves described by polynomials (splines), and as such we can calculate the exact amount of perpendicular acceleration we need to follow the curve at any given speed. Correspondingly we can also find the fastest speed we could travel down a curve, given a maximum acceleration profile.
In mathematical notation we describe the curves our agents follow via parameterised paths, i.e. we take some parameter \(u\) and map it to positions \(\underline{\gamma}(u)\) in a way that is smooth (typically a cubic spline). In order to find the maximum speed \(v_{\rm max}\) set by a maximum perpendicular acceleration \(a_\perp^{\max{}}\), we can use the formula
$$ v_{\rm max} = \sqrt{\frac{a_{\perp}^{\rm max}}{k}} $$
where \(k\) is the curvature (or inverse radius of curvature, see wikipedia), a number that describes how sharp a corner is. This is related to the curve \(\gamma(u)\) given by
$$ k = \frac{\left| \gamma’ \times \gamma^{\prime\prime} \right|}{\left| \gamma’ \right|^3} $$
where \(\gamma’\) and \(\gamma^{\prime\prime}\) refer to 1st and 2nd derivatives of the position with respect to the parameter \(u\).
This works very well if you have a limited sideways acceleration, however we found that if the agent also had a limited turning rate, then for sharp corners they would be unable to turn fast enough and would look like they were sliding into the turns. This is good for spaceships but not for the flight style for birds. The limited turning rates provide another constraint that we need to take into account when calculating the speed of a spline.
A first step to limiting turning rates is to calculate the turning rate required to keep an agent facing forwards (i.e. down the curve) whilst following the curve. If the movement is at unit speed then the angular velocity (wikipedia) turns out to be given by a vector version of curvature
$$ \underline{k} = \frac{\gamma’ \times \gamma^{\prime\prime}}{\left| \gamma’ \right|^3} $$
where the direction of this vector corresponds to the axis you need to turn around and the length corresponds to the turning rate about this axis. For faster speeds we need a higher turning rate, and as such the angular velocity for non-unit speed is \(\underline{\omega} = \underline{k} v\).
Correspondingly, if we want our agent to be able to follow our curve and not exceed some maximum angular velocity \(\omega^{\max{}}\) then we need to obey the combined speed limit
$$ v_{\rm max} = \min \left( \sqrt{\frac{a^{\max{}}_{\perp}}{k}} ,\, \frac{\omega^{\max{}}}{k} \right) .$$
Interestingly this means that when \(k\) is small, it is usually the angular rate limits that are the most important (since \(k\ll \sqrt{k}\) for \(k \ll 1\)). Another way of saying this is that on a tight enough corner you are always turning rate limited rather than limited by your perpendicular acceleration.
Applying limits on pitch and yaw
In our recent versions we wanted to introduce pitch and yaw rate limits, so that an agent that had some limit on how fast it could yaw (or pitch) can choose path speeds that it can achieve. The pitch rate \(\omega_{\rm pitch}\) and yaw rate \(\omega_{\rm yaw}\) can be found by decomposing \(\underline{\omega}\) into the local frame of reference.
In the local frame of reference, the yaw angular velocity direction \(\hat{\Omega}_{\rm yaw}\) is the component in the local up (see diagram), the pitch angular velocity direction \(\hat{\Omega}_{\rm pitch}\) is the local right and the roll \(\hat{\Omega}_{\rm roll}\) in the local forward. We can thus write \(\omega_{\rm pitch} = k_{\rm pitch} v\), \(\omega_{\rm yaw} = k_{\rm yaw}v\), where \(k_{\rm pitch} = \underline{k} \cdot \hat{\Omega}_{\rm pitch}\), \(k_{\rm yaw} = \underline{k} \cdot \hat{\Omega}_{\rm yaw}\).
Note that there is no roll-component since \(\underline{k}\) has no component in the forward direction – this makes sense because we only required the agent forward vector to point down the curve, we put no constraint on the roll.
Now making our agent follow our curve and not exceed a pitch or yaw rate constraint corresponds to the criteria:
$$ v_{\rm max} = \min \left( \sqrt{\frac{a^{\max{}}_{\perp}}{k}} ,\, \frac{ \omega^{\max{}}_{\rm pitch}}{k_{\rm pitch}},\, \frac{\omega^{\max{}}_{\rm yaw}}{k_{\rm yaw}} \right) .$$
For example, if the curve is turning to the left but not turning up or down, then \(k_{\rm yaw}\) will be high and we will be limited by our maximum yaw rate, \(\omega^{\max{}}_{\rm yaw}\). Alternatively our curve turns upwards (i.e. pitching) then \(k_{\rm pitch}\) will be high and we will be limited by our maximum pitch rate, \(\omega^{\max{}}_{\rm pitch}\).
This is really the essence of the speed limits in Mercuna, and one can see how one can build up from here, for example, to integrate the maximum speeds over the curve to find the minimum time to follow, or adjusting the curve \(\gamma\) to make it smoother curves and give us higher speed limits. Mercuna actually does a few other clever things too, such as finding speed minima, and calculating turn constraints for agents that don’t face exactly down the curves, but these are the basics.
Have a look at this video to see some of these in action. I hope you found this article a useful introduction into the methods we use for setting agent movement parameters in Mercuna. If you’ve encountered similar problems then please get in touch!