This isn't entirely a "pathfinding" problem but is still kind of a shortest path problem.

In my navigation mesh system (made of convex polygons) I want to get out a list of instructions for my AI to follow when finding a path from A to B.

From my A* implementation I get a list of edges in the mesh that the unit has to cross to get to it's goal.
The problem is now *where* on the edges it needs to cross to move the shortest distance.

Ideally it would end up looking like this:


My first thought was to simply make lines to the center-points on each edge it crosses and then do an algorithm that 'relaxes' the lines and merging them if possible.

This however smells far away of a worst case O(N^2) algorithm to me (each time I merge two line segments I have to test that the new edge crosses all the edges before. N line segments that needs to have N edges validated = N^2)
Is there a better way to do this?


In the end I want to give the algorithm a radius too to avoid corners and circulate around it:

The navigation mesh needs to support any object size/radius so I cannot preprocess my mesh to be that amount smaller as for example the recast algorithm does when it generates the mesh.

My first thought is that I can simply test the point/line distance to each line-segment from the edge-endpoints and test if I need to insert an 'arc' there the object has to follow. I can figure out the points where it will enter and exit the arc using the solution to the Belt and Pulley problem.
What I am worried about is that the inclusion of a radius will alter the line segments too much that it would need to split up some lines that I already merged.
I could get around that in my initial algorithm by shortening my line segments by the radius:


Would this work in all cases? (from there on I could collapse points on the edge of the circle into the 'arc'.

Am I overthinking this? Are there easier ways to do a smooth path though those edges?

I just implemented a simple navmesh system as well. You're on the right track - compute an A* algorithm per edge of the mesh. I use the edge midpoints as positions when calculating A*. If you have a strict shortest route requirement, this may not be appropriate.

Once you have a list of edge midpoints that represents your path, I use the funnel algorithm to find the corners I should cut. You are already aware of Recast, so refer to http://digestingduck...-algorithm.html This will give you a new list of waypoints representing the final path to follow.

As far as agent radius goes, I haven't gotten that far yet. I did find a paper that talked about the subject, but I'll have to dig it up again.

As far as AI goes in the terms of "using a circle for your agent to avoid the edges with", take the normal of the edge and you can use it to calculate the force to direct the agent away. This avoids the whole "radius avoidance" as the amount of force is calculated real-time and will not force the agent into some sort of wedge; instead it will allow it to flow (i.e. no force is being acted upon because they cancel each other out).

Something like this for you.

Applying that force into an accumulative force (of all the acting forces on your agent), you'll be able to avoid those edges. Using forces instead of sticking to a static mesh will make the agents feel a bit more smooth and dynamic.

Hope I helped any.

I take a different approach to pathfinding based on the articles on this site:[color="#800080"]http://www.red3d.com/cwr/steer/

Here's how they solve your problem: http://www.red3d.com/cwr/steer/PathFollow.html

I <3 this site

-Eric

Thanks for the links and input everyone That Funnel algorithm was exactly what I was looking for thanks! I'm almost having a working implementation now.

The system is going to be used for both complete automatic steering (just follow the path found strictly), but also needs to support 'carrot on a stick' movement for agents (attract agents towards some point in front of them along the path) so I can use boid movement behavior on them and make them avoid local small obstacles.

I will post a demo of it once I have something cool-looking