Hello. I have a problem with path finding through a navigation mesh of triangles. Each node is situated in the centre of each triangle and joined with the nodes of triangles that share edges. The mesh is sorted so that only key nodes need to be searched – that is, nodes that have either three or one connection (so that "corridors" can be skipped when searching) as well as a few other special cases. Once a channel of triangles leading from the start to the end is found another algorithm is implemented that gives the optimum path through that channel. The problem is that I am as of yet unable to take into account size constraints for my agents. I need to be able to determine what places will be too small for my agents to pass through. Ideally I’d like to do this on a per-triangle basis. I cannot just use the length of the edge shared between two triangles as the maximum width for passing between those them because of the case where there are very narrow triangles which have three long edges - even though the edges might be longer than the diameter of my agents the agents still would not be able to pass through. Nor can I just calculate the maximum with of passing through a triangle from the entry edge to the exit edge because my nodes are the triangles, not the edges joining the triangles. I do not wish to expand my geometry by the radius of my agents, because then it will mean using different navigation meshes for different sized agents and that is contradicting the point of my path finding system, would invalidate much of the code optimizations I've implemented, as well as opening up a range of new problems. Any ideas? Forgive my lack of graphics to demonstrate the problem - unforunately I no longer have webspace to host images. Jackson Allan

Could you store a 'max radius' per edge? Or, if you have fixed hull sizes, a mask indicating what hull sizes can cross each edge?

Instead of checking the width of an edge, you might want to check the projection of the triangle on a line that is perpendicular to the direction an agent must go through the triangle.

I can't really explain it better or even hint at a way to implement this, but this site http://www.harveycartel.org/metanet/tutorials/tutorialA.html#section2 has some good explanations.

Hope it helps.