The maze solver is based on a skeleton code from Youhan Xia and Jeffrey Chan.

The Team

Caleb Turner, Danny Ho

Repo

https://github.com/s3603075/aa-assignment2/

Brief

Maze Generation

There are three types of mazes that were to be generated: a normal square maze, a hexagonal maze with hexagonal walls and a normal square maze which has ‘tunnels’ which teleports the path from one location to another one.

Mazes are generated using multiple strategies:

• Growing Tree
• Modified Prims
• Recursive Backtrack

Each maze must have at least one strategy to solve the maze.

Growing tree is a recursive algorithm and is similar to Prim’s algorithm, which is a greedy algoritm that chooses an arbitary vertex (V) and adds it to a set (S) initially, then chooses the next vertex with the smallest weight that connects V with another vertex that is not in V. This creates a minimal spanning tree.

The main strategy is to pick a random cell on the maze, then shuffle an array with all the directions and pick a cell which has not been visited. Additionally, there is a 10% chance picking a random cell to start from to create the dead ends in mazes and randomisation.

Modified Prims is essentially the same as above, but using two starting points to create each path seperately.

Recursive backtrack introduces the new type of maze, the tunnel maze. This generator can generate each type of maze (normal, hexagonal and tunnel). The backtracking algoritim explores an arbitrary path in the maze, then when it hits a dead end, it will backtrack to the nearest cell with unvisited neighbours, then continue searching.

Maze Solving

Two strategies were used to solve the generated mazes:

• Bidirectional Recursive backtracking
• Wall follower

Bidirectional Recursive backtracking as its name suggests, is a solver that takes the end of a maze and the beginning of a maze and creates two seperate paths via recursive backtracking. Once the two paths cross, the maze is solved.

Wall follower is a basic solver that follows the right wall when solving a maze, which will always get a solution.