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

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.

Hello,

I would like to give some ideas that I learned while working on the path-finding for my game. I'm going to try to keep it short :)

First, if you have islands that are not connected, then you should definitely use the above suggestions; i.e. check all blocks against one and pre-calculate the islands. If this value doesn't match starting block it is unreachable. You should also close any blocks that are completely unreachable. For instance, if an area is enclosed by a ring of mountains.

Second, I would break your path down into 2-3 components. In my game, I call the first path calculation the "far-path", which only cares about closed blocks (it ignores all units that can not be seen unless in range). I compress it by saving every X blocks, where X is the max number of blocks (radius) each player unit can see (10 in my game).

When determining each next move, I calculate the "near-path." This process cares about all entities, but only within a range (max G-Value). Any blocks that are greater than this max G-value are ignored as bad choices. I use a range that is equal to max visible blocks * 3, where the destination is taken from the far path. The destination block is always 2 in advance, so you are guaranteed to be checking just out of visible range, which keeps the path smooth.

Finally, there are times when your units get blocked by other units, such as the peninsula case. I handle this case with a 3rd path, which I just call the "middle-path." When my near-path fails, I re-calculate it, but caring only about closed blocks (like I did with the far-path). I save each block that is occupied, which will be player units (dont save the destination since you just checked it).

I work from destination back to the location of the unit requesting next move until a successful path is found. This keeps your units moving and bunches them up at the peninsula. I have some other tweaks like if the unit is within 6 blocks of final destination and cant move, I just clear the path and assume it is bunched up with other units at a mass-destination. This keeps them from trying constantly, which wastes CPU time.

Anyway, this sounds complex but it is really pretty simple. It reduces the constant path-finding calculations of the full path to just an area around the unit. It compresses the path so you dont have to use much memory. It handles dynamic paths around units. It also handles being blocked. There's more to it, but this is already long enough :)

If you are interested in this solution and have any specific questions, please ask.

-Mike