Run-time Navigation Mesh Generation for 2D Tile Maps

Question

I have a 2D tile map, where each tile is marked as blocking or non-blocking. Each tile is 16x16 pixels and sub-tile movement is possible. I'm attempting to generate a navigation mesh from this data, at run-time, using C++.

Is there any well known library that can be used to generate a navigation mesh, given a 2D tile map? Alternatively, is there any algorithm that can be used to intelligently generate a navigation mesh from the tile data?

As far as I can tell, all of the popular solutions are aimed at 3D maps and don't perform well when given the simplified case of a 2D map.

Answer 1

One idea would be to turn the center points of your tiles into a graph (see your data structures text book), on which any number of pathing/traversal algorithms will work (A*, depth first and breadth first traversals). Given the results, which would be a queue of points to follow, your movement routines can build a smoothed path to follow with splines or simply use LOS checks to get from place to place within that point set.

Another idea would be to actually use your tile set and build a 3D representation of your walkable squares and feed it to your favorite 3D navmesh generator and library.

In either case the pixel count doesn't matter as long as you decide on a standard of one tile = 10 units in space (totally arbitrary), just to keep things simple for your math.