What is it?
Path Planner implements the A* Search algorithm to find the best path for hexagonal tile maps. The user can run the algorithm step-wise, in slow motion, or immediately and can configure search parameters using the GUI.
What I did:
I had two main tasks ahead of me, I had to create a search graph to represent the tile-map and write and debug my search algorithm. I wrote my implementation with C++ 11 and had to achieve optimize my algorithm to reach benchmark requirements for speed and memory.
Challenges and Solutions:
The hardest part for me to implement was my search graph representation. I started by reading the tile-map and creating a Adjacency List (vector). I also mapped each tile to their adjacency list with an unordered map. I used an unordered map to reduce computation time from O(log n) to O(1) and used object references to reduce memory use. I also had an unordered visited map.
I started developing my searching algorithm with a simple Breath First Search, which I modified into a Greedy Best First Search using a priority queue and Uniform Cost Search using the euclidean distance formula as a heuristic and combined my work to create A* (which is optimal as long as the heuristic is admissible). Lessons Learned:
This project made me use just about everything I had learned about data structures and improving performance. I also heavily utilized C++ 11 standard library features such as chrono and priority queue.
|
|