Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
I'm working on an RTS game, and I'm using navmeshes for unit pathfinding. I do know how to find a general path within a navmesh, but how do you determine if the unit have enough space to turn?
I have units of different shapes (mostly rectangles with different dimensions), and with different turn radii. Additionally some of units can turn in place, and some can move in reverse.
So, how to find a path which unit can follow, considering that it can not rotate easily?
First of all, a warning. The problem you're trying to solve is complex enough that most professional games don't even bother unless it's a key part of the gameplay. So my advice would be to cheat as much as possible.
For vehicle radius, I would try to use the worst case (the largest dimension) and then treat the vehicle as a cylinder (or a circle, in 2D) for pathfinding. With navmeshes, you can either have a different set of meshes that take into account the different radii, or make the pathfinder stay away from the wall a certain distance. In either case, picture pushing the edges of the navmesh inwards and rounding the corners (this is technically called a Minkowski Sum). Then you can treat the vehicle as a point, in this expanded navmesh.
If you want to take into account turning, you'll have to encode those rules in the pathfinder itself, as it expands. For instance, if a vehicle can't turn in a tight radius, you'll have to both discard some of the polygons offered as connections from the current one, and use this information when optimizing the path during string pulling. In general, you'll also want to encode some of this logic in the heuristic, so that paths try to minimize turns and look as natural as possible.
If you can define the minimum width of the passage that a particular unit requires to be able to pass through then you could subtract that to narrow the polygons on a candidate route on the navmesh. If a part goes negative then you see that it can fit through. Perhaps you can create a passable solution this way, even just by defining safe such width requirements manually for the units.
That is not at all perfect as does not take into account how steep corners are difficult for example for very long vehicles. I suppose there are algorithms to fit shapes inside containers and detect if they don't fit (a simple intersection check would do that but I don't know how to come up with the candidates to check, apart from brute force). Even that would not take into account the turning radii and whether the unit can reverse or not.
Apparently the Corridor Map Method (CMM) is an accepted answer in this similar question, 3D RTS pathfinding
It seems to take account the turning radii in the steering but I did not see anything about the dimensions of the vehicle so not a complete solution to your problem I think.
