I'm having trouble deciding how to proceed in modifying my approach to account for non-zero creature radius. I'm happy for my creatures to be simple circles and for there to be a small fixed set of allowed creature sizes, perhaps four or five. Given this one approach is to rebuild the mesh for each allowed size and "expand" the invalid polygon regions by the creature radius using an approximate Minkowski sum calculation. This seems to work ok but it seems quite inefficient and I'd prefer something more general.
There's a few references in discussions about "skrinking" the navigation mesh, however I don't understand what this means in practice.
One possibility that does make sense to me is instead of reducing the mesh as a whole we first obtain the sequence of edges or portals that we want to traverse to get to the goal by searching the unmodified mesh. We then form a new channel by taking each edge and contracting it along it's length by the radius and use the funnel algorithm on that.
This has a few issues to work out:
- Some channels may be too small for large creatures to traverse at all, the A* search at the start needs to know this so it finds a different path. We need to independently calculate the maximum radius that can traverse each pair of edges.
- The reduced channel doesn't exactly produce the smooth circular arc around the corners that you strictly need, just an approximation
- The boundary of the channel may not always be made of constrained/unwalkable edges, in which case you may not need to skrink it there. Although it could still be near a different constrained edge in which case you need to do something different to work out how much to shrink the channel by. (I think this should be a rare case with a proper triangulation but I don't think it' impossible for the way I build mine at the moment.)