Faster A* algorithm?

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

Recommended Posts

I'll start off by saying that I worked for a week trying to get a binary heap to work. After much hair ripping, I just did it with std containers and was done in less than five minutes. I say this just to outline that I'm aware that binary heaps are faster, but I'd only want to resort to them if it becomes absolutely necessary. --- I'm trying to make a pathfinding algorithm for a 500x500 grid of nodes. Each node has a number identifier which signifies which directions an object on that node can go (it's just a bitflag). This is what the code looks like under the hood:
class aHeap{
private:
std::set<sint> open,closed;//the openset.
std::map<sint,sint> G,H;
std::multimap<sint,sint> working;
uint maxsize;
public:
std::map<sint,sint> parents;
bool find(uint id);
void add(uint id,uint targetid,uint cost,uint parentid=0);
void removeTop(void);
sint getTop(void);
aHeap(uint sz=MAPSIZE*MAPSIZE);
};

void aHeap::add(uint id,uint targetid,uint cost,uint parentid){
if(working.size()>maxsize||closed.find(id)!=closed.end())
if(open.find(id)==open.end()){//tile not yet open
open.insert(id);
if(id!=parentid)
cost+=G[parentid];
H[id]=//basic diagonal shortcut heuristic
parents[id]=parentid;
working.insert(std::pair<sint,sint>(cost+H[id],id));
}
else if(cost+G[parentid]<G[id]){//tile open AND this is shorter
working.erase(working.find(id));
cost+=G[parentid];
working.insert(std::pair<sint,sint>(cost+H[id],id));
}
}
void aHeap::removeTop(){
if(working.begin()==working.end())//the open list is empty
return;
sint drop = working.begin()->second;
working.erase(working.begin());
open.erase(drop);
closed.insert(drop);
}
sint aHeap::getTop(){
if(working.begin()!=working.end())//if the open list ISN'T empty
return working.begin()->second;
return MAPSIZE*MAPSIZE+1;
}


This works fairly well and fairly quickly, but I was wondering if anyone could spot some potential optimizations or alternative methods entirely. There are a few repeat calls that could be moved to a single variable declaration, but beyond that, I wonder if I've missed something. Thanks for any help, or comments on the matter. (EDIT: Added mandatory source tags. -- Kylotan) [Edited by - Kylotan on March 29, 2010 8:05:00 AM]

Share on other sites
Did you try using STL's heap functions?

Share on other sites
Your naming is misleading - a heap is a single data structure but you've packed several in there. You've also commented the open and closed lists both as 'the openset'. And I don't see the need for the working multimap given my understanding of A*, which implies an inefficiency right there.

Share on other sites
I just use a tree-based set for the open list and a hash map for the closed list.

If your world is a bounded grid of some sort then you can further optimize it by using an array instead of a hash map, where N means the node is closed and anything else means its open. This way you not only avoid hashing overhead, but you avoid having to clear the closed list - every time you find a path with A*, you increase N by one. You only need to clear the closed list when N overflows, which is quite a lot of path-finds if you use an unsigned int.

Another optimization is to avoid the "check if node already exists with a different score" part. Just stick the node into the open set anyways - the version with the better score will be processed first and then closed. So if you pop a node off the open set and it's already closed, you know it was a duplicate with a worse score and you just disregard it.

Also, don't use maps for the scores and what-not. Just do something like:
struct aStarNode;typedef boost::shared_ptr<aStarNode> aStarNodePtr;struct aStarNode{    aStarNodePtr parent;    int g, h;    bool operator<(const aStarNode &rhs) { return g + h < rhs.g + rhs.h; }};

This way once you get to the target node, you can easily back-track to get the path, and the g and h scores are kind of... just there.

With all of these I can path-find for several units in packed grids of 1000x1000 and above.

1. 1
2. 2
3. 3
Rutin
24
4. 4
JoeJ
18
5. 5

• 14
• 23
• 11
• 11
• 9
• Forum Statistics

• Total Topics
631766
• Total Posts
3002233
×