Algorithm to make entities closely follow one another?

Question

I have a group of entities that I want to follow a leader very closely. A good example would be how the player's soldiers move in Cannon Fodder.

Any suggestions for achieving movement like this?

Answer 1

I guess you want some ant like behavior (at least as far as comic ants are concerned)?

http://www.youtube.com/watch?v=HccgCeVo-4c

If so, I'd try the following:

• Pick the entity closest to the target as the "head" and mark it so it won't look for another entity to follow.
• For each remaining entity, find the next closest entity that doesn't have a follower yet.
• Once found, set the current entity as the follower of the other entity (which becomes the target).
• This can be optimized using strategies similar to path finding algorithms (if you're not happy with the results).

As an alternative, you could try something similar to what real ants do:

• Rather than path finding, let the "head" entity setup a vector field.
• Each vector points in the direction it should be going.
• Combine that with a simplified flocking algorithm (stay away from others, but follow the path) and you might end up with an even more natural movement.

Answer 2

The behavior I've seen in the video you attached could be mimicked like so:

When the characters are spawned, the current leader's position (2d point) is saved and is currently the only element in an array (or Vector) representing the movement path coordinates or path-array.

All flowers have a goal member that points to that element as the position they need to reach (but they are currently unable to move). They also have another desired-distance member that signifies how close they will be (in the line) to the leader which obviously differs between all followers (possibly something like n units for the closed one, 2*n, 3*n and so forth for the ones behind her).

When the player clicks a new target, the new position is pushed into the end of the vector. The distance between the current position of the leader and the new point is calculated. This distance is the amount the leader will move to reach the new target area. Assuming all soldiers were spawned with the correct distances between them, it is also the distance that each soldier is allowed to move (this is the easy way to implement it using integaral [not floats] units of distance).

So we begin to move the leader to the new point and at the same time, move the others to the leader's spawning point (the first element on the path array). Once each character reaches the leaders spawning point (first element in the path-array), that character's goals member is adjusted to point to the next element in the path-array. Each character is allowed to move exactly as much as the leader or alternatively, until the computed sum of distances from it's current position to it's current goal and from there through all other coordinates until the leader's current goal is equal to their desired-distance.

You could and probably should add a tiny delay from the moment the leader receives an order from the player or computer AI and until the followers begin moving. That delay should be small but you may want to increase it like the desired-distance so t, 2*t, 3*t and so forth as it will give a natural motion (like cars in traffic).

If the leader is redirected whilst she is moving, then her current goal coordinate in the path should be replaced with her current position and the new goal should be pushed as her target. The distance from the previous goal should be deducted from the allotted units of movement allowed to the followers and the distance to the new goal should be added.

As a data-structure, you could / should use a queue. Coordinates that all characters reached could be removed from the queue.