However, I did work on a number of popular open world racing games where a lot of NPCs were travelling across the map, often where no player was nearby. For these, as well as for visualization of travel routes on the map, we used a graph of the road network and A* with some simple modifications such as adding edges from the start and end point to the nearest points on the road network.
Having implemented A*-style algorithms occasionally, I was under the impression that by "navmesh" people mean a planar vector structure that can then be navigated using, for example, A*. As opposed to a grid data structure consisting of cells that can then be navigated using a pathfinding algorithm. I always saw A* as a strategy to find a path in any graph, and I saw navmesh as an example of such a graph.
Now it seems people are defining navmeshes as both a data structure AND pathfinding strategy, and by the same token are likewise seeing A* as both. This seems really confusing to me.
Have I been using the lingo wrong all this time?
This is also how many game engines, including Unity, implement their NavMesh queries.
Maybe they use it cause it's quick and easy, not because it's the most optimal?
Of course this does cover most of the cases, probably even for "space" games (which are often more akin to WW1/WW2 naval simulators).
> It’s not yet clear to what degree new algorithms like Anya and Polyanya can help improve the state-of-the-art in these areas.
Considering how Poly-Anya was sometimes slower than Anya (the non-nav-mesh version of path finding), it seems like the jury is still out as to whether this technique + nav-mesh is useful?
I could be completely wrong, I'm just looking at the results from the papers/slides you posted. It seems that A* still has relevance because it and modifications to it are still the fastest path-finding algorithms?
What I've learned is that A* is largely deprecated these days. Modern games mostly use "navigation meshes" for "any angle" pathfinding to address what is otherwise an np complete problem. The idea is that you generate a set of vertices across your terrain and compute the path from there.
One of the current leading experts in this is Daniel Harabor. His papers are brilliant
http://harabor.net/data/presentations/gdc2019.pdf
https://harabor.net/daniel/index.php/pathfinding/