• Advertisement
Sign in to follow this  

Faster A* algorithm?

This topic is 2890 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

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())
		return;//can't add more OR already closed!
	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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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.

Share this post


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

  • Advertisement