Jump to content
  • Advertisement
Sign in to follow this  
wooyay

Hertel-Mehlhorn NavMesh optimization: Long polygons

This topic is 2702 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

l48hH.jpg

I have implemented the Hertel-Mehlhorn algorithm to optimize my navigation mesh. As you can see in the image there are many cells that are long and thin. This happens when I have large open spaces.
Is that a known behavior of H-M algorithm or do I do something wrong? Is it possible to somehow define a maximum width of a cell? Or are there other ways to deal with this?

(Please ignore that the diagonal obstacles produce a pixel-like effect, that's a topic for another post).

Thank you!
Cheers,
Martin

Share this post


Link to post
Share on other sites
Advertisement
You are applying the Hertel-Mehlhorn algorithm to a starting triangulation that is full of slivers: both the short sides and the long sides are all in the source data.
You apparently fail to merge polygons over what should be collinear segments (for example, each of the rectangular platforms should be one piece): look for accidentally nonplanar geometry (ouch!) or for subtly wrong geometric tests that don't like angles of exactly 180 degrees.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!