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.

Unfortunately, we can't help you speed up a function when you're not showing us that function, or the object it operates on.

Typically, the open set of nodes can be implemented as a priority queue; this makes finding the first element a O(1) operation. It's possible that your current 'Collections.min()' implementation is O(N) and therefore likely to be slower. So, consider changing that data structure as your first thing to try. However, since that structure is sorted on the F score, and you are potentially changing the G scores (and hence the F scores), of nodes already on the open list, you will probably need to pop them off and re-insert them to do this. (Simpler approaches could just have 2 copies of the node with different scores.)

Your `tentativeGScore` calculation is wrong, also; the 'G' score is the actual distance travelled to the node in question, and doesn't include the heuristic at all.

If you've got a large mob of actors all trying to navigate to a single location and your navmesh/grid/whatever has uniform movement costs, you can ditch A* and instead do a single breadth-first flood-fill from the goal location outwards, writing an increasing value each time the fill expands to an unvisited location, then have all actors access the resulting gradient map, which lets them move "downhill" towards the goal location.

Note that the flood-fill approach for multiple enemies from goal outwards assumes every link between nodes is bidirectional. This is often true, but not always. (e.g. Steep slopes, one-way doors.)

And regarding the 'cameFrom' mapping - I wondered about that too, but then (a) noticed that this version of the algorithm has been ported from Wikipedia, and (b) the cameFrom mapping helps to separate out the node itself (which can be immutable) and the route being found through the nodes (which is not). Some versions of A* prefer to create nodes to represent the states they're iterating through, which means you can mutate them all you want, and other versions (like this one) use the states directly as nodes and store the algorithm results outside of the nodes

8 hours ago, Kylotan said:

Note that the flood-fill approach for multiple enemies from goal outwards assumes every link between nodes is bidirectional. This is often true, but not always. (e.g. Steep slopes, one-way doors.)

The simple way around that is to walk "backwards". On an iteration where you expand from node A to say neighbours B1, and B2, check whether you can move from B* to A (instead of the usual A to B*), and take the cost also in the opposite direction, if that matters.

1 hour ago, Alberth said:

The simple way around that is to walk "backwards". On an iteration where you expand from node A to say neighbours B1, and B2, check whether you can move from B* to A (instead of the usual A to B*), and take the cost also in the opposite direction, if that matters.

What Kylotan means is that when the flood fill is performing its outward traversal, if it's at node A and that node does not know about "from" vertices at all, it cannot traverse "uphill" to those nodes.  You would have to search all edges for ones where "to" is node A, which would defeat any of the performance gains you might get otherwse.

This applies for digraphs where the only info you can access at each node are the "to" vertices.  I don't particularly like representing graphs like that, but they can save space since you don't have to store edges in two places.

The graph representations I know of are:

Adjacency matrix:  Edge traversal can be forward or backwards.  Incredibly wasteful for sparse graphs.  Uses an absurd amount of memory unless you compact it somehow (which usually ends up more complicated and less performant than one of the other options below).

Edge list only: Usually uses the least amount of RAM, but most time is spent searching the list for edges where 'from' or 'to' are a specific vertex.  Not really acceptable in terms of performance unless the entire edge list is so small the search loop is insignificant.

Vertices-which-store-edges:  Good for most uses but if you need to store both "to" and "from" edge lists you double your memory use.  Can be acceptable since it still scales better than a sparse adjacency matrix.

Implicit data structure (i.e. the typical 2D grid where neighboring cells are connected):  Great for traversal but only supports graphs that can be mapped onto that data structure.