R/makeMazeHuntAndKill.R

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

#' Hunt and Kill Maze Algorithm
#'
#' Builds a maze via Hunt and Kill 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
#'
#' @return a dataframe generated with the Hunt and Kill algorithm
#' @export
#'
#' @examples
#' maze <- makeMazeHuntandkill(width = 10, height = 10, start = 1)

makeMazeHuntandkill <- 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)

  # Start with this cell
  current_cell <- start
  maze[current_cell, "vis"] <- 1

  # As long as there exist unvisited cells
  while(any(maze[, "vis"] == 0)){

    neighbour_index <- neighbour(current_cell, width, height, maze)
    neighbour_index <- neighbour_index[neighbour_index != 0]

    bool_neighbour_vis <- maze[neighbour_index, "vis"] == 0

    # no cells left to visit, start search for a new one == Huntmode
    if(sum(bool_neighbour_vis) == 0){

      # double loop over all cells beginning in the top left going right
      for(y in height:1){

        for(x in 1:width){

          index <- list_nr(x, y, width)
          # If i find an unvisited cell check if it has visited neighbours and link them together
          if(maze[index, "vis"] == 0){
            neigh <- neighbour(index, width, height, maze)
            neigh <- neigh[neigh != 0]

            # are there any unvisited neighbouring cells
            if(any(maze[neigh, "vis"] == 1)){

              # Only one neighbour
              if(sum(maze[neigh, "vis"]) == 1){
                next_cell <- index
                current_cell <- neigh[maze[neigh,"vis"] == 1]

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

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

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


              } else{

                next_cell <- index
                current_cell <- sample(neigh[maze[neigh,"vis"] == 1], size = 1)

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

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

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

              }

            }
          }
        }
      }

      # If only one is left then visit this one next
    }else if(sum(bool_neighbour_vis) == 1){
      next_cell <- neighbour_index[bool_neighbour_vis]

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

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

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

      # if more than one are avaiable choose one randomly
    }else{
      next_cell <- sample(neighbour_index[bool_neighbour_vis], size = 1)

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

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

      # mark as visited
      maze[next_cell, "vis"] <- 1
      current_cell <- next_cell
    }
  }

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