Hi, so I have this game which I'm working on and I have implemented A* pathfinding algorithm, but the problem is that the game framerate drops significantly if there are more than 50-100 enemies which need to find path to player.
I did some code analyzing and noticed that the part which takes longest to process is part where it searches for node with the lowest F score. Is there anyway I could speed the process up?
Here's the code I'm using:
public ArrayList<Node> getPath(Node start, Node end){
closedSet.clear();
openSet.clear();
openSet.add(start);
cameFrom.clear();
start.gScore = 0;
start.fScore = heuristicCostEstimate(start, end);
while(openSet.size() > 0){
Node currentNode = lowestFScoreNode(openSet);//openSet.findLowestFScoreNode();
if(currentNode.equals(end)){
return reconstructPath(cameFrom, currentNode);
}
openSet.remove(currentNode);
closedSet.add(currentNode);
Node [] neighbours = getNeighbours(currentNode);
for(int i = 0; i < neighboursCount; i++){
if(closedSet.contains(neighbours[i]))
continue;
openSet.add(neighbours[i]);
float tentativeGScore = currentNode.gScore + heuristicCostEstimate(start, neighbours[i]);
if(tentativeGScore >= neighbours[i].gScore)
continue;
cameFrom.put(neighbours[i], currentNode);
neighbours[i].gScore = tentativeGScore;
neighbours[i].fScore = neighbours[i].gScore + heuristicCostEstimate(neighbours[i], end);
}
}
return null;
}
The lowestFScore node function just returns result of Collections.min()
Thanks in advance.