Recursive Division Maze Generator is the fastest algorithm without directional biases. While Recurssive division really stands out with respect to parallelism, this algorithm is particularly fascinating because of its fractal nature: you could theoretically continue the process indefinitely at finer and finer levels of detail (smaller and smaller scales).

This algorithm is somewhat similar to recursive backtracking, since they're both stack based, except this focuses on walls instead of passages. As a Wall Builders generator, the process begins with a large empty space (all cells are connected), and adds walls (disconnect cells) until a maze results.

The general idea of a recursive division is very straightforward: You start off with an empty "room", split it in two part with a wall, make a hole in the wall and repeat this on the two newly created rooms.

Steps

  • Begins with a large empty space (all cells are connected).
  • 1. Randomly build a wall within this space.
  • 2. Randomly build a path within this wall.
  • 3. Recurse on both sides of the wall.

At every step, you still have a valid maze. Each repetition of the algorithm simply increases the level of detail. This could lead to an infinite maze level diving animation.

Pseudo-Code

Maze RecursiveDivisionWrapper(int width, int height)
{
  Maze maze(width, height, Cell::Connected);
  RecursiveDivision(maze, width, height);

  return maze;
}

RecursiveDivision(Maze maze, int width, int height, Cell offSet = [0, 0]})
{
  // Recursion Termination
  if (width < 2 || height < 2)
    return;

  // Randomly build the wall either horizontally or vertically
  auto isHorizontal = Random() % 2;

  // Randomly select the position to build the wall (disconnect cells along the line)
  auto wallIdx = Random(width, height, isHorizontal);
  maze.BuildWall(wallIdx, isHorizontal);

  // Randomly select the position to carve a unique path within this wall
  auto pathIdx = Random(width, height, !isHorizontal);
  maze.CarvePath(pathIdx, !isHorizontal);

  // Recurse on sub areas
  if (isHorizontalCut)
  {
    // Top and Bottom areas
    RecursiveDivision(maze, width, wallIdx, offSet);
    RecursiveDivision(maze, width, height - wallIdx, offSet{y +=  wallIdx});
  }
  else
  {
    // Left and Right areas
    RecursiveDivision(maze, wallIdx, height, offSet);
    RecursiveDivision(maze, width - wallIdx, height, offSet{x +=  wallIdx});
  }
}

Mazes generated by Recursive Division algorithm are in form of rectangular nested fractal. The method results in mazes with long straight walls crossing their space, making it easier to see which areas to avoid. It also tend to have a lot of short dead-ends.