A* PathFinding性能不佳

Question

经过几个小时的调试，该算法似乎正在工作。现在，为了检查它是否工作，我正在检查while循环退出时的currentNode位置的结束节点位置。到目前为止，这些值看起来是正确的。问题是，我离NPC越远，谁现在是静止的，性能就越差。它到达了一个点，即游戏不能玩到低于10帧/秒。我目前的PathGraph是2500个节点，我认为这是相当小的，对吧？对如何提高性能有什么建议吗？

struct Node
{
    bool walkable;      //Whether this node is blocked or open
    vect2 position;     //The tile's position on the map in pixels
    int xIndex, yIndex; //The index values of the tile in the array
    Node*[4] connections; //An array of pointers to nodes this current node connects to
    Node* parent;
    int gScore;
    int hScore;
    int fScore;
}

class AStar
{
    private:
    SList!Node openList;    //List of nodes who have been visited, with F scores but not processed
    SList!Node closedList;  //List of nodes who have had their connections processed

    //Node*[4] connections;     //The connections of the current node;

    Node currentNode;           //The current node being processed

    Node[] Path;        //The path found;

    const int connectionCost = 10;

    Node start, end;

//////////////////////////////////////////////////////////

    void AddToList(ref SList!Node list, ref Node node )
    {
        list.insert( node );
    }

    void RemoveFrom(ref SList!Node list, ref Node node )
    {
        foreach( elem; list )
        {
            if( node.xIndex == elem.xIndex && node.yIndex == elem.yIndex )
            {
                auto a = find( list[] , elem );
                list.linearRemove( take(a, 1 ) );
            }
        }
    }


    bool IsInList( SList!Node list, ref Node node )
    {
        foreach( elem; list )
        {
            if( node.xIndex == elem.xIndex && node.yIndex == elem.yIndex )
                return true;
        }

        return false;
    }

    void ClearList( SList!Node list )
    {
        list.clear;
    }

    void SetParentNode( ref Node parent, ref Node child )
    {
        child.parent = &parent;
    }

    void SetStartAndEndNode( vect2 vStart, vect2 vEnd, Node[] PathGraph )
    {
        int startXIndex, startYIndex;
        int endXIndex, endYIndex;

        startXIndex = cast(int)( vStart.x / 32 );
        startYIndex = cast(int)( vStart.y / 32 );

        endXIndex = cast(int)( vEnd.x / 32 );
        endYIndex = cast(int)( vEnd.y / 32 );

        foreach( node; PathGraph )
        {
            if( node.xIndex == startXIndex && node.yIndex == startYIndex )
            {
                start = node;
            }
            if( node.xIndex == endXIndex && node.yIndex == endYIndex )
            {
                end = node;
            }
        }
    }

    void SetStartScores( ref Node start )
    {
        start.gScore = 0;

        start.hScore = CalculateHScore( start, end );

        start.fScore = CalculateFScore( start );

    }

    Node GetLowestFScore()
    {
        Node lowest;

        lowest.fScore = 10000;

        foreach( elem; openList )
        {
            if( elem.fScore < lowest.fScore )
                lowest = elem;
        }

        return lowest;
    }

    //This function current sets the program into an infinite loop
    //I still need to debug to figure out why the parent nodes aren't correct
    void GeneratePath()
    {
        while( currentNode.position != start.position )
        {
            Path ~= currentNode;
            currentNode = *currentNode.parent;
        }
    }

    void ReversePath()
    {
        Node[] temp;
        for(int i = Path.length - 1; i >= 0; i-- )
        {
            temp ~= Path[i];
        }
        Path = temp.dup;
    }

    public:
    //@FIXME It seems to find the path, but now performance is terrible
    void FindPath( vect2 vStart, vect2 vEnd, Node[] PathGraph )
    {
        openList.clear;
        closedList.clear;

        SetStartAndEndNode( vStart, vEnd, PathGraph );
        SetStartScores( start );
        AddToList( openList, start );

        while( currentNode.position != end.position )
        {
            currentNode = GetLowestFScore();

            if( currentNode.position == end.position )
                break;
            else
            {
                RemoveFrom( openList, currentNode );
                AddToList( closedList, currentNode );

                for( int i = 0; i < currentNode.connections.length; i++ )
                {
                    if( currentNode.connections[i] is null )
                        continue;
                    else
                    {
                        if( IsInList( closedList, *currentNode.connections[i] ) 
                           && currentNode.gScore < currentNode.connections[i].gScore )
                        {
                            currentNode.connections[i].gScore = currentNode.gScore + connectionCost;
                                 currentNode.connections[i].hScore = abs( currentNode.connections[i].xIndex - end.xIndex ) 
                            + abs(     currentNode.connections[i].yIndex - end.yIndex );
                            currentNode.connections[i].fScore =     currentNode.connections[i].gScore +   currentNode.connections[i].hScore;
                            currentNode.connections[i].parent = &currentNode;
                        }
                        else if( IsInList( openList, *currentNode.connections[i] ) 
                                && currentNode.gScore < currentNode.connections[i].gScore )
                        {
                            currentNode.connections[i].gScore = currentNode.gScore + connectionCost;
                            currentNode.connections[i].hScore = abs( currentNode.connections[i].xIndex - end.xIndex ) 
                            + abs(     currentNode.connections[i].yIndex - end.yIndex );
                            currentNode.connections[i].fScore = currentNode.connections[i].gScore + currentNode.connections[i].hScore;
                            currentNode.connections[i].parent = &currentNode;
                        }
                        else
                        {

                            currentNode.connections[i].gScore = currentNode.gScore + connectionCost;
                            currentNode.connections[i].hScore = abs( currentNode.connections[i].xIndex - end.xIndex ) 
                            + abs( currentNode.connections[i].yIndex - end.yIndex );
                             currentNode.connections[i].fScore = currentNode.connections[i].gScore +     currentNode.connections[i].hScore;
                            currentNode.connections[i].parent = &currentNode;
                            AddToList( openList, *currentNode.connections[i] );
                        }
                    }   
                }
            }
        }

        writeln( "Current Node Position: ", currentNode.position );
        writeln( "End Node Position: ", end.position );

        if( currentNode.position == end.position )
        {
            writeln( "Current Node Parent: ", currentNode.parent );
           //GeneratePath();
           //ReversePath();
        }
    }

    Node[] GetPath()
    {
        return Path;
    }
}

Answer 1

您对“开放列表”和“关闭列表”都使用了单链表，这导致了不必要的线性时间操作。

前者应该是一个 (heap)，而后者最好实现为哈希表。

Answer 2

使用未排序的链表作为初学者的数据结构

A*依赖log(n)插入pop和update节点才能正常工作

在min heap上查看

Answer 3

在实现Eric Lippert的A-*算法时，我发现使用HashSet<> (使用散列算法return x<<16 ^ y)或boolWidth，Height来实现closed没有明显的时间差。

我通过替换Eric的PrioirtyQueue<> (使用带有手卷MinHeap<>的SortedDIctionary<>)实现)，能够将性能提高约40%。这是一个大约420x750六角的战争游戏地图，测量地图上的几条长对角线路径。