mockersf
commented
1 year ago That would work for polynya if we're sure that every vertex in the navmesh is on an obstacle. This is not a guarantee coming, from any navmesh made with any polygon, but I think it's true coming from a Constrained Delaunay Triangulation (if the constraints are the obstacles).
Also, this is a way to adapt the navmesh "online" to unit size. I think the other way is to "shrink" the navmesh depending on the unit size. It's a tradeoff between memory usage and pathfinding speed.
It's not uncommon to have units of different sizes, and you might have areas of the navmesh that are accessible to smaller units but not larger units.
Ideally there'd be some way to pass in the unit radius when searching for a path, and it'd return a valid path for a unit of that size.
In the below image, a small unit would take the leftmost passage, a medium unit could go up, and a large unit has to go right and go all the way around.
(image from https://www.jdxdev.com/blog/2021/07/06/rts-pathfinding-2-dynamic-navmesh-with-constrained-delaunay-triangles/)
It might be possible to just compare the interval size against the unit radius, and reject intervals that are too small, but that might end up being too pessimistic (or I might be misremembering how polyanya works)?