Flooding algorithm (flood-fill algorithm) too slow when solving a maze in R

166 Views Asked by At

I have a "maze", which is a dataframe with True/False values, where False values are like walls of the labyrinth, you cannot "walk" on them.

I have to create a function that says if it is possible to get from the starting point (1,1) to the end zone (which is in the middle of the maze).

### Reading in the maze
d0 <- readRDS(file = "maze.RDS")

### Plotting
plot(as.raster(d0))

endRegion <- list(x = 387:413, y = 322:348)

flood_fill_path_exists <- function(matrix, startX, startY, endRegion) {
  if (!matrix[startY, startX]) {
    return(FALSE)
  }
  
  queue <- list()
  queue <- append(queue, list(x = startX, y = startY))
  
  while (length(queue) > 0) {
    current_x <- queue$x[1]
    current_y <- queue$y[1]
    queue$x <- queue$x[-1]
    queue$y <- queue$y[-1]
    
    
    if (x %in% endRegion$x && y %in% endRegion$y) {
      return(TRUE)
    }
    
    matrix[y, x] <- FALSE
    
    moves <- list(c(0, -1), c(0, 1), c(-1, 0), c(1, 0))
    
    for (move in moves) {
      new_x <- x + move[1]
      new_y <- y + move[2]
      
      if (
        new_x >= 1 && new_x <= ncol(matrix) &&
        new_y >= 1 && new_y <= nrow(matrix) &&
        matrix[new_y, new_x]
      ) {
        queue$x <- append(queue$x, new_x)
        queue$y <- append(queue$y, new_y)
      }
    }
  }
  
  return(FALSE)
}

flood_fill_path_exists(d0, 1, 1, endRegion)

I tried the above pasted flooding algorithm, but it's way too slow. How to optimize it? Or maybe there is another, faster way.

(The function doesn't have to provide the path, just answer yes/no whether it's possible to get to the end zone!)

0

There are 0 best solutions below