3
\$\begingroup\$

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!

\$\endgroup\$

closed as too broad by congusbongus, Kromster says support Monica, bummzack, Josh Feb 11 '15 at 21:32

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ This question is too broad in its current form. There are many ways to optimise A* and they are mostly dependent on your map layout and use cases. When is your A* too slow? Also, you should ask one question at a time. \$\endgroup\$ – congusbongus Feb 11 '15 at 1:56
  • \$\begingroup\$ I covered some optimization strategies here:gamedev.stackexchange.com/questions/90555/… \$\endgroup\$ – Steven Feb 11 '15 at 2:29
  • \$\begingroup\$ Does the profiler tell you which lines are slowest? \$\endgroup\$ – amitp Feb 11 '15 at 2:33
  • \$\begingroup\$ I'm not too sure on how to use the VS2013 profiler at the moment. But it seems that the initial creation of the multi-dimensional vector takes a bit of time. \$\endgroup\$ – Moother Feb 11 '15 at 7:39
4
\$\begingroup\$

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:

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
 }
\$\endgroup\$
  • \$\begingroup\$ Thanks, I'll definitely look into this. I see you mentioned using multiple processors, though. I haven't had any experience with multi-threading so does this require getting a little background with multi-thread programming? \$\endgroup\$ – Moother Feb 11 '15 at 7:33
  • \$\begingroup\$ @MrSnappingTurtle: For this I just used the Parallel class. Code added to my posting above. \$\endgroup\$ – Pieter Geerkens Feb 11 '15 at 22:53
2
\$\begingroup\$
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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Sorry, what do you mean by "updating the node"? \$\endgroup\$ – Moother Feb 11 '15 at 7:27
  • \$\begingroup\$ @MrSnappingTurtle I mean the case, that you've opened a node, but later found some better way to reach it. \$\endgroup\$ – Ali1S232 Feb 11 '15 at 7:54
  • \$\begingroup\$ @Ali.S: I believe that case should never happen in a decent implementation of A-star - I have no need of it in my implementation linked to above. \$\endgroup\$ – Pieter Geerkens Feb 11 '15 at 23:00
  • 1
    \$\begingroup\$ @PieterGeerkens The same node can occur in the neighbors list of many other nodes. A* usually checks if the node is already in the Open set. If it's already there, and the previous 'g' value is lower (better) or equal then you don't need to insert the new node. If it's already there, and the previous 'g' value is higher (worse) then you should put the new node into the priority queue. Some implementations will update the existing node in the priority queue to reduce the number of nodes it has (speeding up the PQ) and to reduce the number of nodes processed (speeding up A*). \$\endgroup\$ – amitp Feb 11 '15 at 23:14
  • \$\begingroup\$ But if you are using a PQ to order the node search and have an admissible heuristic, then you never need to re-prioritize the nodes in the PQ. It's a tautology. \$\endgroup\$ – Pieter Geerkens Feb 11 '15 at 23:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.