Details of the full challenge can be found at http://golang-challenge.com/go-challenge6/
Two types of maze are generated. Both are perfect mazes, meaning there are no loops.
Non-perfect mazes requires a more intelligent maze solver to solve but in general, given the same maze dimension (15 x 10), a perfect maze takes more steps to solve.
This maze is generated by Kruskal's algorithm.
Given that the start and end points are randomly placed, the average number of steps taken to solve the maze (via Tremaux algorithm) is 133.
______________________________________________
|__________________ |______ ___| | ______|
| _ |___ | _ _ ___|______ ____ |___ |
| | ____ ___| |__| ____ | |_____| ___|
|__| |___ |_________⏂__ |___ _ |___ ___|
| |__|___ _ ______| ___|x |__| ____ ___|
| |___ ___|__| ___| |____________ | ___|
| | ______| ______| | | _ | _ |___ |
| | _ | ___|___ |_____|__| |__|__|___ |
| ___|__|_________ _ ____ _ _ | _ _ |
|________|___________|__|_____|__|_____|__|__|
I call it pocket maze because it has deep vertical pockets. Pockets may face up or down. Average steps is 136.
______________________________________________
| | | | | | | | | | | | | | | |
| | | | | | | | |x | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | |
|___⏂________________________________________|
Empty Maze - this map with most loops and multiple solutions. But average steps is low. Only 95.
______________________________________________
| _ _ _ _ _⏀ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _⏃ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
|____________________________________________|
Linear Maze - this map has only one single path. Not surprising, the average steps is 100.
______________________________________________
|__________________________________________ |
| _____________⏅____________________________|
|__________________________________________ |
|⏀ __________________________________________|
|__________________________________________ |
| __________________________________________|
|__________________________________________ |
| __________________________________________|
|__________________________________________ |
|____________________________________________|
Recursive Backtracking - this generated map is a perfect maze, but the average steps 116 pales in comparison to Kruskal and Pocket.
______________________________________________
|___ _ |______ _ ___| _ _________| _ |
| ___| | ______|__| ___|____________ | |
| | |___ |⏀ _________| ___| ____ |__| |
| |______ |______ |______ |⏅____|___ | |
| ____ |______ |_________ ___| ______| |
| ___| | _ |________| ___| ___| _ | |
| | ___| |_________ | | ___|___ |_____|
| |________| ______| | |___________|___ |
| | _ |___ | ______| | _ |___ _ | |
|_____|________|______________|________|_____|
The defacto algorithm for the person-focused maze solver (i.e. the person in the maze knows nothing about the maze, has no aerial view) is Trémaux's Algorithm.
Trémaux asks that you backtrack when you have reached a deadend (or a junction that has no new paths). While backtracking, you will explore the first junction you come to that that has unvisited paths. Very similar to recursive backtracking.
Say I started at A and decided to move west, and eventually ended up at B, which is considered a deadend. According to Trémaux, you will attempt to backtrack to A. However along the way, you encounter a junction with unvisted path (leading to C), so stop at explore that junction.
That junction is 3 steps away from B
___ C_______
| ______ B|
|________ A|
I have used an enhanced version that instead of backtracking blindly, will see choose the next junction to go to based on steps required. In this case when it is at B, it will take 1 step south to A and continue exploration.
We don't know if the treasure/destination is at C or at south of A, but we will attempt to move to the nearest unexplored junction.
Using the empty maze as a reference, the average steps are as follows:
- Trémaux's: 95
- Enhanced: 83
- Enhanced, with path prioritisation: 77
There is no performance gain if the maze is a perfect maze.
Full Name: Kelvin Yong
Country of Residence: Singapore
GitHub ID: kelvin-yong
Category: Normal (Just participating)