R/makeMazePrim.R

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

#' Prim's Maze Algorithm
#'
#' Builds a maze via Prim's 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 of the algorithm, can be ommited for a random
#' starting point
#'
#' @return a dataframe generated with Prim's algorithm
#' @export
#'
#' @examples
#' maze <- makeMazePrim(width = 10, height = 10)

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

  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)

  # initialize a weight column with random weights
  # Could add equal weights andadd Parameter named simplified
  #  with default = FALSE TODO
  maze <- cbind(maze, weight = sample(1:n, size = n))

  # start should be random by default and if is.null == TRUE not default TODO
  # add start to the set
  if(is.null(start)){
    set <- sample(1:n, size = 1)
    start <- set
  } else {
  set <- start
  }

  maze[set, "vis"] <- 1

  # while set is not empty
  while(length(set) != 0){

    # In the set, choose cell with heighest weight
    index_highest <- set[which.max(maze[set, "weight"])]

    # calculate neighbours
    neigh <- neighbour(index_highest, width, height, maze)
    neigh <- neigh[neigh != 0]
    bool_neigh_vis <- maze[neigh, "vis"] == 0 # TRUE if not visited

    # If there are no unvisited neighbours left, remove this cell from the stack
    if(sum(bool_neigh_vis) == 0){

      set <- set[set != index_highest]

      # if there is exactly one neighbour link them
    } else if(sum(bool_neigh_vis) == 1){

      next_cell <- neigh[bool_neigh_vis]

      # kill walls
      # one way
      ww <- which_wall(index_highest, next_cell, height)
      maze[index_highest, ww] <- 0

      # the other way
      ww <- which_wall(next_cell, index_highest, height)
      maze[next_cell, ww] <- 0

      # mark as visited
      maze[next_cell, "vis"] <- 1
      set <- c(set, next_cell)

      #if there is more than one neighbour
    } else{
      next_cell <- sample(neigh[bool_neigh_vis], size = 1)

      # kill walls
      # one way
      ww <- which_wall(index_highest, next_cell, height)
      maze[index_highest, ww] <- 0

      # the other way
      ww <- which_wall(next_cell, index_highest, height)
      maze[next_cell, ww] <- 0

      # mark as visited
      maze[next_cell, "vis"] <- 1
      set <- c(set, next_cell)
    }
  }

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