The path follow conundrum (part 2)

So here we go again.

To combat backtracking my first idea was to change the agent’s arrival condition so that we would always consider the closest path node as the current node. However this has a side effect. Essentially, as the picture illustrates, this will be very similar to the previous implementation with changing, but alway relatively big node radii. This will result in unreliable and uncontrollable corner cutting behaviour. I can hardly see the use for such a path follow behaviour.

using closest node as current node

The version my number 1 source (Artificial Intelligence for Games) suggests is somewhat different. Here we project the current position of the agent onto the path. From this we calculate a point on the path with a predefined offset value and always accelerate towards this point. This eliminates backtracking since the agent will accelerate towards a point ahead of itself. However it is a more complex solution and introduces new issues, and a results in a more expensive algorithm.

path following with projected position

In order to project the agent’s position onto the path we would need the path to be represented as a very high, ideally infinite, number of nodes. Although there might be a method for doing this, I’m not aware of it and frankly the idea seems pretty much insane to me.

In my case the path is represented by an array of Vector3 variables (3D coordinates). From this information we can determine a current path segment the agent is moving along with the same method of keeping track of current node and next node as before. We can project the agent’s position to the current segment using a dot product calculation.

calculating projected position

This is how I do it:

  • currentNode, nextNode, and agentOosition are 3D coordinates
  • we have two vectors
  • vectorA = nextNode – currentNode
  • vectorB = agentPosition – currentNode
  • we will need a normalized version of vectorA later
  • we will also need the length of vectorA (not for this calculation though)
  • so we calculate vectorALength
  • vectorANormalized = vectorA / vectorALength
  • l is the length of the vector defined by currentNode and projectedAgentPosition
  • we can calculate l with like this: l = |vectorB| * cosß
  • the dot product of vectorA and vectorB looks like this: |vectorA| * |vectorB| * cosß
  • |vectorANormalized| = 1
  • so l = |vectorANormalized| * |vectorB| * cosß =  dot(vectorANormalized, vectorB)
  • now the only thing left is to calculate the position of the target
  • o is the offset value
  • targetPosition = currentNode + vectorANormalized * (l + o)

So in this implementation the agent is chasing a virtual target that moves along the path. The book uses the analogy of greyhounds chasing the loth rabbit at the dog track, but I wouldn’t know about that.

The last solution I’m going to write about is the version of predictive path following described on the page of Craig Reynolds.

predictive path following

Here we create a kind of channel around the path by setting a radius value (r). Our goal will be to ensure that the agent moves within this channel. Depending on the radius the agent will follow the path more or less loosely.  Craig Reynolds calls this “sloppy path following”.

It works like this:

  • we calculate the future position of the agent from velocity and some preset time interval
  • we project this predicted position onto the path
  • we check if the distance of the projected point and the original point is greater than r
  • if yes we calculate a target point on the segment that is within the radius
  • we then accelerate towards this target

You can find a better description and a nice little demo here.

The point is to create a more natural looking movement. However this upsets the balance of control and natural movement in favour of the latter. While I might be interested in creating something similar in the future, I don’t think it’s likely I would actually use it. As far as I can say after only running it through my head it would involve even more distance calculations, or normalizations, making the algorithm more expensive. I don’t really want to give up any more control over the movement of the agents either. They are already getting into a fair amount of trouble with each other and level geometry, and I’m pleased with the look that results from simple projected path following mixed with path smoothing during pathfinding.


Tags: , , , ,

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: