Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
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 –  Byte56 May 11 '11 at 17:01
    
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. –  user712092 Jul 30 '11 at 6:11
add comment

3 Answers

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.)

share|improve this answer
    
Thanks for the links. D* Lite does seem right from what i've been reading –  Andrei May 12 '11 at 15:27
add comment

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.

share|improve this answer
    
+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 :) –  Olhovsky Jun 24 '11 at 6:57
    
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. –  Imi Feb 18 '12 at 9:07
add comment

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

share|improve this answer
    
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. –  Olhovsky May 12 '11 at 3:52
    
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. –  emartel May 12 '11 at 4:03
    
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. –  Olhovsky May 12 '11 at 4:07
1  
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. –  emartel May 12 '11 at 4:26
1  
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. –  Olhovsky May 12 '11 at 4:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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