DFS-Based Maze Generation

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:

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

Search

    Table of Contents