Sign in to follow this  
Zouflain

Faster A* algorithm?

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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this