Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  Kylotan Nov 16 '12 at 8:50
    
@Kylotan Yes that is exactly what I meant, just a way to combine adjacent polygons. –  Ross Hays Nov 17 '12 at 4:53

2 Answers 2

up vote 11 down vote accepted

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 (purple lines)
  2. Reduce number of points in outlines using Douglas-Peucker algorithm
  3. Feed all points into Delaunay triangulation (to get most uniform triangles)
  4. Add more points in empty areas and along the map edges to get more even coverage
  5. Check along obstacle outlines and flip polygons produced by Delaunay to match outlines
  6. Clip obstacles innards
  7. Fill in connectivity data between remaining polys - thats your navmesh

Result:

tilemap navmesh

share|improve this answer
    
This is exactly what I was looking for. Thank you! –  Ross Hays Nov 17 '12 at 4:52

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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