R/makeMazeSidewinder.R

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

#' Sidewinder Maze Algorithm
#'
#' Builds a maze via Sidewinder 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 bias 0.5 is unbiased, 1 and 0 are totally biased
#'
#' @return a dataframe generated with the binary algorithm
#' @export
#'
#' @examples
#' maze <- makeMazeSidewinder(width = 10, height = 10)

makeMazeSidewinder <- function(height = 10 , width = 10, seed, bias = 0.5){

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

  # Number of cells
  n <- height*width

  # doesn't really matter since we iterate over each row and they are independant
  start <- 1

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

  # Cells on the top
  ind_y <- maze[, "y"] == height
  # Last one should not be opened to the east
  ind_y[n] <- FALSE
  # These cells need to be opened on the west
  ind_w <- ind_y[c(n,1:(n-1))]

  # Kill Walls
  maze[ind_y, "E"] <- 0
  maze[ind_w, "W"] <- 0


  # Contains indices of the current run
  temprow <- numeric(0)

  # Loop over all cells exept the ones on the top
  for(i in 1:(n-width)){

    # 0 -> go east, 1 -> go north
    rv <- sample(c(0,1), size = 1, prob = c(bias, 1-bias)) #rv random variable

    # If we are on the east border we need to go up
    if(i %% width == 0){

      temprow <- c(temprow, i)

      # if you provide sample with only an integer and no vector it will sample from 1:integer
      if(length(temprow) == 1){
        k <- temprow
      } else{
        k <- sample(temprow, size = 1)
      }
      maze[k        , "N"] <- 0
      maze[k + width, "S"] <- 0
      temprow <- numeric(0)
      next
    }

    # Go east
    if(rv == 0){
      maze[i    , "E"] <- 0
      maze[i + 1, "W"] <- 0
      temprow <- c(temprow, i)

    } else{ #go west

      # choose one of the visited cells in the run
      temprow <- c(temprow, i)

      # if you provide sample with only an integer and no vector it will sample from 1:integer
      if(length(temprow) == 1){
        k <- temprow
      } else{
        k <- sample(temprow, size = 1)
      }
      maze[k        , "N"] <- 0
      maze[k + width, "S"] <- 0
      temprow <- numeric(0)
    }
  }

  return(structure(maze, class = "maze",
                   width = width,
                   height = height,
                   start = start))

}