4

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.

Andrew Walker
  • 40,984
  • 8
  • 62
  • 84
tezo
  • 41
  • 1
  • 1
  • 2
  • possible duplicate http://stackoverflow.com/questions/5984129/approaches-to-a-dynamic-pathfinding-algorithm – amit May 14 '11 at 16:44
  • 1
    i'm not if that user is considering moving obstacles or not – tezo May 14 '11 at 18:01
  • 1
    Are there any constraints on the motion of the agent or the obstacles? Velocity or acceleration constraints? Non-holonomic constraints – Andrew Walker Sep 09 '11 at 11:15

3 Answers3

7

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.

David T Wilcox
  • 91
  • 1
  • 4
  • 2
    The link for the paper is broken, this one is working: http://ijssst.info/Vol-05/No-1&2/TOMLINSON.pdf. The title of the paper is, The Long And Short Of Steering In Computer Games! – Ali May 24 '15 at 02:32
6

This article has great ideas about dynamic A*, which could be usuful to you

Anytime Dynamic A*: An Anytime, Replanning Algorithm Maxim Likhachev, Dave Ferguson† Geoff Gordon†, Anthony Stentz†, and Sebastian Thrun Also this article, Randomized Kinodynamic Motion Planning with Moving Obstacles by David Hsu Robert, Kindel Jean-Claude Latombe, Stephen Rock

They should be a good start.

edgarmtze
  • 24,683
  • 80
  • 235
  • 386
0

You can see a dynamic scene such a static scene that is regularly updated and where you have to recompute the pathfinding at each step/modification of the scene

Cf. regularly update the map with new positions of yours moving objets and recompute the pathfinding at each step

For moving obstacles/objects, add for exemple a marging of one or two "pixels" around moving obstacles/objects on your updated map for to easily handle the fact that they can move to a "random but very near" position during the time of the step

Better, mark the trajectories of the maximum of moving obstacles at the begining and only update on real time specials trajectories such as doors, stairs or moving objects for exemples

user3161997
  • 1
  • 1
  • 3