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

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

这是迷宫的俯 View :

迷宫周围有墙，可以将玩家限制在里面，以防很难看到。通常，您更多地将其视为第一人称的观点。

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

如果有帮助的话，这段代码几乎完全来自XNA 4 3D Game Developement by Example一书。我所做的唯一真正的编辑是 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* 算法将更合适，因为(假设您知道您的目标在哪里)它将更有效。

曼哈顿距离(见下图)应该很好地充当算法的启发式部分，因为似乎您无法对角线遍历方 block ，因此，计算距离的最常见方法(欧几里得)的效果会较差。