How should I replan A*?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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 :)

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

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.