I'm just starting to learn about path-finding and have been looking into the A* algorithm and my main concern is that it all of the examples I have seen show static obstacles that it computes around.
If I have moving obstacles, say other characters for example, moving around as well that the character must find their way around, I'm assuming I'll have to run the algorithm each frame, but I'm worried that will become rather expensive for the hardware to process each frame for each moving actor.
So is A* still efficient enough to use whenever the obstacles are moving too, or is there another method of path-finding that handles moving obstacles more eloquently?
Answer
There are multiple algorithms that are much faster than A* when you need to recalculate a path with moving obstacles. See here under "Simple Recalculations".
However, you're not likely going to find an off-the-shelf solution for any of them, so in 99% of cases they're overkill for a game. Your time would be better-spent using an existing, fully-optimized A* solution, and using the common existing tricks for speeding up pathfinding in games:
- Only recalculating the best path in infrequent intervals
- Sharing best-paths among multiple units (example)
- Creating a hierarchical graph so you only need to recalculate part of the path
etc. You can find more info about these tricks and more all over this site, or on Amit's A* pages
No comments:
Post a Comment