Take a look at Mikko Minonen's excellent open source Detour and Recast libraries: https://github.com/memononen/recastnavigation https://github.com/memononen/re

Take a look at Mikko Minonen's excellent open source Detour and Recast libraries: https://github.com/memononen/recastnavigation 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.