19
\$\begingroup\$

I'm currently doing some pathfinding research and my simulation is the following: I have a 3d scene with a start and end point represented, I'm capable of creating navigational meshes, waypoints and polygons to aid with pathfinding.

I've tried an A* algorithm and some of its variants and they work perfectly. However, now I'm more interested in 'dynamic' pathfinding. For example, while finding a path from point A to point B, if a new obstacle suddenly appears, i want my algorithm to immediately be able to re-plan a path and not start searching from scratch again.

I've done some reading on the D* algorithm and wondering if this would be appropriate for what I need or would this seem like an overkill.

So my questions basically are: What algorithm would be best for Real Time Dynamic Pathfinding? OR what combination of techniques could I use instead?

\$\endgroup\$
3
  • \$\begingroup\$ I'm not sure what algorithm they use, so this isn't an answer, but I imagine this is what you're trying to emulate: youtube video \$\endgroup\$
    – House
    Commented May 11, 2011 at 17:01
  • \$\begingroup\$ What about extending A*? Extending what is stored in the nodes of it's open/closed sets by what You want and extending A* to consider it. \$\endgroup\$
    – user712092
    Commented Jul 30, 2011 at 6:11
  • \$\begingroup\$ I was looking for the answer as same as you and I found an article about HPA* and it is related to video game. I am still looking article and probably going to implement it. So far it does make sense to me to improve performance and it can be used in both static and dynamic environment. Here is article \$\endgroup\$
    – NelsonPunch
    Commented Jun 16, 2018 at 0:33

3 Answers 3

Reset to default
19
\$\begingroup\$

D* is quite involved -- I don't recommend trying to implement it. Even when projects that are well funded, and being developed by smart/experienced people, D* lite is used, because D* is such a pain to get right.

You may be interested in this presentation, which includes discussion of Left 4 Dead's pathfinding:

http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

One approach is to use a coarse level A* search to get a general path for an agent, and then to do a fine detail level A* search for an agent's local environment. This way, you can quickly recompute the course detail A* search if the terrain changes, and then quickly recompute the fine detail A* search for a small segment of the environment. This is not perfect. It works as long as your obstacles cannot block out multiple course detail graph nodes, which is fine for most games. This is the method I recommend if you have less than 100 agents.

If you want to support hundreds, or thousands of agents, then you can implement something like continuum crowds. See this research: http://grail.cs.washington.edu/projects/crowd-flows/ That discusses a purely CPU based method that can support thousands of actors in a dynamic environment.

If you want to support tens of thousands, or hundreds of thousands of agents, then you can implement something like continuum crowds, with GPU assistance. See here for the relevant research: https://a248.e.akamai.net/f/674/9206/0/www2.ati.com/misc/siggraph_asia_08/GPUCrowdSimulation_SLIDES.pdf

Here is a video demonstrating continuum crowds in action: http://www.youtube.com/watch?v=lGOvYyJ6r1c (Skip to 4:10 to see large dynamic obstacles like cars and stoplights affecting hundreds of people walking around a city.)

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the links. D* Lite does seem right from what i've been reading \$\endgroup\$
    – Andrei
    Commented May 12, 2011 at 15:27
9
\$\begingroup\$

Have you looked at simple steering behaviors?

http://www.red3d.com/cwr/steer/

You can use them to veer from your A* path in order to do local obstacle avoidance, and then steer back onto your path once you are done.

Its also fairly easy to combine multiple behaviors.

\$\endgroup\$
2
  • \$\begingroup\$ +1. I'm not sure why that got downvoted. Although this is simple, and possibly not the answer that the asker was looking for, I think it's on-topic and I found it useful :) \$\endgroup\$
    – Olhovsky
    Commented Jun 24, 2011 at 6:57
  • 1
    \$\begingroup\$ I have read and implemented this steering behaviour in our latest game. Now we are going to replace it again with other methods. I think it does not do work well together with precomuputed optimal paths. "Combination" of multiple behaviours usually yield in bad results. If you still plan to use it, don't attempt to steer and follow your path at the same time. Instead, switch to 100% steering and switch 100% back once you passed the obstacle. \$\endgroup\$
    – Imi
    Commented Feb 18, 2012 at 9:07
4
\$\begingroup\$

Since your post is in the "Game Development" part of stack exchange, here's what most game programmers would answer you: It's not about Real Time Dynamic Pathfinding, it's about Real Time Dynamic Path*following*!

Some edge cases where an edge on your navigation graph is totally obstructed would require the pathfinder to recompute another path, but most of the time you can simply steer your entities around the obstacles, doing position prediction and avoid in the right direction. For most games, it would be too heavyweight to have to predict over time the position of dynamic agents, especially since you can't predict accurately player actions or agent decisions.

So, my advice would be to start by implementing Steering Behaviors (http://red3d.com/cwr/steer/), handle cases where the path becomes impossible and then add a layer on top of it to handle edge cases that aren't handled by the two previous solutions.

Hope this helps

\$\endgroup\$
5
  • \$\begingroup\$ Uh, no. "Path following" is the same as path finding. There are many approaches that permit realtime following of thousands of agents when obstacles are changing, on a desktop PC. Certainly it is not too expensive to find a path for a single agent, when obstacles move around. Here is one such approach, of many: grail.cs.washington.edu/projects/crowd-flows GPU accellerated versions of continuum crowds exist. \$\endgroup\$
    – Olhovsky
    Commented May 12, 2011 at 3:52
  • \$\begingroup\$ I would have to disagree on this one. Any engine will treat path finding and path following as two distinct problems, where the first one is a graph search of the navigable area and the other one intends in searching the optimal movement vector within the local space. I've worked on such crowd simulation producing middleware used by AAA games without needing to rely on the GPU. Most implementations will use a flow field (the pathfinder) and steering to follow the flow and avoid other agents (the pathfollower). As my answer stated, this is a "game programmer" answer, not an academic answer. \$\endgroup\$
    – emartel
    Commented May 12, 2011 at 4:03
  • \$\begingroup\$ I know you don't need the GPU for contiuum crowds, which is why I linked a CPU based version. Your description of path following is still a pathfinding search, it is just a pathfinding search at a different detail level, on a different dataset. So what you really have is a course detail pathfinding pass, and a fine detail pathfinding pass. Ultimately you are trying to find the path that an actor should follow. Inventing new terms for this just confuses things. \$\endgroup\$
    – Olhovsky
    Commented May 12, 2011 at 4:07
  • 1
    \$\begingroup\$ I'm sorry but "path following" is not an invented term. Read industry produced documents and you'll see it used over and over again: link or link just to link a few. Unfortunately I can't link you to NDA protected documentations of engines / middlewares widely used in the industry. \$\endgroup\$
    – emartel
    Commented May 12, 2011 at 4:26
  • 1
    \$\begingroup\$ Your first link is the link that I gave in my answer btw. Okay fair enough, it might be fair to describe that type of path finding as path following. Ultimately they are both trying to find the path to follow, but I think that in this case I'm wrong, and we should call what we see in your second link as path following. E.g. the act of linking coarse path points together with cubic splies/biezer curves/insert-your-method-here. That said, I still strongly disagree that it is not feasible to implement path finding around dynamic obstacles, as your answer seems to suggest. \$\endgroup\$
    – Olhovsky
    Commented May 12, 2011 at 4:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .