R中的递归迷宫求解器

Question

我想在 R 中解决迷宫问题。我根据相应的 Python 代码创建了一个函数:Solving mazes using Python: Simple recursivity and A* search .

我有一个迷宫(即矩阵)，其中:0 = 空白空间，1 = 墙(无法到达的单元格)，2 = 完成，3 = 已访问。

设置迷宫:

data = c(rep(1, 20),
         c(4,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1),
         c(1,1,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,2),
         rep(1, 20))

maze = matrix(data, 4, 20, byrow = TRUE)

我的尝试:

search = function(x, y){
  if (maze[x,y] == 2){
    print(paste('i am in point', x, y))
    return(TRUE)
  } else if (maze[x,y]==1){
    print(paste('wall in point', x, y))
    return(FALSE)
  } else if (maze[x,y]==3){
    print(paste('visited point', x, y))
    return(FALSE)
  } 
    
  #set as marked
  print(paste('visited point', x, y))
  maze[x,y] = 3
    
  if((x < length(maze[,1])   & search(x+1, y))
       | (y > 1 & search(x,y-1))
       | (x > 1 & search(x-1,y))
       | (y < length(maze[1,]) & search(x,y+1))){
      return(TRUE)
  }
  
  return(FALSE)
}

search(x= 2, y = 1)

不幸的是，代码错误:

[1] "visited point 2 1"  
[1] "wall in point 3 1" 
   
Error in if (maze[x, y] == 2) { : argument is of length zero

我发现 else 语句有问题，因为函数在空单元格(即 0)上停止。

Answer 1

我认为可能需要做一些事情才能在 R 中进行这项工作。首先，python 数组是从 0 开始索引的，但 R 是从 1 开始索引的。所以你的错误可能是访问矩阵中的零索引元素。此外，在递归调用您的函数时，您可能需要将您的 maze 矩阵作为参数反馈。

我根据 python 示例(6 x 6 矩阵)改编了您的演示。数字“2”代表此处的完成位置。 search 函数将单独检查是否越界。要查看迷宫是如何解决的，您可以取消注释 maze 的 print 语句。

data <- c(
  0, 0, 0, 0, 0, 1,
  1, 1, 0, 0, 0, 1,
  0, 0, 0, 1, 0, 0,
  0, 1, 1, 0, 0, 1,
  0, 1, 0, 0, 1, 0,
  0, 1, 0, 0, 0, 2
)

maze <- matrix(data, 6, 6, byrow = TRUE)

search <- function(maze, x, y) {
  
  # Check if out of bounds
  if (x < 1 | x > length(maze[,1])) return (F)
  if (y < 1 | y > length(maze[1,])) return (F)
  
  # Check if at end, already visited, or hitting a wall
  if (maze[x, y] == 2){
    print(paste('i am at the end: ', x, y))
    return(TRUE)
  } else if (maze[x, y] == 3){
    print(paste('already visited point: ', x, y))
    return(FALSE)
  } else if (maze[x, y] == 1){
    print(paste('wall in point: ', x, y))
    return(FALSE)
  } 
  
  # Set point as visited
  maze[x,y] = 3
  print(paste('visiting point: ', x, y))
  
  # Optional show maze as solved
  # print(maze)
  
  # Check clockwise positions for next move
  if (search(maze, x + 1, y)) return (T)
  if (search(maze, x, y - 1)) return (T)
  if (search(maze, x - 1, y)) return (T)
  if (search(maze, x, y + 1)) return (T)
  
  # No other move found
  return(F)
}

search(maze, x = 1, y = 1)

输出

[1] "visiting point:  1 1"
[1] "wall in point:  2 1"
[1] "visiting point:  1 2"
[1] "wall in point:  2 2"
[1] "already visited point:  1 1"
[1] "visiting point:  1 3"
[1] "visiting point:  2 3"
[1] "visiting point:  3 3"
[1] "wall in point:  4 3"
[1] "visiting point:  3 2"
[1] "wall in point:  4 2"
[1] "visiting point:  3 1"
[1] "visiting point:  4 1"
[1] "visiting point:  5 1"
[1] "visiting point:  6 1"
[1] "already visited point:  5 1"
[1] "wall in point:  6 2"
[1] "already visited point:  4 1"
[1] "wall in point:  5 2"
[1] "already visited point:  3 1"
[1] "wall in point:  4 2"
[1] "wall in point:  2 1"
[1] "already visited point:  3 2"
[1] "wall in point:  2 2"
[1] "already visited point:  3 3"
[1] "already visited point:  2 3"
[1] "wall in point:  3 4"
[1] "wall in point:  2 2"
[1] "already visited point:  1 3"
[1] "visiting point:  2 4"
[1] "wall in point:  3 4"
[1] "already visited point:  2 3"
[1] "visiting point:  1 4"
[1] "already visited point:  2 4"
[1] "already visited point:  1 3"
[1] "visiting point:  1 5"
[1] "visiting point:  2 5"
[1] "visiting point:  3 5"
[1] "visiting point:  4 5"
[1] "wall in point:  5 5"
[1] "visiting point:  4 4"
[1] "visiting point:  5 4"
[1] "visiting point:  6 4"
[1] "visiting point:  6 3"
[1] "wall in point:  6 2"
[1] "visiting point:  5 3"
[1] "already visited point:  6 3"
[1] "wall in point:  5 2"
[1] "wall in point:  4 3"
[1] "already visited point:  5 4"
[1] "already visited point:  6 4"
[1] "already visited point:  5 4"
[1] "visiting point:  6 5"
[1] "already visited point:  6 4"
[1] "wall in point:  5 5"
[1] "i am at the end:  6 6"
[1] TRUE

迷宫解决方案

     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    3    3    3    3    3    1
[2,]    1    1    3    3    3    1
[3,]    0    0    0    1    3    0
[4,]    0    1    1    3    3    1
[5,]    0    1    0    3    1    0
[6,]    0    1    0    3    3    2