So I was writing an implementation of the A* search algorithm for a friend. He has a robot that must navigate a maze - the robot can obtain "complete" knowledge of its environment through an instrument called "ladar". It uses lasers to map out the area around it. Thus, knowing the goal and the obstacles around it, the A* search algorithm proved to be a prime solution for automatically navigating the robot.

One of the best ways to implement A* is using a priority queue. That is because of the following. As the search generates steps that it can take, it will store each step in a data structure. The most easiest and abstract way to handle this is to have a priority queue, so that when you enter a new step or move the robot can take, it will be inserted automatically (by order of the cost it will take to get there) in the sequence of moves it has already generated. Thus, when you remove the first element from the queue, it will be the best and lowest costing move.

The internals of the priority queue is based on a heap structure. (See out http://window.terratron.com/~sosman/computers/java/heap/ for a good applet and http://en.wikipedia.org/wiki/Priority_queue for describing it). This heap is a binary tree which allows for quick access and retrieval. The most attractive feature is that it lets me find the the lowest costing node in constant time because I am not searching for it.

Writing a queue in any real language isn't so hard. But writing it in a low level language like C proved to be a challenge. In the case anyone else can use this implementation, I've posted it here for general availability. It should be known that I am no expert C programmer - so if anyone has any improvements or ideas, let me know! 

Downloads 

Filename	Filesize	Date	Link
	pqueue.zip	1.89 K	2006-06-24	Download