
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 nth dimensional space."
Thanks!
