Skip to main content
GameDev.net gamedev.net
🔒 Locked

Pathing with variable unit radius.

Started by Mussi Jul 2, 2010 at 8:20 AM 14 replies 3.9k views
Original Post
Mussi
Mussi
Hi there,

I've implemented A* path finding for my units and all my units block nodes within their radii. The nodes are not specifically grid aligned and are positioned in 3D and contain pointers to adjacent nodes. The problem arises when a unit passes another unit and cuts trough. The unit pushes the other unit, which could be a player, out of the way. The problem is illustrated in the following image:

path finding problem

The target location is chosen correctly, as in the circles won't intersect. The path finding algorithm however sees this as a valid path, but it shouldn't be. Now I could check for each node in the algorithm weather there are any other nodes within the radius that are blocked but this would slow down the algorithm by a lot.
I've thought about detecting if there are any nearby nodes that are blocked when the unit moves to a node and if that happens temporarily block the node and recalculate the path, but that could result into a lot of recalculations.

Is there a fast way to get a path that takes the unit's radius into account?
alvaro
alvaro
Increase the radius of the obstacles by the radius of the unit.
Mussi
Mussi
Quote:
Original post by alvaro
Increase the radius of the obstacles by the radius of the unit.


The radius of the unit is variable, are you suggesting that for every unit I should go trough all units and recalculate what nodes they block? That could possibly be the best solution computation wise. Any other ideas are more than welcome.
alvaro
alvaro
Quote:
Original post by Mussi
Quote:
Original post by alvaro
Increase the radius of the obstacles by the radius of the unit.


The radius of the unit is variable, are you suggesting that for every unit I should go trough all units and recalculate what nodes they block?


Well, that or you could store in each node what the distance to the closest blocking unit is, and have a quick check to see if it's blocked for this particular unit radius.

Mussi
Mussi
Quote:
Well, that or you could store in each node what the distance to the closest blocking unit is, and have a quick check to see if it's blocked for this particular unit radius.


That seems like the most elegant solution. Thanks a lot for your input!
Mussi
Mussi
I've tried you're approach Alvaro, but with 8 units it's already taking about 2ms to calculate unit distances for all the nodes and the game is designed about having 30-40 units actively combating with more nodes as well. That would mean it could take close to 10ms to get the data right, that's just too much.
Any other possibilities?
alvaro
alvaro
Perhaps you are spending a lot of time computing square roots... Use squared distances instead!

If that doesn't solve the problem, I would suggest using a profiler. What language and compiler are you using?
Mussi
Mussi
Quote:
Perhaps you are spending a lot of time computing square roots... Use squared distances instead!


Unfortunately that is not possible, the closest distance from a node to a unit is the length from the node to the unit minus the unit radius.

I'm using c++ and visual studio 2008.

I just thought of something though. My nodes contain information about the distance to adjacent nodes. If every unit blocks only the closest node and store their radius in the node I could then do the following before path finding for a unit: check all blocked nodes, for those nodes use Dijkstra's algorithm to temporarily expand the nodes being blocked using the units radii and the node distance information. This would require no distance calculation and reduces the amount of nodes to check. Please let me know what you think.
alexjc
alexjc
How variable are your unit radii? If you can safely approximate the radius by a worst-case estimate, then it'll be much faster. Almost no modern game uses a dynamic radius AFAIK.

Alex
Join us in Vienna for the nucl.ai Conference 2015, on July 20-22... Don't miss it!
Mussi
Mussi
Quote:
Original post by alexjc
How variable are your unit radii? If you can safely approximate the radius by a worst-case estimate, then it'll be much faster. Almost no modern game uses a dynamic radius AFAIK.

Alex


Thanks for your input. Unit radii can variate quite a bit, melee attacks could be dealt from a too large range if the largest radius is taken for all units.

My idea worked though and it seems to be less intensive. For anyone that's interested, this is how I solved my problem:
Every unit has a pointer to the closest node. The closest node stores the unit radius that's closest to it as it's block radius. Nodes contain adjacent node information and information about the distance to the adjacent nodes. When a unit needs path-finding it goes trough all other units and and temporarily blocks their surrounding nodes using a sort of Dijkstra algorithm. Something along the lines of:
increase the start nodes radii with the unit radiusfor every node call this functionblockExpand(node start, list of nodes that will get blocked){set starting node distance to 0while(open list is not empty){get first node in open listremove it from the open listadd it to the closed list and to the blocked listblock the nodego trough adjacent nodes{if(in closed list already)continueelseif(distance current node + distance to adjacent node <= start node block radius){add it to the open listset it's distance to parent distance + distance to this node}}}decrease the start nodes radii with the unit radius to reset the original state


Thanks again for the help guys.
Sneftel
Sneftel
Recent work by Overmars et al. on corridor maps is well-suited for pathing many units with circular footprints of varying radii.
Hexmind
Hexmind
I'm not sure if this is your case but if you calculate the path at each frames, perhaps you could save the path in an appropriate variable and calculate the path once every 10 frames or so. Things don't change that much in a single frame to affect path finding. Just a thought.
Mussi
Mussi
Thank you for the replies.

Quote:
Original post by Sneftel
Recent work by Overmars et al. on corridor maps is well-suited for pathing many units with circular footprints of varying radii.


That seems like a very interesting paper, however 3D pathing is not covered in it it seems. Also I've just fully implemented my solution which seems to be doing a great job :D.

Quote:
Original post by Hexmind
I'm not sure if this is your case but if you calculate the path at each frames, perhaps you could save the path in an appropriate variable and calculate the path once every 10 frames or so. Things don't change that much in a single frame to affect path finding. Just a thought.


I limit path calculations to like 3 paths per frame using a queue system. The game is action based so the response time of the units is a factor here.


Seems like this is a difficult topic, maybe I should write an article in the near future on my fairly simple to implement approach.
Emergent
Emergent
Quote:
Original post by Sneftel
Recent work by Overmars et al. on corridor maps is well-suited for pathing many units with circular footprints of varying radii.


Looks a lot like Voronoi roadmaps. The idea of smoothly interpolating between max-clearance and min-time paths is interesting though...
Sneftel
Sneftel
Quote:
Original post by Emergent
Looks a lot like Voronoi roadmaps.
That's its basis, certainly. Actually, the thing I find most intersting about corridor maps is how well they dovetail with dynamic behaviors like collision avoidance. Rather than rubber-banding to the exact, inscrutable polyline one gets out of most path planners, agents can use conventional separation behaviors, and still maintain a good-looking trajectory.
Mussi
Mussi
Quote:
That's its basis, certainly. Actually, the thing I find most intersting about corridor maps is how well they dovetail with dynamic behaviors like collision avoidance. Rather than rubber-banding to the exact, inscrutable polyline one gets out of most path planners, agents can use conventional separation behaviors, and still maintain a good-looking trajectory.


Correct me if I'm wrong but collisions can still and probably will occur though. It might be so that rubber-banding is not needed for this particular technique, but that goes for most path planners as well. Is there something I missed?

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.