Jump to content
  • Advertisement
Sign in to follow this  
Mussi

Pathing with variable unit radius.

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

If you intended to correct an error in the post then please contact us.

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:

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?

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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 radius
for every node call this function
blockExpand(node start, list of nodes that will get blocked)
{
set starting node distance to 0
while(open list is not empty)
{
get first node in open list
remove it from the open list
add it to the closed list and to the blocked list
block the node
go trough adjacent nodes
{
if(in closed list already)
continue
else
if(distance current node + distance to adjacent node <= start node block radius)
{
add it to the open list
set 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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!