75x50 Maze generated by a Recursive Division algorithm (Top-Left flooding).

Flooding starting from Top-Left corner.

The tree representing its data structure topology from Top-Left corner.

Recursive Division Maze Generator is the fastest algorithm without directional biases. While recursive division stands out concerning 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 are both stack based, except this focuses on walls instead of passages. As a Wall Builders generator, the process begins with ample space (all cells are connected) and adds walls (disconnect cells) until the maze results.

The general idea of a recursive division is very straightforward: We start 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 ample 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 increases the level of detail. This could lead to an infinite maze level diving animation.

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 the form of the 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 tends to have a lot of short dead-ends.

1. Randomly build a wall and a path within an empty space.

2. Recurse on upper side and repeat the operation.

3. From the upper side, on more recursion to its left side.

4. Few recursions later, the upper area maze is built.

4. Same process occurs on bottom area (second main recursion) resulting on the full maze!