In this third and final section, we'll cover how to solve harder problems that don't necessarily have a single solution, or ones that have solutions that can't be written as an equation of known variables.

If you haven't read Part 1, we covered some simple state machines and some general ideas on how I try to approach these kind of problems.

You might also want to check out Part 2, where we went over how to build up more complex movement by combining functions of state.

And finally, all of the (interactive!) animations here are running in javascript canvas, so you can open the source code in the inspector or find it on my github for the site!

These tenticles/ arms/ vines might make a fun enemy or background in a game, but also demonstrate an idea that can be used to solve all kinds of problems! The same idea (gradient descent) is the backbone of a huge amount of modern AI - used to improve Google's results, autonomous cars, and more… And all you need to understand it is a basic knowledge of derivatives.

Generally, (and according to google) kinematics is a branch of mechanics that deals with the features or properties of the motion of an object. It's often referred to as the "Geometry of Motion". For character animation, we usually deal with Kinematics of Simple Chains - or limbs…

For a given arm, Forward Kinematics is working out where the hand (or end) is in space given the angles between the shoulder, and upper and lower arms. The opposite of this, called Inverse Kinematics (IK), is where you have a fixed target point and instead want to choose the same angles so the hand is as close to it as possible.

Forward Kinematics:

Your upper arm is at \(\alpha\) to your torso, and your upper arm is \(\beta\) to your lower arm, where is your hand?

Inverse Kinematics:

You want to reach for a ball in-front of you, what angles should you have at your shoulder and elbow?

We're going to look at the second one. Inverse Kinematics are used for all kinds of character animation, robotics, and predicting people's location in VR. It'd be pretty useful to have a way to solve it!

For the 2D case, and when there are only two joints in the arm, there are (usually) two solutions - an 'elbows up' position, and an 'elbows down' one.

Of course, there are cases where there is no solution. If the ball is out of reach, for example.

It's possible to work out these two angles with coordinate geometry or a bit of trig, as long as you have the lengths of both arm segments and the target location. However, as there are a million other gamedev sites, robotics courses, and random medium posts, I won't explain it here again. It is a fun problem though - I'd recommend giving it a go!

It's also worth noting problems and limbs in 3D can be solved using the same 2D algorithm/equation with one trick: An 'elbow target'. We add a point that, given the choice, the elbow will be as near to as possible. This (interestingly) causes all 5 points: Shoulder, Elbow, Hand, Hand Target, and Elbow Target to all lie in the same plane. We can take the plane defined by the fixed points: Shoulder, Hand Target, and Elbow Target and solve the problem in 2d on that plane. This is how a lot of kinematics in games is done.

It's not possible to solve harder problems using the same idea however, if you add an extra segment to the arm there suddenly isn't a way to find solutions (mostly because there are now likely infinite solutions…).

This is what I wanted to write about… How can you find approximate or fast solutions to a problem that's much harder to solve exactly, or find 'organic' solutions to some problem that has a lot of possible solutions.

Instead of trying to find a solution instantly, we take the current position of the arm and figure out how to improve it slightly. The solution is then calculated iteratively, looping over and over either until we're not getting any closer or we're within some distance.

Because we're only 3 dimensional creatures… The solution is easiest to describe for arms with 2 joints… But the maths works for any number of joints.

First, we need to work out where the end of our arm is… We write the angle at the shoulder as \(\alpha\), and at the elbow as \(\beta\). The length of the upper arm is \(l1\), and forearm is \(l2\). I take the shoulder to be at \((0,0)\)

To do this, we can split it into 2 parts. The position of the elbow will be at:

\begin{align*} Elbow_x & = l1 * sin(\alpha) \\ Elbow_y & = l1 * cos(\alpha) \end{align*}

Then, similarly, we can work out the position of the hand relative to the elbow. This is a little harder to see, but we can take the angle of the arm relative to the ground (\(\alpha + \beta\)) and use the same trig formula.

\begin{align*} Hand_x - Elbow_x & = l2 * sin(\alpha + \beta) \\ Hand_y - Elbow_y & = l2 * cos(\alpha + \beta) \end{align*}

Then the position of the hand is simply the sum.

\begin{align*} Hand_x & = l1 * sin(\alpha) + l2 * sin(\beta - \alpha) \\ Hand_y & = l1 * cos(\alpha) + l2 * cos(\beta - \alpha) \end{align*}

In order to perform gradient descent, we need a formula for the error we're trying to reduce. This is the distance from our hand to our target. Ideally, we want this distance to be 0, which'd mean our hand is exactly on the target.

The distance in x and y can be written from the above. Here \(|x|\) means the absolute value of x, or the non-negative value of x.

\begin{align*} Dist_x & = | Target_x - (l1 * sin(\alpha) + l2 * sin(\alpha + \beta)) | \\ Dist_y & = | Target_y - (l1 * cos(\alpha) + l2 * cos(\alpha + \beta)) | \end{align*}

Then using pythagoras the distance is:

\begin{align*} Dist = \sqrt{Dist_x^2 - Dist_y^2} \end{align*}

We can look at this distance for any value of \(\alpha\) and \(\beta\). If we plot \(\alpha\) and \(\beta\) on the x and y coordinates of a graph, and the corresponding distance the arm is from the target the z (vertical) axis, we can view the distance as a shape.

Each point on the surface corresponds to some shoulder and elbow angles, and the height (or colour) there corresponds to the distance those angles put the hand from the target. As you change the angles of the arms, you can see the graph translate - the center of it shows the current elbow and shoulder angles.

Try tweaking lengths, then read the lowest/highest point from the graph… Then change the arm's angles to those and see what it looks like.

There's often two low points in the graph - which correspond to the two best solutions. Moving the ball far away gives only one low point - meaning there's only one best solution; when the arm is pointing towards it. There's also usually one worst solution (the reddest/ highest point), which is where the arm is pointing away from the ball.

Our goal will be effectively to try and find the lowest point on this surface - the angles there will bring our arm closest to our target ball.

We can use the derivative of this distance function to improve our errors. First, write the distance corresponding to \(\alpha\) and \(\beta\) as \(Dist(\alpha, \beta)\).

Then we can consider the partial derivative with respect to the angles.

\begin{align*} \frac{\partial Dist}{\partial \alpha} \end{align*}

This works out to a single value, and can be read/ thought of as 'how does the distance to the target change when I change \(\alpha\) by a very small amount'.

For example if \(\frac{\partial Dist}{\partial \alpha}\) is positive, then increasing \(\alpha\) will increase the distance. Decreasing \(\alpha\) then brings the hand towards the target. If the derivative is negative, we should instead increase \(\alpha\) by a small amount to improve our hand position. This can be written as:

\begin{align*} \alpha := \alpha - k * \frac{\partial Dist}{\partial \alpha} \end{align*}

Here k is a small value, in the animations I have it set to 0.0001. This means each update loop we update alpha to move the hand a little closer.

The maths is exactly the same for the elbow position:

\begin{align*} \beta := \beta - k* \frac{\partial Dist}{\partial \beta} \end{align*}

And for any number of limbs.

This method of improving iteratively is called 'gradient descent'. This can be visualized from Anim 2; we're essentially standing on a point on the surface, then finding the direction of steepest descent and moving a short distance. Repeating this process will, in many problems (including this one), always get us to a solution if it exists.

Proving that this method finds the direction of steepest descent, or that this problem is convex and so will always find a possible solution is left as an exercise to the reader :)

The demos just perform this update once per frame, but it's easy to completely solve the system by running for more iterations.

It might help to look through the source code for the animations (embedded into this page), or available here on Github. You're free to lift this for anything, the code's CC0!

Here's a bonus of what happens when you accidentally make 3 arms compete for who renders at the same time…

Anyway, I hope this helped! Gradient descent is a very powerful tool for solving any kind of problem if you're able to express it in a certain way. For more procedural animation stuff, you might be interested in Part 1 where I looked at some core ideas and a light animation, or Part 2 with some more fancy function ideas and shapes.