I'm trying to implement path following, but I'm not quite sure how to do it. I found this thread here, but I'm still not sure about how I can detect when the agent has arrived at a point in the path (its current goal node) and needs to set its goal to the next node in the path. The only thing I can think of involves checking the distance of the agent from the node. I can maybe check if the agent is within N units of the goal node, and if it is then advance to the next node, but what happens if the game happens to "jerk" at just the wrong moment and the agent overshoots the node without detecting that it's arrived at the goal? Or maybe I could keep track of the agent's position at the previous frame, and as soon as it starts moving away from the goal (comparing the distances of the current position and the previous position from the goal node) it moves to the next node. Any suggestions? Edit: wow, bad HTML [Edited by - BradDaBug on November 10, 2007 8:26:42 PM]

Here's how I handle it. Each segment of the path has a starting point and and ending point. The entity following the path has a velocity along the segment. I also store the current time whenever the entity reaches a starting point in a segment. Each frame, the entity's position is set along the segment vector (end point - start point) according to its velocity and the amount of time that has elapsed since it first reached the segment. Given the distance and the velocity, you can calculate how much time it takes to reach the end point of the segment. Once that amount of time has elapsed (either exactly or gone over), I know it's time to move to the next segment. At that point, you can easily calculate the position along the next path segment for any amount of time that has gone over the time to reach the end of the previous segment. Hopefully this makes sense and helps!

That's not a particularly robust solution strtok. All you're doing is storing a set of headings implicitly as a sequence of locations and switching between them at preset times (although your times are also implicitly encoded via velocities and lengths). This is not not path-following but rather plan execution. The problem with this is in any scenario where the moving entity is delayed (typically because of a dynamic object, or some other interaction with the game that causes it to change velocity). Obviously you could test for such changes and recompute the expected traversal time (and hence the desired action duration), however you're now back to the root problem of detecting when the entity reaches (or predicting when it is going to reach) each node.

It's a very cheap computation to check the remaining distance along a path segment to the next waypoint and you can do it efficiently while computing the appropriate steering for your entity as it tries to stay on the path. It's also one of the easiest methods to code.

Cheers,

Timkin

Store a line (ray) perpendicular to the current node. Once the player crosses this line it's time to move to the next node, simple as that. Hickups with an overshoot won't make a differnce, and he won't try backtracking at all. This gets rid of almost all special cases.

Quote: Original post by Timkin
It's a very cheap computation to check the remaining distance along a path segment to the next waypoint and you can do it efficiently while computing the appropriate steering for your entity as it tries to stay on the path. It's also one of the easiest methods to code.

I assume by "steering" you're not talking about interpolating between two points to find the position of the agent (like the post I referenced suggested), but instead finding a vector pointing from the agent to the goal node and using that to move the agent?

Quote: Original post by Ready4Dis
Store a line (ray) perpendicular to the current node. Once the player crosses this line it's time to move to the next node, simple as that. Hickups with an overshoot won't make a differnce, and he won't try backtracking at all. This gets rid of almost all special cases.

Hmm, that sounds like it might work. But wouldn't it be possible for the agent to get incredibly close to the goal (as in 0.0001 units away) and just sit there, without ever actually crossing the line and deciding it's arrived at the goal? Or would you combine this with a distance threshold?

Good advice; I've used those two approaches and they work quite well.

If the "jerk" behavior bothers you though, try having a "carrot" move along the path 1-2m in front of the bot. The carrot may jerk, but if you use a steering behavior towards it, the movement won't jerk as much.

Another quick calculation to handle the overshoot problem is that if you are between the next node and the next node + 1, then you should go to the +1 instead.

Using the carrot idea does also tend to smooth out your corners somewhat rather than a hard corner right at the node. Much more aesthetic and natural.

With the infinite ray that is perpendicular to the current line you are following, you can very easily determine the distance from point -> ray, especially when it's infinite! So, being .00001 away would be no problem, just check that distance (since you are calculating it anyways to determine which side of the ray you are on) and check it against however much of an error you want. I typically do an acceleration/velocity vector that allows it to not look jerky. The person/bot/vehicle whatever is only allowed to accelerate and turn at a specific speed, so when they come near a corner they will never just sharply turn. I have used a following guide before (carrot?) with good results as well. Using the infinite ray, you will never have an overshoot problem again though, and using any sort of smoothing algorithm will keep it from making sharp turns. You can also use this method with a limited length ray to do checkpoints and such in a racing game or similar, so it is very useable for future projects if you have anything to do with a player needed to cross a finish line, etc.

InnocuousFox: "Another quick calculation to handle the overshoot problem is that if you are between the next node and the next node + 1, then you should go to the +1 instead."

How do you determine if you are between 2 nodes? The only way I can think is by creating 2 rays one at each point of the nodes, and perpendicular to each point->point-1, which is over 3x more calculations than just checking if you crossed a single ray and doesn't give you any more benefit.

Quote: Original post by BradDaBug
I assume by "steering" you're not talking about interpolating between two points to find the position of the agent (like the post I referenced suggested), but instead finding a vector pointing from the agent to the goal node and using that to move the agent?

By "steering" I mean those control actions that achieve the goal (following the path) while minimising the cost function (which is presumably minimum time). How you determine this steering is up to you (there are many alternative methods)... around here, many people would recommend "steering behaviours" (c.f. Craig Reynolds' work).

The point of my previous post though was that most dynamic programming solutions to this problem will require the computation of the distance to the target node... so you might as well cache it and use it.

Cheers,

Timkin