Entomon
Procedural Animation
Entomon is the name of the collection of systems I created for multi-legged procedural locomotion. In it, I wanted to create a realistic, artist-configurable system of procedural locomotion fit for creatures with at least 5 legs.
This project was created in parallel with the school curriculum.
My system was later used by Jo Colomban who added the AI we created together for Menagerie.
(5 Legged Locomotion)
Auto-Rig
The first step for the spider is to rig it. Now, Auto-Rig might not be entirely truthful in that an armature does need to be in place. The auto-rigging part is using this very basic armature, and separating it into Limbs that can be procedurally animated.
The prerequisite for having the auto-rigging work is for all limbs to have consistent naming schemes. The "hip", or the bone closest to the body, needs to contain a certain key that is shared between all of the limbs to be procedurally animated, and likewise for the end effector. Then, the program loops over the armature and automatically separates it into distinct limb objects. This takes mere micro-seconds, and only needs to be performed once, at the start of play. In this step, a lot of the heavy lifting for the IK-system is also performed. Additionally, the parameters for the Foot Planning are set.
The benefit of this method is that the same system can be used by many different multi-legged creatures with minimal setup.
Pictured above is a minimalistic representation of the rig, where the purple arrows represent the foot direction, and the white ones the Pole Constraint for the IK.
Inverse Kinematics
Inverse Kinematics are the backbone of many kinds of procedural animation, whether used for correctly placing the foot on stairs, or like I have, to drive procedural animation.
Initially, I used CCD IK, which is one of the simpler real time methods, but as it turned out, it came with some draw backs.
Partly due to being angle based, CCD has a tendency to produce unnatural results when no constraints are used for the angles.
Because I wanted a system that required minimal setup, I did not want to force the user to define these constraints per limb.
Unnatural looking results from CCD
More natural results from FABRIK
Instead, I turned to FABRIK, a positional approach to IK. FABRIK has exploded in popularity in recent years due to being faster, easier and more natural looking than CCD. Even without any constraints, FABRIK looked far better. However, I did still apply a pole constraint automatically based on the resting position of the limb.
Writing these two IK Solvers, and getting them to behave, took a large chunk of time from the project. I am however still happy I did it, as I learned a lot.
Setting up the IK was more or less as simple as creating the pole constraint, which can be represented simply as a point in space towards which the limbs are moved before the solving starts. The solving always produced good enough results in only two or three iterations, but I set it to 10 since the performance was so good that it didn't matter.
The essential code for the FABRIK Solver. EvaluateAngles() takes the positional changes in BackwardReach() and ForwardReach() and converts it into an angular change.
For two bones, it is possible to solve the IK analytically, but it was important to me to allow for as many bones as were needed.
While Unreal Engine has an implementation of IK, it is node based, and was simply insufficient for my needs.
Foot Planning
Foot planning is the core of how the system looks. In essence, the spider is a drone with constraints to only be able to move in certain ways, and the legs are completely cosmetic. In the future I would like to also constrain the movement by the state of the legs, but as of right now that is not the case.
The video above is a simplified diagram of how the essential foot planning is taking place. Each blue notch represents when a certain limb should move. The pawn holds a repeating clock that constantly checks if it is time for any of the limbs to move. For an 8 legged spider without any "personality offsets" (slight randomness per limb to make it look more natural), this diagram wouldn't look too complex, as the offsets would most likely either be zero or half.
I was inspired by Karim Et Al and their Gait Manager, which requires the user to define a gait offset for each limb. This method allows for many kinds of gait and for it to be easily swapped out depending on any factors, such as when a horse goes from a trot to a gallop (the timings per leg are different).
Beyond the gait management is the moving of the foot itself. When the foot is to move, it calculates the "optimal position" based on the resting foot location and the velocity of the body. It then traces around this point to find an actual point on geometry where it can place a foot. When it has found one, it also performs a series of traces at the middle point between the current foot location and the target, so that the foot will raise enough on the way there to hopefully not hit any obstacles.
A standard spider gait.
A non-standard spider gait with some personality offsets.
The foot planning is still the biggest point of improvement. Sometimes it chooses undesirable locations. Also, when it cannot find a foot placement, the spider should stop walking, and try a different path until it can pass.
Path Finding
For the path finding, I decided to do something less orthodox. Since I wanted free movement on all axes, I created what I call a Nav Volume (a play on Nav Mesh). A nav volume is a grid of points, where each point stores its neighbors as well as the offset to the nearest surface.
The picture above shows a lower resolution representation of the calculated fuzzy normals. These are used for the desired orientation of the multi-legged actor.
In path-finding, then, the distance can be used to allow or disallow the path.
After the path has been found using a simple A* implementation, it is smoothed, simplified, and corrected to look more natural. This includes moving the points to the Actor's preferred distance. This can safely be done because the normal is known.
Building the Nav Volume
One would rightly assume that it takes some time to build the nav volume. This is true. For a 32x32x32m volume with a distance of 64 cm between the points, that would mean evaluating 125k points. Most of these points would be culled and not added to the final list of points. In my case, about 60% of points were culled. Luckily, all of that data can be built and stored in a file that is simply read when the level loads.
Improvements
The main improvement is for the foot placement. Sometimes it chooses bad locations that result in intersections with the obstacles. Additionally I would really like to add a kind of body bobbing from the steps. I started doing it, but never quite finished since it ended up being quite complicated, and so I deemed it as out of scope.
But I believe that it is certainly possible to extend the system to accomodate this. The only problem is that in many cases, since the legs are timed in parallel, the bobbing forces are cancelled out. I would need to find another solution, possibly one that does not use physics, or at least hi-jacks it to do what I want it to do, to simulate the body bobbing.
In addition, I would like the path-finding to work better in crawl-spaces. It behaves very unnaturally in such spaces.