HomeEssaysInterviewsProgramsBooksMediaSoftwareHardwareGamesFeatures
Discussion BoardAISolutionsCompetitionEducationProjectsGlossaryLinksSearch
Search:

A* Pathing Finding: CPathFinder

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

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

Implementation

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

Example

class 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.
  • Game Reviews - All platforms, even PlayStation2!

  • Gaming Essays - Essays on programming game AI.
  • Gaming AI Programs - Windows-based, full source code included.
  • Gaming AI Interviews

  • AISolutions


    All content copyright © 1998-2002, Generation5