Pathing with variable unit radius.

Artificial Intelligence Programming

Started by Mussi July 02, 2010 08:20 AM

14 comments, last by Mussi 13 years, 10 months ago

4,453

Author

July 02, 2010 08:20 AM

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

21,604

July 02, 2010 09:53 AM

Increase the radius of the obstacles by the radius of the unit.

Mussi

4,453

Author

July 02, 2010 10:03 AM

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

21,604

July 02, 2010 11:08 AM

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

4,453

Author

July 02, 2010 11:44 AM

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

4,453

Author

July 02, 2010 05:21 PM

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

21,604

July 02, 2010 05:24 PM

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

4,453

Author

July 02, 2010 05:50 PM

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

458

July 03, 2010 04:44 AM

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

4,453

Author

July 03, 2010 02:54 PM

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.

Pathing with variable unit radius.

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Pathing with variable unit radius.

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines