Jump to content
  • Advertisement
Sign in to follow this  
Lode

A* path finding

This topic is 3943 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

What algorithm is the best to use to find paths on a 2D grid of squares where some squares are blocking? I'm using A* right now, but am a bit disappointed that it's appearantly not that fast. That is, on a intel E6600 CPU, when compiled without optimization, when there are 20 monsters looking for the path, there is a slight lag if the paths of the 20 monsters are recalculated, in a world of 16x16 tiles. I expected that it wouldn't be noticable, even when compiled without optimizations, because some macromedia flash games use a similar path finding thing and there I never notice slowness because of it. Is A* not the best algorithm to use for this? What are good path finding algorithms for this case? Or could my code be wrong? Here it is:
//world is a 2D tilemap, with rectangular tiles that are either filled or empty, supporting positive and negative coordinates of tiles. x0y0x1y1 are the borders inside the world in which to work.
bool World_AStar::findPath(std::vector<PathFindPos>& o_path, const PathFindPos& start, const PathFindPos& end, const PathFindPos& corner0, const PathFindPos& corner1)
{
  Node startnode(start.x, start.y);
  Node endnode(end.x, end.y);
  
  struct NestedFunctions //functions nested inside this function for convenience
  {
    static int heuristic(const Node& current, const Node& end)
    {
      int hx = (end.x - current.x);
      int hy = (end.y - current.y);
      if(hx < 0) hx = -hx;
      if(hy < 0) hy = -hy;
      return 10 * (hx + hy);
    }
  };
  std::list<Node> open; //open list: squares to look at next. Using an std::list allows to insert new squares sorted by cost in it
  std::list<Node> closed; //closed list: squares we don't have to look at anymore for now
  
  startnode.g = 0;
  startnode.h = NestedFunctions::heuristic(startnode, endnode);
  startnode.f = startnode.g + startnode.h;
  startnode.parent = 0;
  open.push_back(startnode);
  
  bool path_exists;
  
  for(;;)
  {
    if(open.size() == 0)
    {
      //the open list is empty... no path is found
      path_exists = false;
      break;
    }
    
    Node current = open.front(); open.pop_front(); //take the one with lowest cost from the open list
    closed.push_back(current);
    
    if(current == endnode)
    {
      //the end is reached
      path_exists = true;
      break;
    }
    
    //find the adjendant squares
    for(int i = 0; i < 8; i++) //for each neighbor
    {
    
      Node neighbor(current);
      switch(i)
      {
        case 0: neighbor.y -= 1; break; // +-x->
        case 1: neighbor.x += 1; break; // y 704
        case 2: neighbor.y += 1; break; // | 3 1
        case 3: neighbor.x -= 1; break; // v 625
        case 4:
          neighbor.x += 1;
          neighbor.y -= 1;
          break;
        case 5:
          neighbor.x += 1;
          neighbor.y += 1;
          break;
        case 6:
          neighbor.x -= 1;
          neighbor.y += 1;
          break;
        case 7:
          neighbor.x -= 1;
          neighbor.y -= 1;
          break;
      }
      
      int extra_cost;
      if(i < 4) extra_cost = 10;
      else extra_cost = 14; //10 * sqrt(2)

      
      ///is the neigbhbor walkable?
      bool walkable = true;
      if(neighbor.x < corner0.x || neighbor.x >= corner1.x || neighbor.y < corner0.y || neighbor.y >= corner1.y) walkable = false;
      if(blocks(neighbor.x, neighbor.y)) walkable = false;
      //diagonal also blocks if two walls are in the way
      if(i >= 4)
      {
        if(blocks(neighbor.x, current.y)) walkable = false;
        if(blocks(current.x, neighbor.y)) walkable = false;
      }
      
      if(!walkable) continue;
      
      ///if the neighbor is already on the closed list, skip it
      bool already_on_closed_list = false;
      for(std::list<Node>::iterator i = closed.begin(); i != closed.end(); i++)
      {
        if(neighbor == *i)
        {
        already_on_closed_list = true;
        break;
        }
      }
      
      if(already_on_closed_list) continue;
      
      neighbor.parent = &closed.back();
      
      neighbor.g = current.g + extra_cost;
      neighbor.h = NestedFunctions::heuristic(neighbor, endnode);
      neighbor.f = neighbor.g + neighbor.h; //the cost
      
      ///find if the neighbor is already on the open list
      bool better_one_already_on_open_list = false;
      for(std::list<Node>::iterator i = open.begin(); i != open.end(); )
      {
        if(neighbor == *i)
        {
          if(neighbor.f < (*i).f)
          {
            i = open.erase(i);
          }
          else
          {
            better_one_already_on_open_list = true;
            ++i;
          }
        }
        else ++i;
      }
      
      if(better_one_already_on_open_list) continue;
      
      ///place the neighbor node in the open list, correctly sorted by cost
      bool inserted = false;
      for(std::list<Node>::iterator i = open.begin(); i != open.end(); i++)
      {
        if(neighbor.f <= (*i).f)
        {
          open.insert(i, neighbor);
          inserted = true;
          break;
        }
      }
      if(!inserted) open.push_back(neighbor); //either open was empty, or neighbor had higher cost than everything in it, so insert it at the back now
    }
  }
  
  //The while loop is now over. Either a path is found, or there exists none. Now store the result in the return path.
  
  Node node = closed.back();
  o_path.push_back(PathFindPos(node.x, node.y));
  while(node.parent != 0)
  {
    node = *(node.parent);
    o_path.insert(o_path.begin(), PathFindPos(node.x, node.y));
  }
  
  return path_exists;
}


Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Ravuya
If the map is static, why don't you just do a few passes of A* and cache the results?


What do you mean? Will doing a few passes return a full path?

What I do is, whenever the map changes, I recalculate all the monsters. The map doesn't change all the time, but when it does I notice the small lag.

EDIT: oh, your post is suddenly gone :(

Share this post


Link to post
Share on other sites
Compile with optimizations on. Otherwise, you're just looking at how fast the debug vector and list iterators are.

Share this post


Link to post
Share on other sites
Looking at your code, it's also possible that you're running into a lot of reallocations in your path Vectors, and you might be doing a lot of searching in your lists.

The way I understand it, most industrial strength pathfinders use clever data structures (such as intrusive heaps and hash tables) to store their open and closed "lists", and they pool all their A* nodes at the beginning of the algorithm to minimize search times through the lists and stay off the heap. It probably isn't a big deal when you're only pathfinding a single character, or even 3 or 4, but when you're getting up to 20, I imagine it adds up.

With that being said, I've never implemented a super-industrial pathfinder myself, so prioritize things other people say higher than my suggestion :)

Good luck!

Share this post


Link to post
Share on other sites
Stoic has the right idea - heavy memory reallocation can be murder.

Even still, there's a lot of general inefficiency in your code. For example, I suspect that if you store your map in a different way, you can eliminate that switch in the middle and a lot of the walkable checks (which are terribly inefficient - you have a lot of cases where checks are made repeatedly, when you already know the square is blocked and can therefore stop checking the node entirely).


Last off - something about the implementation feels wrong. I don't have time to look over it in painstaking detail right now, but it seems like it won't always find the least-cost path. Not sure if that really matters, depending on your usage, but there you go.


[edit] Afterthought: one thing to check is how you sort your list of eligible paths. It's easy to get the comparison backwards, and sort by least-preference rather than by greatest-preference. (As a matter of fact, I just made that mistake myself earlier today.) If nothing else, try swapping the sort order of your list and see if the search speed increases or decreases dramatically.

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
[edit] Afterthought: one thing to check is how you sort your list of eligible paths. It's easy to get the comparison backwards, and sort by least-preference rather than by greatest-preference. (As a matter of fact, I just made that mistake myself earlier today.) If nothing else, try swapping the sort order of your list and see if the search speed increases or decreases dramatically.


If I swap the comparision (if(neighbor.f >= (*i).f)), then the monsters zigzag to the target in the longest path possible :) And the calculating is longer.
So probably at least the sort order was right.

Very interesting posts though, I'll look into it, thanks.

In the implementation as I posted it seems as if they're taking the shortest path. Do you have any hint about what you feel might be wrong?

Share this post


Link to post
Share on other sites
Try a simple test case: a single origin/destination, with two equal-length paths, split like halves of an O. On one half, make the cost low for most of the trip, then throw in one very high-cost node just before the endpoint. On the other half, make the cost slightly higher, but set it up so that the total cost is less than the total of the first half.

A* should correctly return the second path, even though it "appears" more expensive until the final step is considered. I may be wrong, but the way your implementation is laid out, it seems like it might return the misleading path instead.

Of course, if you're not planning on needing variant node traversal costs, then this is totally irrelevant.

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQOf course, if you're not planning on needing variant node traversal costs, then this is totally irrelevant.


Ha, I'm not needing this, at least not yet, maybe for some smarter AI (avoiding towers) this could be useful if I'd ever want it later.

Share this post


Link to post
Share on other sites
The first thing I would do is to add a lookup table to see if a node is on the closed list. At the moment, imagine that you've explored half your 16x16 map, so there are about 128 nodes on the closed list if your map has plenty of obstacles. Every new node you explore generates 8 neighbours, and for each of those neighbours, you have to compare it with 128 nodes on the closed list. That's looping over 1024 existing nodes every time you investigate a new one. And it gets worse as the search approaches the goal and the closed list keeps growing. Really you want to get this to be an O(1) operation so that it's just 8 instant comparisons.

I'd probably just implement this lookup table as an array of chars, (World_Width * World_Height / 8) in size. (Round up to nearest whole char.) std::fill it with zeros at the start, and set the bits as you add nodes to the closed list. If you have a little inline function to set and check individual bits, this is great.

Although to be honest, with a world as small as yours, you can just use an array of bools. But if your world gets bigger you'll probably find that packing it into a structure eight times smaller helps.

And, if you're not ever considering promoting a node from the closed list back to the open list (eg. in situations where you found a shorter route to an already explored position - not possible in certain implementations and not generally possible in a pure A* implementation), you don't even need the closed list itself, just the lookup table.

Share this post


Link to post
Share on other sites
Some more thoughts:

Consider using a more advanced data structure for the open list. For example a priority_queue will dramatically speed up the retrieval of the best node, but it'll make the search for a neighbour that's already on the list very awkward. A separate map can make that quick if you need it.

One more speed up you could get is by pre-calculating all the valid directions you can move and storing them within each square. You only need 8 bits of storage per square (one bit for each direction) to do that and it saves on doing all the checks for the edge of the map as well as the other collision checks in the search. You just need to recompute it when the map changes (and even then only for the squares that change, and the ones next to them).

There's another trick to speeding it up which has nothing to do with optimizing the algorithm. You can limit the maximum number of units that can calculate a path on any one frame (or limit the total time taken calculating paths to a few ms). You might want to prioritize units controlled by the user over AI ones to maximize responsiveness, but don't let the user block the AI completely.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!