-1

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

我相当确定这是我对每个循环进行排序或通过封闭集循环的方式，但我不确定如何避免这种情况，因为 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();
}
4

1 回答 1

8

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

于 2012-04-15T18:36:26.967 回答