Optimizing A* for grid maps

Take a look at Mikko Minonen's excellent open source Detour and Recast libraries:

https://github.com/memononen/recastnavigation

He does automatic graph construction from dense data. Recast can generate this dense data automatically by populating a graph at voxel centers based on the level geometry, but it can also accept a tile-grid at that point.

It is a terrific system, and if you want to learn about how robust pathfinding should be done in games, you can do much worse that find out how it works.

Related to this idea is the "Jump Point Search" algorithm, an optimization of A* which does this sort of straight-line optimization for exactly this use case.

http://zerowidth.com/2013/05/05/jump-point-search-explained....

> Navigation meshes, visibility graphs, and hierarchical approaches are all worth a look.

Navigation meshes in particular are worth consideration. There is a great reference here [1] from Epic Games about navigation meshes, and why they made the switch from a traditional node-based graph to them for the Unreal Engine. Although for most simple cases, a graph is much easier to conceptualize and implement.

[1] https://udn.epicgames.com/Three/NavigationMeshReference.html

This was basically what a lot of Quake era bots did to improve their AI. In order to find their way around a map, they precomputed paths. Later bots, when put in a map that wasn't precomputed, they would build a similar mapping on the fly, pruning "symmetrical" nodes and therefore reducing their path finding. When the not would discover the location of an item, it would graft that new branch back into the graph.

I've been thinking about doing this for procedurally generated dungeon maps. Basically, randomly add some subset of grid squares, then work out naive as-the-crow-flies connectivity between the closest neighbors to generate the sparse graph.

For straightforward corridor and room maps, each corridor/room object just becomes a node.

I attempted the recent MIT AI competition, but stumbled at the point where I wanted to build something like the post suggests, except that the map is not initially discovered. :( if anyone could point me to a method for constructing such a graph through discovery, that would be great.