如何加快我的A*寻路速度？

Question

当没有障碍物移动或从障碍物的顶部移动到侧面时,我的寻路工作正常,但是当它需要从障碍物的顶部到底部找到它时,它太慢了.

我很确定这是我排序每个循环或循环通过封闭集的方式,但我不知道如何避免这种情况,因为在Windows Phone 7上没有SortedLists

//This Vivid Destination means it doesn't have to find the exact location 
//which is helpful as it is continuous environment  
Rectangle vividDestination = new Rectangle((int)character.destination.X - 10, (int)character.destination.Y - 10, 20, 20);

while (!vividDestination.Contains(Maths.vectorToPoint(OpenNodes[0].position)))
{
    Node Current = OpenNodes[0];
    OpenNodes.RemoveAt(0);
    ClosedNodes.Add(Current);
    Current.calculateNeightbours();

    foreach (Node neighbour in Current.neighbours)
    {
        neighbour.parents = Current.parents + 1;
        //The cost of the node is the amount of parent nodes + the distance to destination
        neighbour.cost = calculateCost(neighbour.position, character.destination, neighbour.parents);

        for (int i = 0; i < OpenNodes.Count; i++)
        {
            //Round Vector rounds the floats in the Vector to the nearest integer
            if (Maths.roundVector(OpenNodes[i].position) == Maths.roundVector(neighbour.position) && OpenNodes[i].parents < neighbour.parents)
            {
                break;
            }
            else
            {
                OpenNodes.RemoveAt(i);
                OpenNodes.Add(neighbour);
                i--;
                break;
            }
        }

        bool closedNode = false;
        for (int i = 0; i < ClosedNodes.Count; i++)
        {
            if (Maths.roundVector(ClosedNodes[i].position) == Maths.roundVector(neighbour.position))
            {
                closedNode = true;
                break;
            }
        }

        if (!closedNode)
        {
            OpenNodes.Add(neighbour);
        }
    }

    OpenNodes = OpenNodes.OrderBy(item => item.cost).ToList();
}

Answer 1

你在做什么是非常低效的.列表的排序需要n*log(n)时间,并且您可以为图表中的每个顶点对列表排序一次.这导致算法采用V ^ 2*log(V)时间,其中V是顶点的数量.如果您只是保留一个未排序的列表,那么您可以通过循环所有项目并保持最低值的计数来提取线性时间的最小值.在这种情况下,时间变为V ^ 2.这只是一个微小的改进.当然,如果你使用一个适当的优先级队列(比如一个基于二进制堆的队列),那么算法将运行得更快,更快,因为那时操作只花费log(n).编写自己的二进制堆并不是太困难,如果平台本身不支持,我强烈建议你这样做.在这种情况下,插入并找到最小值仅占用log(n)时间,得到E log V时间(其中E是边缘数,在平面图中与V成比例).