为游戏领域创建算法

Question

我目前正在寻找一种方法来检查是否可以访问每个字段，如果可以，是否有一种方法可以在不使用一个字段两次的情况下访问每个字段。我目前的想法是尝试从各个方向开始，将用过的田地用作新墙。如果机器人卡住了，他会重新启动并转向另一个方向。但我不确定这是否行得通。性能怎么样？这真的有用吗？

world/walls和机器人的位置是随机的。机器人不能使用他以前使用过的字段。

这是一个示例图片。

Answer 1

根据您的输入，您可能会使用 breadth first search algorithm 搜索世界，将机器人的起始位置作为树的根。通常，对于 BFS，您会记住在这种特定情况下您已经看到了哪些 'nodes' 或图块。当算法终止时，您可以检查访问的节点列表是否等于您想要到达的节点列表。

我想你可以这样做，如果你知道每个图块都是相邻节点（例如通过引用）。

Answer 2

这个问题可以建模为图中的连通性问题，我们可以在其中运行在迷宫中进行一次深度优先搜索，找到从起始位置可到达的每个位置，如果有任何位置不是wall/block 并且在运行宁 DFS 之后没有访问过，那么你无法从起始位置沿着迷宫中的任何路径到达此位置。

基本上，您需要将游戏中的每个位置表示为图中的一个节点，其中每个节点都有其北墙、东墙、南墙和西墙的标志。当您想通过边缘访问相邻位置时，只有当相邻位置的墙不在您尝试来自的方向上时，您才能这样做。所以你需要做的就是修改DFS算法，在没有墙的情况下，你只能在相邻节点上visit/call dfs。

void explore(Node position)
{
    position.visited = true

    while(position.hasUnvisitedDirection())
    {
        //random unvisited direction
        int direction   =   position.getDirection();

        if(direction == WEST && !west(node).visited && !position.westWall)
            explore(west(node));

        if(direction == EAST && !east(node).visited && !position.eastWall)
            explore(east(node));

        if(direction == SOUTH && !south(node).visited && !position.southWall)
            explore(south(node));

        if(direction == NORTH && !north(node).visited && !position.northWall)
            explore(north(node));

    }
}

这里我们对 DFS 进行了修改，因为我们 select 在我们访问的每个位置都有一个随机未访问的位置。 east(Node)、north(Node) 等调用将 return 分别位于所传递节点的东、北位置 - 注意网格中的边缘情况（如果将图形建模为一个二维数组）。

接下来我们要检查该图是否只有一个强连通分量，如果我们的 DFS 中只有一个跳跃，就会出现这种情况，也就是说，我们将在深度优先搜索森林中有一棵树，并且每个位置都可以从我们的起始位置到达，这就是您想要的。否则，那些在运行ning DFS 之后未访问的节点将无法访问，如果算法 returns 为假，您可以检查这些位置。所以下面应该实现这个：

boolean isConnected(Graph g, Node startPosition)
{
    int jumps   =   0;
    for (Node node : g.nodes())
    {
        if(!node.visited)
        {
            jumps++;
            if(jumps > 1) return false;
            else explore(position);
        }
    }

    return true;
}

Depth first search can be used to generate 并如上所示解迷宫。

Answer 3

所有单元格的可达性很容易，每个单元格只有一个布尔矩阵"reachable"，从机器人起始位置开始传播连接信息，确保所有单元格最终都被标记。这与世界大小成线性关系，所以没有问题。

对于非冗余路径，基本上你需要一个启发式，因为正如其他答案中已经提到的那样，哈密顿路径问题是 NP。然后你编写搜索的 BFS 或 DFS 遍历 space 寻找获胜路径。

我使用了以下启发式方法，它在 "chessboard horse" 上扩展得很好，在国际象棋 "knight" 中，您必须覆盖棋盘上的所有位置。如果从拓扑的角度来看，确实是和你一样的问题

因此，启发式：

在每个单元格中数一数你可以摆脱它的方法的数量。将此信息存储在矩阵中。所以中间的单元格有 4 个，靠墙的单元格只有 3 个等等...
在 DFS 中的每个决策点，select 下一个单元格作为退出次数最少的单元格（这是启发式的核心）
如果两个相邻的单元格在 1 个出站出口，回溯，问题沿着这条分支就死了
当您进入一个单元格时，相邻单元格的退出量递减

冲洗并重复

这只是指导探索，运气不好的话整体复杂度还是很高的。

直觉上，现在去出口较少的区域是好事，因为以后再回到那里会比较困难。具有 1 个退出规则的 2 个单元只是一种优化，但它可以修剪大的子树，这很好。如果根据放置测试的位置检测到具有 0 个出口的未访问单元格，您也可以回溯。

即使在比经典的 8x8 更大的棋盘上，我也可以通过这种启发式轻松地吐出很多解决方案。

Answer 4

我实现了类似这样的东西 here 来解决一个名为 "Knight's Tour" 的谜题。我相信这个问题几乎应该涉及相同的逻辑，并进行一些小的修改。

而不是谈论遍历，我会尝试使它更普遍地访问 - 从任何给定的角度来回答问题 "what is the next best move?" 你想进一步思考并问："what is the most limiting factor?"在这种情况下，根据您的下一个可用动作，最大的限制因素是每个动作有多少可用动作。您的每个下一个可用动作都会有自己的一组下一个可用动作。下一个可用移动的数量最少的下一个可用移动是您最大的限制因素。

因此，例如，假设我有可用的移动 x、y 和 z。 x 和 z 都有 2 个下一个可用移动，y 有 3 个下一个可用移动 - 你想移动到 x 或 z（你决定哪个并不重要，所以你可以像我在代码中那样随机化它）。

为什么这是有道理的？换个角度思考——下一个可用的移动（在我们的示例中为 x、y 和 z）都是您必须在某个时刻到达的位置！ x、y 和 z 的下一个可用移动也可以被视为您将 BACK 返回到 x、y 或 z 的方式。由于返回 x 和 z 的方法较少，您不妨现在就使用其中一种方法。例如，如果 x 只有 1 个下一个可用移动（所有其他条件不变），那么 x 将是您唯一有效的选项（作为优化，您可以立即转到 x 的下一个可用移动，因为您知道只有 1 个）。

我提供的代码有很多你不需要关心的东西，但它应该是自包含的，所以你应该能够将它弹出到 JSFiddle 或 html 页面中并且它应该只是工作。与您的问题相关的函数是 getPossibleMoves、getAvailableMoves 和 getBestNextMove（以及这些函数调用的任何函数）。 getPossibleMoves 函数中的插值点内容与 D3 相关，您无需担心。该函数根据允许骑士如何移动的规则，从一个点（具有 x 和 y 属性）简单地计算所有可能的移动，然后简单地评估这些点中的每一个以查看它们是否在边界内。修改此函数以适应机器人允许的移动应该不会太难，您还需要更新检查点是否在边界内的函数，以禁止有墙的点。

免责声明：我将这段代码放在一起只是为了好玩所以它没有经过优化或者无论如何都是 JavaScript

中编码实践的优秀示例

另请注意，这只是解决此问题的一种方法。当然还有其他方法可以解决它，但这是我所知道的最直接的方法。

为游戏领域创建算法

Creating a algorithm for a game field

algorithm

logic