# How should I replan A*?

I've got a pathfinding boss enemy that seeks the player using the A* algorithm. It's a pretty complex environment, and I'm doing it in Flash, so the search can get a bit slow when it's searching over long distances. If the player was stationary, I could just search once, but at the moment I'm searching every frame. This takes long enough that my framerate is suffering.

What's the usual solution to this? Is there a way to "replan" A* without redoing the entire search? Should I just search a little less often (every half-second or second) and accept that there will be a little inaccuracy in the path?

-

## 7 Answers

You don't have to search the entire path in one frame, I have done this by giving a limit on the search loop, the AI will then start to follow the little information it has, and the next frame I'll search some more, it might take 3 frames until the path is found. It can look quite convincing to, as it looks like the AI is actually searching.

-
+1. This is also what Mat Buckland describes in his A.I book. He calls it "Time sliced path planning" (books.google.ch/…). Good stuff. –  bummzack Feb 12 '11 at 10:15

I created a game for a 48 game competition where an A* character follows the player around a level. Because my A* implementation was slow (it couldn't run every frame) I put the interval on a three second delay. This had the unintended result of allowing the player to "trick" the AI for a few moments. It actually made the game more fun.

Later on, I improved the performance of the A* implementation and tried running it on every frame. The game stopped being fun because the enemy would always perfectly seek the player.

That was unexpected and a good learning experience.

-
That's a good point. I remember reading about path finding in pac-man where they deliberately used an imperfect algorithm, allowing the player to outsmart the ghosts. Each ghost had a slightly different imperfection giving them more character. The take away here is that in games, fun > all else. –  Nick Van Brunt Mar 3 '11 at 18:46

Unless you absolutely want (or need) to use A*, you could also take a look into Steering Behaviours. As there is no complete path planning per frame involved, it should be a lot lighter on the processing.

-
I use Steering Behaviors (specifically Seek) in cases where there are no obstacles between the agent and its target. Unfortunately, my environment contains things like twisting corridors, where a smarter solution is necessary. –  Gregory Avery-Weir Feb 12 '11 at 16:06

If it's a static environment then you can precalculate all-pairs shortest path.

-
If it's a small static environment. –  user744 Feb 12 '11 at 13:57
Depends on platform and memory available. –  Nate Feb 12 '11 at 16:53
@Joe, @Nate, true. –  Peter Taylor Feb 12 '11 at 19:02

Not really answering your exact question, but... if you're willing to "cheat", you can make the player leave "breadcrumbs" and have the boss follow them. If the breadcrumbs path crosses itself, follow the most recent one (this makes the boss avoid loops and other paths that may be too long, not to mention not following the exact path of the player)

This would work fine if the boss is some kind of animal with a good sense of smell. This would work a lot like following the scent of the player :)

-

You could use proximity detection to run the algorithm every few frames if the distance is very great (because in most cases if the distance is large, the target path wont change drastically from frame-to-frame). For example:

``````      Distance > 100, run A* every 2 seconds
100 > Distance >  50, run A* every 1 second
50  > Distance >  25, run A* every 10 frames
25  > Distance <  25, run A* every frame
``````

This is assuming that there is a distance where running A* every frame has performance that is still acceptable. In short, I'd go for your second option. Especially if what you have is working, I'd avoid reimplementing something else if I can just scale back what is working well. The bottom line is that you'll have to try it out to see if it works for your game.

-

Your case is pretty much what HPA* was invented to address. If it seems like overkill, though, I would tend to think that pathfinding every half second or so should work out pretty well.

-