The Million-Pixel Maze

The other day, my roommate found this picture, a 10001 pixel by 10001 pixel maze, with black pixels being the walls, and the white pixels representing traversable floor. Presumably, it was designed to be incredibly difficult to solve, at least my normal human means. However, once he showed the picture to me, I thought it was be an interesting problem to solve.
My first reaction was to use C++, since it has an advantage in terms of memory management. However, after googling around for about a while, the image processing portion of the problem was getting to be a real pain in C++. So, after using the File and ImageIO classes in Java, I was easily able to read in the bitmap to a 2D array.
For the solution to the problem, I have a 2D array of bytes and a LinkedList, with one unique class structure, the MazeNode class, which holds a parent MazeNode and x and y coordinates. The 2D array of bytes holds the image data, with a 0 for an open spot, a 1 for a closed spot, and a 2 for a spot that has already been traversed.
The LinkedList essentially works as a queue. While the LinkedList isn’t empty, a MazeNode is popped off of the list which correlates to a pixel on the map. If the coordinates equal the end coordinates of the maze, then the MazeNode is returned. The program then marks this spot in the 2D array as a 2, then checks the pixel directly upwards, downwards, and to the left or right of the pixel to see if there are any open spots that haven’t been traversed yet. If there are, then a new MazeNode is created in these coordinates, with the current MazeNode as the parent, and it is then added to the LinkedList. We then grab the next MazeNode, and the cycle continues. In this way, we essentially do a breadth-first search of the maze, and the length of the chain of MazeNodes returned is the length of the solution of the array. After a solution is found, I modify the ImageData orginally read in to trace the solution path, then output the maze with the solution traced onto it.
It takes about 20 seconds to run though on my computer, but here is a link to the project so you can a) try it out for yourself, and b) generate the solution if you want, because for some reason adding a 3rd color to the bitmap increases the file size from ~10MB to ~300MB, which is unfeasible to host and download.
It’s not especially impressive, but I thought it was a fun little project.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s