-1

私のパスファインディングは、障害物がない状態で移動する場合、または障害物の上部から側面に移動する場合は正常に機能しますが、障害物の上部から下部への移動を見つける必要がある場合は遅すぎます。

私はそれが各ループをソートする方法または閉集合を介してループする方法であるとかなり確信していますが、SortedListsはWindows Phone 7で利用できないため、これを回避する方法がわかりません

//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）時間かかり、グラフの頂点ごとに1回リストを並べ替えます。これにより、V ^ 2 * log（V）時間かかるアルゴリズムが生成されます。ここで、Vは頂点の数です。ソートされていないリストを保持するだけの場合は、すべてのアイテムをループし、これまでの最小のアイテムの数を保持することで、線形時間で最小値を抽出できます。この場合、時間はV^2になります。これはほんの小さな改善です。もちろん、適切な優先度キュー（バイナリヒープに基づくキューなど）を使用する場合）その後、アルゴリズムははるかに高速に実行されます。それ以降、操作のコストはlog（n）のみです。独自のバイナリヒープをコーディングすることはそれほど難しくありません。プラットフォームがネイティブヒープをサポートしていない場合は、それを行うことを強くお勧めします。この場合、挿入と最小値の検出にはlog（n）時間しかかからず、結果としてE log V時間になります（ここで、Eはエッジの数であり、平面グラフではVに比例します）。

于 2012-04-15T18:36:26.967 に答える