R/makeMazeAldousBroder.R

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

#' AldousBroder Maze Algorithm
#'
#' Builds a maze via AldousBroder 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 starting point of the algorithm
#'
#' @return a dataframe generated with the AldousBroder algorithm
#' @export
#'
#' @examples
#' maze <- makeMazeAldousBroder(width = 10, height = 10, start = 45)


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

  # number of cells
  n <- height*width

  if(!missing(seed)) set.seed(seed)
  if(missing(start)) start <- sample(1:n, size = 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
                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

  # Count how many cells we visited
  count_vis <- 1

  # remebers where I am
  current_cell <- start

  while(count_vis != n){

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

    # will never have the length one which would be problematic for sampling
    next_cell <- sample(nachb[nachb != 0], size = 1)

    # hasn't been visited
    if(maze[next_cell, "vis"] == 0){

      maze[next_cell, "vis"] = 1

      # k <-  1 for N, 2 for E, 3 for S, 4 for W
      k <- which_wall(current_cell, next_cell, height)
      maze[current_cell, k] <- 0

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

      current_cell <- next_cell

      count_vis = count_vis + 1
    }else{

      current_cell <- next_cell
    }
  }

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