The problem that I tried to solve for this final project was the Maze Runner. I was given an image of a maze. With this image, I had to convert it into some usable data structure and use a path-searching algorithm (BFS, DFS, or A*) in order to find the shortest path from the entrance of the maze to the exit. This particular problem comes in two parts: converting the image into a data structure and applying one of the path-searching algorithms to this data structure.

Let’s start with the first part: converting the image. I was given two images of a maze, one of which was smaller than the other. When looking at both images of the maze, I realized that each maze could be drawn as a series of squares with some width and some height. Each square had some part of the maze in it, whether it be a vertical part, a horizontal part, a dead end, and so on. If each maze could be pictured in this way, then a given maze could be thought of as a node-connected graph with a number of nodes equal to the product of the maze’s width and height.

With this number of nodes in mind, I could now start plotting nodes onto a graph. To do this, I loaded the image using pyplot. From there, I recorded the coordinates of each node using numpy. To record the coordinates, I used the ginput library to allow myself to click on two points on the maze and record them, repeating this process until there were a number of nodes equal to the area of the maze. Once I had these nodes, I wrote them into a text file (see Figures 2 & 4). Then, I utilized the graph visualizer program that was used in Homework 2 in order to visualize the node-connected graph representing the maze (see Figures 1 & 3). Initially, I ran into the problem of not being able to properly connect certain nodes to each other. Each node has a label starting at ‘1’ and moving up until it reaches the number of nodes in the maze. However, I could only increment the label by one for each time I clicked on the image, so if I needed to connect two non-sequential nodes, say node 1 and node 2, I had difficulty doing so. The rudimentary solution I found to this problem, however, was simply keeping track of the names of these non-sequential nodes and connecting them later on in my program. It took some time, but it got the job done. If I had to redo this project, however, the first thing I would do is look into how I can automatically find these nodes and not have to manually keep track of them myself.

Once I converted the image into a usable data structure, I moved on to the second part of the problem: finding the shortest path between the start and end of the maze. I decided to utilize the breadth-first search algorithm. Not only had I already written the code for BFS, but I also wrote code for DFS and A* for the second homework. While I knew that I could copy the code for any of these algorithms, I found BFS to be the simplest to understand and fix if need be, so I decided to use that algorithm. However, by copying this code over, many of the problems I ran into in homework 2 came up in this assignment too. For example, the BFS function in my code is a recursive function, so it calls itself whenever it does not find the goal node (the end of the maze). When it does this, it carries over the list of nodes in the frontier. However, sometimes it would not carry over these nodes, and I could not figure out why this was for the longest time. Upon careful inspection, I realized that there were a couple of typos in my code that were the cause of everything screwing up. Once these bugs were squashed out, the algorithm worked! As it makes it way across the graph, it prints out the node it is currently at and any new children that it can add to the frontier. The nodes are explored in the order they were found in. If a node does not have any new children, the program prints this out. If any of the nodes in the frontier are the goal node, it prints this node and says that the end has been found.