Maze Creation

— real time application of DFS

What is DFS ?

Let’s discuss about DFS first. DFS means Depth First Search. 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.

graph data structure

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 = true
while (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