经过几个小时的调试，算法似乎已经正常工作了。现在为了验证其是否工作，我在while循环结束时检查结束节点的位置和当前节点的位置。到目前为止，数值看起来是正确的。问题是，当我离当前静止的NPC越远，性能就越差。到了游戏帧率低于10帧，几乎无法玩的地步。我现在的路径图有2500个节点，我认为这已经相当小了，对吗？有什么提高性能的建议吗？

struct Node{    bool walkable;      //这个节点是否被阻挡或开放    vect2 position;     //地图上瓦片的位置，以像素为单位    int xIndex, yIndex; //瓦片在数组中的索引值    Node*[4] connections; //当前节点连接到的节点指针数组    Node* parent;    int gScore;    int hScore;    int fScore;}class AStar{    private:    SList!Node openList;    //已访问但未处理的节点列表，带有F分数    SList!Node closedList;  //已处理其连接的节点列表    //Node*[4] connections;     //当前节点的连接;    Node currentNode;           //正在处理的当前节点    Node[] Path;        //找到的路径;    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;    }    //这个函数当前会导致程序进入无限循环    //我还需要调试以找出为什么父节点不正确    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 看起来找到了路径，但现在性能非常差    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( "当前节点位置: ", currentNode.position );        writeln( "结束节点位置: ", end.position );        if( currentNode.position == end.position )        {            writeln( "当前节点的父节点: ", currentNode.parent );           //GeneratePath();           //ReversePath();        }    }    Node[] GetPath()    {        return Path;    }}

回答：

你使用单向链表来存储“开放列表”和“关闭列表”，这导致了不必要的线性时间操作。

前者应该使用优先级队列（堆），而后者最好使用哈希表实现。