Uses the A* algorithm in order to find the best path through a 2D maze.
This algorithm works by finding the start and then moving to the next non-visited closest node with the lowest distance already traveled + heuristic. I used the Manhattan distance to the end as the heuristic since it is much faster, and we are only moving in 4 directions. If a neighboring node is a bomb, it adds 20 to the priority, while if it is gold it subtracts 4 from priority. This incentivizes A* to dodge bombs and pick up gold in the most efficient way possible, while also keeping with the heuristic. It has a runtime complexity of about O(n log(n)) in the worst case because if you end up not needing the heuristic, it will end up being Dijkstra and search the whole map for the best path. The space complexity is O(n^2), because I needed to store all the priorities for the matrix in a separate matrix and the parent’s path in a separate matrix to make it faster. Unfortunately, since this is a greedy algorithm, it may not find the best answer every time. I optimized my search to use the speed of A* and still go for gold when it is optimal. I spent hours researching the best way to implement this algorithm.
I used this algorithm because I wanted to find a good enough answer much faster than any other algorithm and it allows me to easily implement the gold and bomb systems using the priority queue. I also considered the following alternative: • Dijkstra: this algorithm works the exact same, except there is no heuristic. Instead, it looks at all possible paths. This algorithm is much slower because of this, but it also has a much better chance of finding the right answer.