4.3
I’m trying out some of the demos by Godot and found something weird in navigation_mesh_chunks. One of the edges seem to be avoided making the path sub-optimal. I might have missed something, but wanted to write a comment somewhere.
What do you mean with
avoided making the path sub-optimal
The path is like it is because of the polygon corridor that A* picked that travels from closest polygon edge position to closest possible edge position towards the target, and because if you zoom in you see that this last polygon is a very thin polygon.
From the perspective of A* when entering at the topleft corner using the polygon under your red arrow is suboptimal edge distance towards the target so it picks the southern edge and polygon instead to travel further. A* does not know that the southern polygons later will end up as a visibly worse option with the path postprocessing. A* does not search all the additional polygon options to the left and right of its polygon corridor that failed the first edge test, if it finds a polygon corridor to the target it is done, because as far as A* is concerned it was the shortest possible edge path in its corridor.
The pink/magenta corridor funnel snaps to polygon corridor corners while the yellow edge centered snaps to the middle of the crossed polygon corridor edges. Both use the same pathfinding polygon corridor just use the polygon geometry result differently.
If you really wanted a “perfect” shortest path you would need to explore the majority of all the polygons on the map many times over, and be more an algorithm like djstika instead of A* that explores all the additional options and takes a lot longer to finish. Because that is not something A* covers the result of the pathfinding is very much depending on the polygon layout and the polygon corridors that A* builds along them.
The additional edges in the middle of the surfaces caused by the chunk slicing makes this A* behavior just more obvious than usual but is the same reason why e.g. a TileMap that adds a lot of extra edges on otherwise open surfaces causes very suboptimal paths depending on its polygon layout, or why A* fails to find shortest paths on more complex layouts or as soon as polygon costs are involved, it is just a too greedy and tunnel-visioned algorithm designed for speed instead of quality.
That is not the case because the polygon to the right fails the A* edge distance check. All the positions on this polygons left edge are further away towards the target compared to the edge positions on the south edge of the left polygon. That is why A* decided to go south and make a polygon detour. It is a general problem of A* and polygon corridors, A* is too greedy for layouts like this.
While your expectations as a user are for sure valid strictly technical they are not for A*. it would require a different algorithm or additional postprocessing like a backward looking visibly check along polygons to fix at the cost of performance, options that are not build-in available.
