A* pathfinding with ds

I recently did a complete rewrite of my graph-based A* pathfinder example because I received a lot of questions on how to implement path-finding using the new ds library. So here is an updated demo that works with ds 1.32:

Interactive demo: A* pathfinding with ds

I’m transforming the point cloud with delaunay triangulation into a graph structure. Then the system computes and draws the shortest path between two selected points.

Compile instructions

Running and examining the example is really easy:

  1. Use the automated installer to install haXe from http://haxe.org/download.
  2. Download the latest haXe nightly build and overwrite the existing ‘haxe.exe’ and ‘std’ folder with the downloaded version.
  3. Install the polygonal library by opening the command prompt and typing:
    $ haxelib install polygonal.
  4. Sources should now be in {haxe_install_dir}/lib/polygonal/1,18/src/impl/sandbox/ds/astar, where {haxe_install_dir} is usually C:/Motion-Twin/haxe on Win7.
    The demo can be then compiled with:
    $ cd C:\Motion-Twin\haxe\lib\polygonal\1,18\build
    $ haxe.exe compile-ds-examples.hxml

Extending the Graph class

You have basically two options to extend the functionality of the Graph object: by composition or inheritance. While I highly recommend to use composition whenever possible, I’ve also included a version using inheritance – just so you see the difference.

The composition version looks like this:
A* using composition

The Graph object manages GraphNode objects, and each GraphNode holds a Waypoint object, which defines the world position of the waypoint as well as intermediate data used by the A* algorithm. Notice that GraphNode and Waypoint are cross-referencing each other as a Waypoint object has to query the graph for adjacent nodes. As a result, you have a clean separation between the data structure (Graph, GraphNode) and the algorithm (AStar, Waypoint) and don’t need object casting, which is good news because casting is a rather slow operation.

Now let’s look at the version using inheritance:
A* using inheritance
Here, Waypoint directly subclasses GraphNode. Since the Graph is defined to work with GraphNode objects, we need a lot of (unsafe) down-casts to access the Waypoint class. Furthermore, the use of haxe.rtti.Generic will be very restricted or even impossible (implementing this marker interface generates unique classes for each type to avoiding dynamic).

Heaps and Priority Queues in ds 1.31

I recently revised and improved the Heap and PriorityQueue classes, mainly because the difference between both has always been somewhat blurry. The new implementations are included in ds 1.31, so let’s talk a bit about the changes.

The Heap class

By definition, a heap is a dense binary tree for which every parent node has a value that is less (or greater; henceforward I assume elements are sorted in ascending order) than or equal to any of its children. A heap defines a set of simple operations:

  • Insert element
  • Query smallest element
  • Remove smallest element

In the old implementation, insertion was done by calling enqueue(), and removal by calling dequeue(). This was a bit misleading because a heap is not a queue, instead it’s used as an efficient data structure for implementing priority queues. Thus the existing heap API has been modified and now consists of the methods add(), top() and pop(), corresponding to the old methods enqueue(), front() and dequeue(), respectively. I’ve also added some additional methods:

  • replace() – replaces the smallest element with a new element
  • change() – updates an existing element after it has been changed (restores heap condition)
  • sort() – returns a sorted array of all elements (runs the heap sort algorithm)
  • bottom() – finds and returns the largest element
  • repair() – rebuilds the entire heap

Note that replace() and change() is a lot faster than a combined remove() and add() operation. Also, bottom() runs in O(n) wheres top() is O(1). This can be further improved by a Min-Max Heap, which I may add in a future release.

Last but not least I did some optimizations, lowering memory requirements and almost doubling performance. And you don’t have to enable element-removal capabilities through the constructor as the heap now always supports removal of arbitrary elements.

The PriorityQueue class

As mentioned above, heaps are used for implementing priority queues and as the name implies, it’s a queue ADT so PriorityQueue now implements the Queue interface, defining the following methods:

  • enqueue() – adds an element
  • dequeue() – removes the element with the highest priority
  • peek() – returns the element with the highest priority (without removing it)
  • back() – returns the element with the lowest priority (without removing it)

The Heap class requires that every element provides a comparison function by implementing the Heapable interface. This is not needed for the PriorityQueue class, because here the elements are sorted using integer keys, resulting in a much better performance. So if you are only interested in managing prioritized data this is the perfect choice, while the Heap class is best used as an all-round tool for solving common problems like finding the min, max or k-th largest element.

Usage

Elements to be inserted into a heap have to implement the Heapable interface, which is defined in haXe like so:

interface Heapable implements Comparable
{
    /**
     * Tracks the position inside a binary heap.
     * This value should never be changed by the user.
     */
    var position:Int;
}

Declaring a field in an interface is not supported in ActionScript 3.0, so when you inspect the compiled class from an SWC file, it has become an empty marker interface. So don’t forget to define the position field as you don’t get compile-time errors. I could have defined position as a getter/setter style function, but I don’t want to give up all those nice haXe features because it has become my primary language for a long time now. So the AS3 implementation of a heap element would look like this:

package
{
    import de.polygonal.ds.Heapable;
    
    class HeapElement implements Heapable
    {
        public var value:int;
        public var position:int;

        public function HeapElement(value:int)
        {
            this.value = value;
        }

        public function compare(other:Object):int
        {
            return other.value - value;
        }

        public function toString():String
        {
            return "" + value;
        }
    }
}

Similary, elements to be inserted into a PriorityQueue have to implement Prioritizable like this:

package
{
    import de.polygonal.ds.Prioritizable;
    
    class PriorityQueueElement implements Prioritizable
    {
        public var priority:Int;
        public var position:Int;
        public function PriorityQueueElement() {}
    }
}

Once we have a heap element defined, we can use the Heap like so:

...
var heap = new Heap();
var a:HeapElement = new HeapElement(2);
var b:HeapElement = new HeapElement(5);
var c:HeapElement = new HeapElement(9);

//insert elements
heap.add(a);
heap.add(b);
heap.add(c);

//dump all elements
trace(heap);

//query smallest element
trace(heap.top());

//change element
a.value += 4;
heap.change(a);

//remove smallest element
trace(heap.pop());

//remove largest element
heap.remove(heap.bottom());
...