Just as a side note: bidir A* is not that straight forward as you need a special finish condition to keep the algorithm optimal. (For games you probably don't need this but for tests and real world road routing it is important IMO)
> The long-range pathfinder can be simpler and more efficient if it has a grid representation of the map.
> (Since our maps are large and open [] and must support dynamic generation [] and dynamic modification [], a grid is likely better than a nav mesh)
Can someone explain why this is the case? I feel like using a grid will result in them generating the equivalent of a fresh nav mesh every time they want to pathfind, as opposed to using a cached navmesh (generated when terrain is loaded) which they can modify in place every time a dynamic event occurs (building placed).
I like how this article gives some insights on how to go from A* to a practical AI pathfinder. You always hear about 'use A* for pathfinding', only to get yourself stuck in the actual wiring the A* algorithm into your application.
Always fascinating is the actual Edge-Case Handling (UnitsStuck). Setting Collission off and sending Units back shortest path can yield unexpected results there.
Well you use a Quadtree for path-finding. That gives you some advantages- regarding
a) Resolution, (Long stretches of open terrain can be handled in one entry)
b) Memory needed (Quadtrees are always just resolved as deep as needed and can be placed cache friendly in mem)
c) Ask kloot. https://www.youtube.com/user/Kleaut
Basically, grab some graph paper. Put your left index finger on start. Right index finger on end.
Move your fingers towards each other, avoiding obstacles as you go.
Wherever they happen to meet, the path formed by the trail of both your fingers combined is the path to use.
That's the general idea. It's important to trace from both simultaneously, otherwise you run into some degeneracies.