Just for fun, I am working on a little side-project: As a first step, I want to be able to build a grid-based world (think Dungeon Keeper), generate a nav-mesh for this world and then let agents wander around it. I've already done plenty of googling and ended up following the instructions given in the answer to this gamedev question: How can I generate a navigation mesh for a tile grid?

Now, I've completed step 1 in that I now have iso-lines representing the outlines of the walkable area. This could look like this:

walkable area outlines

The blue lines are the generated outlines of the walkable area. As you can see, in this case there is one walkable areas defined by two lines because the area is a circle.

This is where I'm stuck: If it were a regular polygon I'd probably be able to implement some sort of triangulation algorithm (there's plenty of examples on the net, I guess), but how do I go about this case? Do you have any pointers for me?

  • \$\begingroup\$ asked and answered on SO accepted answer leads to: cs.cmu.edu/~quake/triangle.html \$\endgroup\$ Commented Nov 9, 2014 at 11:59
  • \$\begingroup\$ My answer on the linked question explains it in short words. Do you have any specific problems with step 3 ? \$\endgroup\$
    – Kromster
    Commented Nov 9, 2014 at 17:26
  • \$\begingroup\$ tbh, I haven't attempted the Delaunay triangulation yet as I was puzzled concerning the way it would handle the "hole case" described above. \$\endgroup\$
    – Lunikon
    Commented Nov 11, 2014 at 13:37

1 Answer 1


If you want a generic "good for all cases" solution (and it looks that you need one, given how varied DK kind of game levels can be, unlike, say, a circle-racing game) then you should refer to the question you have linked (How can I generate a navigation mesh for a tile grid?). It deals with this problem in steps 2-7. Not simple, I agree, but universal.


You must log in to answer this question.

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