These algorithms can be executed to look instantaneous by removing the wait times, but I wanted to visualize them because I thought it'd look cool. The algorithm finds and retraces the path by using an array that is filled with the most current polled keys so when it reaches, it will have have all of the correct keys. The explored paths are labeled in white and once the end is found, it is retraced to show the path. That's my understanding of the algorithm, and it kind of shows why it's not the best to use in this case, because the cost to go from one path to the other is always one and it may go on a bunch of unnecessary paths simply because a route hasn't been explored yet, but I still thought it was fun to implement. The way Dijkstra's algorithm works is that it pulls out the key value pair with the shortest path (in this case that would be the value) and repeats the steps again and again until the end is found. the queue stores the position of the node as the key and the distance from the start as the value. It begins at the start position and adds neighboring paths to an indexed priority queue. It certainly is not the best algorithm to use in this case because it's being used in a maze (which is an unweighted graph, so a better algorithm would be a breadth-first search) but I decided to implement it because I had been recently learning about it. I decided to make the visited walls red.įor solving the maze I used an algorithm called Dijkstra's algorithm. This is done by selecting a wall, then adding the surrounding walls to a stack and then visiting one of those walls, and this repeats over and over until there are no more walls to visit/destroy. I then did something called a depth-first search where I go through every wall in the maze, and removed it. Thank you! For generating the maze I first generated an N x N grid by generating a part on every square on the baseplate.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |