R/makeMazeWilson.R

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

#' Wilson Maze Algorithm
#'
#' Builds a maze via Wilson algorithm.
#'
#' @param height how high should the maze be
#' @param width how wide should the maze be
#' @param seed a particular seed for reproducible results
#' @param start starting point or the algorithm
#'
#' @return a dataframe generated with the Wilson algorithm
#' @export
#'
#' @examples
#' maze <- makeMazeWilson(width = 10, height = 10, start = 1)

makeMazeWilson <- 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

  # Are there any unvisited cells
  while(any(maze[, "vis"] == 0)){
    bool_unvisited <- maze[, "vis"] == 0

    # need to take care of the case when there is only one point left
    if(sum(bool_unvisited) == 1){
      next_cell <- maze[bool_unvisited, "ind"]
    }else{
      # choose any unvisited point as startpoint
      next_cell <- sample(maze[bool_unvisited , "ind"], size = 1)
    }

    # start a vector with the unvisited point
    path <- next_cell

    # Loop until you meet a visited cell
    while(TRUE){
      neigh <- neighbour(next_cell, width, height, maze)

      # choose a random valid neighbour
      # there are at least two valid neighbours (important for sampling)
      next_cell <- sample(neigh[neigh != 0], size = 1)

      # if not visited add it to the path
      if(maze[next_cell, "vis"] == 0){
        path <- c(path, next_cell)

        # delete the loops in the path if there are any
        lp <- length(path)
        last <- path[lp]
        if(any(last == path[-lp]) == TRUE){
          index <- which(path[-lp] == last)
          path <- path[-(index:(lp-1))]
        }

      }else{

        path <- c(path, next_cell)

        # kill walls and mark all as visited and exit the nested loop
        for(i in 1:(length(path)-1)){

          # one way
          ww <- which_wall(path[i], path[i+1], height)
          maze[path[i], ww] <- 0

          # the other way
          ww <- which_wall(path[i+1], path[i], height)
          maze[path[i+1], ww] <- 0

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

        }
        break
      }
    }
  }

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