I noticed a bug in my RTS when a unit wants to get to a location to which there is no valid route. In this situation A* causes every possible tile the unit CAN reach to be visited - which is a lot. And this happens not just when a unit is moving but when attacking a target - so if a bunch of units are trying to attack something just off-shore (on a small island) then part of their update routine is to try and find a route each update, for each unit. Suddenly the FPS drops to 2! So how can I detect a situation like this? Setting a maximum route length seems possible but some rutes can be very long if the map is quite 'full' of obstacles. I guess that in the no-path situation the tiles visited is going to be O(d^2) (where d is map size in tiles) where as normally it should max out as maybe O(d*4) - te circumference of the map. But is there a better way?

You could precompute a number for every tile such that all tiles with the same number are connected and all with differing numbers aren't connected. Then the check is extremely simple.

No because the obstacles include buildings and other units. One case was where I had a peninsular-like section on the map and sent a big army (30+ units) to attack something at the end. The units at teh front blocked the whole width of the peninsular and the rest couldn't find a path so kept scanning the whole map.

You can recompute connections every time you add a building.

For units you can first compute the path without unit collisions and then the path with units and a length limit of x*path-without-units

One thing you should do at first, to stop having FPS drops is to spread your queries on multiple frames (one or more frames - and it works also if 10 000 units request a pathfind, they're added to the queue and won't impact the FPSs).

Another thing you can do is process both a path from the target pos to your unit and from your unit to your target pos, when ever one reaches the other or both reach the same node, you're done... when ever one fails, abort your pathfinding. But watch out if you aren't using a bidirectionnal graph, as paths might be usable in one way but not the other (though I doubt its the case if you're doing a RTS)

Hope this helped.

Eric

I guess I should have read the whole thread first.

Another thing I'd do, is not consider other (friendly) units as obstacles. Since friendly units should be able to communicate with each other, would it be acceptable to make them ask for a passage through blocking units? Or even, stop there, draw something in the hud telling units are "stuck" (after waiting for a few secs, else the msg will pop too often), and resume movement as soon as other friendly units have moved out of the way?

I remember playing StarCraft a lot and getting pissed whenever my dragoons would backtrack because other dragoons would be blocking the way.

Hope this helps

Eric

Quote: Original post by xEricx
I guess I should have read the whole thread first.

Another thing I'd do, is not consider other (friendly) units as obstacles. Since friendly units should be able to communicate with each other, would it be acceptable to make them ask for a passage through blocking units? Or even, stop there, draw something in the hud telling units are "stuck" (after waiting for a few secs, else the msg will pop too often), and resume movement as soon as other friendly units have moved out of the way?

I remember playing StarCraft a lot and getting pissed whenever my dragoons would backtrack because other dragoons would be blocking the way.

Hope this helps

Eric

And add an extra cost for the blocking friendly (to reflect that unit might stand there for a while before clearing the path). Thus it would be a potential path that might be resolved later, and a better path if found would be chosen over the traffic jammed path. Experimentation might be needed to determin what the right cost might be (and maybe a special function to multiply the cost if the current path is dependant on multiple units blocking -- to compensate for the added uncertainty....)

For the OP -- you might be interested in looking into hierarchical A* where a 'Coarse' level of area nodes is checked first (and that island might be determined to be unreachable in a much faster path search without resorting to a much more costly 'Fine' pathfinding.)

One option would be to try the A* path from both ends at once.

Then once you've filled up the little island with closed nodes, you know there is no path and there's no need to explore the entire mainland.

I think there must also be a way of working it out by knowing when the target is entirely surrounded but has not yet been reached. I'm not sure how this would work.

Consider:

..................................................................................................***....................*F*...............S....***.....................................S = startF = finish* = impassible

Once the path has surrounded F and there are no more open nodes inside, the search can stop.

What isn't entirely clear is how you would determine this.

Mark

For the OP -- you might be interested in looking into hierarchical A* where a 'Coarse' level of area nodes is checked first (and that island might be determined to be unreachable in a much faster path search without resorting to a much more costly 'Fine' pathfinding.)
[\quote]

MM i would really be interested in this, infact i had started to create the division tree for this type of pathfinding.

TRAP once again ur ever growing wisdom is present. Yes giving the connected tiles diffrent numbers is an elite idea!!!.. UR A BLOODY GENIUS.

You can also give the numbers to islands (considering bridges un passable) thus when a unit wants to move from a tile (1) to a tile marked(8) u know he will have to walk over bridges and this will help un cutting down unpotential areas.

For the most up-to-date stuff on point-to-point path search look here:
Andrew V. Goldberg's homepage

Nice papers, all of them.