Jump to content
  • Advertisement
Sign in to follow this  

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.

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{
			std::set<sint> open,closed;//the openset.
			std::map<sint,sint> G,H;
			std::multimap<sint,sint> working;
			uint maxsize;
			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){
		return;//can't add more OR already closed!
	if(open.find(id)==open.end()){//tile not yet open
		H[id]=//basic diagonal shortcut heuristic
	else if(cost+G[parentid]<G[id]){//tile open AND this is shorter
void aHeap::removeTop(){
	if(working.begin()==working.end())//the open list is empty
	sint drop = working.begin()->second;
sint aHeap::getTop(){
	if(working.begin()!=working.end())//if the open list ISN'T empty
		return working.begin()->second;

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