Simple Maze Generation with DFS

Intro

I recently came across a simple and clever technique to generate mazes using the DFS (Depth-First Search) algorithm.

Traditionally, DFS is used to find a path through an existing maze—for example, from the entrance to the exit. But I became curious about how DFS could be adapted to generate a maze from scratch.

My first instinct was to start with a grid completely filled with walls and then “carve out” a path as we traverse the space. This carving process breaks walls to form valid paths, creating a maze.

Below is an interactive JS project that starts with a fully walled square matrix and runs a basic DFS traversal from (0, 0) to (size - 1, size - 1). However, this version isn’t quite what we want for maze generation. It tends to go straight toward the goal, producing a single winding path rather than a maze with dead ends and branches.

To generate a more maze-like structure, we need to make a couple of key modifications to the traditional DFS.

Shuffle the directions

The first tweak that needs to be added is to shuffle the directions in which we move. In order to add randomness to movements, rather than going straight to the exit. Added another interactive JS project with this modification below. The results look better but not quite right yet.

Move 2 steps

The second tweak is to move two cells at a time instead of one. We still go up, down, left, or right—but in increments of 2. This lets us leave walls between paths and creates more complex maze structures.

Here’s the final version with both tweaks applied: