# Pathing with variable unit radius.

This topic is 2910 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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:

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?

##### Share on other sites
Increase the radius of the obstacles by the radius of the unit.

##### Share on other sites
Quote:
 Original post by alvaroIncrease 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.

##### Share on other sites
Quote:
Original post by Mussi
Quote:
 Original post by alvaroIncrease 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.

##### Share on other sites
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!

##### Share on other sites
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?

##### Share on other sites
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?

##### Share on other sites
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.

##### Share on other sites
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

##### Share on other sites
Quote:
 Original post by alexjcHow 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.

• 11
• 20
• 12
• 10
• 34
• ### Forum Statistics

• Total Topics
631399
• Total Posts
2999854
×