# 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 <location, direction> 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 */
while(!stk.empty()){
/* Pop off location at top of stack */
auto curTup = stk.top();
Location curPos = std::get<0>(curTup);
Direction curDirection = std::get<1>(curTup);
stk.pop();

/* 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. */
if(mazeData.count(next)){
continue;
}

/* Otherwise, mark both locations as passages. */
curPos = next;
mazeData.insert(next);
mazeData.insert(curPos);

/* 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){
stk.push(on);
}
}
}
``````

# How would this look?

Glad you asked. Here’s an example using the ffmpeg API to visualize the randomized DFS algorithm’s behavior: 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: 