R/makeMazeRecursiveBacktracker.R

In Ziegelsteintom/rmazing: Algorithms for Different Kinds of Perfect Mazes

#' Recursive Backtracker Algorithm
#'
#' Builds a maze via recursive backtracker algorithm.
#'
#' @param height how heigh should the maze be
#' @param width how wide should the maze be
#' @param seed a particular seed for reproducible results
#' @param start which is the starting point of the algorithm
#'
#' @return returns a dataframe generated with the recursive backtracker algorithm
#' @export
#'
#' @examples
#' makeMazeRecursiveBacktracker(height = 10, width = 10, seed = 42, start = 1)

makeMazeRecursiveBacktracker <- function(height = 10 , width = 10, seed, start = 1){

  if(!missing(seed)) set.seed(seed)

  # number of cells
  n <- height*width

  # Initialize maze
  maze <- cbind(N = rep(1,n),     # North
                E = rep(1,n),     # East
                S = rep(1,n),     # South
                W = rep(1,n),     # West
                vis= rep(0,n),    # Visited
                x = rep(1:width, height),         # x-Coordinate
                y = rep(1:height, each = width),  # y-Coordinate
                ind = 1:n)

  # mark start point as visited
  maze[start, "vis"] <- 1

  # Initialize stack which remembers where we were
  stack <- start

  while(length(stack != 0)){

    # current cell
    i <- stack[length(stack)]

    nachb <- neighbour(i, width, height, maze)

    # If all neighbouring cells have been visited delete the current cell from the stack
    if(all(maze[nachb, "vis"] == 1)){
        stack <- stack[-length(stack)]
        next
    }

    # k tells me which way to go (1N, 2E, 3S, 4W)
    for(k in sample(1:4, size = 4)){

      if(nachb[k] != 0 && maze[nachb[k], "vis"] == 0){

        # mark next cell as visited
        maze[nachb[k], "vis"] <- TRUE

        # kill the wall of the current cell
        maze[i, k] <- 0

        # kill the wall of the next cell
        ifelse(k > 2, z <- k -2, z <- k + 2)
        maze[nachb[k], z] <- 0

        stack <- c(stack, nachb[k])
        break
      }
    }
  }
  return(structure(maze, class = "maze",
                   width = width,
                   height = height,
                   start = start))
}