c - 视力有限的寻路

Question

我正在制作一个基于 2D 方 block 的迷宫游戏，并且我正在尝试编写一个可以在迷宫中找到路径的 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
}

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

Answer 1

如果迷宫的入口和导出(开始/结束)都通过其他墙连接到外墙(即，一个不在中间的“孤岛”上)，则您有一个简单连接的迷宫。

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

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

简单连接的迷宫

如果你没有像上面那样的“孤岛”情况，你可以使用简单的“wall follower”方法，你可以蒙住眼睛(即完全没有视力!)。只需将左手(或右手)放在墙上，然后走路即可。如果您遇到障碍物，请转向允许您将手放在墙上的任何方向。如果有导出，您最终会到达导出。

复杂的“岛屿”迷宫

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

显然，当访问一个图 block 时，您会递增标记，因此假设:

• 开始时，沿随机有效方向 (N/S/E/W) 移动。
• 当您到达一个 0-visit 方 block 时，朝未标记的随机方向行走。
• 当您到达 1-visit 板 block 时，转身并原路返回。
• 否则，转到标记最少的方 block 。

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

参见 Wikipedia page on maze solving获取更多信息。