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?

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

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.

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.

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!

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?

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?

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.

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

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:


Thanks again for the help guys.