Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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?

share|improve this question

marked as duplicate by BlueRaja - Danny Pflughoeft, Anko, bummzack, Byte56 Aug 16 '13 at 0:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

up vote 3 down vote accepted

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.

share|improve this answer
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. – Cory Klein Aug 14 '13 at 23:12
Also, this paper is great. – Cory Klein Aug 14 '13 at 23:43
Also of note is the funnel algorithm – Cory Klein Aug 14 '13 at 23:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.