Hunt-and-Kill maze algorithm
Hunt-and-Kill carves a random walk until it gets stuck, then scans the grid for an unvisited cell next to the maze and starts again from there.
How it works
The 'kill' phase is a random walk that only steps into unvisited cells, carving as it goes. When it runs out of moves, the 'hunt' phase scans the grid row by row for the first unvisited cell that touches the maze, connects it, and starts a new walk from it.
The result looks a lot like a recursive backtracker maze, with long corridors, but it needs no stack, because it hunts instead of backtracking. The scanning makes it slower on big grids.
What to watch for
Watch long runs of corridor, then a pause as the hunt jumps to a new starting point near the top of the unfinished area.
Properties
- Texture
- Long corridors
- Dead ends
- Few
- Uniform
- No
- Speed
- Medium (the hunt scans rows)
- Memory
- None beyond the grid
Try it
Open the studio to carve your own Hunt-and-Kill maze at any size, solve it with up to four algorithms, and save the video. Or print one.
FAQ
How is Hunt-and-Kill different from the recursive backtracker?
When stuck, the backtracker retraces its steps using a stack; Hunt-and-Kill scans the grid for a new place to continue, so it needs no stack.