为游戏场地创建算法

Question

为游戏场地创建算法

7

我正在寻找一种方法来检查是否可以到达每个领域，如果可以的话，是否有不重复使用领域的去到达每个领域的方法。我的想法是尝试从各个方向开始并将使用过的领域作为新的墙壁。如果机器人被卡住了，它会重新开始并选择另一个方向。但我不确定这是否可行。至于性能如何？这样做可行吗？

世界/墙和机器人的位置是随机的。机器人不能使用它之前用过的领域。

以下是示例图像。

- Jannis Lehmann

4

您可能正在寻找类似于“泛洪填充算法”的东西。 - Paul R

3

你也可以考虑使用你自己的规则生成世界。这样，你就可以在二维地图上随机生成一些不重复的连续路径。然后你只需要倒出这条路径上的节点，就可以得到你的地图了。 - dfens

4

你所描述的是汉密尔顿路径问题，这是一个困难的问题。我编写了一个程序，在几毫秒内就可以解决问题中给出的8x10迷宫。但当我将迷宫扩展到完整的10x14网格时，有些配置在运行30秒后仍未得出结果。因此，我同意 @dfens 的看法，最好的方法是使用你的规则生成世界。 - user3386109

1

@user3386109 是正确的。哈密顿路径问题不仅困难，而且是NP完全问题。 “尽管可以快速验证（在多项式时间内）NP完全问题的任何给定解决方案，但没有已知的有效方法来首先找到解决方案; 实际上，NP完全问题最显着的特征是不知道如何快速解决它们。” https://en.wikipedia.org/wiki/NP-completeness 除非在计算机科学领域取得了巨大突破，否则您将无法获得详细的规范答案。 - Erick G. Hagstrom

我在想，简单的搜索算法（如广度优先、深度优先等）甚至是有启发式的算法（如A、IDA），是否能够处理这个问题的规模。我的意思是，可以用某种技术来建模问题，并不意味着该技术在某些给定的维度上能够解决该问题。我建议在文献中寻找最好的已知算法来解决哈密顿路径问题，并从实现较简单的算法开始。 - eguaio

显示剩余8条评论

4个回答

1

所有单元格的可达性都很容易，只需要为每个单元格创建一个布尔矩阵“reachable”，从机器人起始位置开始传播连通性信息，确保所有单元格都被标记。这与世界大小成线性关系，因此没有问题。

对于非冗余路径，基本上需要一种启发式方法，因为如其他答案中已经提到的汉密尔顿路径问题是NP问题。然后，编写搜索空间的BFS或DFS遍历以寻找获胜路径。

我在“棋盘马”问题上使用了以下启发式方法，在这个问题中，您需要用“骑士”走法覆盖棋盘上的所有位置。如果你从拓扑的角度来看待它，它实际上是与你的问题相同的问题。

所以，这是启发式方法：

在每个单元格中计算可以离开该单元格的方式数量。将此信息存储在矩阵中。因此，中间单元格得到4个，靠近墙壁的单元格只有3个等...
在DFS的每个决策点上，选择下一个单元格作为出口最少的单元格（这是启发式的核心）
如果两个相邻单元格的出口数为1，则回溯，该分支的问题已死
进入单元格时，减少相邻单元格的出口数量

洗涤并重复

这只是引导探索，如果你运气不好，整体复杂度仍然很高。

直觉上，现在最好去出口较少的区域，因为以后回到这些区域会更加困难。有一个只有1个出口的2个单元格规则，这只是一种优化，但它可以修剪大的子树，这是好的。根据测试放置的位置，如果检测到未访问的0个出口的单元格，则还可以进行回溯。

即使在比经典的8x8更大的棋盘上，我也能轻松地用这个启发式方法找到很多解决方案。

- Yann TM

0

我已经实现了类似于这里的东西来解决一个名为“骑士之旅”的难题。我相信这个问题应该涉及相同的逻辑，只需要进行一些小的修改。

与其谈论遍历，不如让我们更普遍地考虑——从任何给定点开始，回答“下一步最好的移动是什么？”这个问题，你需要再思考一步，并问：“最具限制性的因素是什么？”在这种情况下，根据你的下一个可用移动，最具限制性的因素是每个移动可用的移动次数。每个你的下一个可用移动都将有自己的下一个可用移动集合。拥有最少数量的自己的下一个可用移动的下一个可用移动是你最具限制性的因素。

例如，假设我有可用的移动x、y和z。x和z都有2个下一个可用移动，而y有3个下一个可用移动——你想要移动到x或z（你可以像我在代码中所做的那样随机选择其中一个，这并不重要）。

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

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

免责声明：我只是为了好玩而把这段代码组合起来的，因此它并没有经过优化，也不是JavaScript编程实践的绝佳示例。

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

- Jordan

0

这个问题可以建模为一个图形连通性问题，在迷宫上运行一次深度优先搜索，找到从起始位置可达的每个位置。如果在运行DFS后，有任何未被访问且不是墙/阻挡物的位置，则说明无法通过任何迷宫路径从起始位置到达该位置。

实质上，您需要将游戏中的每个位置表示为图形中的节点，其中每个节点都有其北、东、南和西侧墙的标志。当您想要通过边访问相邻位置时，只有在您试图来自的方向上没有相邻位置的墙壁时，才能这样做。因此，您只需要对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进行修改，每次访问一个位置时选择一个随机未访问的位置。 east（Node），north（Node）等调用将返回传递的节点东、北方向的位置，请注意网格中的边缘情况（如果您将图形建模为2D数组，则相当直观）。

接下来，我们想要检查图是否只有一个强连通分量，如果在DFS中只有一个跳跃，则是这种情况，即深度优先搜索森林中只有一棵树，并且可以从起始位置到达每个位置，这正是您想要的结果。否则，在运行DFS后未被访问的节点将是无法访问的，您可以在之后检查这些位置以查看算法是否返回false。因此，以下内容应该能够实现此目的：

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;
}

深度优先搜索可以用于像上面展示的那样生成和解决迷宫问题。

- kyleruss

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Glubus · Accepted Answer

根据您的输入，您可以使用广度优先搜索算法，以机器人起始位置为树的根，在整个世界中进行搜索。通常情况下，使用BFS时您会记住已经看过的“节点”或瓷砖。当算法终止时，您可以检查访问过的节点列表是否等于要到达的节点列表。

我认为，如果您知道每个瓷砖的相邻节点是哪些（例如通过引用），那么您就可以这样做。