maze-generator-backtrack

A recursive-backtracking maze generator algorithm

This is a plugin for the sbj42/maze-generator package.

Recursive-backtracking is like a randomized depth-first search of the
grid. A random passage is dug from a random starting location, making
sure that the passage doesn't intersect itself. At some point it
becomes impossible for this initial passage to make any more progress.
Then we travel back along the passage until we find a cell where we can
create a branch. That branch is then extended randomly until it can no
longer proceed. This process repeats until all cells have been connected
to the maze.

Recursive-backtracking tends to generate long, winding passages,
with few dead-ends.

``
___________________________________________________
| | ___________ _____ | ___________ _ __|__ | _ _ |
| __|________ | | | __| | _______ | | | ____| | |_|
| |__ ___ | __| | | | | |_| ______| | | | __| |__ |
|_____| | | _ | |_____|____ | ___ | | | | ______| |
|____ | __| | | | _______ | | |_____|_| |_____| _ |
| ___ | |___| | | | ___ |___| | ________| ______| |
|__ |_| | _ | |___|__ | _ | __|______ | __| _ __| |
| _ | __| |______ | __| |_|__ _ | _ | |__ |_| | __|
| |_|__ |__ | __| |___|__ _ | |_| | |_____| __|__ |
| | ____| __| _ |______ | |_|_____| _____ | | _ | |
| | |__ _ | __|____ _ |__ | _____ |____ | __| |___|
| |__ | | |____ | __|_| __|____ | | ____| | __|__ |
| __| |_| | __| |____ | |____ | |___|_____|______ |
| | __| __| ____| ____|____ | |______ | _____ __| |
|_______|_______|___________________|_______|_____|
``