MazeReducer
Introduction
I was quite ill during September 2018, enough to miss a few days of sixth form. In those few days off, I watched a Computerphile video about maze solving and decided to make my own maze solver. If I remember correctly, in the video Dr Mike Pound implements some common graph traversal algorithms (e.g. depth and breadth first, Dijkstra's shortest path, A*), all of which are probably faster than the method I came up with, which essentially converts the maze to a graph, and reduces the graph until only the path from start to finish remains (if there are multiple paths, it chooses one of them).
I had made a GUI for it, but it was quite sloppy because I'd done that bit in a rush, so I've since removed the GUI and made it into a CLI application. The actual algorithm itself was programmed a bit sloppily as well, so I've improved that quite a bit, though the code is far from beautiful!
The program reads in mazes as images and produces an image of the solved maze as output (if there actually is a solution). To make an image the solver can understand, the start point must be blue (#0000FF), the end must be green (#00FF00), and the walls must be black (#000000). It will treat any deviation from those colours as a path. The solved maze will have a path from start to finish drawn on in red. It isn't guaranteed to be the shortest path or anything, but it will link the start and end. In fact, many times it will go a seemingly roundabout route to get to the end. It was just an idea I had for an algorithm which finds a path from the start to the end.
To run the program, you must pass it two command line arguments - the first is the input file (the original maze image) and the second is where the solved maze should be output to. If it can be solved, it will save the solved maze there, but if it can't be solved then no changes will be made to the filesystem and an error message will be displayed.
I've included some sample mazes which you can test the program on (they're the ones I tested it with). Youu'll notice that when solving the "blobby" maze, the path seems to fill a large area of the maze with a block of red. However, it's not a block of red, but rather a path which weaves up and down until it can't any more. This happens because the algorithm first looks for a route upwards, then leftwards, then downwards, and finally rightwards. If I searched them in a different order, it wouldn't produce the block of red for this maze, but it would for some other maze, due to symmetry. As I said, it is by no means the best solution, but it's definitely a solution!
Files
Screenshots
You may want to zoom in a bit to see the image properly - the paths and walls of the maze are one pixel wide.
32×32 maze, before and after