The path follow conundrum (part1)

Caution, this is going to be long!

Among steering behaviours, the path follow is one that calculates acceleration to move the agent along a path, which most of the time is returned by some pathfinding algorithm. A path can be a spline, or I think more commonly a poly line, which can basically be described by an array of 2D, or 3D coordinates. I’ll be referring to these endpoints of the path segments as nodes.

I was quite happy with my path follow behaviour, but when I started mixing in other behaviours such as collision avoidance, or separation, which essentially bring the agent off path, issues started to emerge.

applying acceleration towards next node

This is how I handled pathfollowing until now. Black lines are the path, blue circle represents the agent, red arrows are the acceleration vectors, and dotted circles around nodes are the node radius.

  • I keep track of the current node’s index in the path array.
  • Next node is always path[currentNodeIndex + 1].
  • I apply acceleration towards next node.
  • When the agent’s distance from the next node is less than node radius, next node becomes the current node.

We need this node radius because of floating point inaccuracy. If we were to make the condition for advancing to the next segment, an exact match of the agent’s and the node’s position, the agent would overshoot most of the time.

Depending on the path radius and the amount of acceleration we use this implementation will follow the path rather accurately. A big path radius will result in more corner cutting, and a small acceleration in more overshooting before moving towards next node.

This behaviour gives us very good control over the movement, but might look unnatural. We could use path smoothing (during pathfinding) to make the movement more natural, but this will reduce control just the same. I find this to be one of the biggest dilemmas of AI movement. Are we going to sacrifice the illusion of natural movement, to prevent our agent from bumping into level geometry, or vice versa?

agent backtracks to node when brought off path

So this is one of the issues we are almost certain to encounter using this method. The agent ran into some obstacles, and the avoidance behaviours steered it off path. Since it never reached the node radius of the next node, it will still accelerate towards it once the follow path behaviour gets the overhand again. This might result in one of the following things:

  • Agent looks stupid backtracking to the node.
  • Agent bumps into, or gets caught on level geometry. Remember we can only be sure of a safe path towards next node if we come from current node.
  • The obstacles the agent was trying to avoid are still there, and the agents gets caught in an unstable, or stable equilibrium.

An equilibrium in our case means a state where the accelerations returned by the steering behaviours cancel each other out, bringing the agent to a halt. When caught in an unstable equilibrium, the same floating point inaccuracy we were forced to hack our way around when calculating our arrival at a node, will eventually break the agent out of the equilibrium. In the case of the stable one the agent always falls back into it.

stable and unstable equilibria

To be continued…


Tags: , , , , , , ,

One response to “The path follow conundrum (part1)”

  1. onetinyleap says :

    Little correction:

    “If we were to make the condition for advancing to the next segment, an exact match of the agent’s and the node’s position, the agent would overshoot most of the time.”

    I actually mean that the agent wouldn’t register reaching the neaxt node, the node indexes would not be changed, and the agent would oscillate around the node.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: