为游戏领域创建一个算法

 

我目前正在寻找一种方法来检查每个字段是否可到达，如果是的话，是否有办法在不使用字段两次的情况下到达每个字段。 我目前的想法是尝试从各个方向开始，并将使用过的领域用作新墙。 如果机器人卡住了，他会重新启动并进入另一个方向。 但我不确定这是否会起作用。 表演怎么样？ 这甚至工作吗？

世界/墙壁和机器人的位置是随机的。 机器人不能使用他以前使用过的字段。

这是一个示例图像。 在这里输入图像描述

根据您的输入，您可以使用广度优先搜索算法，搜索具有机器人起始位置的世界作为树的根。 通常在BFS中，您可以记住您已经看到的特定情况下的哪些“节点”或磁贴。 算法终止时，您可以检查访问的节点列表是否等于您想要到达的节点列表。

我认为你可以这样做，如果你知道每个瓦片是相邻的节点（例如参考）。

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

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

我使用了以下启发式，可以在“棋盘马”上进行很好的缩放，在这里棋子“骑士”必须覆盖棋盘上的所有位置。 如果你从拓扑的角度来看待它，这和你的问题是一样的。

所以，启发式：

  • 在每个细胞中计数你可以从中获得的方法数量。 将此信息存储在矩阵中。 所以一个中间的细胞得到4，一个细胞旁边的墙壁只有3等...
  • 在DFS中的每个决策点处，选择下一个单元作为退出次数最少的单元（这是启发式的核心）
  • 如果两个相邻的单元位于1个出口出口，回溯，则问题沿着该分支死亡
  • 当你输入一个单元格减少相邻单元格的退出

    • 冲洗并重复

    这只是指导探索，如果你不走运，这种探索仍然很复杂。

    直观地说，现在去那些退出较少的地区是很好的，因为稍后再回到这些地方会更困难。 具有1个退出规则的2个单元只是一种优化，但它可以修剪较大的较大的子树。 如果您根据放置测试的位置检测出未访问的单元格，则可以退出原始单元格。

    我有这种启发式的方式，即使在比传统的8x8更大的棋盘上也可以轻松地分发大量解决方案。

    这个问题可以模拟为一个图形中的连通性问题，我们可以在迷宫中运行一次深度优先搜索，并找到从起始位置到达的每个位置，如果任何位置不是墙/块，并且在运行DFS后未访问那么在迷宫中的任何路径之后，您都无法从起始位置到达此位置。

    从本质上讲，您需要将游戏中的每个位置都表示为图形中的一个节点，其中每个节点都有针对它的北，东，南和西墙的标志。 当您想通过边缘访问相邻位置时，只有在相邻位置的墙壁不在您尝试来的方向时才可以这样做。 因此，您只需对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)等调用将分别返回通过节点的东，北分别位置 - 小心网格中的边缘情况（如果将图形建模为二维数组，则非常直观）。

    接下来，我们要检查图中是否只有一个强连通的组件，如果我们的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;
}

    如上所示，深度优先搜索可用于生成和解决迷宫。

    链接地址: http://www.djcxy.com/p/29059.html

    上一篇: Creating a algorithm for a game field

    下一篇: How to stop creating .stat file in Delphi 10 Seattle IDE