18
\$\begingroup\$

I haven't actually started programming for this one yet, but I wanted to see how I would go about doing this anyway.

Say I have a grid of tiles, all of the same size, some traversable and some not. How would I go about creating a navigation mesh of polygons from this grid?

My idea was to take the non-traversable tiles out and extend lines from there edges to make polygons... that's all I have got so far. Any advice?

\$\endgroup\$
  • 2
    \$\begingroup\$ Technically the grid is pretty much equivalent to a navigation mesh. I suspect you're actually asking for a way to optimise the grid and coalesce adjacent squares. \$\endgroup\$ – Kylotan Nov 16 '12 at 8:50
  • \$\begingroup\$ @Kylotan Yes that is exactly what I meant, just a way to combine adjacent polygons. \$\endgroup\$ – Ross Hays Nov 17 '12 at 4:53
27
\$\begingroup\$

Here's one of the methods I came up with when doing navmesh for an RTS game. Note that it is homebrew, no third-party tools were used, it took me about 3 weeks to implement and bugfix:

  1. Use Marching Squares algorithm to convert obstacle tiles into outlines. Note that map edges is an outline too and need to be included as well.
  2. Reduce number of points in outlines using Douglas-Peucker algorithm (purple lines on the bottom picture)
  3. Feed all points into Delaunay triangulation (to get most uniform triangles)
  4. Add additional points in empty areas and along the map edges (to get more even navmesh)
  5. Check along obstacle outlines and flip polygons produced by Delaunay to match outlines. - Often Delaunay could place triangles (grey) mismatching your outlines (red), then you need to detect and flip them. Adjoining them back into a polygon, split it along outline(s) and triangulate it manually enter image description here
  6. Clip obstacles innards - remove polygons that are within obstacles (pink on the picture above)
  7. Fill in connectivity data between remaining triangles and vertices as you need - that's your navmesh.

Result:

tilemap navmesh

\$\endgroup\$
  • 1
    \$\begingroup\$ This is exactly what I was looking for. Thank you! \$\endgroup\$ – Ross Hays Nov 17 '12 at 4:52
  • \$\begingroup\$ @Kromster I don't understand steps 5 and 6. To me they are both opaque. Please explain them in just a little more detail. \$\endgroup\$ – oskarkv Sep 11 '16 at 18:02
  • \$\begingroup\$ @oskarkv Answer updated \$\endgroup\$ – Kromster Sep 12 '16 at 4:03
1
\$\begingroup\$

Meshes are typically implemented as graphs. If you wish to implement path-finding in a map based on a grid do the following:

Create a graph where each traversable square is represented as a vertex. Each pair of adjacent traversable squares represented as vertices, will have an edge between them. And you're done.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is not how navmeshes are typically implemented. The purpose of a navmesh (and, I imagine, the reason the asker even asked their question here) is to optimize the graph down to a minimal required number of polygons (usually triangles) that span the most useful spaces to reduce both the number of steps required to find a good path, and the memory footprint required to define the mesh. A raw implementation would both eat up a ton more memory, and would waste valuable AI processing time. \$\endgroup\$ – Gurgadurgen Jul 9 '16 at 21:21
  • \$\begingroup\$ You are correct. Of course decimation (polygon reduction) is a reasonable and desired optimization. It is just that when you read the op's question, you are getting the sense he just wants to turn a grid into a graph. \$\endgroup\$ – wolfdawn Jul 12 '16 at 9:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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