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.

Seconded, Recast+Detour is terrific.

You can feed it raw tris, the same stuff you would send to the graphics card to render, and get out a high quality, extremely fast navigation mesh.

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

Navmeshs are pretty common these days. My perspective is that they're much more common for high end games than any other technique (nodes, grids, ...), but that might just be because we use them at work.

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.

Not a solution but a starting point: http://en.wikipedia.org/wiki/D*

I used this for a similar problem in my computer science studies. We had a map with an unknown layout of fields, each with a different travel cost and had to drive a tour of multiple flags in the fastest way possible. It worked quite well.

A*-like algorithms aren't really even applicable to Battlecode though because of the tiny bytecode limit. You're essentially forced to use local navigation or something like distributed BFS.