Hi guys,

For the most part my navigation system is working, there are, however, some glitches. I'm not really sure what method I should use to have my agent go to his computed waypoints. Please keep in mind this is for an action game and I want the agent to recalculate his path every frame.

Take a look at this (mesh is pre-shrunken for agent radius) :

I have problems with this simplistic scenario. The white point (the left of the portal) is the waypoint computed to get him to the next node (node 1) where the goal is.

If I just move him to the waypoint and do a small distance check he'll arrive just to the left of it, then head to the goal which will put him out of the mesh (by cutting the corner.) If I have him simply head toward the waypoint until he's in node 1 it won't work if he's not heading up at all, he'll stay in node 0. I can make it so he has to pass the waypoint a little but if he's coming from a different direction he could pass it and end up off the mesh.

How do I determine when he should start heading directy toward the goal ?

How is the basic navmesh with computed waypoints generally handled ?

Thanks a lot.

Have you tried either increasing radius you use for shrunking, or decreasing distance used during waypoint arrival check (or both)?

Otherwise you can add something like wall following steering behaviour (see http://www.red3d.com/cwr/steer/Wall.html for example)

The way that Recast & Detour handles this is to include the agent's radius in the navmesh (to avoid having to post-process paths). In my game, I just apply velocity in the bearing of the waypoint until within a specific margin (0.01 m or so (> than 1 frame velocity error)) and then switch to the next waypoint. You could also check if the dot of the vector from the current waypoint to the npc position is greater than the distance between the current and next waypoint.

I avoid recalculating paths by only doing so if the target moves. You could extend this further by keeping track of entites within the same node and checking if they're in the path or not. To handle the case where the player leaves the navmesh, I keep track of the last node the player was within, then find the nearest neighbour according to the edge distance (assuming that I'm not currently in a node).

it seems you want the agent to overshoot the waypoint if entering the portal 'region' from left, and undershoot if from right (eg would leave portal region if overshot)

Let p1 and p2 be the waypoints that define the portal, with p1 our waypoint and p2 the other one.

Find (p2-p1).unit and take dot product of that and agent position.

If negative, overshoot. If positive, undershoot. This should ensure you never go too far or get stuck in corners etc.

Hi Angus, thanks for addressing those points for me; with your help I was able to get my basic system up and running and it seems pretty robust (so far.) Do you do any kind of agent-agent collision avoidance ? I was thinking about how best to handle that and some pointers will be helpful.

Waterlimon, thanks man, I wasn't sure how to undershoot, that info will come in very handy.

Hi Angus, thanks for addressing those points for me; with your help I was able to get my basic system up and running and it seems pretty robust (so far.) Do you do any kind of agent-agent collision avoidance ? I was thinking about how best to handle that and some pointers will be helpful.

Waterlimon, thanks man, I wasn't sure how to undershoot, that info will come in very handy.

My experience with a range of techniques in this field is limited at the moment. I'm actually revisiting some pathfinding-systems I wrote in the past, which is why it's topical :)

NB, Mikko Mononen, the author or Recast & Detour, wrote some articles on his blog about general pathfinding & following concepts.

At the moment, I've left this in my own works, because I'm trying to get more performance out of the general navigation code (it seems that the funnel algorithm is running slowly for me, time to dig out the profiler!). However, local steering behaviours are the basis for collision avoidance, and there are a few great articles on digestingduck (the aforementioned blog) that describe how he does this. There are certainly other methods, though I will note that I like his approach to problem solving, which doesn't settle for cornercases.