I've been making a pathfinding system for my project using a triangular navigation mesh. This is working quite well, I can now build the mesh and find simple paths and smooth the paths using the funnel algorithm outlined in this blog post:

http://digestingduck...-algorithm.html

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.)

I'd be grateful for any advice on this approach and whether it's worth pursuing, or any other suggestions.

Your approach sound reasonable: just annotate the edges with some clearance information to help the pathfinder. You may also want to look at Douglas Demyen's TRA* article; I believe it solves a similar problem to yours. Google for it, I'm sure you'll find it easily.

What's wrong with the Minkowski approach btw? You do it once as a pre-processing step so it shouldn't matter if it takes some time? Thomas Young had a nice article on implementing this sort of thing in Game Programming Gems 2. It was called "Expanded Geometry for Points-of-Visibility Pathfinding". Maybe look at that. iirc: he simply drags the collision shape of the agent around the mesh of each obstacle in order to expand its bounding volume. I think this is much faster than calculating a proper Minkowski sum.