Pathfinding with different unit sizes

I don''t think it would be a significant use of CPU time as long as the check itself is not too complex. Perhaps most elegant would be the ability to pass in a functor or function pointer to the pathfinding routine which is given a start node, a adjacent node, and a unit, and returns true if the adjacent node can be reached from the start node by that unit.

If you only had a small number of distinct unit sizes however, you might consider it worthwhile to generate several different pathfinding graphs, one for each size. The graph for large units would probably have fewer nodes due to the number of impassible sub-paths. But I reckon this would be premature optimisation. Try the simple and obvious method first, profile it, and then see if you need to change anything.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ]

One way is to store information about the width of a path between nodes in your search space. Then, the pathfinder can test a path width against the object width when evaluating possible paths.

For example, lets say a path exists from node A to node B that is 2 units wide, from A to C that is 3 units wide & from B to C that is 4 units wide. If an object wishes to travel from A to B & the object is 3 units wide, it cant get there directly ( A-B ), but it can do it indirectly ( A-C-B ).
If another object 4 units wide tried to go from A-B, then no path would be found that is wide enough for the object.

Well, thanks! I think that storing the width of a path in the nodes would be a huge improvement; still, when units are moving all around, this would require updating search nodes almost continually. But doesn''t have to be a big problem, since node selection in my pathfinder occurs much more often than actual unit movement. I''m going to try this out!

The only problem I can foresee is that this node updating is not entirely trivial. Nodes in open spaces can get very high width values, and a single unit could influence the width of a large number of nodes. Hmm, well, I think I should limit the maximum size of a unit anyway.

Thanks!
-Fri

If you are using a grib, you will probably want to preprocess it & build up a highway system with on/off ramps. Then, to calculate a path, a unit needs only find the nearest highway ramp & then travel along it. Highways can store a width, like I mentioned above, & units can dynamically alter the width of a highway with their width as they travel along them( so if a unit is on a highway & takes up all the room, other units will know they can''t past ).

Game Programming Gems has some chapters that talk about this sort of thing & even more about how to collapse the search spaces down. Check it out for more in depth exploration of this topic.