A* is know to be accurate but somewhat slow.

possible fixes:

1. re-calc A* less often. re-calc when player moves 2 squares, instead of one, for example. pros: processing is cut in half. cons: unit path changes are 1/2 as responsive to changes in player location.

2. re-calc A* in a round robin fashion. when its time to re-calc A*, do it for one or a few units per frame unit all are updated. pros: only one or a few units update A* per frame, IE fewer A* re-calcs per frame on average. cons: units have to wait for their turn (A* update) to change path, you must re-calc enough units per frame to keep up with player movement in a sufficiently timely manner.

3. a combo of re-calc'ing less often, AND in a round robin fashion. pros: less A* re-calcs per frame on average. cons: less responsive to player movement.

4. abandoning A* for a fatser algo such as line-of-sight: relative heading = heading to player - unit's heading. limit relative heading to +/- unit's max turnrate. turn unit by relative heading. move unit. pros: runs really fast. cons: you lose collision avoidance, and must implement some sort of collision recovery such as "bang and turn". line-of-sight with bang and turn only works well for sparsely distributed obstacles, such as trees on a grassy plain, and doesn't work well for walls, and doesn't work at all for concave obsacles unless you add heuristics. fast heuristics can be used to implement pretty good collision avoidance, wall following, etc, but the better it gets, the more complex its rule set (and therefore code) becomes.

5. jump A* is a modified A* that works faster with large open areas. pros: a faster A*. cons: only helps in special cases.

6. limit the number of units that use A* to what the processor can deal with. this is a common design trade-off gamedevs must make. A* and rendering hi-rez skinned meshes are the two things that keep shooters from having lots of hostiles on screen at once. pros: units use A* and game runs fast enough. cons: the number of active hostiles must be low to prevent slowdowns. This is why an encounter in a shooter may have perhaps 6 hostiles vs 60 hostiles. They cant draw and pathfind 60 hostiles without slowdowns.

7. increase the size of a "square" used by A*. pros: bigger squares = fewer squares to test in A* = faster A*. cons: lower resolution, perhaps too low. for example: if you use 32x32 pix tiles for walls etc, A* squares of 64x64 pix won't work, you need 32 pix resolution accuracy, which means a square size no bigger than 32x32 pix..

8. some other method that hasn't occurred to me. maybe some else here has additional options to provide.

in my own quest for large numbers of active hostiles, i've gone to method 4 (line-of-sight with bang and turn collision recovery) for path finding, and rigid body animation for rendering. i can have ~125 hostiles active onscreen at once before i experience slowdowns. the line-of-sight path finding is so fast that pathfinding is no longer the bottleneck in AI. the bottleneck in AI is now target selection which requires iterating though the lists of active player and non-player entities.

fast accurate pathfinding is still one of the holy grails of game development. but line-of-sight + advanced heuristics and collision recovery can give A* a good run for its money.

The canonical solution to this involves steering behaviors - there are numerous references available for free on the web.

The simple pathfinding-based solution to your problem is to do incremental path searches. When the player is at Point A, find a path to Point A. When he has moved on to Point B, find the shortest path from Point A to Point B. By sampling the player position periodically instead of constantly, you smooth out the "zig-zag problem" and also save on computational cost. The search from A to B is likely a lot shorter than the search from the enemy's position to the target, as well.

There are plenty of other tricks you can try just on the pathfinding level. For example, for distant units, you can use hierarchical A* and just find a path to the player's current "zone" if your world geometry is well subdivided. You can use the ratio of (distance to player) vs (distance between current target point and player location) to decide when to re-path, i.e. don't bother searching for a new path if the destination is only a short distance from where you're already heading. Some minor modifications to your A* heuristic can give you "find me a path that gets me in range of the player" if your units can interact with the player over a reasonable distance.

Ultimately the best solution depends on a combination of factors: what your world geometry looks like, how fast units move, whether there are additional constraints on the path search such as minimum radius, and so on. Most of the solutions will involve something that looks like steering behaviors anyways, so that's a good tool to have on your belt.


Contrary to what some people believe, a good A* implementation is blazing fast and should have zero problems handling the situation you've described when used correctly. There do exist some modifications and adjustments to A* to make it faster in special cases, but again, that depends a lot on the world you're doing path searches in. The tricky part of A* is that it's very easy to write a correct but horrifically slow implementation, and amateurs and the inexperienced are often fooled into thinking that the algorithm is to blame.

Adding to ApochiPiQ's suggestion, you can obtain better incremental pathfinding at a higher cost by discarding the last part of the old path and extending the chaser's path from there, with increased opportunity to take shortcuts against the target's meanderings. At most, you can discard the whole previous plan, going back to non-incremental pathfinding. The amount of discarding can vary adaptively (e.g. according to how much of the last discarded path portion is reconstructed without change).