Maze Runner
A Java maze-solving engine that parses text mazes, models them as a graph, and escapes them three different ways — breadth-first search, Trémaux, and the right-hand rule — printing the route as a factorized instruction string.
The assignment arrived twice. First I wrote a maze runner: read a maze out of a text file, get from the entrance to the exit, print the moves. Then, after a term of design patterns, I got the same problem back with instructions to go through my own code, write down in detail what was wrong with it, and build it again. The report that ships with this project is mostly me marking my own homework, which is a strange thing to hand in and the most useful thing I wrote for that course.
The program is a command-line tool. Point it at a maze file with -i and it prints one line of instructions: F for forward, R and L for turns. Give it -p with a path somebody else produced and it runs the other way, answering correct path or incorrect path. -method picks which algorithm solves it, and -baseline names a second algorithm to measure the first against, which is where the timings and the speed-up line come from.
The first version worked and was badly built, and the specific ways it was badly built are what the first three answers of the report are about. The Maze class solved the maze, verified whole paths and validated individual moves, three jobs with no reason to share a class. There was no interface for a solver, so adding a second algorithm meant editing the code that already worked instead of adding a class beside it. The right-hand solver was the worst of it: movement rules hardcoded into long chains of conditionals, a pile of booleans standing in for what the runner was currently doing, the same logic written twice between finding a path and checking one, and no bounds checking anywhere near a raw two-dimensional array.
The rebuild starts by changing what a maze is. Instead of a grid you step around, it becomes a graph. A node is a position together with a heading, because standing on a square facing north is not the same situation as standing on it facing east, and an edge is the sequence of moves that carries you from one node to the next. GraphBuilder walks the maze once from the entrance and produces that graph with the instructions already sitting on the edges. A search over it does not return coordinates for something else to translate. It returns the moves.
BFS then does what BFS does: a FIFO queue, nodes expanded in the order they were discovered, each one visited once, and a Map of every node to the node it was reached from. Walking that map back from the exit and stitching the edge instructions together in reverse gives the shortest path. Trémaux and the right-hand rule never see the graph at all. They stay on the grid, one marking junctions as it passes through them and the other keeping a hand on the wall, and they are still in the program mostly so there is something for BFS to be compared against.
Three Gang of Four patterns hold the rebuild together. Strategy appears twice: MazeSolver is the contract Main depends on, and GraphTraverser is a separate contract for anything that operates on the graph, so a graph algorithm and a grid algorithm never have to pretend to be the same kind of thing. Adapter is what joins the two. GraphTraverserAdapter implements MazeSolver while holding a GraphTraverser, so BFS can be selected exactly like the other two: the adapter builds the graph, runs the traversal, and converts the Map it gets back into a Path. Visitor is the one I would defend hardest. MazeSolverPerformanceVisitor times each solver, and times graph construction separately for the adapted one, without a line of timing code inside any algorithm. SpeedUpCalculator then divides the baseline's step count by the chosen algorithm's, so the number the program prints is a ratio of route lengths rather than of clock time.
What the design is genuinely good at is absorbing new algorithms. Another graph traversal is a class implementing GraphTraverser and one more case in a switch. What it is bad at, and the report says so plainly, is a change of maze representation: every interface takes a Maze, so if that type changes shape the algorithms stop working and the only honest fix is rewriting them. The stack is small on purpose. Java 21 built with Maven, commons-cli for the flags, log4j2 for tracing a run, and JUnit for seven suites aimed at the places the logic actually lives: the graph builder, the adapter's path reconstruction, BFS itself, nodes, edges, the two path forms and the speed-up arithmetic.
The algorithms below are a faithful port of the Java classes, not the original program running remotely — nothing leaves your browser. Their output was checked against the compiled jar: identical instruction strings on every example maze.
Watch it solve
Pick a maze and an algorithm, then watch it work. These are the example mazes from the repository, and the line the terminal types out at the end is the whole output of the program: the same factorized instruction string the Java prints, F for forward and R and L for turns, ported to TypeScript so it can run in your browser.
The three disagree in a way you can see. BFS spreads outward evenly, because it expands nodes in the order it discovered them, so the first time it reaches the exit it has already found the shortest route. Trémaux reads as a walker instead of a flood: it commits to a corridor, marks the junctions it passes through, and backs out of dead ends it has already been down. The right-hand rule never decides anything at all. It keeps a hand on the wall and arrives at the same exit having taken several times as many moves.
Instructions and cells visited are the numbers worth comparing, and they are listed beside the maze. Timings taken in a browser would say more about your laptop than about any of the three algorithms.
> maze: small
> algorithm: —
> waiting for a run…
PATH
- Algorithm
- —
- Instructions
- —
- Cells visited
- —
- Status
- Idle
The design report
The write-up submitted with it: a critique of my own first attempt, the graph formalisation that replaced it, and the class and sequence diagrams for the rebuild.