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.

  • \$\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, 2017 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, 2017 at 0:34
  • \$\begingroup\$ Also, the A* question is from 2010; it's had years to accumulate those votes. \$\endgroup\$
    – Pikalek
    May 27, 2017 at 3:18

1 Answer 1


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.


You must log in to answer this question.

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