   Practical path finding for RTS
  So, a couple days ago I decided to experiment a bit with path finding. I made a small demo with 2D grid based terrain, implemented basic A* and now have 2 questions to more experienced guys:1. Local Repair A*Is this something that is widely used? I found it mentioned in this doc but I can't see much more on this.My current approach is that a unit generates A* path, then follows it. When it becomes blocked (it can only be dynamically blocked by other unit), it waits a while. If it's still blocked it rebuilds new path to target. If there's no path to target it waits and so on...This works but rerunning A* seems expensive and I'd prefer not to do that if possible. In my case - most of the time - it's clear to see that just modifying a couple nodes in the path would solve the problem.The main question is: how to fix the path?2. Getting as close as possible to target.Currently if I order unit to go to designated target location, if that location can't be reached, my unit just waits. What I want here is, instead of waiting, it should move towards target "as far as possible".I've been thinking about couple different approaches how this could be solved but I'm not quite happy with them. I think my goal here is to move my unit to such position that if all dynamic blocking objects disappeared, my unit would find closest possible path to target.How do games typically decide where to actually go when target location can't be reached?Thanks in advance for any hints.   
Quote:1. Local Repair A*The standard approach is to set up unit priority list and a common path list (eg you "flock" units or set up a subordination system where a group of units has a commander that is responsible for the actual pathfinding). With many and differently sized units this can become a pretty complicated issue to handle.However, to address your question directly and assuming you don't have/need a unit subordination system, you would still benefit from setting up a priority system (based on whatever, eg the cost or experience of the unit) and could really benefit from rudimentary inter-unit communication. Then handle pathfinding as such:1) Find full path for unit A (let's say it's a higher priority unit)2) Find full path for unit B (lower priority unit)(Assume A and B's paths intersect)3) follow both units along the path as they move, seeking a small number of "tiles" in advance each interval (eg 500 or 1000 ms or when the unit reaches a new tile). Do temporal unit projection for each tile if you have cycles to spare. The number of tiles could be something like 5-10 depending on the size and the speed of the unit.4) If you can foresee a collision in the small look-ahead segment, apply some logic:  a) if B's path is being blocked by A and A is moving, slow B down and allow A to pass (assumes you do projection)  b) if A is not moving (it has a higher priority!), find a way around it from B's current position and rejoin the original path (which you do not need to modify) behind A  c) if you're A and the other unit, B, is not moving, order it to move out of the way (inter-unit communication)  d) if the other unit is blocking a bottlenck and is not under orders from the player to stay put and not move, ask it to move if possible; if moving is not possible, the units might be stuck and you need to repathQuote:2. Getting as close as possible to target.You need to decide whether you need to get physically as close to the target as possible, or logically. Physically means, you choose the node that has the shortest direct (Euclidean) distance to target. For a logically closest position, you'll need to trace through obstacles that can move in the future and find the tile that is currently blocked but would otherwise provide the shortest route to the target.IMO moving as close to the target without being able to reach it is bad AI in most cases - unless you're sending the unit to uncharted territory or provide it with a more generic command apart from Move (such as Attack, which would cause the unit to attack everything it sees), it would make more sense to just notify the player that the destination is unreachable. Just my preference.   ;  Thanks a lot, that was helpful.I'll try to implement unit priorities as well as inter-unit communication. Both sound reasonable to me.As for getting as close as possible to target, I think I meant more the logical distance rather than euclidean.   ;  Starcraft 2 is doing a lot of your 2nd option. You can see this most often if you have your base blocked in (e.g. with supply depots). If you send units via command or rally point to an destination OUTside your base, they will make it to the supply depots and then locate to a position that is nearest to where you sent them. They do NOT repath on the fly. Even if you remove the blocks while they are still moving, they do not repath. That says that they are actually pathing to their eventual (less preferable) location once they determined they couldn't get where they were going. It looks natural.   