Graph Node generation from Tile Map

Quote:

Original post by Wicked Ewok Hi there, I was wondering if there are any good algorithms to generate undirected graphs from a Tile map for path finding? Thanks! Marvin

Why do you need a graph for pathfinding on a regular tile map? Simple A* generates paths extremely well on regular tiles..

If you really need something for graph generation, Delaunay triangulation / Voroni diagram can build your graph once you've found the critical points. For a tile map, I imagine critical points would probably be corners of regions.

frob.

Hi frob, thanks, I will look into Delaunay triangulation. Reason for trying to construct a graph: I did implement A* except the movement along long stretches of diagonals can be kind of weird, especially if there's a one line direct route to the goal node.

Thanks!
Marvin