3
\$\begingroup\$

A* and Dijkstra's pathfinding algorithms work by navigating a node map. In a tile-based 2D environment, these nodes could easily be inferred to be the literal x,y positions of the map.

For example, the agent is at (0,0), an obstacle is at (0,1), and the agent wants to go to (0,2).

However, in a 2D environment where locations are represented using floating point variables float x, float y, agents and obstacles can exist between the traditional style nodes (0,0) and (0,1).

How do you create a node map from such an environment?

\$\endgroup\$
0

1 Answer 1

3
\$\begingroup\$

The two most common answers are to use waypoints or navigations meshes (navmeshes).

In the former case, you pick various points on your map, precompute which are "neighbors" (have a clear path between them), and explicitly link them together.

In the latter case, you generate a triangle mesh covering all walkable regions. Your nodes can be triangles with graph-edges being the shared triangle-edges. Or nodes could be midpoints of triangle-edges with the graph-edges being computed from the triangles.

\$\endgroup\$
3
  • \$\begingroup\$ This is GREAT information, thank you. The phrase "triangular navigation mesh" eventually led me to this rather educational paper Navigational Queries on Triangular Meshes. I feel much better equipped to approach this problem now. \$\endgroup\$
    – Cory Klein
    Aug 14, 2013 at 23:12
  • \$\begingroup\$ Also, this paper is great. \$\endgroup\$
    – Cory Klein
    Aug 14, 2013 at 23:43
  • \$\begingroup\$ Also of note is the funnel algorithm \$\endgroup\$
    – Cory Klein
    Aug 14, 2013 at 23:48

Not the answer you're looking for? Browse other questions tagged .