When generating a maze, you could start with an empty space and then randomly adding some walls. Would the resulting structure be any interesting? Well, maybe. Depending on the number of walls that you added, at least some areas of your maze will be impossible to reach, while other parts of the maze will constitute perfect loops. In the image below you can see what is called a “perfect” maze. This means that every point in this maze can be reached from any other point in the maze. There are no loops in this maze and any two points are connected by one path only. How can you generate such a maze? One way is by using a “recursive backtracking algorithm”. In this tutorial you will learn how to implement this algorithm in R. We will implement the algorithm from scratch, i.e., without making use of any packages.

The recursive backtracking algorithm

We can think of the maze in the figure above as a square matrix. The matrix has \(n\) rows and \(n\) columns. Thus, the matrix has \(n^2\) many cells. Each cell has a set of walls. For simplicity, we will refer to these walls as “north”, “east”, “south” and “west”, depending on whether they are at the top, right, bottom or left of the cell. At first, each cell has all four walls. The maze, therefore, looks like a grid. Then, we select one of the cells as the starting place for the algorithm. We add the cell to an object (which is typically just a list or a vector) called the “stack”. The stack keeps track of the way that the algorithm has taken through the maze. The recursive backtracking algorithm now works as follows:

What does that pseudo-code mean? The algorithm carves its way through walls to reach new cells. However, in a case where it could only re-visit cells that it has already reached in the past, the algorithm stops and goes back. Hence the term “backtracking”. The algorithm goes back one cell and tries to find other new cells to carve into. If it fails again, it goes back another cell and so on. This way, the algorithm will never carve into the same cell twice. Consequently, in the end, each cell will only have one way in and one way out. The resulting maze will therefore be free of any loops, neither will it contain any dead ends.

Walls only

As said before, the procedure for generating a maze with recursive backtracking begins with unvisited cells that are each fully surrounded by walls. Since R is certainly not the greatest language for object-oriented programming, we cannot create these cells as class objects. We will model them as lists instead. Each cell will have seven properties: its row position, its column position, a boolean that indicates whether or not it has been visited, and another four booleans that indicate where there are walls around the cell. We will store all cells in list called maze.

# create maze (all walls) of size n
n <- 10
maze <- vector("list", 0)
for (i in 1:n) {
  for (j in 1:n) {
    cell <- list(
      i = i,
      j = j,
      visited = FALSE,
      north = TRUE,
      east = TRUE,
      south = TRUE,
      west = TRUE)
    maze[[length(maze)+1]] <- cell
  }
}
rm(i,j,cell)

# show the first cell
maze[[1]]
## $i
## [1] 1
## 
## $j
## [1] 1
## 
## $visited
## [1] FALSE
## 
## $north
## [1] TRUE
## 
## $east
## [1] TRUE
## 
## $south
## [1] TRUE
## 
## $west
## [1] TRUE

Next, we need a function to visualize the maze. Our function will start with a line from \((0,0)\) to \((0,n)\). Then, for each cell of the maze, it will draw all those walls that are equal to TRUE.

# function to show maze
showMaze <- function(maze) {
  
  # background
  par(mar = rep(1,4), bg = "burlywood4", bty = "n")
  plot(rep(0,n+1) ~ c(0:n), type = "l", asp = 1,
       ylim = c(0,n), xlim = c(0,n),
       yaxt = "n", xaxt = "n",
       ylab = "", xlab = "")
  
  # highlight visited areas
  for (idx in 1:n^2) {
    i <- maze[[idx]]$i
    j <- maze[[idx]]$j
    if (maze[[idx]]$visited) rect(j-1, i-1, j, i, col = "deepskyblue3", lty = 0)
  }
  
  # draw walls
  for (idx in 1:n^2) {
    i <- maze[[idx]]$i
    j <- maze[[idx]]$j  
    if (maze[[idx]]$north) lines( rep(i,2) ~ c(j-1,j), col="white", lwd=4)
    if (maze[[idx]]$south) lines( rep(i-1,2) ~ c(j-1,j), col="white", lwd=4)
    if (maze[[idx]]$east) lines( c(i-1,i) ~ rep(j,2), col="white", lwd=4)
    if (maze[[idx]]$west) lines( c(i-1,i) ~ rep(j-1,2), col="white", lwd=4)
  }

}

# demonstration
showMaze(maze)

Finding neighbors and removing walls

Before we can start programming the recursive backtracking algorithm, we need to define two more functions. First, we define a function that given an index value produces the index value of an unvisited neighbor. In case no such neighbor exists, the function will return NA. Possible neighbors, i.e., “candidates”, are the cells directly above, below, to the left or to the right of the current cell. Of these candidates, we will only consider those that have not yet been marked as “visited”.

# function to find a neighbor
findNeighbor <- function(idx) {

  # select cell at position "idx"
  cell <- maze[[idx]]
  
  # determine rows and columns of all cells in the maze
  rows <- sapply(maze, FUN = function(cell) cell$i)
  cols <- sapply(maze, FUN = function(cell) cell$j)
  
  # determine neighbor candidates
  above <- which(rows == (cell$i + 1) & cols == cell$j)
  below <- which(rows == (cell$i - 1) & cols == cell$j)
  left <- which(cols == (cell$j - 1) & rows == cell$i)
  right <- which(cols == (cell$j + 1) & rows == cell$i)
  candidates <- c(above, below, left, right)
  
  # neighbors must be unvisited
  visited <- sapply(maze[candidates], FUN = function(cell) cell$visited)
  neighbors <- candidates[!visited]
  
  # return
  if (length(neighbors) == 0) {         # no suitable candidates
    return(NA)
  } else if (length(neighbors) == 1) {  # exactly one candidate
    return(neighbors)
  } else {                              # multiple candidates 
    return(sample(neighbors,1))       
  }
}
# demonstration
set.seed(123)
findNeighbor(1)
## [1] 11
findNeighbor(50)
## [1] 49
findNeighbor(100)
## [1] 90

Now, that we can find a suitable neighbor cell for a given current cell, we need a another function to remove the wall between these two cells. The function first determines (via if-statements) how the two neighboring cells are positioned. If cell a is positioned over b, then we need to remove the southern wall of a and the northern wall of b and so on.

# function to remove walls
removeWalls <- function(maze, a, b) {
  
  # a over b
  if (maze[[a]]$i == maze[[b]]$i + 1 & maze[[a]]$j == maze[[b]]$j) {
    maze[[a]]$south <- FALSE
    maze[[b]]$north <- FALSE
  }
  
  # a under b
  if (maze[[a]]$i == maze[[b]]$i - 1 & maze[[a]]$j == maze[[b]]$j) {
    maze[[a]]$north <- FALSE
    maze[[b]]$south <- FALSE
  }
  
  # a left of b
  if (maze[[a]]$j == maze[[b]]$j - 1 & maze[[a]]$i == maze[[b]]$i) {
    maze[[a]]$east <- FALSE
    maze[[b]]$west <- FALSE
  }
  
  # a right of b
  if (maze[[a]]$j == maze[[b]]$j + 1 & maze[[a]]$i == maze[[b]]$i) {
    maze[[a]]$west <- FALSE
    maze[[b]]$east <- FALSE
  }
  
  # return
  return(maze)
  
}

Programming the recursive backtracking algorithm

Finally, we can program the maze generating algorithm as explained above.

# setup
set.seed(1234)
current <- 1
stack <- c(current)

# create maze using recursive backtracking
while (length(stack) > 0) {
  
  # mark current cell as visited and find neighbors
  maze[[current]]$visited <- TRUE
  neighbor <- findNeighbor(current)
  
  # remove walls, update stack and update current OR backtrack
  if (!is.na(neighbor)) {
    maze <- removeWalls(maze, current, neighbor)
    stack <- c(stack, neighbor)
    current <- neighbor
  } else {
    stack <- stack[0:(length(stack)-1)]
    current <- stack[length(stack)]
  }
  
  # show progress
  showMaze(maze)
  if (length(current) > 0 ) {
    i <- maze[[current]]$i
    j <- maze[[current]]$j
    points(x = j - 0.5, i - 0.5, col = "red", pch = 16, cex = 2)
  }
  Sys.sleep(0.5)
} 

# show final result
showMaze(maze)