JoeJ said:
That's a nice example of how the region growing makes sense, and also a nice example of Dijkstra being better than Astar becasue Astar supports only one goal for its scoring heuristic, i guess?).

Standard Astar doesn't do that indeed, but it's not impossible. If you are at some point and must add the heuristic, compute it for all goals and take the minimum. In that way you always aim for the nearest goal.

Alberth said:
If you are at some point and must add the heuristic, compute it for all goals and take the minimum. In that way you always aim for the nearest goal.

Awesome :D

I have some more questions about Astar:

How is it with 3D Navmesh (or the surface of any 3D model?). Is there a trick to make Astar work with this?

And how do we calculate the heuristic? If this is Dijkstra: nodeScore[neighbor] = nodeScore[current] + edgeWeight;

Is it simply like this: nodeScore[neighbor] = nodeScore[current] + edgeWeight + Distance(neighbour, goal); ?

JoeJ said:
How is it with 3D Navmesh (or the surface of any 3D model?). Is there a trick to make Astar work with this?

I have no idea, never worked with navmesh.

Conceptually however, Astar works on a graph of nodes. Since we typically use a rectangular grid to navigate on, we don't actually have a graph of nodes stored, since you can easily compute that from the grid position. This is why you never see an explicit graph in any explanation of Astar in game context.

Astar works as follows in a graph: You track the exact travelled distance from the start to where you are. Expanding a node means you move to all the direct neighbours of the current position, and update the travelled distance for each of them. For all the new positions, you compute the heuristic, which expresses an estimate of the distance still to go. The sum of the travelled path and the heuristic is the score of the node. Nodes with the smallest score that you haven't expanded already should be further explored first. If you want an optimal path, the estimate should never be more than the real distance to the goal.

If you know a way to make this graph exploration work on a navmesh (probably you need a way to see the navmesh as a graph of nodes that you can visit), then sure you can have Astar on a navmesh. As far as I know however, an element in a navmesh is not a single position, but it's an area with an infinite number of positions. Traversing an infinite graph works, but takes a little very very long (around infinity somewhere). So you need to have a finite (preferably small) number of positions in a navmesh element. You'll loose optimality, but if you can live with sub-optimal solutions, likely there exist ways to do this (and given that navmesh is used, no doubt someone has figured out how to do that).

JoeJ said:
If this is Dijkstra: nodeScore[neighbor] = nodeScore[current] + edgeWeight;

Dijkstra also originally operates on a graph. It does not expand all neighbours of a node at the same time. Instead you consider all nodes that you have not yet fully expanded, and pick a single(!) new neighbour node with the smallest total distance (sum of the travelled distance of the previous node + length of the edge to the new node). In other words, you constantly look for the globally nearest new neighbour along the edge of the (partially) explored nodes. There is no heuristic in Dijkstra, only a set of (partially) explored nodes, and the real travelled distance (which is also the minimal distance from the start).

As with Atar however, since we typically use rectangular grids, Dijkstra's concept of ‘single nearest new neighbour node in a graph’ becomes “all grid cells directly attached to the edge of the explored area” since we don't need to store a graph, and all distances are the same everywhere. As such you can make a few simplifications in the original algorithm for the grid case.

Alberth said:
If you want an optimal path, the estimate should never be more than the real distance to the goal.

Then it should work. I will try out…

The reason i thought it would not is this:

It's a torus with a bumb in the middle. For the heuristic we can only take euclidean distance (green straight line). But the actual geodesic distance on the walkable surface is always larger if the surface is not flat.
Derivative of geodesic distance is not smooth. It has discontinuities at sections where talking a complete different path becomes shorter:

Like in this image, at the front side of the bunny it looks all fine, but at the back we see a flipping case along the red line where the shortest path to the goal flips to either side of the line. (We could cut the mesh open to get topology of a disc to make UVs for example.)
Taking euclidean distance would completely miss this, and i just assumed that's the reason why Astar would fail to find the shortest path.
All geometry processing projects i've seen use Dijkstra. But maybe i missed they do so because they had many goals, like each vertex to get a cheap approximation of geodesic distance.

I'll try out and report back. Although people with navmesh experience should know and could just confirm, so i'll wait a bit… : )

hmmm, there is indeed a difference on the found paths. Red is Dijkstra, green is Astar.

Can be quite a difference:

Also the processing win of AStar is less than i thought. I could get the same with ‘meet in the middle’ optimization.

Final picture on pretty flat surface, here AStar is big win. Looks a bit buggy at first but it's ok.

So… for geometry processing i can't use it. But for navmesh in a game where levels have low vertical complexity it seems an option : )

Looks like a nice experiment ?

Your torus also happens in 2D, imagine it to be a flat field, with the area around the point being impassable. In such a case you also ignore the impassable field, and also return a distance that is much shorter than the actually walkable path since the latter must take a detour around the the impassable area.

JoeJ said:
All geometry processing projects i've seen use Dijkstra. But maybe i missed they do so because they had many goals, like each vertex to get a cheap approximation of geodesic distance.

Dijkstra computes the shortest path of all surrounding nodes, this is an advantage if you need to know distance to many nodes from the start.

JoeJ said:
hmmm, there is indeed a difference on the found paths. Red is Dijkstra, green is Astar. Can be quite a difference:

Astar has problems with large flat areas. All distances become the same, leaving not much to make a sane selection for a path. As a result, it just picks arbitrary nodes. To see this happening, you should also show which points it explores.

You get pictures like

Alberth said:
Your torus also happens in 2D

Hmm, thought about this myself meanwhile. The difference is that in 2D geodesic distance equals euclidean distance, but that's not true for 3D. So a heuristic using euclidean is a problem.

Reading up on Astar i see there are two forms of heuristics that work, but only one (monotone) allows Astar heuristic to be used in Dijkstra algorithm. And that's what i did by adding just the target distance to the cost.
If the heuristic is not monotone (probably that's the case for me), the algorithm needs modification so it can visit nodes multiple times to make corrections. I did not know this.

I also learned there are two forms of Astar with a faster one that gives not always the shortest path. (https://medium.com/ironequal/pathfinding-like-a-king-part-1-3013ea2c099)​
@calin No details but nice overview, also talking about flow fields which i had proposed for RTS.

JoeJ said:
If the heuristic is not monotone (probably that's the case for me), the algorithm needs modification so it can visit nodes multiple times to make corrections.

Not sure what monotone means, but you can do a lot by extending the notion of “position”. Traditionally, it's a set of coordinates like (x, y) in 2D, but there is nothing that prevents to add eg “orientation” (looking left, right, up, or down) or “speed” or something else. In other words, (x=1, y=2, orientation=up) is a different position from (x=1, y=2, orientation=left). JPS (jump point search) does this too, adding a direction of movement, so it can store the need to explore the area further in several directions all from the same (x,y) point. Obviously, the downside is that you enlarge the graph that needs to be searched (eg adding orientation means I don't have 1 XY plane to search, but 4 such planes layered on top of each other).

JoeJ said:
I also learned there are two forms of Astar with a faster one that gives not always the shortest path

Not sure it counts as two forms, but it's about the quality of the heuristic.

If you don't give any clue how close a point is to the goal (eg heuristic is always 0), then the algorithm has no way to decide which is the better point to explore, and thus will always expand a position with the shortest traveled path, which leads to equal expansion in all directions until you hit the goal, much like what Dijkstra does.

If the heuristic is always exactly the remaining real distance to the shortest path, then forward movement on that path does not change the cost (the travelled path gets a bit larger, and the heuristic decrease with the same amount, so the sum of both doesn't change). This makes exploration away from the shortest path always increase in cost (travelled path increases, and heuristic decreases less or even increases if the travel in the wrong direction). Such off-path positions will not be explored further as there is always a position exactly at the shortest path that can be explored which has lower costs. (This is the optimal case, except it never happens, since if you can give the exact estimate at every point, you can also use that information to decide where to go, no need to compute a path with Astar then.)

If you do give a non-zero heuristic but it may be underestimated (eg ignoring impassable areas in your heuristic), you get a mix of the above. The heuristic does steer the search towards points that are more near the shortest path, but it also explores points somewhat off-path. It's less efficient than the above optimal case, but you do get the real shortest path eventually.

If your heuristic is an overestimate, then positions further away from the goal (where the heuristic is a larger fraction of the total cost) become less attractive to explore. In other words, a position near the start which is actually on the shortest path may become less attractive than a position more close the the end-goal which is not on the shortest path. Remaining distance becomes the dominant factor in deciding which point to explore further. This reduces the number of positions to explore at the cost of a non-optimal path. The amount of non-optimality is related to the amount of over-estimation, so you can control the trade-off between optimality and speed of search.

If you do want optimality, you can also improve performance of the algorithm by sorting on decreasing travelled path length within the set of positions with equal total cost. In this way, you favour exploring near the goal first for the positions with minimal total cost. This is allowed by Astar, it only says “explore a position with minimal total cost”, but if you have multiple such positions, it doesn't say which one to do first.