2
\$\begingroup\$

I would like to understand on a fundamental level the way in which D* pathfinding works. Any code or psuedo-code implementations as well as visualizations would be helpful.

\$\endgroup\$
  • \$\begingroup\$ Why is this getting downvoted? The Wikipedia page offers a broad explanation that isn't very helpful, and the counterpart question seems to be doing quite well: gamedev.stackexchange.com/questions/15 \$\endgroup\$ – Dave May 26 '17 at 23:57
  • 2
    \$\begingroup\$ We don't need to get too hung up on votes. All that a single downvote means is that one person thought the question "does not show research effort, is unclear, or not useful." That's not the end of the world. If you want to address that feedback, you could edit your question to show research effort (explaining what you know about the algorithm) or add more clarity (by describing what specific aspects of the algorithm you need help understanding). \$\endgroup\$ – DMGregory May 27 '17 at 0:34
  • \$\begingroup\$ Also, the A* question is from 2010; it's had years to accumulate those votes. \$\endgroup\$ – Pikalek May 27 '17 at 3:18
2
\$\begingroup\$

D* isn't used anymore. Its replacement, called D*-lite, does the same thing as D*, but is faster and easier to implement.

D*-lite is based on an algorithm called LPA* (aka. Incremental A*). D*-lite is trivial to understand once you understand LPA*, but unfortunately LPA* is less trivial to understand.

Unfortunately I'm not aware of any good "layman" explanation online. Your best bet is to just read the paper introducing LPA*. After that the paper on D*-lite should be an easy read. Good luck!


Also, since this is a Game Dev site: it's unlikely you truly need to implement D*-lite to get acceptable performance for a game. D*-lite is mostly for traversing a single unit through a very large, complicated, changing graph, whereas most games require navigating many units through 2D/3D grids that are fairly open and usually static.

If you explain your actual problem better (in another question) we can help you determine a better solution.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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