Snake. Smooth and accurate following behaviour

Following another object is one of the most basic movement behaviours an item can exhibit – both in the real world, and in games.

There are many different ways in which objects can follow each other, and depending on the circumstances, different kinds of movement may be appropriate.

Today we will look at one particular kind: A number of objects following another in a trail at regular distances. The movement found in games like Snake.

However – unlike the original Snake and many of its spin-offs – we will neither constrain ourselves to a grid, or to fixed time steps.

Instead we want our solution to follow arbitrary paths with arbitrary accuracy.

Constraints, requirements, basic implementation

The basic specifications of the system we are trying to develop are as follows:

• We have one head object, which is followed by a number of tail segments;
• Each segment follows the previous one at a fixed distance.

The second point implies – if this is not even its only meaning – that a segment will never be further away than the given distance from the one it is following.

This interpretation can be translated into code almost trivially:

void followParent()
{
    var differenceToParent = this.parent.Position - this.position;
    var distanceToParent = differenceToParent.Length;
    if (distanceToParent > followDistance)
    {
        var tooFar = distanceToParent - followDistance;
        var translation = differenceToParent.Normalized() * tooFar;
        this.position += translation;
    }
}

Baring mathematical optimisations, this is pretty much as simple as it gets.

Here is a little animation of how this implementation looks in real-time:

Not too bad!

Except – once the snake starts turning around, it’s tail seems to stop moving and collapse in on itself.

In some situations, that might be exactly what we want. But in this post it is not. We want our tail to follow the head smoothly, and without taking short cuts.

That is exactly what is happening here: We formulated – and more importantly implemented – our constraints too simply, which means that our tail segments are able to take a short cut. They move only the least distance they have to, in order to fulfil the distance requirement.

Remembering where we were

Let us take a look by how far we were off from our desired behaviour. We can easily keep track of the positions of the head, and draw a path along this path, to visualise it.

We can clearly see how our trail remains reasonably accurate if the head does not change its direction of movement too much. However, as soon as we turn to any significant degree the trail folds in on itself, which results in large deviations from the actual path.

How can we improve this?

As I am sure is already clear, the answer is contained in the above animation: We can simply keep track of the exact path our head moves along and position the tail along that path.

Let us build this system step by step – solving any problems we may encounter as we encounter them.

Leaving bread crumbs

At first, how exactly do we keep track of our previous positions? A simple list of vectors will do the trick:

List<Vector2> previousPositions = new List<Vector2>();
void update()
{
    this.updateMovement();
    this.previousPositions.Add(this.position);
}

Actually, there really is no reason – and it probably is a bad idea in most cases – to keep a list of previous positions since the beginning of the game. We want to be able to add new positions to one end of the list, while easily removing them from the other.

At first it looks like we may want to use a queue for this. However, we also need to be able to enumerate the list, which is a feature a lot of queue implementations do not support. To keep things easy, we will go with a linked list.

LinkedList<Vector2> previousPositions = new LinkedList<Vector2>();
void update()
{
    this.updateMovement();
    this.previousPositions.AddFirst(this.position);
}

Following the path

The next step is calculating the position of our segments from the recorded path.

Note that there are two possible approaches here: We could record a path for each segment, and have each following segment find the correct position on the path of the one it is following.

However, this will mean keeping track of a lot of redundant data – doing the same work again and again – and even more importantly it will be prone to the same accuracy errors as we see above – albeit to a smaller degree.

Instead, we will record only one path – that of the head – and have all parts follow this same path with an increasing distance.

Further note how the recorded path is really just a list of small line segments, each connecting two of the points. Our objective is to find the correct line segment for each part of our tail – and the correct position along the segment.

Let us assume that each part knows what distance it should keep from the head along the path. Knowing that we can loop over the recorded path adding up the lengths of segments, until we find the correct one. On that segment we can then interpolate the correct position:

void followHead(LinkedList<Vector2> path)
{
    var distanceLeft = this.distanceToParent;
    var segmentStart = path.First.Value;
    foreach (var point in path.Skip(1))
    {
        var segmentEnd = point;
        var segmentDiff = segmentEnd - segmentStart;
        var segmentLength = segmentDiff.Length;
        if (segmentLength >= distanceLeft)
        {
            var percentageAlongSegment = distanceLeft / segmentLength;
            this.position = segmentStart +
                            segmentDiff * percentageAlongSegment;
            break;
        }
        segmentStart = segmentEnd;
    }
}

While considerably more complex than what we had before, this method really is not all that bad.

If we replace our original movement with it, this is how it will look in game:

Perfect!

Yes. And no.

Almost perfect

The solution above does indeed do what we want. It is all but perfect however.

First, we are still missing the functionality to cut off the unnecessary end of the path. Further, we are recording a new point every frame, which could lead to a very long list – especially if we are moving slowly compared to our frame rate. I am sure you can see what would happen if we dared to stand still.

However, these problems are relatively minor and fixed easily. We can get the distance of our last tail piece and remove any segments further away than that. In addition we can add a small minimum distance required before we add a new point to the list resolving this possible memory leak as well.

Secondly, there are a few special cases that we did not cover: What is the list is empty or has only a single item? What is the recorded path is shorter than the distance assigned to our tail segment?

Again, these are relatively trivial to resolve, if we decide on how we want our snake to behave in these cases.

Performance considerations

The real problem I have with the code posted above is its runtime: We loop over the entire recorded path for every single part of the tail.

In other words, our runtime is O(nm), with n and m being the numbers of segments and tail parts respectively.

Note that the work we do inside the loop is also all but trivial: To calculate the length of each segment we need to use a square root. This is a significantly slower operation than simple algebra.

Arguably, the runtime is linear in both parameters and in fact it will not be a major problem for short tails, and paths made from reasonably few segments – something which we can influence with the minimum segment length mentioned above.

However, what if we do want snakes dozens of pieces long, with an accuracy of hundreds of segments?

For that matter, what if we simply care a lot about the runtime of our algorithm?

Fortunately for either case, we can optimise.

If we consider our tail pieces in the order they appear on the tail – starting at the head – each piece is further away from the head than the previous one. That means, that no piece is on a path segment closer to the head than any previous one either.

Using this fact, we can combine the loop over the line segments with that over the tail pieces. In pseudo code:

segment = first path segment
foreach tailPiece
{
    segment = advance to segment that tailPiece is on
    tailPiece.position = interpolate on segment
}

The actual code is somewhat more complicated, especially if we include the edge cases and other behaviour mentioned above. Ignoring the treatment of a path too short however, we might get something like the following:

void followHead(List<TailPart> tail, LinkedList<Vector2> path)
{
    // assuming at least one node in linked list
    var segmentStart = path.First.Value;
    var segmentEndNode = path.First.Next;
    var lengthToSegmentEnd = 0f;
    foreach (var part in tail)
    {
        var segmentEnd = Vector2.Zero;
        var segmentDiff = Vector2.Zero;
        var segmentLength = 0f;
        var lengthToSegmentStart = lengthToSegmentEnd;
        // advance to correct segment if needed
        while (part.DistanceToParent > lengthToSegmentEnd)
        {
            if (segmentEndNode == null)
            {
                // path too short
                // NullReferenceException inbound, if not handled
            }
            segmentEnd = segmentEndNode.Value;
            segmentDiff = segmentEnd - segmentStart;
            segmentLength = segmentDiff.Length;
            lengthToEnd += segmentLength;
            segmentEndNode = segmentEndNode.Next;
        }
        // interpolate position on segment
        var distanceLeft = part.DistanceToParent - lengthToSegmentStart;
        var percentageAlongSegment = distanceLeft / segmentLength;
        part.position = segmentStart +
                        segmentDiff * percentageAlongSegment;
    }
    // cutting off unnecessary end of path
    while (segmentEndNode != path.Last)
    {
        path.RemoveLast();
    }
}

Note that despite the nested loop our runtime has now changed to O(n+m) – significantly better.

The only other easy optimisation to make would be precalculating the lengths of each segment when recording them. The rest of the algorithm is about as close to optimal as we are going to get.

A variation on the above would be switching the order of the loops: The outer loop would iterate over the path, placing tail pieces using the inner loop.

While the two might perform different in a production case – depending on a variety of factors – they are equivalent in terms of their runtime.

Conclusion

In this post we started with a naive implementation of our desired behaviour – quickly finding its flaws. By analyzing the same, we clarified our requirements, and developed a new solution which we iterated upon until reaching an optimal one.

I hope this approach has been interesting to you. Feel free to leave a comment and let me know what you think!

Also make sure to let me know if you use this code, or the presented algorithm in your own game/application. It is always great to know to have helped out.

Enjoy the pixels!