Find your way with dynamic obstacles

Question

I use a simulation that requires me to have some way.
A * works great for me when my environment doesn't change.
LPA * and D * Lite work great for me when I encounter a static obstacle that is not in my original map.

However, how can I deal with a situation where these obstacles move at a certain speed?
Is there a variant of the LPA * or D * Lite algorithm that handles this?
OR Do I need to combine some form of steering behavior with these algorithms?

In my simulation, I want my “agent” to move from a start point to an end point in an environment in which obstacles will arise.

Answer 1

This article has some great ideas about dynamic A * that might be useful to you.

Anytime Dynamic A *: anytime replacement algorithm Maxim Likhachev, Dave Ferguson † Jeff Gordon †, Anthony Stents † and Sebastian Tron Also this article , Randomized kinodynamic planning of moving with moving obstacles David Hugh Robert, Kindel Jean-Claude Lathomb, Stephen Rock

They should be a good start.

Answer 2

Perhaps you better think about breaking the problem into two than trying to solve it using one algorithm.

A character’s movement consists of two components: selecting high-level goals and finding a path, as well as local management. Pathfinding solves the problem "I'm here and I need to know how to get there." Local steering solves the problem of "I am there and someone was just bothering me."

Save your way as you do now. What needs to be added is the ability of the characters to detect obstacles when moving along this path, and then adjust this local part of the path to avoid the obstacle.

The book "Artificial Intelligence for Games" (authoring site: http://ai4g.com/ and Amazon: http://amzn.to/k9K62F ) contains several ways to combine path searches with collision avoidance. This paper also describes high-level steering algorithms well. The highly effective method that I implemented is the steering pipeline, also known as cooperative arbitration.

Any complete answer will depend on your worldwide representation and other factors specific to your implementation, but I hope this helps.