🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Pathfinding with different unit sizes
Author
Hi all,
I''m currently writing a simple pathfinder for a randomly generated grid map. The problem is that I want to support units (tanks, jeeps, etc.) of different sizes, so I want my pathfinder to be aware of ''tight spots''. The pathfinder should not produce paths that are to narrow for a unit to use.
I was wondering how this is done in other games. A brute force solution would be to inspect surrounding nodes during the node selection in my pathfinder, but that seems like an awful waste of cpu time.
If you have any ideas, I would really like to know about them!
-Fri
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 ]
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.
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.
Author
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
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
