# Quick Access

# Description

**Depth First Search (DFS) Maze Generator** is a randomized version of
the depth-first search traversal algorithm.
Implemented with a stack, this approach is **one of the
simplest ways** to generate a maze.

# How To Build

Let's first have a look on the DFS traversal algorithm:
One **starts at any cell** and **explores as far as possible**
along each branch before backtracking.

To generate a maze, we just have to randomize the traversal:
meaning we pick a **random** but unvisited neighbor to continue our traversal.
When we hit a **dead end** (cell with no unvisited neighbors),
we **'backtrack' to the most recent cell** in the stack.

## Steps

- Choose a starting cell in the field and add it to the stack.
- While there is cell to be handled in the stack:
- 1.
**Pop cell**from the top of the stack. - 2.
**Connect and visit all available neighbours**from: bottom, left, right, top and unvisited. - 3.
**Randomly select the one to be on the top**and Push those neighbours on the stack.

## Pseudo-Code

Maze DFS(int width, int height, Cell startCell) { Maze maze(width, height); Stack pathStack(startCell); // While there is node to be handled in the stack while (!pathStack.empty()) { // Handle the cell at the top of the stack: // Get available neighbours from bottom, left, right, top and unvisited Cell cell = pathStack.pop(); auto neighbours = GetAvailableNeighbours(maze, cell); // If there is avaible node to process (loop to backtrack - 'pop' otherwise) if (!neighbours.empty()) { // Randomly select a node to be processed auto randIdx = Random() % neighbours.size(); // For each available node: connect to the cell, mark it as visited // and push it into the stack. for (auto i = 0; i < neighbours.size(); ++i) { cell->Connect(Cell::Visite(neighbours[i])); // Only the choosen item should be add to the top following a DFS strategy if (i != randIdx) pathStack.push(neighbours[i]); } // Add the choosen node as the next one to be processed pathStack.push(neighbours[randIdx]); } } return maze; }

# Texture

Mazes generated have a **low branching factor** and
contain many **long corridors**, because the algorithm explores
as far as possible along each branch before 'backtracking' (using previous cell on the stack).

The **River** characteristic means that when creating the Maze,
the algorithm will look for and clear out nearby cells:
It **flows** into the Maze like water.
DFS Mazes tend to have a **main River**, resulting in a
**large amount of short dead ends**.

All of this makes depth-first a good algorithm for generating mazes in video games.

In mazes generated by that algorithm, it will typically be relatively easy to find the way to the root since most paths lead to or from there, but it is hard to find the way out.