Hi all,

I'm trying to write a navmesh generator from scratch. Why from scratch? Because I want to understand it.

So I have an arbitrary world. I can query each point to see if it's blocked, or not blocked (functionally, my world is made up of polygons, lines, and circles, all of which block. Everything else is open).

I've had several false starts, which end up leaving me blocked. My first goal was to treat the whole world as a single rectangular polygon, then cut holes in it where the obstacles are, and then triangulate that.

Turns out cutting holes in a polygon efficiently and always correctly is some ancient math mystery that one day might be solved if we can just invent a quantum hyperspace computer.

Then I tried producing a grid, and tried to floodfill to produce a navmesh. What I got instead was a navmess.

So, does anyone know of a nice simple resource for the beginning navmesher? Everything I google up basically starts out "now that you're a level 99 math phd with full gear, consider the trivial problem of bisecting a rotating arbitrary voxel polygon hypercube in n-th dimensional space."

Thanks!

The most popular modern technique is to voxellize the world from the polygon collision data of the map and then use that data to validate walkable height regions, exclude cells a certain distance from the edges of the areas, and finally merge the results into triangular or polygonal regions.

This is a great open source resource that you can learn alot from if you go back through the blog history.
http://digestingduck.blogspot.com/

I did the holes in polygon method that you mention a long time ago and used the gl tessalation library. I think nowadays the voxelization route suggested by JeremyS is the way to go.