具有有限视觉的路径查找

Question

我正在制作一个基于二维瓷砖的迷宫游戏，我正在尝试编程一个人工智能玩家，可以找到它的路径通过迷宫。不同于一般的路径发现，我想限制每个玩家(包括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
}

有什么办法可以解决这个问题呢？我在想，我可以宣布一个数组大小的整个地图，并记录的愿景，人工智能球员的地图。但是后来我被困在该怎么做next...any的主意上了？谢谢。

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
|         |
+---------+

简单连接的迷宫

如果你没有像上面这样的“孤岛”情况，你可以使用简单的“墙跟随者”的方法，你可以蒙住眼睛(即根本没有视觉！)把你的左手(或右手)放在墙上，然后走。如果你到达一个障碍，转到任何一个方向，你可以让你的手在墙上。如果有出口的话，你最终会到达出口。

复杂的“岛”迷宫

如果您必须处理岛屿，您可以使用类似Trémaux的算法。如果你想到二维瓷砖迷宫中的每个空瓷砖，那么每个瓷砖要么是空的，要么是标记一次，或者是两次。(0、1或2标记)

显然，当访问一个瓷砖时，您会增加标记，因此假设如下：

• 在开始时，向一个随机有效方向移动(N/S/E/W)。
• 当你到达一个0访问瓷砖时，沿着一个没有标记的随机方向走.
• 当你到达一次访问瓷砖，转身，走回来的方式你来了。
• 否则，用最少的标记去瓷砖。

当你到达出口时，标上一次标记的瓷砖将把你带回起点。

有关更多信息，请参见关于迷宫解决的维基百科页面。

Answer 2

这是可以做到的，运行两个不同的路径搜索嵌入在彼此。一种算法分析玩家可以看到的迷宫补丁(没有玩家的移动)。另一种算法是移动人工智能本身并搜索路径。分析迷宫中可见部分的算法被用来搜索可能的进一步路径以寻找人工智能。这样，AI就可以在不知情的情况下分析整个迷宫。

路径查找本身是特定于实现的，除了BFS、DFS和其他路径查找算法之外，还有一个很好的可用算法列表(算法)。

所使用的算法取决于人工智能的行为。例如，墙跟随算法很容易实现，但如果AI代表游戏中的一个字符，它会显得相当愚蠢。最有效的算法可能是A*，具有适当的启发式(通过该算法可以修改AI的行为)。