视力有限的寻路

Question

我正在制作一个基于 2D 方块的迷宫游戏，我正在尝试编写一个可以在迷宫中找到路径的 AI 播放器。与普通寻路不同，我想将每个玩家（包括 AI 玩家）的视野限制在他们周围的 2x2。也就是说，AI 应该只知道它周围的 5x5 网格和迷宫中的确切坐标，例如：

Tile mapRecord[MAP_SIZE][MAP_SIZE];
Direction FindPathAI(int row, int column, Tile surroundings[5][5]) {
    int i, j;
    int r = row - 3, c = column - 3;
    for (i = 0; i < 5; i++) {
        for (j = 0; j < 5; j++) {
            r = (r + MAP_SIZE + 1) % MAP_SIZE; //wrap around
            c = (c + MAP_SIZE + 1) % MAP_SIZE; //wrap around
            mapRecord[r][c] = surroundings[i][j];
        }
    }

    //FindPath

    //return the direction to go
}

有什么可能的方法可以解决这个问题？我在想我可以声明一个整个地图大小的数组，并将AI玩家的视野记录到地图上。但后来我陷入了下一步该做什么……有什么想法吗？谢谢。

Answer 1

这是可以做到的运行 2 个不同的路径搜索相互嵌入。一种算法分析玩家可见的迷宫块（玩家无移动）。另一种算法移动 AI 本身并搜索路径。分析迷宫可见部分的算法用于为 AI 搜索可能的进一步路径。这样AI就可以在不知情的情况下分析整个迷宫

路径查找本身是特定于实现的，并且有大量可用算法 (https://en.wikipedia.org/wiki/Maze_solving_algorithm) - 除了 BFS、DFS 和其他图形路径查找算法。

所使用的算法取决于 AI 的行为方式。例如，墙壁跟随器算法很容易实现，但如果 AI 表示例如游戏中的角色。最有效的算法可能是具有适当启发式的 A*（通过它也可以修改 AI 的行为）。

Answer 2

如果迷宫的入口和出口（start/finish）都通过其他墙与外墙相连（即，一个不在中间的"island"上），则您有一个简单连接的迷宫。

+----S----+
|         |
|   +-F-+ |  <-- OK: "Finish" is connected
|   +---+-|      Simply-connected maze
|         |
+---------+

+----S----+
|         |
|   +-F-+ |  <-- Bad: "Finish" is not connected
|   +---+ |      Maze with Start or Finish on an island
|         |
+---------+

单连通迷宫

如果您没有上述 "island" 情况，您可以使用简单的 "wall follower" 方法，您可以蒙住眼睛（即完全没有视力！）。只需将左手（或右手）放在墙上，然后走路即可。如果您遇到障碍物，请转向允许您将手放在墙上的任何方向。如果有的话，你最终会到达出口。

复杂的"island"迷宫

如果您确实需要处理孤岛，可以使用类似 Trémaux 算法的算法。如果您想到基于 2D 方块的迷宫中的每个空方块，每个方块要么是空的，要么标记一次，要么标记两次。（0、1 或 2 分。）

显然，当访问一个图块时，您会增加标记，因此假设，这里：

开始时，向随机有效方向移动(N/S/E/W)。
当您到达 0 次访问的磁贴时，朝未标记的随机方向行走。
当您到达 1 次访问板块时，转身并原路返回。
否则，转到标记最少的方块。

当您到达出口时，仅标记一次的方块将带您回到起点。

有关详细信息，请参阅 Wikipedia page on maze solving。

视力有限的寻路

Path finding with limited vision

c

algorithm

path-finding

单连通迷宫

复杂的"island"迷宫