BFS搜索函数

Question

通过分析我的应用程序，我发现我的应用程序的瓶颈是下面的函数。特别是，它将由许多实体(怪物)在一个游戏中执行，这将在智能手机上。

图是这种类型的网格的模型：(最后一个是25x45)

另外，每个单元格都有一个由4个指针组成的数组:如果单元格是IsNorthPassable，那么它有一个指向Up单元格的指针(如果不是null )。

如果我对其他课程有更多的了解，请告诉我。

private List<Cell> FindPath(Cell A, Cell B)
{
    var parent = new Dictionary<Cell, Cell>();

    List<Cell> queue = new List<Cell>();
    List<Cell> visited = new List<Cell>();

    queue.Add(A);
    parent.Add(A, null);

    while (queue.Count != 0)
    {
        Cell c = queue[0];
        queue.RemoveAt(0);

        visited.Add(c);

        if (c == B)
            break;

        foreach (Cell near in c.Links)
        {
            if (near != null)
            {
                if (!visited.Contains(near))
                {
                    parent.Add(near, c);
                    visited.Add(near);
                    queue.Add(near);
                }
            }
        }
    }

    List<Cell> path = new List<Cell>();

    if (parent.ContainsKey(B))
    {
        Cell backTrack = B;
        do
        {
            path.Add(backTrack);
            backTrack = parent[backTrack];
        }
        while (backTrack != null);
        path.Reverse();
    }

    return path;
}

Answer 1

看着密码我没看到什么奇怪的东西。

关于搜索速度的优化，我建议使用迭代深化算法和启发式函数 (连接点A和点B的线路的坡度可以用来建立一个很好的启发式函数)。

关于更多的信息/帮助，我建议询问堆栈溢出，因为我不知道这是否是正确的网站。

Answer 2

我花了很多时间来优化路径查找代码。最重要的是只在需要的时候运行路径查找器：

• 如果所有怪物都在同一个地方开始或结束，您可以在整个图上运行一次BFS，并缓存结果。然后找到怪物需要移动的方向总是O(1)。
• 对于大多数游戏来说，最短路径的近似是可以接受的。HPA*是一个非常好的算法，它易于编程和理解。有关其他选项，请参见这个职位。

至于你的具体执行情况：

• 如前所述，请确保使用正确的数据结构，队列使用Queue，访问节点使用Set。
• 将其转换为一个*相当简单，后者应该具有更好的性能。您需要用优先级队列替换队列。我已经为C#编写了一个，它已经为路径查找进行了高度优化。您也可以找到这里.，请确保使用正确的断系准则。

Answer 3

并不是为了让它变得更有效率，而是为了让它更漂亮，尽量不要比你必须做的更多。

foreach (Cell near in c.Links) { if (near != null) { if (!visited.Contains(near)) { parent.Add(near, c); visited.Add(near); queue.Add(near); } } }

您应该在下面的for循环中合并两个if语句，如下所示

foreach (Cell near in c.Links)
{
    if ((near != null) && (!visited.Contains(near)))
    {
        parent.Add(near, c);
        visited.Add(near);
        queue.Add(near);
    }
}