Re: [Algorithms] A-Star Adjacency Measure for Navigation Mesh

[Jason H. <jas...@di...>]

Hi Sam,

I implemented a similar system for a company last year.  The problem 
with polygon centers, as you've discovered, is they make a lousy 
approximation for area.  If you constrain the problem to them, you can 
still get good results, however it takes a little more effort than 
adjusting the input.  Adjacency should be literal topological adjacency, 
though.  If your system assumes physical proximity, I'm not sure how 
that factors in... do you reject any faces that are not significantly 
planar with the ground?  Weaving them into a coherent graph is not a 
trivial problem.  You could try to increase the density of your A* graph 
by connecting all close vertices AND centers, then find a metric to 
remove redundant edges.  Quite a bit of work, and bound to give bad 
results somewhere.

In terms of pathing once you have a solution, I found that the triangle 
centers along a path are not the places you really want to walk 
towards.  The constraints are really the two edges (incoming and 
outgoing) of the triangle, and you simply need to find a relaxed path 
that is as straight as possible and manages to hit all the edges of 
interest, with minimum angular deviation.  Some pathing agents will 
behave differently (ie. tanks versus birds), and might need a different 
relaxation technique, or parameterize it with a smoothness factor .

Check out "convex points in A*" to see how the rigorous libraries do it.

Best of luck,
JH


Sam Yatchmenoff wrote:
> I'm developing a pathfinding system that procedurally generates a 
> NavMesh from level geometry then uses A* to find the paths from point A 
> to point B.  That's working fine except in case where I have very 
> elongated polygons in the mesh.  The pathfinder will often give me an 
> obviously suboptimal path because my adjacency measurement is the 
> distance between the centers (averages of vertices) of the polygons and 
> this is sometimes a much greater distance than the agent will actually 
> travel through these polygons.
>
> I have a few questions about this.  First of all, can I safely alter my 
> adjacency measurement so that it takes into consideration the path back 
> to the starting position?  If not, then what would be a good strategy to 
> deal with this problem?  The simplest solution I can think of would be 
> to alter NavMesh so that it had more squarish nodes, but I'd like to 
> here any ideas that DON'T involve changing the nodes.
>
> Thanks in advance,
>     Sam Yatchmenoff
>
>
>