Pathfinding with Dynamic Obstacles

Question

I am implementing a simulation that requires me to have some pathfinding.
A* works fine for me when my environment does not change.
LPA* and D* Lite work fine for me when I encounter a static obstacle that is not in my original map.

However, how do I handle the situation when these obstacles are moving at a certain velocity?
Is there a variant of the LPA* or D* Lite algorithm that handles this?
OR Do i have to combine some form of steering behaviour with these algorithms?

Utimately in my simulation I want to have my 'agent' move from a start point to an end point in an environment in which there will be obstacles that move.

Answer 1

You might be better to consider breaking the problem into two parts than trying to solve it using a single algorithm.

Character movement has two components: high-level goal selection and pathfinding, and local steering. Pathfinding solves the problem of "I'm here, and I need to know how to get there". Local steering solves the problem of "I'm on my way there and someone just got in my way".

Keep your pathfinding as it is now. What you need to add is the ability for characters to detect obstacles as they are moving along that path and then adjust that local portion of the path to avoid the obstacle.

The book Artificial Intelligence for Games (author site: http://ai4g.com/ and Amazon: http://amzn.to/k9K62F) details several ways to combine pathfinding with collision avoidance. This paper also covers steering algorithms fairly well at a high level. A highly effective technique I've implemented is a steering pipeline, also known as cooperative arbitration.

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