Animation done externally will not always fit the environment that the characters will exist in, and this was the case for my 6th game project at TGA. Our biggest enemy had six big legs that would not fit in the environment while moving around. This was what inspired me to create a system to procedurally animate this character depending on its movement, model and the environment around it.
FABRIK
To solve inverse kinematics you can do all the math and find all possible positions of the joints to achieve the desired result. Though this is much too expensive and hard to implement. A much faster and performant algorithm is using Forwards And Backwards Reaching Inverse Kinematics (FABRIK).
FABRIK works by making all joints push and pull on each other to always keep a set distance between them. There are two steps to create this, the first is moving the foot to a desired location then rotating and translating the joints to face the previous joint and hold a set distance. This is the “Forward Reaching” part of the algorithm and creating a worm-like behaviour.
Then to attach this back to the model, we perform the exact same steps but in the other direction. Move the joint furthest from the foot to the attachment point of the leg then move all joint in the same way as the first step.
// Forward reaching
for (int i = 1; i < aIKBone.chainLength; ++i)
{
const Tga::Vector3f previousJointPos = ikJointChain[i - 1].position;
Tga::Vector3f fromPrevious = ikJointChain[i].position - previousJointPos;
fromPrevious.Normalize();
ikJointChain[i].position = previousJointPos + fromPrevious * aIKBone.jointLengths[i - 1];
}
// Backward reaching
for (int i = aIKBone.chainLength - 1; i >= 0; --i)
{
const Tga::Vector3f previousJointPos = ikJointChain[i + 1].position;
const Tga::Vector3f currentPos = ikJointChain[i].position;
Tga::Vector3f fromPrevious = currentPos - previousJointPos;
fromPrevious.Normalize();
ikJointChain[i].position = previousJointPos + fromPrevious * aIKBone.jointLengths[i];
}
This is the “Backwards Reaching” part and will make the model look like a leg… but a very broken one…
I must admit that I spent way too much time solving this. I started by researching how this is done in robotics and found different types of joint constraints and started implementing these in the FABRIK solver. A hinge constraint would limit the movement of joints to only rotate around an axis, and a ball joint that would let the leg rotate freely in a cone shape. With these constraints the leg would straighten itself with the hinge constraint and I could limit how far the legs could turn with the ball constraint. But this was much harder to create than what I originally though and often resulted in the leg not finding a position that would put the foot in the right spot and could create sporadic movement when bent in extreme angles.
I later realized that there was a much simpler solution, before performing the FABRIK algorithm I could just translate all joints upwards which would act as a bias and make the joints trend upwards, and this worked unexpectedly well.
This was a MUCH simpler solution and was also easier to work with, and more performant too. I could also control how much the joints move upwards every frame to make the leg more or less stiff. Combining this with some more code to solve the rotation of all joints created the result above.
Moving the feet
With FABRIK implemented I could now move the foot to any point I want and it would bend accordingly. But currently I had to move all feet manually and moving the robot itself only made the legs point to their original position.
This was a good start but now I had to find where to move the feet to and also when to move them. One option would be to put all legs in a list and move through the list moving each leg one after the other, this would work great for when the robot is moving forward, but may look weird when rotating and changing directions and does also not give a lot of control to tweak the movement.
I instead chose to define a rest position and a reach for each leg and then move them when they strayed too far from their rest positions. And for picking where to move it I chose the position opposite of their rest position.
The problem with this was when applying this to all legs, all of them moved in unison.
To solve this, I calculated an average offset from the feet to their rest position. When the average became too big, I picked the leg that was displaced furthest in the wrong direction and moved it in the direction of the robot’s velocity. This then made the average closer to 0 and the robot would have to move further for another leg to move.
Vector3f trend;
for (const InverseKinematicBone& ikBone : allIkBones)
{
const Vector3f worldSpaceOrigin = aEntityTransform * ikBone.footModelOffset;
trend += (worldSpaceOrigin - ikBone.footWorldTarget) / ikBone.footReach;
}
InverseKinematicBone* worstBone = nullptr;
float worstBoneAbility = 0.f;
for (InverseKinematicBone& ikBone : myConstraintController.AccessIKBones())
{
Vector3f offset = ikBone.footModelOffset;
const Vector3f worldSpaceOrigin = aEntityTransform * ikBone.footModelOffset;
Vector3f toOrigin = worldSpaceOrigin - ikBone.footWorldTarget;
float interpolationProgress = ikBone.interpolationProgress;
if (interpolationProgress < 1.f) continue;
if (toOrigin.Dot(aEntityVelocity) < 0.f) continue;
float ability = toOrigin.Length() * max(0.f, toOrigin.GetNormalized().Dot(trend.GetNormalized())) / ikBone.footReach;
if (ability > worstBoneAbility)
{
worstBoneAbility = ability;
worstBone = &ikBone;
}
}
if (worstBone && trend.Length() > 1.f)
{
const Vector3f worldSpaceOrigin = aEntityTransform * worstBone->footModelOffset;
const Vector3f toOrigin = worldSpaceOrigin - worstBone->footWorldTarget;
worstBone->lastFootWorldTarget = worstBone->interpolatedFootWorldTarget;
worstBone->footWorldTarget = worldSpaceOrigin + aEntityVelocity.GetNormalized() * worstBone->footReach;
worstBone->interpolationProgress = 0.f;
}
This worked great for moving the legs when moving the robot, the legs move one by one and followed the direction that the robot was moving in and when the faster the robot was, the more often the legs were moved. Then just adding some interpolation to the feet created convincing step-like motion.
After this I added so a number of raycasts would fire when a leg attempted to move that was trying to find a surface to put the foot.
Creating an editor
In order to apply my IK system to any model, I created an editor where you can edit which bones the IK should apply to, their rest positions, how far they can reach and much more. This is to create a good pipeline for animators to preview and quickly change how the system should behave and look.
In this editor I also included tools for previewing how the final result will look in game. You can move the model, set a constant walking speed and others. This helped me a lot when picking metrics for the character and was a big contributor to the final product.
Polishing The Looks
The hardest part about this project was making the legs move in a convincing way. Tweaking when the feet should move and to where, how to choose rotation for all the joints and picking rest positions and reach for each leg. Having an editor with tools to edit these values and preview the movement made this process much easier. And also utilising tools like Live++ to hot-reload code also improved the iteration speed of changing the behaviour.
I tested the movement in different environments, flat ground, stepping over large obstacles and moving close to walls.
Reflections
I did not have time to optimize the performance of the FABRIK algorithm, but because not many of these enemies was going to be present at the same time, this was not a problem for the project that they were going to be used in, so I could instead spend the time polishing the looks and behaviour. But if I would continue the project this is one of the things I would want to do.
Many parts of the projects are also specifically made to work for this model and may not work as great for other models. With the editor, this system can be used on any model but I believe more tools and customisation would be required for use with other models.
I spent a lot of time making advanced constraints when there was a simpler solution. Moving forward with other projects I will strive to find these simpler solutions as I wasted a lot of time with code that did not end up in the final product.
I realise that the code to find when and what foot to move may have been too complex and a simpler solution may have been enough. If I were to redo the project I would definitely first attempt to simply move the legs in a predetermined order as this may be all that is required. If it would work I would save a lot of time.
Special Thanks
Thank you to Zoe Schönborg for letting me use this amazing robot model in my portfolio and thank you Leonardo Grothe for rigging and animating the model. And a huge thank you to everyone that worked on Steel Over Eden with me, the game that all videos here were recorded in.