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?