# Maze Creation

## — real time application of DFS

--

# What is DFS ?

Let’s discuss about DFS first. **DFS** means **D**epth **F**irst **S**earch. It is a searching algorithm in a graph data structure. If you are from a Computer Science background, you have heard that before. It is an easy algorithm and must know algorithm to learn for a Programmer or any other Computer Science field. The search starts from the root node. Then it looks for its neighboring nodes. Then it chooses a neighbor node that is not yet visited, finally we move to the chosen node.

Whenever a node is visited, the node is pushed to a stack data structure which stores the path we are currently on. If a node has no neighbors, then we pop the last item from the stack and consider that node as the current node. Now repeat the same process until the stack becomes empty.

For the graph above, the DFS output will be as follows:

1 -> 2 -> 4 -> 7 -> 5 -> 3 -> 6 -> 8

That’s it! Let’s discuss about the maze creation.

**Maze Creation**

Let’s start creating the maze with the algorithm we learned right now. I am going to implement the simplest way possible to understand. Let’s go through the pseudo code first.

`// for simplicity stack can be implemented as an array`

stack = []

// take the initial node and mark it as visited, add it to the stack

start.visited = True

stack.append(start)

// do the operation until the stack become empty

while len(stack) > 0:

//pop the last node from the stack and make it as current

current = stack.pop(0)

if current.has_unvisited_neighbors():

// current node has unvisited neighbors get a random one

neighbor = current.get_random_neighbor()

// push the current node to stack

stack.append(current)

// remove the wall between the current and neighboring node

remove_wall_between(current, neighbor)

// moving to neighboring node and adding it to stack

neighbor.visited = True

stack.append(neighbor)

Let’s create the game as a web app do that we can visualize the algorithm. I am just going to go through the code that corresponds to algorithm, you can implement the app as per your wish. First, let’s see the structure for each node. You can use the class object to the make a node but for simplicity sake, I have made it as a simple object. It is created as follow:

`{`

row: i,

col: j,

// borders

top: true,

left: true,

bottom: true,

right: true,

// check if already visited

visited: false

}

The top, left, right, bottom values implies the border of each node. The row and col represents the actual row and col of the node. Visited simply used to track whether the node is already visited or not. Now, let’s get into creating maze.

export function createMaze(grid) {

// stack DS to track the current node

const stack = []// starting with first node and mark it as visited

stack.push(grid[0][0])

grid[0][0].visited = truewhile (stack.length > 0) {

// taking the last item visited in the stack and get all their nighbours

const current = stack.pop()

const neighbours = getAllNeighbours(current, grid)// proceed only if there is atleast one neighbour

if (neighbours.length > 0) {

// as the current node has a nighbour it is added to the stack

stack.push(current)

// get a radom neighbour from the neighbours list

const neighbour = getRandomNeighbour(neighbours) removeWall(current, neighbour)// mark the neighbour as visited

neighbour.visited = true

stack.push(neighbour)

}

}

}

To get the neighboring nodes, we can separate that in another function as follows:

// get all the neighbour for maze creation

// visited neighbour is not valid here

function getAllNeighbours(current, grid) {

const neighbours = []

const [row, col ] = getPos(current)if (row > 0 && !grid[row - 1][col].visited)// top

neighbours.push(grid[row - 1][col])if (row < ROWS - 1 && !grid[row + 1][col].visited)// bottom

neighbours.push(grid[row + 1][col])

if (col > 0 && !grid[row][col - 1].visited)// left

neighbours.push(grid[row][col - 1])

if (col < COLS - 1 && !grid[row][col + 1].visited)// right

neighbours.push(grid[row][col + 1])return neighbours

}

and for removing the wall:

`removeWall(current, neighbour) {`

// removing the wall between the current and the considered neighbour

if (current.row > neighbour.row) {

current.top = false

neighbour.bottom = false

}

else if (current.row < neighbour.row) {

current.bottom = false

neighbour.top = false

}

else if (current.col > neighbour.col) {

current.left = false

neighbour.right = false

}

else {

current.right = false

neighbour.left = false

}

}

Considering that each node has the border on all the sides. So if we want to remove the wall between current and neighbor node, we need to remove the wall from both the nodes. For example, if the current is below the neighboring node, then we need to remove the top border of the current and bottom border of the neighbor node. To get a random neighbor we use another function as follows:

`// get a random neighbour from the list of neighbours`

function getRandomNeighbour(neighbours) {

const index = Math.floor(Math.random() * neighbours.length)

return neighbours[index]

}

If you are interested in viewing the whole project (which is damn so simple project), checkout the code in GitHub. If you just wanna try the app to be in action, you can check that out here. In this project, I have also made functions to find the path between any start and end node using an algorithm called A* path finding algorithm. It was really a great algorithm to learn. If you are interested, I have already made an article about that. You can check that out here -> https://18ganapathy04.medium.com/a-path-finding-algorithm-1dd35f49c164

Thanks for reading. Enjoy your day