What I'm surprised to not have seen more often is attempts to preprocess a map, group points of it into larger sections and then perform pathfinding on those sections - e.g.:
- split a map into convex polygons
- use pathfinding to find out which polygins you have to traverse (either by making each polygon a node in the pathfinding graph or by selecting points on the polygon's edges and using those as nodes)
- move in a straight line inside a polygon.
It seems, especially for "almost convex" maps, this could move a good deal of pathfinding computation into the build phase.
- split a map into convex polygons - use pathfinding to find out which polygins you have to traverse (either by making each polygon a node in the pathfinding graph or by selecting points on the polygon's edges and using those as nodes) - move in a straight line inside a polygon.
It seems, especially for "almost convex" maps, this could move a good deal of pathfinding computation into the build phase.