迷宫求解算法 -> 迭代技术不能捕获所有特殊情况

Question

我只是用 JS 构建了一个迷宫求解器算法。它工作正常，但有两种特殊情况，它没有。

该程序还预先生成一个迷宫。如果目标（一个帽子（“^”）字符）生成到迷宫的起点，我希望程序生成一个新的迷宫。但这在某种程度上不起作用:(
该程序从左上角到右下角进行迭代，并检查其周围位置是否有帽子或田野角色。问题是，如果迷宫看起来像这样，程序就会停止并且无法运行：

[ [ '*', 'O', 'O', 'O', '^' ],
  [ '░', 'O', '░', 'O', '░' ],
  [ '░', '░', 'O', 'O', '░' ],
  [ '░', '░', 'O', 'O', '░' ],
  [ '░', '░', '░', '░', '░' ] ]

我想让它反过来穿过整个迷宫，但这也行不通...

我很高兴就这些问题提出任何建议！谁能给我一些关于代码的反馈？我写了很多评论，问题应该很容易理解！

这是我的回购的 link：https://github.com/Dimianovic/maze_solver/blob/main/main.js

谢谢！

Answer 1

关于您的代码的一些注意事项...

mazeChecker 函数不执行 path 搜索，而是简单地循环检查每个方块的局部邻居的二维数组。 mazeChecker函数需要找到起始方格，然后从那个方格开始进行搜索，跟踪它已经访问过哪些方格，接下来可以走到哪些方格，直到找到目标方格或者没有更多空心方块。
简单代码的关键之一是利用数据结构。具体来说，建议在构建包含边缘方块的迷宫时，这样做时，遍历方块时无需检查数组边界。相反，代码只需要检查边缘字符，或者更确切地说，检查要移动到的可用方块而不用担心数组的边界。

mazeTest =
[ [ 'X', 'X', 'X', 'X', 'X', 'X', 'X' ],
  [ 'X', '*', 'O', 'O', 'O', '^', 'X' ],
  [ 'X', '░', 'O', '░', 'O', '░', 'X' ],
  [ 'X', '░', '░', 'O', 'O', '░', 'X' ],
  [ 'X', '░', '░', 'O', 'O', '░', 'X' ],
  [ 'X', '░', '░', '░', '░', '░', 'X' ],
  [ 'X', 'X', 'X', 'X', 'X', 'X', 'X' ] ];
 

function printMaze( maze ) {
  let result = '';
  for ( let row = 0; row < maze.length; row++ ) {
    for ( let col = 0; col < maze[ row ].length; col++ ) {
      result += maze[ row ][ col ] + ' ';
    }
    result += '\n';
  }
  return result;
}

console.log( printMaze( mazeTest ) );

此外，随着边缘字符现在成为迷宫的一部分，当前方块周围的每个方块的检查可以包含一组选项，代码可以循环遍历这些选项，而无需四 (4) 组if 语句检查数组边界。（如果希望允许对角线移动，或者如果更改为六角形垫脚石布局，这也使得调整代码变得更加容易...）以下摘录显示了基本概念...

    const moveOptions = [ { r: -1, c: 0 }, { r: +1, c: 0 }, { r: 0, c: -1 }, { r: 0, c: +1 } ]; 

        o
        o
        o

    // From the current position, let's look in the immediate vicinity for
    // available squares.
    for ( let mo of moveOptions ) {
      let option = { row: currentSquare.row + mo.r, col: currentSquare.col + mo.c };
      let square = maze[ option.row ][ option.col ];
      
      // Did we find our goal?  If so, set it as the currentSquare and exit
      // the while loop.
      if ( square === '^' ) {
        currentSquare = option;
        break;
      }
      
      // If the square is available, then let's push it on the stack as a
      // starting point for another search.  Also, let's mark the square
      // as being in the stack so we don't visit it again!      
      if ( square === '░' ) {
        nextSquares.push( option );
        maze[ option.row ][ option.col ] = 's';
      }
    }

        o
        o
        o

上面的代码摘自深度优先搜索。深度优先搜索只涉及...
- 创建一个空数组堆栈，其中包含要移动的 nextSquares。
- 定义 currentPosition 并将其设置为起始方块。
- 虽然是真的
  - 循环 currentPosition 中的 4 个可能的方块
    - 如果找到目标方块，则退出循环并return结果。
    - 如果找到一个空方块，将其压入 nextSquares 堆栈，标记该方块现在在堆栈中。（这是为了在下一次搜索 4 个可能的方块时不再将其视为空方块。）
  - 如果 nextSquares 堆栈为空，则退出表示未找到目标方块。
  - 否则，将 currentPosition 设置为从 nextSquares 堆栈弹出的方块，循环回到 While 语句的开头。

重构代码时请考虑以上注意事项...

迷宫求解算法 -> 迭代技术不能捕获所有特殊情况

Maze solving algorithm -> iteration technique does not catch all special cases

javascript

maze

solver

node.js