Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Optimizing A* Pathfinding

edited September 2020 in Programming

Hi, I am having roughly about 25ms delay on my A* pathfinding system. I am using a secondary thread for potential lag -spikes if a lot of units want to find a path at once. I want to optimize it to make the units receive their paths quicker.

Here is the code:

            Heap<Node> openList = new Heap<Node>(30 * 30);
            HashSet<Node> closedList = new HashSet<Node>();


            openList.Add(startNode);
            Node current = null;
            while (openList.Count > 0)
            {
                // Find least cost node
                current = openList.RemoveFirst();
                closedList.Add(current);


                // If the target node is the current node we found a path
                if (current == endNode)
                    break;


                Node[] neighbours = GetNeighbours(current).ToArray();
                for (int i = 0; i < neighbours.Length; i++)
                {
                    if (neighbours[i].walkable == false || closedList.Contains(neighbours[i]))
                        continue;


                    int movementCostToNeighbour = current.gCost + 1;
                    if (movementCostToNeighbour < neighbours[i].gCost || !openList.Contains(neighbours[i]))
                    {
                        neighbours[i].gCost = movementCostToNeighbour;
                        neighbours[i].hCost = GetDistance(neighbours[i], endNode);


                        neighbours[i].parent = current;


                        if (!openList.Contains(neighbours[i]))
                            openList.Add(neighbours[i]);
                    }
                }
            }


            List<Vector3> path = RetracePath(endNode);


            PathfindData data = new PathfindData(path, path.Count > 0, callback);


            pathfindQueue.Enqueue(data);

A Heap allows me to instantly selected the least fCost node in the openlist.

Best Answer

  • Sl0thSl0th Member
    Accepted Answer

    Hey there, I have some suggestions for you.

    The most important one is to cut out all the Contains operations. They take linear time, which is really slow given that it happens a linear amount of times. (Theoretically your algorithm goes through every node, and Contains then goes through every now again, bringing you to O(n^2) time. Instead of saying for example openList.Contains(current), you should use an array of booleans, where each value correlates to a node. If it is true, it is in the list, if not, it is not. That requires you to give each node an index beforehand (of course just when setting the project up, don't assign indices every time you need to find a path). Alternatively, it looks like you're using a grid of nodes, so you could have a 2d array where the "coordinates" match with where the node physically is. Whichever is easier. The point is to go from a linear operation to a constant one.

Answers

  • PathfindData is what a unit receives which has a success boolean and the path.

    I add the it to the pathfindQueue to transfer to the main thread using the Update method next frame.

  • A second thing to optimize is to remove Distance() calls, as I believe those involve calculating the square root. Given that you are on a grid, you could probably make some pretty accurate approximations that let you avoid Distance() calls.

    Two other things you may or may not want to consider is the use of Node and GetNeighbours(). I generally try to avoid using objects when writing efficient algorithms. Structs might be okay, though, I can't say anything for sure about that. (I of course don't know which of the two Node is).

    About GetNeighbours(), I again don't know how it is implemented. I am just mentioning it in case you have written it in a way that it checks all nodes if they are neighbours or something like that. Finding neighbours should just be about looking it up in a grid array or taking the information from a predefined array in the Node or something like that. If it's not an extremely fast method, it could probably be improved.


    Hope this helps.

Sign In or Register to comment.