波前算法

Question

我正在创建一个迷宫程序,迷宫是随机生成的,用户必须找到一个随机放置的立方体.现在,我希望能够让游戏以解决本身,使用波前算法, Dijkstra算法或 A*算法？

这是生成迷宫墙的代码.

    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 Game Developement by Example一书.我做的唯一真正的编辑是RandomWalls()方法.

Answer 1

我认为波前算法可能有点太复杂而无法用于此问题,因此在我的回答中我将关注其他两个图搜索算法.

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

1. 将地图中的每个方块(平铺)表示为图形中的节点.
2. 如果在任何两个给定的相邻方块之间没有边缘,则在两个节点之间存在表示这些方块的边缘.

完成后,您将需要分配权重.因为在你的情况下你似乎没有任何偏好超过一个边缘或另一个边缘,给每个边缘成本1应该没问题.

之后将生成加权图,您需要搜索它.我认为这两个最流行的算法Dijkstra's Shortest Path Algorithm和A*算法.

根据我的理解,你没有关于立方体放置位置的信息,在我看来,这意味着你不能使用,A*因为A*基础本身就是启发式,在这种情况下可以是当前节点和当前节点之间的距离.目标节点是你不知道的东西.

因此,剩下的唯一选择是Shortest Path Algorithm.但是,要执行此操作,您需要稍微修改搜索的停止条件,因为您需要检查每个节点为其内容表示的方块.如果你找到了你想要的东西,你就停下来.

另一方面,如果由于某种原因你将不得不使用负权重,那么Shortest Path意志将不再起作用.为此,您需要使用相同的方法,但使用a Label Correcting Algorithm或Bellman-Ford Algorithm.

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

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

Manhattan distance (见下图)应该很好地作为算法的启发式部分,因为看起来你不能对角地遍历方块,因此,计算距离(Euclidean)的最常用方法效果会较差.