Along with the everyone else, I came to the conclusion simple hexagon based graph search for my spherical world is not going to cut it.
So I’ve implemented kind of a navmesh solution. It is very loosely inspired by recast (combining hexagons into big convex regions), but has very similar properties that would be expected from navmesh (faster path finding, it is dynamic, quicker to return to path). It is no where as good, but I kind of think it might be good enough. Not shown is the ability to path find through hexagon vertices (you don’t see it because it is low priority and not needed in the demo).
The entire path finding and updating of the navmesh runs in its own low priority thread using a lockless design. This means the AI would queue up a path finding task and get a call back once the pathing is done. The call back schedules a task on the game thread. The schedule task then reads from the task output queue and then updates the AI’s path. The updates to the navmesh happen the same way.
I was not clear in the video, but at one point you see a path running through a hexagon. That is because the path find happens just before the update.
Here is the video with an actual pawn (it uses collisions to determine if it is stuck)