经过几个小时的调试,该算法似乎有效。现在要检查它是否有效,我正在检查 while 循环退出时到 currentNode 位置的结束节点位置。到目前为止,这些值看起来是正确的。问题是,我离当前静止的 NPC 越远,性能就越差。它达到了游戏无法播放低于 10 fps 的地步。我当前的 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 = ¤tNode;
}
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 = ¤tNode;
}
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 = ¤tNode;
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;
}
}
最佳答案
您对“打开列表”和“关闭列表”都使用单链表,从而导致不必要的线性时间操作。
前者应该是 priority queue ( heap ),而后者最好实现为 哈希表 .
关于artificial-intelligence - A* PathFinding 性能不佳,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9983781/