StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>A* Search</strong></p> <p>Take a look at the <a href="http://en.wikipedia.org/wiki/A-star" rel="nofollow noreferrer">A*</a> pathfinding algorithm. It's essentially <strong>the standard</strong> approach for stuff like this.</p> <p>Amit Patel's write up on <strong><a href="http://theory.stanford.edu/~amitp/GameProgramming/" rel="nofollow noreferrer">pathfinding for games</a></strong> has a pretty good introduction to A* as well as popular variants of the algorithm. </p> <p>You'll find a C# implementation <a href="http://www.codeproject.com/KB/recipes/graphs_astar.aspx" rel="nofollow noreferrer">here</a>, and <a href="http://dotnetperls.com/pathfinding" rel="nofollow noreferrer">here</a></p> <p><strong>Dynamic A*</strong></p> <p>Let's say the terrain you'll be searching is not known ahead of time, but rather is discovered as the agent explores its environment. If your agent comes across a previously unknown obstacle, you could just update the agent's map of the terrain and then re-run A* to find a new path to the goal that routes around the obstruction. </p> <p>While a workable solution, rerunning the planning algorithm <strong>from scratch every time you find a new obstacle</strong> results in a sizable amount of redundant computation. For example, once you're around the obstacle, it might be that the most efficient route to the goal follows the one you were planning on taking before you discovered the obstacle. By just rerunning A*, you'll need to recompute this section of the previous path.</p> <p>You can avoid this by using <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.8257" rel="nofollow noreferrer">Dynamic A* (D*)</a>. Since it keeps track of previously computed paths, when the agent finds a new obstacle, the system only needs to compute new routes in the area around the obstacle. After that, it can just reuse existing paths.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload