What is DFS?

DFS, or depth-first-search, is an algorithm that searches a tree as deeply as possible (hence the name "depth-first") before backtracking to a higher level. It is most commonly implemented using a stack or via stack-based recursion.

Maze generation with randomized DFS

Starting with an n row by m column matrix of walls (a location can either be a passage or a wall) and a stack capable of holding a object, push an arbitrary starting location onto the stack. To keep things simple, I start at the top-left corner going downwards.

  1. If the stack is empty, exit. Otherwise, pop off the next <location, direction> pair (named l and d respectively) from the stack.
  2. Check if the point l2 ahead of the location l in the direction d is a wall. If not, go to step 1. Otherwise, mark both location l and l2 as passages in the n by m matrix.
  3. For each of the 4 cardinal directions from location l2, select only the directions fulfilling the following criteria:
    1. In the given direction, a location must exist inside the maze 2 spaces ahead from the current position.
    2. The locations 1 space ahead and 2 spaces ahead must both be walls.
  4. For each direction fulfilling the above criteria, push the first point in that direction and the direction onto stack (e.g. a <(1,1), UP> object).
  5. Go to step 1.

Sample Implementation

Here's an example bare-bones implementation in C++11.

int MAZE_WIDTH = 10, MAZE_HEIGHT = 10; // can be customized

struct Location { int x, y; };
typedef enum {
    RIGHT = 0,
    LEFT = 1,
    DOWN = 2,
    UP = 3
} Direction;

std::stack<std::tuple<Location, Direction> > stk;
std::set<Location> mazeData; // any location contained in this set is a passage; any other location is a wall
Location INVALID_LOCATION = (Location){.x = -1, .y = -1};

inline bool is_valid(Location loc){
    /* Return if a given location is valid (e.g. in the maze). */
    int x = loc.x, y = loc.y;
    return (x >= 0 && x < MAZE_WIDTH && y >= 0 && y < MAZE_HEIGHT);
Location lookInDirection(Location loc, Direction d, int n = 1){
    /* Return the point n spaces ahead from location loc in direction d */
    static int dx[] = {1, -1, 0, 0};
    static int dy[] = {0, 0, 1, -1};
    int x = loc.x, y = loc.y;
    y += dy[d] * n; x += dx[d] * n;
    loc.x = x;
    loc.y = y;
    if(is_valid(loc)) return loc;
    else return INVALID_LOCATION;
std::list<std::tuple<Location, Direction> > getNeighbors(Location loc){
    /* Return all valid neighbors of given location */
    int r = loc.y, c = loc.x;
    std::list<std::tuple<Location, Direction> > ret;
    for(int i = 0; i < 4; i++){
        Direction d = Direction(i);
        Location one = lookInDirection(loc, d, 1);
        Location two = lookInDirection(loc, d, 2);
        if(two != INVALID_LOCATION && !mazeData.count(one) && !mazeData.count(two)){
            ret.push_back(std::make_tuple(one, d));
    return ret;
void generateMaze() {
    /* Push starting location on stack */
    stk.push(std::make_tuple((Location){.x = 0, .y = 0}, DOWN));

    /* Loop while stack is not empty */
        /* Pop off location at top of stack */
        auto curTup = stk.top();
        Location curPos = std::get<0>(curTup);
        Direction curDirection = std::get<1>(curTup);

        /* Ensure the location ahead of the current position in the current direction is a wall */
        Location next = lookInDirection(curPos, curDirection);

        /* If it is not a wall, re-loop. */

        /* Otherwise, mark both locations as passages. */
        curPos = next;

        /* Get all valid locations and directions. */
        auto pos = getNeighbors(curPos);

        /* Shuffle the list. */
        std::vector<std::tuple<int, Direction> > filtered(pos.begin(), pos.end());
        std::shuffle(filtered.begin(), filtered.end(), std::default_random_engine(rand()));

        /* Push the list onto the stack. */
        for(auto on : filtered){

How would this look?

Glad you asked. Here's an example using the ffmpeg API to visualize the randomized DFS algorithm's behavior:

DFS-based maze generation

You can see the full implementation, complete with ffmpeg-based video generation, at https://github.com/firebolt55439/maze-generator.

Just for fun

Feast your eyes on this beauty:

A Giant Maze