1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ asked and answered on SO accepted answer leads to: cs.cmu.edu/~quake/triangle.html \$\endgroup\$ – ratchet freak Nov 9 '14 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 says support Monica Nov 9 '14 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 Nov 11 '14 at 13:37
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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