Search⌘ K
Home
Courses
Mazes for Programmers

The Recursive Backtracker Algorithm

Explore how the Recursive Backtracker algorithm generates mazes by performing constrained random walks and using a stack to backtrack from dead ends. Understand how the algorithm visits cells, chooses random neighbors, and retraces steps to ensure all maze cells are connected.

We'll cover the following...

Introduction

The Recursive Backtracker algorithm works very much like the Hunt-and-Kill algorithm, relying on a constrained random walk to weave its rivery way across our grid. The difference is in how it recovers from dead ends: instead of hunting for another viable cell, it backtracks, retracing its steps until it finds a cell that has an unvisited neighbor.

The Recursive Backtracker algorithm explained and illustrated

Let’s walk through it and see how it works. We’ll use a stack to keep track of the cells we’ve visited. A ...