An Universal Solution for Procedural Locomotion

During Thanksgiving of 2022, I was thinking about making an independent game with various robots in a deprecated planet. While suffering from a bulk of animation sequence required for each type of robots locomotion, I am thinking about developing an universal procedural solution for it.

Since only few people actually dive deep into this topic after searching around, I hope this essay could be helpful :)

After weeks of experiment, the final result could satisfy the following requirements:

1. coping with any rig systems, including unsymmetrical rigs.

   

2. coping with any terrain conditions.

   

3. dynamic transition from different velocity input.

   

The project was written in Unity C#.

---

Structure

Here is the framework of algorithm.

So intuitively speaking, I want to break the process into three parts:

1. Body Prediction
2. Body coordination
3. leg movement
4. Dynamic Prediction Adjustment

---

1. Body Prediction

Prediction system is to check if there exist any legs that need to move given locomotion instruction.

The algorithm is about predicting the future location of each foot within a period given velocity input. And if there exists the legs that prediction is far enough. Then set to body status from “Static” to “Move” and start scheduling “How to move legs”. There will be a array of legs in order of moving priority.

there are different ways of checking whether legs have to move or not, like the one made by checking gravity center, but from my perspective, measuring center of gravity cannot describe the motivation for legs movement, like rotating and acceleration. Measuring it from each legs perspective seems to be most practical.

---

2. Body Coordination

Coordination between different rig system

Empirically, creature move legs by order. Like some of us like to move left legs first as “regular” and others do right first as “goofy”. But none of us move two legs both ordinarily. So there is a specific sequence that drive all the legs. Each legs are trigger one by one within a “locomotion period”. I break each legs in “period” into two phase “Time_moving” and “Time_stop”, which “Time_moving” describe the phase when legs are moving in the air, and “Time_stop” describe the phase when feet on the ground supporting the body.

Coordination between different velocity

Here is the comparison between running and walking for biped rig. As you can see the difference that in running circle there is a period that both legs are in the air. we call it as “Time_in_air”. Since creatures are actually dropping with gravity in “Time_in_air”, the period is actually really small on earth, around 0.1- 0.3s max.

Coordination Algorithm

So the algorithm is pretty simple. Once we start to cycle the sequence, if a leg meets the trigger time:
1)Find the predicted destination.
2)Start to move to the destination in “Move Time”.

But how should we coordinate velocity and period? We all know that when running fast, the period is much shorter than walking one. The key to answer this is that “Time_stop” is the only relevant to “Velocity”and “Leg length”. Think about what happened during the “Time_stop”? Our body moves from backmost to front most, in “Speed” and “Stall Time”, right?
So We can conclude that:

$$\begin{aligned} T_{\text {period }} & =T_{\text {move }}+T_{\text {stop }} \\ T_{\text {stop }} \times V_{\text {body }} & =L_{\text {stride }} \\ T_{\text {stop }} & =\frac{L_{\text {stride }}}{V_{\text {body }}} \\ \end{aligned}$$

Then how do we know period? Suppose “Time_in_air” is constant around 0.1s (we are all ruled by gravity). Which means that the starting time of last leg should be no longer than the end of first leg moving plus Time in air.

We could say that:

$$\begin{aligned}T_{\text {stop }}+T_{\text {in air }} & =\frac{T_{\text {period }}}\\ T_{\text {in air }}+\frac{L_{\text {stride }}}{V_{\text {body }}}=\frac{T_{\text {period }}}{n} {n}\end{aligned}$$

So that, we can conclude all the relation to Velocity.

$$\begin{array}{l} T_{\text {period }}=n \times\left(T_{\text {inair }}+\frac{L_{\text {stride }}}{V_{\text {body }}}\right) \\ T_{\text {stop }}= \frac{L_{\text {stride }}}{V_{\text {body }}} \\ T_{\text {move }}=n \times T_{\text {in air }}+\frac{n \times L_{\text {stride }}}{V_{\text {body }}}-\frac{L_{\text {stride }}}{V_{\text {body }}} \\ T_{\text {move }}=n \times T_{\text {in air }}+\frac{(n-1) \times L_{s t i d e}}{V_{\text {body }}} \end{array}$$

So here we obtain the the relationship between input velocity and “Period”,”Time_move” and “Time_triggering” and “Time_stop”. And Length of Stride here is constant.

$$L_\text {stride } \approx \sqrt[2]{L_{\text {leg height }}{ }^{2}-L_{\text {leg length }}}{ }^{2}$$

3. Leg Movement

Driver and IK

I write a simple 2-link IK algorithm to make driver control the leg animation. You can find a lot about IK system so I won’t elaborate it here.

Driver Detailed Animation

This is quite important. If you watched the Unity Official Video, They describe the driver movement that’s the y-axis movement as a semi-sphere, which is wrong. The best way to describe feet movement is more like a cubic Bezier curve.

To simplify, we take the four control points of this Bezier curve in ((0,0), (0,1)), ((0.5,0) (1,0)) .

The form of Cubic Bezier is:

$$\mathbf{B}(t)=(1-t)^3 \mathbf{P}_0+3(1-t)^2 t \mathbf{P}_1+3(1-t) t^2 \mathbf{P}_2+t^3 \mathbf{P}_3, 0 \leq t \leq 1$$

Since t is just the lerp value on X axis, so that we could obtain the movement on Y axis is:

$$\begin{aligned} Y(t)= & (1-t)^{3} \cdot 0+3(1-t)^{2} t \cdot 1 +3(1-t) t^{2} \cdot 0+t^{3} \cdot 0 \\ Y(t)= & 3(1-t)^{2} t \end{aligned}$$

So this form is pretty simple.

Optimization: Dynamic Prediction Adjustment

Remember that currently each foot destination is determined at the trigger moment. But is that destination ideal? The problem is what happen if velocity change during leg is moving? Do we have any remedis?
Yes, Since before the foot hit the destination, it is always moving and adjustable. So we can adjust the destination on each frame. Here is the numerical algorithm.

Here is the comparison between period prediction(left bone) and dynamic prediction adjustment(right one).

As you can see, the robot with “Dynamic Prediction Adjustment” has much cleaner animation.