Take the 2-minute tour ×

There are links to some papers on D* here, but they're a bit too mathematical for me. Is there any information on D*/D* Lite more geared towards beginners?

share|improve this question
D* isn't a beginner sort of algorithm, and it's use case is fairly narrow. are you sure you don't just need A* for your application? –  Donnie May 24 '10 at 22:26
I need a bot to navigate around walls to a goal. The player can place obstacles in the bot's way and the bot should be able to be able to find a new path in real-time. D* is good for changing environments like this, right? –  tehalynn May 24 '10 at 23:09
I agree completely. I've implemented the A* many times and on a wide variety of graphs and I've been wanting to implement D* (lite) for some time too. There are two or three whitepapers on the net but I have yet to manage getting something useful out of those unreadable math descriptions. –  Trillian Jul 27 '10 at 13:27
Once you've implemented it, please write the tutorial that you were looking for :) Personally, I'd love to see it! –  Merlyn Morgan-Graham Aug 2 '10 at 21:46
This should be highly relevant to you: cstheory.stackexchange.com/questions/11855 –  BlueRaja - Danny Pflughoeft Jun 28 '12 at 15:53
add comment

4 Answers

Wikipedia has an article on the topic: http://en.wikipedia.org/wiki/D*

Also a D* Lite implementation in C is available from Sven Koenig's page: http://idm-lab.org/code/dstarlite.tar However I find the impenetrable math much easier to read than the C source code ;-)

Another implementation of D* Lite (in C++) is available here: http://code.google.com/p/dstarlite/

share|improve this answer
+1 I haven't searched myself, but judging from the answers here, and reading the wiki article, this seems to be the closest thing available to what the OP wants. –  Merlyn Morgan-Graham Aug 2 '10 at 21:51
add comment

Well if pseudo code is hard for you (you don't have to read theorems and proofs - pseudo code is pretty straight forward if you know standard algorhitms) and you complain against published C and C++ code then I guess you'll need to go doing something else :-)

Seriously, don't expect that someone can teach you a top grade algorithm in a few web paragraphs. Take a pen and paper and write, draw and follow on paper what's going on. You may have to read something twice and google one or two references to get to know a few concepts around it, and there's no need to dig in the theorems and proofs at all - unless you hope to prove the author wrong that is :-))

Can't go forward without some more math - c'est la vie. Imagine that you asked someone to teach you what on earth is matrix inversion but you don't know what are vectors. No one could help you till you learned enough of the math context first.

share|improve this answer
There are so many clear explanations of A* on the net that I'm really surprised that there are none for D*. I know D* is a step over A* in terms of complexity, but I expected someone would write an explanation for the layman. Yeah, this is laziness, I know, and as there are no suitable answers I'll dive in the papers again. I just feel a math-full whitepaper isn't the best way to develop an intuitive understanding of an algorithm. –  Trillian Aug 2 '10 at 14:31
There's a step between asking about matrix inversions when you don't know about vectors and asking about D* when you know about A*. –  zneak Aug 2 '10 at 21:42
add comment

Having said that, why not add a few more papers, yes they have math as well :-) but I'll try to get some more recent stuff. People usually get better at explaining their own work as the time goes by, so the focus is on Stentz, Likhachev and Koenig

share|improve this answer
Thanks for the more practical answer. I hadn't found out most of those papers. I might just award this answer the bounty to prevent your other answer to get it automatically. After all, your other answer is more of an opinion than an answer, even if it motivated me to dive back in the whitepapers, if only to prove I can do so :) –  Trillian Aug 2 '10 at 14:43
You'll need to be on academic or corp net that is Springer "subscriber" if you want PDF-s the easy way. Some authors publish slightly changed papers with other journals, some don't. That's why my search heuristics is to try to follow authors first and Springer site is the easy way to get fresh info fast. The first one might even be worth buying if you are into that stuff not just for the algo but for reading a Stantz paper stating that his new algo is based on D* Lite - very hard thing for a researcher to admit even implicitly. –  ZXX Aug 2 '10 at 23:35
add comment

I came up with this
http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf and this

I hope those link will help you :)
Edit: After posting I noticed that the links I gave you were in the link you pointed out as well. Nevertheless I found those directly on Google. Anyway I've looked them up a bit and they don't seem to be that complicated. If you know A* well you should manage to understand D* as well.
From experience I can tell you that A* can be used for what you want as well.

share|improve this answer
Yeah, those are the whitepapers I've found myself by googling. The explanations are in impenetrable maths jargon and the pseudocode isn't much better. As for using A*, I have a highly optimized implementation in my RTS game, but it's not fast enough such a highly dynamic world. –  Trillian Jul 27 '10 at 15:48
add comment

Your Answer


