![]()
A* Pathing Finding: CPathFinderThe A* algorithm is another well known but little understood algorithm. This is a class breakdown of my CPathFinder class that implements the A* algorithm. For the accompanying case study, see the A* For the Masses essay. Note that essay assumes that you have read the case study, therefore no theory is explained here. You should fairly good with C++ - if you're scared of pointers, start running now.
Class Headerclass _asNode { public: _asNode(int a = -1,int b = -1) : x(a), y(b), number(0), numchildren(0) { parent = next = NULL; memset(children, 0, sizeof(children)); } int f,g,h; int x,y; int numchildren; int number; _asNode *parent; _asNode *next; _asNode *children[8]; // Assumes square tiles };I felt that the _asNode would be better implemented as a class since all initialization would be taken care of upon construction. With this constructor, you can set the x and y coordinates immediately on construction too. I initially had number also calculated here, but since the class is built to take any sized map, this could not be done without unnecessary additional complications. Also note, that this class assumes squared tiles - with potential successor being the surrounding 8 squares. For situations that require only 4 adjacent squares (no diagonals) or hexagonal movement, various elements will have to be changed. // Stack for propagation. struct _asStack { _asNode *data; _asStack *next; }; typedef int(*_asFunc)(int, int, void *);Here we have the structure for the stack. This stack is used to push and pop nodes to allow the A* to transverse the nodes like a tree. Also, the _asFunc definition is here. I used that definition for both the udValid and udCost since the udValid can return a bool as an integer a la C-style! The parameters are two integers and a void pointer - the coordinates being evaluated, and a void pointer to a user-defined data. This can be used for anything, but I use it with object-orientated programming in mind. You can pass the this pointer to the class, then use it to access elements in a static class function. Now, on to the actual class. class CPathFinder { public: CPathFinder(); ~CPathFinder(); bool GeneratePath(int, int, int, int); void SetValid(_asFunc sv) { udValid = sv; } void SetCost(_asFunc sc) { udCost = sc; } void SetData(void *sd) { m_pCBData = sd; } void SetRows(int r) { m_iRows = r; } _asNode *GetBestNode() { return m_pBest; } protected: int m_iRows; int m_iSX, m_iSY, m_iDX, m_iDY, m_iDNum; void *m_pCBData; _asNode *m_pOpen; // The open list _asNode *m_pClosed; // The closed list _asNode *m_pBest; // The best node _asStack*m_pStack; // Propagation stack _asFunc udCost; // The user-defined cost function _asFunc udValid; // The user-defined validity function // Functions void AddToOpen(_asNode *); void ClearNodes(); void CreateChildren(_asNode *); void LinkChild(_asNode *, int, int); void UpdateParents(_asNode *); // Stack Functions void Push(_asNode *); _asNode *Pop(); _asNode *CheckList(_asNode *, int); _asNode *GetBest(); // Inline functions inline int Coord2Num(int x, int y) { return x * m_iRows + y; } };There are no surprises here. A quite note on some of the variables: m_iRows is simply used to calculate the node numbers (see Coord2Num), m_iDNum is the number of the destination node. m_pCBData is the data passed back to the static functions specified in udCost and udValid. Now, the scary part - implementation!
Implementationbool CPathFinder::GeneratePath(int sx, int sy, int dx, int dy) { ClearNodes(); m_iSX = sx; m_iSY = sy; m_iDX = dx; m_iDY = dy; m_iDNum = Coord2Num(dx,dy); _asNode *temp = new _asNode(sx, sy); _asNode *best; temp->g = 0; temp->h = (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy); temp->f = temp->g + temp->h; temp->number = Coord2Num(sx, sy);This is the function that is called to generate the path - it will return true if a path is found, and false if not. The important part here is the assigning of temp->g, temp->h, and temp->f. Note that the initial cost is minimal, since we haven't moved from our start! The distance is very roughly calculated - there is no need to square root the overall cost, since it doesn't make any relational difference (49 < 64, sqrt(49) = 7, sqrt(64) = 8, 7 < 8), and would merely slow everything down. f is the sum of g and h. m_pOpen = temp; while (true) { if (!(best = GetBest())) return false; if (best->number == m_iDNum) break; CreateChildren(best); }; m_pBest = best; return true; }You see here how our initial starting point is put on the Open list. Now, here comes the bit I don't like - the infinite loop. Nevertheless, the loop will break upon one of two conditions being met. GetBest returns NULL (nothing on Open), or we have reached our destination successfully. If neither of these conditions are met, we generate the children of the best node and continue. We won't look at GetBest - but note that this is the function that moves nodes off the Open list and on to the Closed list.
void CPathFinder::CreateChildren(_asNode *node) { int x = node->x, y = node->y; for (int i=-1;i<2;i++) { for (int j=-1;j<2;j++) { if (i == 0 && j == 0 || !udValid(x+i, y+j, m_pCBData)) continue; LinkChild(node, x+i, y+j); } } }This routine loops around the surrounding squares, and if the conditions are met links the child node into the graph. There are two conditions for every node, firstly we check that we're not looking at the node itself, the second condition is user-defined. LinkChild is the main function on the A* implementation, so pay attention...
void CPathFinder::LinkChild(_asNode *node, int x, int y) { int g = node->g + udCost(x,y,m_pCBData); int num = Coord2Num(x,y); _asNode *check = NULL; if (check = CheckList(m_pOpen, num)) { node->children[node->numchildren++] = check; // A better route found, so update // the node and variables accordingly. if (g < check->g) { check->parent = node; check->g = g; check->f = g + check->h; } }Here is the second user-defined function being called to add the cost to the node. Now, since we need to check whether the node we are looking at already exists on one of our lists, we do a quick check by looking up the number that node would generate. If it is found on the Open list, we add check to node's children. Now, if the g-value is less than the current value of g for check that means we have found a better route via this node. We therefore update the check's variables accordindingly. else if (check = CheckList(m_pClosed, num)) { node->children[node->numchildren++] = check; if (g < check->g) { check->parent = node; check->g = g; check->f = g + check->h; UpdateParents(check); } }This is essentially the same as the previous segment, except that if a better route is found, we have to propagate all the changes down! This can really slow the algorithm down, but is necessary to get the best possible route. This is the function looked at next. else { _asNode *newnode = new _asNode(x,y); newnode->parent = node; newnode->g = g; newnode->h = (x-m_iDX)*(x-m_iDX) + (y-m_iDY)*(y-m_iDY); newnode->f = newnode->g + newnode->h; newnode->number = Coord2Num(x,y); AddToOpen(newnode); node->children[node->numchildren++] = newnode; } }If the node wasn't on either the Open or Closed lists, we have a new node to create and link. Therefore, we add the new node and set all the variables accordingly. AddToOpen adds the node on to the Open list with respect to f - therefore, the Open list is sorted from best f to worst. This helps the GetBest routine, since that returns the node with the highest f. Now, for the UpdateParents function - remember that this function treats the A* graph a bit like a tree, pushing and popping nodes as it transverses and propagates the changes backwards. void CPathFinder::UpdateParents(_asNode *node) { int g = node->g, c = node->numchildren; _asNode *kid = NULL; for (int i=0;i<c;i++) { kid = node->children[i]; if (g+1 < kid->g) { kid->g = g+1; kid->f = kid->g + kid->h; kid->parent = node; Push(kid); } }This sets up the initial stack with the children with higher g-values pushed on it. Therefore, this function's speed very much depends on the initial children count. _asNode *parent; while (m_pStack) { parent = Pop(); c = parent->numchildren; for (int i=0;i<c;i++) { kid = parent->children[i]; if (parent->g+1 < kid->g) { kid->g = parent->g + udCost(kid->x, kid->y,m_pCBData); kid->f = kid->g + kid->h; kid->parent = parent; Push(kid); } } } }You can see that this function has a 'semi-recursive' nature to it - with additional children being pushed on to the stack within the while(m_pStack) loop. This function is not complicated, but the calculations involved can take an extremely long time for large maps. Another thing to note is that the kid's cost is reassessed here and added to the parents g-value. Finished. Wasn't too complicated, if you can understand the back-progagation of the g-values. Now, to incorporate this class into your game/program, it is very simple. Simply call SetRows, SetValid, SetCost, and SetData, then GeneratePath with the start and destination values. Here is an example: Exampleclass B { int m_iBoard[30][20]; CPathFinder Find; void Find(); static int Valid(int, int, void *); static int Cost(int, int, void *); } // ... Initialize board ... // All spaces are valid, as long as they're within the board. int B::Valid(int x, int y, void *p) { if (x < 0 || y < 0 || x > 30 || y > 20) return 0; return true; } // Cost is 1 per space. int B::Cost(int x, int y, void *p) { return 1; } void B::Find() { SetRows(30); SetData(reinterpret_cast(this); SetValid(Valid); SetCost(Cost); if (Find.GeneratePath(0,0,15,15)) { printf("Path found...from dest to start, nodes are:"); _asNode *dest = Find.GetBestNode(); while (node) { printf("(%d, %d) ->", dest.x, dest.y); dest = dest->parent; } } else { printf("Cannot find a path..."); } }For a more advanced use of the class, see the A* Demonstrator Win95 program based on this class. ![]()
All content copyright © 1998-2002, Generation5 |