16 ms·

I just got into the weeds of this for a hobby game I'm working on. What I've learned is that A* is largely deprecated these days. Modern games mostly use "navi

by warent 4y ago

I just got into the weeds of this for a hobby game I'm working on. 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 http://harabor.net/data/presentations/gdc2019.pdf https://harabor.net/daniel/index.php/pathfinding/ https://harabor.net/daniel/index.php/pathfinding/

Agentlien 4y ago
In all games I've worked on nav meshes have been used. They are definitely the goto solution for NPC movement. 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.
marijnz 4y ago
Note that a navmesh can be used exactly with A* (and also for a post-search path shortening pass, with for example http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html http://digestingduck.blogspot.com/2010/03/simple-stupid-funn...)
Udo 4y ago
Maybe someone can clear something up for my understanding here. 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?
- warent 4y ago
  No I think you're right and that I was mistaken. The only navmesh implementations I've seen do not use Astar, with Astar only being used in grid structures. But now I see that was a coincidence.
  - dheera 4y ago
    Astar can also be used for non-grid structures. It can actually be used for any graph traversal, including e.g. Google Maps Navigation type use cases, and is arguably even more suited to those problems than grid movement, since the lowest-cost path through a grid is often a very unnatural way to move through an open space, especially if you're using Manhattan distances.
  - Agentlien 4y ago
    I've worked on several AA and AAA games which use nav meshes and they've all used A* for search. This is also how many game engines, including Unity, implement their NavMesh queries.
agumonkey 4y ago
Very nice paper, thanks.
1248 4y ago
But if you want to navigate in a 3d space (flying/space games) navmeshes are useless and you have to roll your own spline(ish) 3d space navigation/obstacle avoidance system. (It's kinda weird that an engine as popular and massive as UE5 only has nav meshes.)
- softfalcon 4y ago
  Yeah, both UE5 and Unity3D seem to rely heavily on nav meshes for their built in path-finding. In my experience, both are sub-optimal for many, many use cases but are convenient in that they apply to a bunch of "on the ground" topology that can be somewhat easily generated using a quick ortho camera project/ray-cast operation. Maybe they use it cause it's quick and easy, not because it's the most optimal?
- BlueTemplar 4y ago
  IIRC UE also still only has the (built-in) option for a static, same vector at every space&time point (gravitational) force field ? Of course this does cover most of the cases, probably even for "space" games (which are often more akin to WW1/WW2 naval simulators).
softfalcon 4y ago
Interesting, this was at the bottom of the slides: > 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?
hesdeadjim 4y ago
A* is as valid on a navmesh as it is in a grid-based layout. A* just needs "points" (or each edge of a navmesh polygon) and the edges that connect them, how those points and edges are represented or exist in the world is entirely an implementation detail.
- TillE 4y ago
  It's funny cause A* (a slight modification of Dijkstra's algorithm) is explicitly an algorithm that operates on graphs. Applying it to a "navmesh" is actually conceptually simpler than thinking of a grid-based game world as a big uniform graph.
Mageek 4y ago
You still run A*, it’s just on the nav mesh rather than on a grid.

by warent 4y ago

Agentlien 4y ago

In all games I've worked on nav meshes have been used. They are definitely the goto solution for NPC movement. 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.

marijnz 4y ago

Note that a navmesh can be used exactly with A* (and also for a post-search path shortening pass, with for example http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html http://digestingduck.blogspot.com/2010/03/simple-stupid-funn...)

Udo 4y ago

Maybe someone can clear something up for my understanding here. 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?

warent 4y ago
No I think you're right and that I was mistaken. The only navmesh implementations I've seen do not use Astar, with Astar only being used in grid structures. But now I see that was a coincidence.
- dheera 4y ago
  Astar can also be used for non-grid structures. It can actually be used for any graph traversal, including e.g. Google Maps Navigation type use cases, and is arguably even more suited to those problems than grid movement, since the lowest-cost path through a grid is often a very unnatural way to move through an open space, especially if you're using Manhattan distances.
- Agentlien 4y ago
  I've worked on several AA and AAA games which use nav meshes and they've all used A* for search. This is also how many game engines, including Unity, implement their NavMesh queries.

agumonkey 4y ago

Very nice paper, thanks.

1248 4y ago

But if you want to navigate in a 3d space (flying/space games) navmeshes are useless and you have to roll your own spline(ish) 3d space navigation/obstacle avoidance system. (It's kinda weird that an engine as popular and massive as UE5 only has nav meshes.)

softfalcon 4y ago
Yeah, both UE5 and Unity3D seem to rely heavily on nav meshes for their built in path-finding. In my experience, both are sub-optimal for many, many use cases but are convenient in that they apply to a bunch of "on the ground" topology that can be somewhat easily generated using a quick ortho camera project/ray-cast operation. Maybe they use it cause it's quick and easy, not because it's the most optimal?
BlueTemplar 4y ago
IIRC UE also still only has the (built-in) option for a static, same vector at every space&time point (gravitational) force field ? Of course this does cover most of the cases, probably even for "space" games (which are often more akin to WW1/WW2 naval simulators).

softfalcon 4y ago

Interesting, this was at the bottom of the slides: > 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?

hesdeadjim 4y ago

A* is as valid on a navmesh as it is in a grid-based layout. A* just needs "points" (or each edge of a navmesh polygon) and the edges that connect them, how those points and edges are represented or exist in the world is entirely an implementation detail.

TillE 4y ago
It's funny cause A* (a slight modification of Dijkstra's algorithm) is explicitly an algorithm that operates on graphs. Applying it to a "navmesh" is actually conceptually simpler than thinking of a grid-based game world as a big uniform graph.

Mageek 4y ago

You still run A*, it’s just on the nav mesh rather than on a grid.