Preface

     Pathfinding is fairly essential for any game with map traversal. The most standard algorithm for pathfinding, A*, shines when used on a static map. However, for problems where the map for pathfinding changes - for instance, games where the user can change the environment, games where cars have to maneuver around each other, or even real-life AI pathfinding in self-driving cars - these are where A* struggles. A* cannot handle changes in its pathfinding grid, and to find a way around obstacles would require running A* again. This can be rather slow, as every time A* runs, it does not retain any of the information from other runs.

Part I: Learning

     There have been many algorithms developed as a more efficient solution to the problem of maps changing on the fly. Dynamic A*, otherwise known as D* developed by Anthony Stentz in 1994, first finds a path similar to A*. As the path is obstructed, all points affected are placed back onto the open list and reevaluated based on whether their cost was raised or lowered. Nodes continue to be reevaluated until nodes of non-modified costs are hit. Then, the new path is calculated. Although this is significantly faster than re-calling A*, the D* algorithm is much more complicated to implement and has a reputation for being extremely complex.

     Other options and improvements are out there - as time goes on, more algorithms are developed that further optimize continuous-time pathfinding. LPA* and D*-Lite are among the most well-known for simple pathfinding recalculations.

     Whereas Dijkstra's and A* pathfinding algorithms have been around for nearly 70 and 50 years respectively and thus have thorough and extensive applications, documentation, and academic papers written on them, D* and improved algorithms based on it are significantly newer, and thus have significantly less beginner-friendly resources. According to the research of these Stack Exchange forum users, D*-Lite, the most recent permutation of D* for simple and accurate continuous pathfinding on a grid, was only invented in 2002. As a very visual learner, I was able to find a small handful of resources, including incomplete pseudocode from the D* wikipedia article, and two videos which demonstrated D*/D*-Lite running visually.

A quick and brief visual look at D* in action with a handy step-through visualizer.

A beginner-friendly primer on D*-Lite, brief history, and its advantages over A*.

     With research under my belt and a general understanding of how D* worked, I started to implement D* within my base Pathfinding project. My code was mostly based on the pseudocode found on the D* Wikipedia article, pictured below.

Pseudocode taken from the D* Wikipedia article (https://en.wikipedia.org/wiki/D*#Pseudocode).

     My initial implementation of D* successfully found a path just like A*, but once I modified the map it severely spiked my memory usage. Although it was successful in finding a path, it certainly wasn't showing any advantages over A* in my implementation's broken state as it was unable to recalculate a path after the map was updated.  I suspect my implementation of the isRaise function wasn’t quite accurate due to my implementations of calculateCostVia() and setNextPointAndUpdateCost(). Unfortunately, this pseudocode did not contain definitions for those two functions, and at this point in my programming experience I was unable to decipher the 1994 papers by Sven Koenig and Anthony Stentz, who wrote on D*-Lite and D* respectively. These papers can be found below:

[Sven Koenig]

[Anthony Stentz]

     Anyway, to put it lightly: My work towards D* was not working.

Look at that memory spike up!

     As seen in the gif above, the moment I added a new blocked node, all the units stopped moving. To the right is the diagnostic tools, showing a huge spike in memory. After much unfruitful fiddling, I backtracked.

Part II: Bargaining

     Since I couldn’t get the D* algorithm to work, I ended up trying the aforementioned less-efficient solution: First, run A* to find a path, and whenever the map changes, stop the current calculation and put in a new request. Luckily, this wasn’t too big of a change due to my work in the previous assignment: A “pooling” pathfinding queue that ran the pathfinding algorithm over multiple frames, and only ran the algorithm when the pathfinder was not calculating already. This was great to reduce screen hangs and stabilized FPS since there wasn’t a huge pause when the A* algorithm was running every single request before continuing to the next frame.

Pathfinding for 100 units using a pathfinding queue and a path cache.

     This was also great as it didn’t create an incredible spike in memory from even requesting 100 pathfinding requests, as they didn’t all run at the same time. Additionally, even running 100 pathfinding requests was fairly fast after a few paths were found, due to my implementation of a path cache, where if a portion of a path was already found, the units would use the cached path instead of continuing calculations. Efficient!

     With this in mind, I tried to press on to make a successful continuous pathfinding solution. I knew it wouldn’t be as optimal as D*, LPA*, or D*, but I wanted to make it work, albeit not as efficiently as I initially researched for.

     …however, my efforts were still unfruitful. In the interest of time, I tried my best to continue modifications, and I got to the point where the pathfinder pool could successfully stop the steering and stopped the current A* pathfinder’s calculations, but upon asking for a new request with the modified grid it couldn’t always find a new path and often left the unit stuck where it was.

Part III: Acceptance

     Unfortunately, due to my limited amount of time for this research project, I was unable to create a functioning tech demo - for now! 

     I did learn a lot about D* and the concepts behind continuous pathfinding. A bit too late into the game, I found out that for the most part, the D* implementation is obsolete due to its extreme complexity, and that LPA* and D*-Lite are widely regarded as easier to implement and more efficient. Many forums I surfed even go so far as to say D* isn’t worth trying, and that if I am to look into continuous pathfinding, that trying A*, then LPA*, then D*-Lite is the way to go.

     Despite my lack of a working prototype, I have a solid basis on which to continue my learning and give continuous pathfinding another try, but for today this concludes this blog post. Thank you for following my adventures in the land of continuous pathfinding!

________________________________________________________________________

References:

D* Wikipedia Article: https://en.wikipedia.org/wiki/D*#Pseudocode 

D* Visualization: https://www.youtube.com/watch?v=e_7bSKXHvOI 

D*-Lite vs A*: https://www.youtube.com/watch?v=skK-3UfcXW0

Forum Post on History of Continuous Pathfinding: https://cstheory.stackexchange.com/questions/11855/how-do-the-state-of-the-art-pathfinding-algorithms-for-changing-graphs-d-d-l 

Codebase is a mixture of a lightweight game engine base written by Prof. Dean Lawson for class use at Champlain College, references to Artificial Intelligence for Games, 2nd Edition by Ian Millington, and my own code.