I currently have a working implementation of A* using navigation meshes. Agents are moving around a 3d navigation mesh, reaching their target, however often a sub-optimal path is chosen, when considered from the user's perspective. I have narrowed this down to the cost calculations for long edges when the agent is trying to hug one edge of the polygon. To be clear the graph connects polygon edges, not polygon centroids. I have an idea for a solution, but first please consider the following diagram with both path through midpoints, and optimal path. It is only a subset of the search space, but one that is currently not traversed because the total cost is too high when compared to another part of the mesh.

enter image description here

To get from the start point to the end points, the cost calculations use the midpoints of each edge. However, the best path is actually a lot cheaper, but the algorithm does not return this set of edges because the valuation is too high. Always using mid points causes these bad routes to be ignored in cases of long edges, so I have modified my algorithm to generate three nodes per edge - the two end points and the mid point. This solves the problem - agents now take this path - but at the cost of a much larger search space.

As a solution I have been thinking instead of doing a closest-point-to-edge test when doing the scoring, essentially making a dynamic, adaptive point on the edge for scoring. For each edge I would do a closest point on the edge segment to the segment from the grandparent cell's midpoint - the parent of the parent - to the current edge's midpoint, and then score from that, instead of using the parent's midpoint. You can see these steps and the composite path in the following diagram, where G is the grandparent midpoint, X is the current edge midpoint and A is the adaptive midpoint. I have included a diagram showing the composite cost of the edges, which looks odd but is shorter than the original mid-point only (I think).

enter image description here

I have yet to implement this in my system. My question is does changing the cost calculations to use the 'adaptive' points seem reasonable or am I going to blow up my cost valuations? What if I use the minimum cost of this value and the midpoint value? Does anyone have any other good ideas here? Currently the cost of doing 3 times the nodes is too much as is three times the memory for the nodes.

Thank you.


migrated from stackoverflow.com Nov 16 '14 at 5:42

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Can you edit the question to clarify what problem you are trying to solve? You start out by saying you have a working algorithm for your problem, but you don't tell us what the problem itself is - we're left to infer that from the rest of the description. This makes it harder to answer your question. $\endgroup$ – D.W. Nov 16 '14 at 8:54
  • $\begingroup$ You might be able to adapt the techniques from the Theta* algorithm. It doesn't create new points dynamically, but it instead creates new edges dynamically. You can set up a navmesh with the polygon corners as the nodes, and then I think (but am not sure) that your shortest path will always use those corners, even if it has to create new edges dynamically. $\endgroup$ – amitp Nov 20 '14 at 1:11
  • $\begingroup$ @amitp - I think that is what I am doing already - for each edge I use the midpoint and the two vertices, which essential creates many-edge graph connections between the nav-mesh edges. I know there is one commercial implementation out there that does something similar to what I am suggesting, but I don't know all of it's implementation details as it is closed source. $\endgroup$ – Steven Nov 20 '14 at 3:17
  • $\begingroup$ @amitp - I took a look at the Theta* and I believe that is what I am seeing in the commercial implementations I have seen. Thanks for pointing me too it. I think it essentially results in the diagrams I have posted above. I will make some tests and then report back. $\endgroup$ – Steven Nov 20 '14 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.