0
\$\begingroup\$

I've read a couple of articles on Navmesh+A* navigation. So, I'm trying to implement a pathfinding for an RTS type of game. However, it seems I don't understand how to calculate a distance for A* when searching a path on navmesh.

I cannot really calculate distance between centers of navmeshes because in that case I don't get the best path.

Example:

enter image description here

Here I have three navmeshes interconnected with each other. If I need to move a unit as illustrated in the picture the optimal path is obviously the green one.

However, if I calculate the distance between centers of navmeshes when I use A*, the path would be calculated as red in the picture.

So, how do I account for entry and exit point in navmeshes when calculating the distance for A*?

New contributor
Dmitrii Naumov is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
2
\$\begingroup\$

When you say you want to calculate the "distance for A*", you mean the heuristic, right? The heuristic is an estimate of the distance. And you want to avoid overestimating it. See Admissible heuristic.

Unless we are dealing with teleportation, or some not euclidean geometry, there is no way that units will reach the destination via a shorter path than a straight line. Thus, the distance on straight line never overestimates the distance. Therefore the distance on straight line is an admissible heuristic. Which means A* should work correctly using it.

I mean, something like this:

distance_estimate = (dst - src).length()

However, if I calculate the distance between centers of navmeshes when I use A*, the path would be calculated as red in the picture.

This could happen if you overestimated the distance. The distance from the centers of the navmeshes can be longer than the actual distance, so that can happen. Although you still got a valid path.

By the way, I imagine you are doing something like this:

var src_area = get_area(src)
var dst_area = get_area(dst)
distance_estimate = (dst_area.center - src_area.center).length()

So, how do I account for entry and exit point in navmeshes when calculating the distance for A*?

You can pick the exit that is closer to the other point. Closer as measured in a straight line. That might not be the correct exit, but it would avoid overestimating the distance (assuming you have convex areas, which is how these systems work). Which makes it an admissible heuristic.

I mean, something like this:

var src_area = get_area(src)
var src_exit = get_min(src_area.exits, exit => (exit - dst).length())

var dst_area = get_area(dst)
var dst_exit = get_min(dst_area.exits, exit => (exit - src).length())

distance_estimate += (dst_exit - src_exit).length()

However, it is not necessarily a better heuristic. We want to make sure we don't overestimate, but we want to underestimate as little as possible. We can make it better if we add the distance from the point to the exit we picked.

So, you would do something like this:

var src_area = get_area(src)
var src_exit = get_min(src_area.exits, exit => (exit - dst).length())

var dst_area = get_area(dst)
var dst_exit = get_min(dst_area.exits, exit => (exit - src).length())

distance_estimate = (src_exit - src).length()
                  + (dst_exit - dst).length()
                  + (dst_exit - src_exit).length()
\$\endgroup\$
4
  • \$\begingroup\$ Thanks for the detailed answer. That makes sense. However, I have a follow up question. So, does that mean that when building the navmeshes we need to store coordinates of all the exits on that navmesh? I think it does but wanted to make sure that I'm not missing anything. \$\endgroup\$ Jan 13 at 3:17
  • 1
    \$\begingroup\$ @DmitriiNaumov We are being loose with the term "navmesh". The term refers to a polygon mesh, where the connections are given by shared edges. However, we can use a navigation graph, which is done with circular areas and links (or, in this case "exits"). Which matches what you depicted on the question. If you are using that, then yes, store the exits. Sometimes the navigation graph is generated from the navigation mesh. It loses precision - ok with obstacle avoidance and wall following - and it is simpler and easier to work with. \$\endgroup\$
    – Theraot
    Jan 13 at 6:39
  • \$\begingroup\$ You are right of course. I think the question is "how to properly generate navigation graph". Generating navigation graph using centers of navmeshes as graph nodes does not seem to be a good idea. I thought about that a bit more and storing exit locations does not solve the problem if there are more intermediate nodes than in the above example. However, using exists as navigation graph nodes and navmeshes as graph edges seems to solve this. \$\endgroup\$ 2 days ago
  • 1
    \$\begingroup\$ @DmitriiNaumov See Navigation Graph Generation. \$\endgroup\$
    – Theraot
    2 days ago

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .