30
\$\begingroup\$

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?

\$\endgroup\$
27
\$\begingroup\$

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

\$\endgroup\$
10
\$\begingroup\$

Yes. A* is still the way to go in almost every case. It's your node cost calculation that becomes dynamic and therefore more complex to calculate and track.

If you already know where the moving obstacles will be in the future your A* can take the temporality of obstacles into account in the cost function.

E.g.: This node will be reached in 4 ticks, occupied from tick #3 until tick #6, so travel cost on this node is 6 - 4 = +2 ticks. That may still be the best path.

The travelling direction of the obstacle also has to be taken into account.

If you don't know in advance then you can assume no obstacles and recalculate the path when obstacles are reached but you will need to do something about deadlocks and livelocks. (The same applies if you can predict where obstacles will be but that in itself is a type of deadlock/livelock avoidance and that can be good enough for your purpose.)

A deadlock is when both wait for the other to move and none move.

A livelock is when both (or more <- this is important to consider) move to avoid the other in the same direction and end up going back and forth with no progress.

Solving livelocks can become very complex and that depends entirely on your game's collision rules and mechanics (e.g.: should they fight and destroy the obstacle?).

It often comes back to having your moving objects schedule node/path reservations (don't forget cancellations when they change path or die) so other moving objects can plan ahead.

Once you have this information you can also plan interceptions.

\$\endgroup\$
  • 19
    \$\begingroup\$ Oh my god, "livelock" - you've described that awful left-right dodge thing I end up having to do in hallways all the time. \$\endgroup\$ – Ethan The Brave Oct 27 '17 at 18:17
  • 2
    \$\begingroup\$ A simple live/deadlock solution is to randomly pick between the available options (e.g. 50% chance to not move and a 50% chance to move left). As long as each actor chooses randomly, there's a non-zero chance that the lock will be resolved. \$\endgroup\$ – Draco18s no longer trusts SE Oct 28 '17 at 20:13
  • \$\begingroup\$ @Draco18s And exponentially increase the size of your flailing back and forth until one gives way (I may have just described how Ethernet collisions are resolved!) \$\endgroup\$ – Cort Ammon - Reinstate Monica Oct 29 '17 at 4:40
  • \$\begingroup\$ I suppose they could play Rock Paper Scissors or a friendly game of Petri Dish Prisoner's Dilemma instead. ;P \$\endgroup\$ – Draco18s no longer trusts SE Oct 29 '17 at 5:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.