Procedural Animation 3: Gradient Descent

Intro

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!

What we'll make!

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.

Your browser doesn't support html5 canvas :c.

Anim 1: Reaching arms with 20 and 100 segments. Click & Drag to move the ball!

The problem: Kinematics

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 refered to as the "Geometry of Motion". For charachter 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 infront 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 charachter animation, robotics, and predicting people's location in VR. It'd be pretty useful to have a way to solve it!

Your browser doesn't support html5 canvas :c. Shoulder Angle (α) Elbow Angle (β)

Anim 1: The problem: Trying to reach for the ball by changing the angles of both joints. How can we find these angles?

Simple arms in 2d

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 are 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's a million other gamedev sites, robotics courses, and random medium posts, so I'll 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.

Harder problems.. I.e. Arms with more joints..?

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 itteratively, 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.

Forward Kinematics

First, we need to work out where the end of our arm is… We write the angle at the shouder 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*}

Distance function

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 corrisponding distance the arm is from the target the z (vertical) axis, we can view the distance as a shape.

Your browser doesn't support html5 canvas :c. Shoulder Angle (α) Elbow Angle (β) Upper Arm Len Forearm Len

Anim 2: The distance function for any of the shoulder and elbow angles. On the graph: Click to pan, scroll wheel to zoom, and mouse over to see the distance/angles at any point. Try messing around with the angles and arm lengths, or move the target ball!

Each point on the surface corrisponds to some shoulder and elbow angles, and the height (or colour) there corrisponds 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 corrispond 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.

Gradient Descent

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

Then we can consider the partial derivitive 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 bring increase the distance. Decreasing \(\alpha\) then brings hand towards the target. If the derivitive 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 is called 'gradient descent', because if we look at the surface, each time we update we travel down the surface until we reach the bottom.

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

Implementation & Extras

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…

Your browser doesn't support html5 canvas :c.

Anim 3: Glitchy movement, could be a neat effect for a Stranger Things monster..?

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.