Hunt and Kill Maze Generator
Published: February 7, 2025 at 4:27:57 PM UTC
Maze generator using the Hunt and Kill algorithm to create a perfect maze. This algorithm is similar to the Recursive Backtracker, but tends to generate mazes with somewhat less long, winding corridors.The Hunt and Kill algorithm is really a modified version of the Recursive Backtracker. The modification consists of systematically scanning (or "hunting") for a new cell to continue from when it can't go further, as opposed to a true recursive search, which will always go back to the previous cell on the stack.
Because of this, this algorithm can easily be adapted to generate mazes with different look and feel, just by choosing to enter "hunting" mode more often or according to specific rules. The version implemented here only enters "hunting" mode when it can't go further from the current cell.
A perfect maze is a maze in which there is exactly one path from any point in the maze to any other point. That means you can't end up going around in circles, but you will often encounter dead ends, forcing you to turn around and go back.
The maze maps generated here includes a default version without any start and finish positions, so you can decide those for yourself: there will be a solution from any point in the maze to any other point. If you want inspiration, you can enable a suggested start and finish position - and even see the solution between the two.
About the Hunt and Kill Algorithm
The Hunt and Kill algorithm is a simple yet effective method for generating mazes. It is somewhat similar to a depth-first search (i.e. the Recursive Backtracker algorithm), except than when it can't go further from the current position, it systematically scans (or "hunts") over the maze to find a new cell to proceed from. The algorithm consists of two main phases: walking and hunting.
How the Hunt and Kill Algorithm Works for Maze Generation
Step 1: Start at a random cell
- Find a random cell in the grid and mark it as visited.
Step 2: Walking Phase (Random Walk)
- Choose a random unvisited neighbor.
- Move to that neighbor, mark it as visited, and carve a path between the previous and new cell.
- Repeat until there are no unvisited neighbors left.
Step 3: Hunting Phase (Backtracking via Scanning)
- Scan the grid row by row (or column by column).
- Find the first unvisited cell that has at least one visited neighbor.
- Connect that cell to a visited neighbor to resume the walking phase.
- Repeat until all cells have been visited.