Possible A* Optimizations [closed]

Question

I have implemented A* in my game. However, I am not happy with the performance and need some help deciding what to do next.

I have already done the following optimizations:

• Not having a closed list (a Node just stores a bool onClosedList())
• Not iterating through the open list to check if a Node is on it (I have a bool onOpenList() too)
• Using a std::priority_queue to store the what is on the open list
• Using a heuristic that just adds up the difference in x and y coordinates
• If the zombie is targeting the player, it only updates if the player moves tiles
• If the zombie is targeting an object other than the player, it only finds the path once as objects(i.e turrets) don't move.

Some questions about my pathfinding:

• Zombies will eventually position themselves directly horizontally or vertically to to the player, and then follow the same path. Can I make it more random?
• I've heard about pre calculating every possibly path, but I feel like that will be extremely memory intensive as my map size is 257 x 257 tiles.

How my pathfinding works:

1. Create a multi-dimensional vector (matrix?) of Nodes
2. Put the starting node into the openList
3. Pop the top of the openList and set that node's onOpenList value to true.
4. Get its neighbors (!onOpenList && !onClosedList && walkable) into the openListafter calculating their values. If the neighbor is the target, put it on the stack and stop.
5. Set its onClosedList value to true
6. Repeat 3-5 until you find the target
7. Stack the parent of the top Node on the stack until it is the root node.
8. The zombie will keep moving to the top Node in the stack and then pop it.

My code:

void Zombie::findPath(std::vector< std::vector<Tile> >* pVTiles)
{
    //Creates a matrix of nodes
    std::vector< std::vector<Node> > mNodes_(257, std::vector<Node>(257, Node(sf::Vector2i(0, 0))));

    //Clears the stack
    while (!sPNodes_.empty())
        sPNodes_.pop();

    if (targetPosition_ != sf::Vector2i(0.0f, 0.0f))
    {
      readyToRepath_ = false;

        //Initiates lists
        std::priority_queue<Node*, std::vector<Node*>, compNode> openList;
        Node* currentNode;
        bool pathFound = false;

        //Initiates the great journey
        Node* pStartNode = &mNodes_.at((int)(positionGlobal_.x / 32)).at((int)(positionGlobal_.y / 32));
        pStartNode->setPosition(sf::Vector2i(positionGlobal_.x - fmod(positionGlobal_.x, 32.0f) + 16, positionGlobal_.y - fmod(positionGlobal_.y, 32.0f) + 16));
        pStartNode->setIsStartNode(true);
        pStartNode->setIsOnOpen(true);
        openList.push(pStartNode);

        while (!pathFound)
        {         
                //Gets the a pointer to the top item in the openList, then moves it to the closed list
            currentNode = openList.top();
            currentNode->setIsOnClosed(true);
            currentNode->setIsOnOpen(true);
            openList.pop();

            //For the eight neighboring tiles/nodes
            for (int i = 0; i < 8; ++i)

              {
                int xPos;
                int yPos;

                //xPos
                if (i == 0 || i == 4)
                    xPos = 0;
                else if (i > 0 && i < 4)
                    xPos = 1;
                else
                    xPos = -1;

                //yPos
                if (i == 2 || i == 6)
                    yPos = 0;
                else if (i < 2 || i > 6)
                    yPos = 1;
                else
                    yPos = -1;

                sf::Vector2i nodePosition = currentNode->getPosition() + sf::Vector2i(xPos * 32, yPos * 32);


                //Creates a node for the tile
                Node node(currentNode, sf::Vector2i(xPos, yPos));

                //Checks to see if it is the target adds node to stack and breaks if so
                if (node.getPosition() == targetPosition_)
                {
                    pathFound = true;
                    sPNodes_.push(node);
                    break;
                }

                //Stop working if the node/tile is a wall or contains a tree
                  if (pVTiles->at(nodePosition.x / 32).at(nodePosition.y / 32).getType() == "unwalkable")
                    continue;


                //If it's not the target
                if (!pathFound)
                {
                    float parentDistanceValue = node.getParentNodePtr()->getDistanceValue();

                    //Distance is 1.4f x 32 if diagonal, 1 x 32 otherwise
                    if (xPos == yPos)
                        node.setDistanceValue(parentDistanceValue + 44.8f);
                    else
                        node.setDistanceValue(parentDistanceValue + 32.0f);

                    //Gets the distance to the target(Heuristic) and then gets the total(Distance + Heuristic)
                    node.setHeuristicValue(abs(targetPosition_.x - nodePosition.x) + abs(targetPosition_.y - nodePosition.y));
                    node.setTotalValue();

                    //If the node is not already on the open/closed list
                    Node listCheckNode = mNodes_.at((int)(node.getPosition().x / 32)).at((int)(node.getPosition().y / 32));
                    if (!listCheckNode.isOnClosed() && !listCheckNode.isOnOpen())
                    {
                        mNodes_.at((int)(node.getPosition().x / 32)).at((int)(node.getPosition().y / 32)) = node;
                        openList.push(&mNodes_.at((int)(node.getPosition().x / 32)).at((int)(node.getPosition().y / 32)));
                    }
                }
            }
        }

        //Keeps stacking parent nodes until the start is reached
        while (!sPNodes_.top().isStartNode())
        {
            Node parent = *sPNodes_.top().getParentNodePtr();
            sPNodes_.push(parent);
        }
        //Pops the top node as the zombie is already on it
        sPNodes_.pop();
    }
}

Thanks!

If you need more information or have any questions, just ask!

Answer 1

Rather than pre-calculating every distance, simply pre-calculate the distances to and from each corner of the map to every node(perfect use-case for Dijkstra's algorithm) and then use this information and the Triangle inequality to generate a heuristic. This algorithm modification is referred to as ALT, or A-star with Landmarks and Triangle inequality. I have implemented this on a hex-grid (along with a Heap-On-Top Priority Queue and Bi-Directional search) and it calculates paths in under 100 ms on a 750 * 450 terrain grid. Pre-calculation (for 10 landmarks and 335,000 nodes using 6 of 8 processors on a 3-year old Intel i7 notebook) takes about 3 seconds.

One point to note that took me a while to unravel, is that each travel direction from each landmark generates an admissible heuristic for only one direction of the bidirectional search.

Additional Links:

• Computing Point-to-Point Shortest Paths from External Memory
• PNBA* - A Parallel Bidirectional Heuristic Search Algorithm
• Yet Another bidirectional algorithm for shortest paths

The Hex-Grid utility linked to is Open Source under the MIT Licence.

Update:

Sample C# code for the parallel calculation of the Landmark distances:

public static ILandmarkCollection CreateLandmarks(
  IHexBoard<IHex> board, 
  IFastList<HexCoords> landmarkCoords
) {
  if (landmarkCoords==null) throw new ArgumentNullException("landmarkCoords");

  ILandmarkCollection tempLandmarks = null, landmarks = null;
  int withCores = Math.Max(1, Environment.ProcessorCount - 2);
  try {
    tempLandmarks = new LandmarkCollection( (
                      from coords in landmarkCoords
                      where board.IsOnboard(coords) 
                      select Landmark.HotPriorityQueueLandmarkWithoutReset(coords,board)
                ).ToList<ILandmark>() );

    ( from landmark in tempLandmarks
      from direction in Landmark.Directions
      select new {
        Landmark  = landmark,
        Direction = direction
      }
    ).AsParallel().WithDegreeOfParallelism(withCores)
     .ForAll(item => item.Landmark.Reset(item.Direction));

    landmarks     = tempLandmarks;
    tempLandmarks = null;
  } finally { if (tempLandmarks != null) tempLandmarks.Dispose(); }
  return landmarks;
}

/// <summary>TODO</summary>
public ParallelLoopResult ResetLandmarks() {
  return Parallel.For(0, Count, i => { var l = this[i]; if (l!=null) l.Reset(); } );
}

and

  [DebuggerDisplay("Coords={Coords}")]
  public sealed partial class Landmark : ILandmark, IDisposable {
    /// <summary>TODO</summary>
    public enum Direction {
      /// <summary>TODO</summary>
      ToHex,
      /// <summary>TODO</summary>
      FromHex
    }
    /// <summary>TODO</summary>
    public static IList<Direction> Directions { get {return _directions;} }

    // other stuff
 }

Answer 2

std::vector< std::vector<Node> > mNodes_(257, std::vector<Node>(257, Node(sf::Vector2i(0, 0))));

This isn't optimal, a more efficient structure would be a

std::vector<Node> mNodes_(257*257, Node(sf::Vector2i(0, 0)));

and index with x*257 + y. You can possibly keep it allocated statically (or thread locally when multithreading) and reset when you need to.

Also instead of recalculating the entire path when the player moves prefill the open list with the previous path (returning if the player is already on it) as it is very likely the first part (until clearing obstacles) will remain the same.

Answer 3

Another possible optimization would be to not use priority_queue...

Using priority queue won't let you update each node distance individually (which is needed for A*). Using a custom implementation of min-heap, you can fix that issue. This way pushing, and popping nodes into the heap would be of O(logn), and so will updating be. But size of your heap will always be equal to the number of your open nodes.