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).

Data structures example: the graph class

In the last data structures post I talked about the tree structure, now let’s head towards graphs. As usual I’m also providing the source files for all included examples, which you can download here.
The code is a bit rough and there is plenty room for optimizations, but nevertheless I hope you understand what’s going on. Also make sure you have the latest release, because I have modified almost all graph-related classes.

What’s a graph?

Graphs (also known as Networks) are very powerful structures and find their applications in path-finding, visibility determination, soft-bodies using mass-spring systems and probably a lot more. A graph is similar to a tree, but it imposes no restrictions on how nodes are connected to each other. In fact each node can point to another node or even multiple nodes at once.

A node is represented by the GraphNode class, and the connections between GraphNode objects are modeled by the GraphArc class. The arc has only one direction (uni-directional) and points from one node to another so you are only allowed to go from A to B and not in the opposite direction. Bi-directional connections can be simulated by creating an arc from node A to B and vice-versa from B to A. Also, each arc has a weight value associated with it, which describes how costly it is to move along the arc. This is optional though, so the default value is 1.

Putting it together, the graph is implemented as an uni-directional weighted graph. The Graph manages everything: it stores the nodes and the arcs in separate lists, makes sure you don’t add a node twice, or mess up the arcs (for example if you remove a node from the graph, it also scans the arc list and removes all arcs pointing to that node) and provides you with tools to traverse the graph.

Building the graph structure

In figure 1, you see a simple graph containing 8 nodes. You can add additional nodes, which will be placed at the position of the cursor by pressing ‘a’ or start with a fresh graph by pressing ‘r’. To create an arc point from node A to Node B, simply click both nodes successively. Traversal is also possible: First press ‘t’ to switch to ‘traverse’ mode, then click a node to find all nodes which are connected to the this node.

Figure 1: Building a graph structure

Graph traversal

If you have tried out the traversal in the example above, you may wonder how it’s done. The answer lies in two common algorithms to accomplish this: Breadth-first search (BFS) and depth-first search (DFS). (The demonstration above used the breadth-first search.)

The BFS algorithm visits all nodes that are closest to the starting node first, so it gradually expands outward in all directions equally. This looks like a virus infecting the direct neighborhood at each search iteration. BFS utilizes a queue and proceeds as follows:

  1. Mark the starting node and enqueue it.
  2. Process the node by calling a user-defined function on it.
  3. Mark all connected nodes and also put them into the queue.
  4. Remove the node at the front of the queue.
  5. Repeat steps 2-5 with the node that is now at the front of the queue.
  6. Stop if the queue is empty.

The depth-first search (DFS) on the other hand takes the starting node, follows the next arc it finds to get to the next node, and continues this until the complete path has been discovered, then goes back to the starting node and follows the next path until it reaches a dead end and so on. It’s currently implemented as a recursive function, that means that it probably can fail for very large graphs when the call-stack exceeds the maximum size (I don’t know how big it is in AS3 though).

Both algorithms have in common that they mark a node when it’s added to the queue, otherwise the node would be enqueued and unnecessarily processed multiple times, because different nodes can all point to a common node. So before you start a BFS or DFS it’s very important to reset all markers by calling the clearMarks() function on the graph.

The two algorithms are visualized in figure 2 below. I’ve created a rectangular grid of nodes (similar to a tilemap) by connecting each node with the top, bottom, left and right neighbors (I left out the arcs because it would be a total mess). I have also deleted some nodes to show you that both algorithms don’t rely on a regular structure and can look like anything. Just click a node to start the traversal. You can toggle between both algorithms by pressing ‘b’ BFS and ‘d’ (guess what ;-)).

Figure 2: Building a graph structure

BFS is much more useful than DFS in most situations. But DFS is likely to be faster, for example when you only want to modify all connected nodes in some way.

A graph-based A* pathfinder

Now for the cool part. I have created a pathfinder to demonstrate the power of the BFS algorithm. When building the graph it’s important that all arcs are bi-directional, so the pathfinder can figure out the shortest path between two locations.

I can’t explain how a pathfinder works in detail, because it’s a vast subject, but actually it’s not that different from the tile-based version, which you probably realized when looking at figure2: in a tilemap, you have 8 directions (N, S, W, E, NW, NE, SW, SE) and you go from one tile to another by adjusting the x and y tile index, in a graph you just follow all arcs of the current node. The implementation is a little chaotic, because I have to render and compute the path simultaneously, so it needs definitely some refactoring to make it clean and reusable, but for demonstration purposes it should hopefully do the work.

Figure 3: Graph based pathfinding, click a start and end node.

After finding a path through the A* algorithm, I store the nodes in a queue. You could then use a command queue so a character can follow the path. In contrast to tile-based path finding, the graph based version is lightning fast and there is still plenty room for optimizations: for example you could run a breath-first search on the graph to precompute all distances between the nodes. That’s all I have to say about graphs, next time I take an closer look at my favorite structure – linked lists!

See also:
Linked lists
The queue class
The tree class