c# - 波前算法

Question

我正在创建一个迷宫程序，其中的迷宫是随机生成的，用户必须找到一个随机放置的立方体。现在，我希望能够让游戏自行解决，使用 wavefront algorithm , Dijkstra's algorithm ，或 A* algorithm ？

这是生成迷宫墙的代码。

    public void GenerateMaze()
    {
        for (int x = 0; x < mazeWidth; x++)
            for (int z = 0; z < mazeHeight; z++)
            {
                MazeCells[x, z].Walls[0] = true;
                MazeCells[x, z].Walls[1] = true;
                MazeCells[x, z].Walls[2] = true;
                MazeCells[x, z].Walls[3] = true;
                MazeCells[x, z].Visited = false;
            }
        MazeCells[0, 0].Visited = true;
        EvaluateCell(new Vector2(0, 0));
    }

    public void resetMaze()
    {
        for (int x = 0; x < mazeWidth; x++)
            for (int z = 0; z < mazeHeight; z++)
            {
                MazeCells[x, z].Visited = false;
            }

        RandomWalls(new Vector2(0, 0));
    }

    private void EvaluateCell(Vector2 cell)
    {
        List<int> neighborCells = new List<int>();
        neighborCells.Add(0);
        neighborCells.Add(1);
        neighborCells.Add(2);
        neighborCells.Add(3);

        while (neighborCells.Count > 0)
        {
            int pick = rand.Next(0, neighborCells.Count);
            int selectedNeighbor = neighborCells[pick];
            neighborCells.RemoveAt(pick);

            Vector2 neighbor = cell;

            switch (selectedNeighbor)
            {
                case 0: neighbor += new Vector2(0, -1);
                    break;
                case 1: neighbor += new Vector2(1, 0);
                    break;
                case 2: neighbor += new Vector2(0, 1);
                    break;
                case 3: neighbor += new Vector2(-1, 0);
                    break;
            }

            if (
                (neighbor.X >= 0) &&
                (neighbor.X < mazeWidth) &&
                (neighbor.Y >= 0) &&
                (neighbor.Y < mazeHeight)
                )
            {
                if (!MazeCells[(int)neighbor.X, (int)neighbor.Y].Visited)
                {
                    MazeCells[(int)neighbor.X, (int)neighbor.Y].Visited = true;
                    MazeCells[(int)cell.X, (int)cell.Y].Walls[selectedNeighbor] = false;
                    MazeCells[(int)neighbor.X, (int)neighbor.Y].Walls[(selectedNeighbor + 2) % 4] = false;
                    EvaluateCell(neighbor);
                }
            }
        }
    }

    //Removes random walls
    private void RandomWalls(Vector2 cell)
    {
        List<int> neighborCells = new List<int>();
        neighborCells.Add(0);
        neighborCells.Add(1);
        neighborCells.Add(2);
        neighborCells.Add(3);

        while (neighborCells.Count > 0)
        {
            int pick = rand.Next(0, neighborCells.Count);
            int selectedNeighbor = neighborCells[pick];
            neighborCells.RemoveAt(pick);

            Vector2 neighbor = cell;

            switch (selectedNeighbor)
            {
                case 0: neighbor += new Vector2(0, -1);
                    break;
                case 1: neighbor += new Vector2(1, 0);
                    break;
                case 2: neighbor += new Vector2(0, 1);
                    break;
                case 3: neighbor += new Vector2(-1, 0);
                    break;
            }

            //Ensures that end piece is not deleted
            if (
                (neighbor.X >= 0) &&
                (neighbor.X < mazeWidth) &&
                (neighbor.Y >= 0) &&
                (neighbor.Y < mazeHeight)
                )
            {

                //if cell was not visited
                if (!MazeCells[(int)neighbor.X, (int)neighbor.Y].Visited)
                {
                    Random random = new Random();

                    MazeCells[(int)neighbor.X, (int)neighbor.Y].Visited = true;

                    //if random number is >= a certain number, removes the walls on both ends
                    if (random.Next(20) >= 15 && removed <= 100)
                    {
                        //MazeCells[(int)neighbor.X, (int)neighbor.Y].Visited = true;
                        MazeCells[(int)cell.X, (int)cell.Y].Walls[selectedNeighbor] = false;
                        MazeCells[(int)neighbor.X, (int)neighbor.Y].Walls[(selectedNeighbor + 2) % 4] = false;
                        removed++;
                    }

                    RandomWalls(neighbor);
                }
            }
        }
    }

对于缺少注释，我深表歉意，但本质上它是将所有单元格放入一个盒子中，然后撕掉墙壁，以便您可以到达迷宫中的任何单元格。然后我只是移除了一些额外的单元格，这样迷宫就不会让人感到幽闭恐怖。

这是迷宫的图片:

迷宫周围有墙，将玩家留在里面，以防他们很难被看到。通常，您更多地将其视为第一人称视角。

那么，目标:现在，我想让相机找到立方体的位置，以及相机的位置，然后找到两者之间的最短路线。然后，我想让相机慢慢地沿着路线到达那里，直到它碰到立方体。现在，我应该使用哪种算法，以及如何使用。

如果有帮助，此代码几乎完全来自 XNA 4 3D 游戏开发示例 一书。我所做的唯一真正的修改是 RandomWalls() 方法。

Answer 1

我认为波前算法可能有点太复杂而无法用于此问题，因此在我的回答中我将研究其他两种图形搜索算法。

您需要采取的第一步是生成迷宫的图形表示。我认为最简单的方法是:

1. 将 map 中的每个方 block (方 block )表示为图中的一个节点。
2. 如果任意两个给定的相邻 方 block 之间没有边，则表示这些方 block 的两个节点之间有一条边。

完成后，您需要分配权重。由于在您的情况下您似乎对一条边或另一条边没有任何偏好，因此为每条边赋予 1 的成本应该没问题。

生成加权图后，您需要对其进行搜索。我认为两个最流行的算法是 Dijkstra's Shortest Path Algorithm和 A*算法。

据我了解，您不知道立方体的放置位置，我认为这意味着您不能使用 A*，因为 A* 以启发式为基础，在这种情况下，它可能是当前节点与目标节点之间的距离，这是您不知道的。

因此，剩下的唯一选择就是最短路径算法。然而，要做到这一点，您需要稍微修改搜索的停止条件，因为您需要检查每个节点代表其内容的方 block 。如果找到您正在寻找的东西，您就会停下来。

另一方面，如果出于某种原因您必须使用负权重，则最短路径 将不再起作用。为此，您将需要使用相同的方法，但是，请使用 Label Correcting Algorithm或 Bellman-Ford Algorithm .

一旦您获得了从源节点到目标节点的最短路径，您就可以提取一系列向量，这些向量将使您从一个方格移动到下一个方格。获得这些向量之后，您应该能够按照 this 中的说明移动相机。 MSDN 教程。

编辑:你问题中的这一行:所以，目标:现在，我希望相机找到立方体的位置让我明白你事先不知道立方体在哪里.如果不是这种情况，那么根据@Gene 的评论，A* 算法将更合适，因为(假设您知道目标在哪里)它会更有效率。

Manhattan distance(见下图)应该很好地作为你算法的启发式部分，因为你似乎不能对角地遍历方 block ，因此，最常见的计算距离的方法(欧几里得) 效果会较差。