If never used pathfinding in any of my projects and I felt it was time to see what pathfinding is all about so I can use this for future projects.
I started with looking through through the different pathfinding algorithms out there, this
website visualizes several options for pathfinding. And helps getting a better understanding of how different solutions function.
I have chosen to implement the A* algorithm a variation on the Dijkstra algorithm. I have chosen this algorithm because it the best for finding the shortest path fast in a static environment.
There are a ton of good articles and videos that explain how A* works and even step by step guides how to implement it. So I'm not going to do that as well, but I wil recommend a few I found useful.
Sebastian Lague has a really good video series that gives a step by step example of A* pathfinding including some optimization and things like weights with all the the project material available on GitHub. You can find the videos
here.
Mike Clift has a article that also gives a step by step explanation how A* works with code snippets and good visualization of what is going one. You can find his post
here.
Jasper Flick has a cool series on making a terrain with hexagons tiles. Part 16 is a cool tutorial on how to navigate a grid of hexagons with A*. You can find this post
here.
Instead i'll show of my implementation that visualizes how A* works.
Use
Q to set a start
W to set a finish and
E to set walls. When you're ready to execute A* press
Space.
You can play around with a larger version
here
After playing around with A* I gained a intrest in trying out D*lite, which uses the same principles as D* with is a improvement on A*. The research paper is a great resource witch kan be found
here. But can be a bit technical. My best bet for quickly implementing D*lite was to look at a java implementation of D*lite. This helpt me a lot in understanding how D*lite functions. Regretfully I couldn't fint more time to finish this implementation and probably continue working on it in the future.
Clift M. (2014)
A Simple A* Path-Finding Example in C# [online] Available at:
http://blog.two-cats.com/2014/06/a-star-example/
Koenig S, Likhachev M. (2002)
D*Lite [online] Available at:
http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf