For my final project, I generated a n by m maze for a helicopter to fly through. I used Prim's algorithm to generate the walls of the maze. To solve the maze, the user can swap between Depth First Search, Breath First Search, and A* Then I used Key Frame animations to animate the helicopter's flight plan.
I used Prim's minimum spanning trees algorithm to create a maze of n by m dimensions. First I created a graph. To do this I linked together a 2D array of cells such that each cell had a top, right, bottom, and left cell. The I defined the starting and ending location of the maze. The starting location was always halfway down the left side and the ending location was always half way down the right. The starting and ending locations could have been anywhere, but I decided to fix them so I could write a good heuristic later for my path finding.
Next I randomized all of the edge weights of the graph. The randomized edge weights will allow Prim's algorithm to make a maze for us. I decided to seed the random number with a varible (as opposed to seeding it with the time function) so that I could increment up and down and force the mazes to be the same each time I ran the program. Once the weights were set I ran Prim's algorithm and it generated the maze by traversing the nodes and setting some of them to floors and the rest to walls.
Prim's algorithm only connects to each node of the graph once. Because of this, a maze created using this algorithm will not have any loops in it. There would only be one path from the beginning to the end. After I ran Prim's algorithm, I randomly set some of the remaining walls to floors in order to generate multiple paths.
The picture of the left is the maze before I added any holes to it. The yellow tiles are the starting and ending nodes, the green tiles are traversed via Prim's Algorithm, and the purple tiles are set after.
For pathfinding, I traversed from the starting node to the ending node using three separate graph search algorihtms, Depth First Search, Breadth First Search, and A*. These search algorithms have the same structure but use a different data type in their operation. DFS uses a stack, BFS uses a queue, and A* uses a priority queue. Once I coded up one of them, programming the other two was fairly simple.
The pictures above depict the different search algorithms. The green nodes are unsearched nodes (The more green nodes there are the faster the algorithm is, mostly). The blue tiles are the traversed nodes. The lighter the tile the earlier it is traversed. The first node is always the lightest, because it is the first not seen, while the last node is always the darkest. A* search typically traces far less nodes than DFS or BFS.
But A* is not always better than DFS or BFS. It depends on how good the heuristic is. I uses a simple manhattan distance heuristic for the example above, but in the example below I uses a terrible heuristic that tries to search the end node last.
All of the mazes I have shown are 19x19, but I can generate any size maze (within reason). Here are two videos of 75x75 mazes.
OpenGL
Cute Helicopter give to us in assignment 1
C - Toggle color for floor tiles
S - Increment seed and regenerate maze
X - Decrement seed and regenerate maze
D - Set DFS as pathfinding algorithm
B - Set BFS as pathfinding algorithm
A - Set A* with manhattan heuristic as pathfinding algorithm
Q - Set A* with bad heuristic as pathfinding algorithm
Space - Pause/Play