DStarLite Java Pathfinding

D* Lite is an incremental heuristic search algorithm that is used by agents (game ai, or robots) where the surrounding terrain is not completely known. The algorithm makes assumptions about the unknown terrain. D*Lite finds the shortest route from the start to the goal position, and as it encounters new obstacles these are taken into account and only part of the path is modified. Alternatively, pathfinding algorithms like A* typically have to replan the entire path when the environment changes.

D* Lite was developed by Sven Koenig in 2002 is based on the LPA* algorithm. I needed a suitable, computationally efficient algorithm for pathfinding in my current project and couldn’t find any java versions of the D*Lite algorithm that would have suited my purpose. My version is a standalone java version of D*Lite based on an existing C++ implementation.

This implementation is based on the original research paper http://idm-lab.org/bib/abstracts/Koen02e.html and also based on the c++ version located here: http://code.google.com/p/dstarlite/

For further reading check out the wikipedia article: Here
Sven Koenig’s personal page: Here
There is also an applet to help understand the algorithm: Here 

You can find my DStarLiteJava project on GitHub: Here

Advertisements

4 thoughts on “DStarLite Java Pathfinding

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s