An Age of Empires developer explained how they handled the problem of group movement, if you want to look at it: Coordinated Unit Movement : http://gamecareerguide.com/features/19990122/movement_01.htm Implementing Coordinated Movement : http://gamecareerguide.com/features/199901...ementing_01.htm According to litterature there are two main ways to solve this. The first is named "Steering behaviors", which is what you want here, and the other one is about crowd simulations, wich is out of scope and still an area of research. Note that it is also possible to cheat and allow units to cross each other. Steering Behaviors For Autonomous Characters : http://www.red3d.com/cwr/steer/gdc99/ If the new short-range path fails (rare), then you can always ask for a new path. Concerning CPU cycles, it's possible to give the pathfinding code a budget each frame, and ask him to continue the computations the next frame if it's not finished. There are a lot of possible optimisations too but I guess they should only be performed if pathfinding takes too much time.