A* optimisations?

d000hg · 2005-10-09T22:01:10

I've implemented a first try at A* for better path-finding in a tile-based world. Preliminary tests seems to show that it works, but is very slow - for a path of ~100 tiles it took ~0.25s (on a 750MHz processor) which is unacceptable for real-time use, even if the calculation is spread over several frames. I reckon i need to boost performance by an order of magnitude, which may be possible since this is a straight-from -the-book implementation with no performance considerations. Here is the method which calculates the path. Note that m_Open & m_Closed are std::lists. It's not too long or complex! bool PathFinder::CalculatePath3(RTSUnit *pUnit,WORD destX,WORD destY) { //if this unit is a user of any other paths, unregister it from them Cancel(pUnit); WORD startX = pUnit->Pos().x, startY = pUnit->Pos().y; m_Open.clear(); m_Closed.clear(); PathSearchNode N,Nnew,*pN; m_Open.push_front(PathSearchNode(0,startX,startY,destX,destY)); while(!m_Open.empty()) { N = m_Open.front(); m_Open.pop_front(); if(N.m_X == destX && N.m_Y == destY) { //found a route - genreate the list of tiles PathDataTileList *pPath = new PathDataTileList(this); for(pN = &N; pN; pN=pN->m_pParent) { pPath->AddPoint(pN->m_X,pN->m_Y); } m_Paths.push_back(pPath); m_PathLocations.push_back(new PathLocation(pPath,pUnit)); return true; } //push N onto closed and remember it's address for setting it as a parent to the new nodes m_Closed.push_back(N); pN = &m_Closed.back(); //find the 8 surrounding nodes for(WORD y = max(N.m_Y,1)-1; y<= N.m_Y+1; ++y) for(WORD x = max(N.m_X,1)-1; x<= N.m_X+1; ++x) if(y!=N.m_Y || x!=N.m_X) //don't select current node again! { Nnew.Set(pN,x,y,destX,destY); bool skip =false; // check - if Nnew in closed or open, and existing version has lower G, then skip this one for(std::list<PathSearchNode>::iterator Iopen = m_Open.begin(); Iopen!= m_Open.end(); ++Iopen) if((*Iopen) == Nnew && (*Iopen).m_G <= Nnew.m_G) { skip =true; break; } for(std::list<PathSearchNode>::iterator Iclosed = m_Closed.begin(); Iclosed!= m_Closed.end(); ++Iclosed) if((*Iclosed) == Nnew && (*Iclosed).m_G <= Nnew.m_G) { skip =true; break; } if(skip) continue; //if in closed, remove it if(Iclosed != m_Closed.end()) m_Closed.erase(Iclosed); //add to open if(Iopen == m_Open.end()) m_Open.push_front(Nnew); } //sort all nodes by ascending F. m_Open.sort(); } return false; } For reference, here is the node class I am using: class PathSearchNode { public: PathSearchNode *m_pParent; float m_F,m_G,m_H; //G is cost to this node, H heuristic estimate from here to end, F node cost G+H WORD m_X,m_Y; //the tile this node is located at PathSearchNode(){} PathSearchNode(PathSearchNode *pParent,WORD X,WORD Y,WORD destX,WORD destY) { Set(pParent,X,Y,destX,destY); } void Set(PathSearchNode *pParent,WORD X,WORD Y,WORD destX,WORD destY) { m_pParent = pParent; m_X = X; m_Y = Y; //no parent - start point if(!m_pParent) m_G=0; else if(m_pParent->m_X != m_X && m_pParent->m_Y != m_Y) m_G = m_pParent->m_G + 1.4f; //extra cost for diagonal movement else m_G = m_pParent->m_G + 1.0f; m_H = EstimateGoalDistance(destX,destY); m_F = m_G + m_H; } bool operator<(const PathSearchNode &comp) { return (m_F < comp.m_F); } bool operator>(const PathSearchNode &comp) { return (m_F > comp.m_F); } bool operator==(const PathSearchNode &comp) { return (m_X==comp.m_X && m_Y==comp.m_Y); } int EstimateGoalDistance(WORD destX,WORD destY) { int dx = max(m_X,destX) - min(m_X,destX); int dy = max(m_Y,destY) - min(m_Y,destY); return max(dx,dy); } }; To my mind, the fact that I keep iterating through the open/closed lists is probably a bad thing. Also, I am just pushing/popping from the Open list and calling std::list::sort on it. Recursion can be used to eliminate the open and closed lists completely, but a) can the stack take this and b)that means I can't spread the path-finding calculations over a second or two. Any advice would be gratefully received.