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.

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

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.

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

Data structures example: the queue class

FIFO - First In, First Out

The queue class is rather basic, which saves me a lot of writing :-). The idea is simple: Think of waiting in a line at a movie theater; you get in line at the end to buy a ticket (enqueue); you reach the head of the line (peek) and finally buy the ticket and leave the line (dequeue). To use the queue class you only need three basic methods. Here are the method signatures:

var success:Boolean = myQueue.enqueue(obj);
var obj:* = myQueue.peek();
var obj:* = myQueue.dequeue();

Enqueue() obviously enqueues an item, peek() returns an instance to the front item and dequeue() removes and returns the front item at the same time. Here is a simple demonstration (first click flash to get focus):

Use key e to enqueue an item and d to dequeue the front item (blue colored circle). The numbers indicate the order of the items inside the queue. Lower numbers leave the queue before higher numbers. Also if the queue is full, all nodes are purple colored.

Size matters

A limitation of the queue class is that it has be to initialized with a fixed size. So in case the queue is full, the enqueue() method does nothing and just returns false:

var success:Boolean = myQueueInstance.enqueue(obj);

Defining a size for a new queue is also a bit different from other classes in the package because it has to be a multiple of two - this is needed for a fast bitwise modulo to speed up the array access. A queue is used so often in game programming that it should run as fast as possible, although it wasts some memory - the array might be bigger than actually needed. Instead of passing the target size directly, you pass the exponent by which 2 is raised:

var myQueueInstance:ArrayedQueue = new ArrayedQueue(4);

The queue above can store 16 items, because 2^4 (eq. 1 << 4) is 16. To be able to store 32 items, pass 5 (2^5) and so on.

Performance

If you now think “Who needs a class for it ? I keep it real and just use the native flash array methods push() and shift() !” then I have a surprise for you. Lets create a really big queue with more than 100,000 elements (131,072 to be exactly, which is 2^17). Now we enqueue items until its full, then empty it with dequeue.

The push/shift version (or unshift/pop, it doesn’t matter) takes 13 seconds(!) on my machine:

var size:int = 1 << 17;
var que:Array = [];
for (var i:int = 0; i < size; i++)
{
    que.push("foo");
}
for (var i:int = 0; i < size; i++)
{
    var result:String = que.shift();
}

Now the queue class, which takes only 40 milliseconds:

var aq:ArrayedQueue = new ArrayedQueue(17);
var success:Boolean;
do
{
    success = aq.enqueue("foo");
}
while (success);

var result:String;
do
{
    result = aq.dequeue();
}
while (result);

Here is a comparison table using a queue with a more realistic size:

As you see, the queue class grows linearly in processing time, while the array methods increases more drastically. This is because the flash player has to move a lot of data around inside the memory every time you add or remove the first element of an array (or any other in between except for the last one).

For very small queues, the class is a little bit slower. On the other hand it manages the size of the queue for you and also provides an iterator and implements the collection interface.

So this should be all you need to know about queues. Besides, the package contains also the LinkedQueue, which is based on a linked list, thus has no size limitations and performs the same no matter how many elements are stored inside it. The class itself is simple - it just defines some wrapper functions for a the linked list to provide queue-like access.

A command queue

Finally a little real-world example of what is called a command queue. I used it to create a very basic waypoint system. Click on the flash to add a waypoint, and the ‘plane’ (the colored circle) follows all waypoints until the queue is empty.

The sources for the flash examples can be downloaded here (Flash CS3 required). Next in the series will be the graph class, so stay tuned :-)

See also:
Linked lists
The tree class
The graph class

Data structures example: the tree class

First, I have updated the data structures source to version 0.7.3, so make sure you have the latest version. The source code for the SWFs in this post can be obtained here (Flash CS3 required).

Using the tree iterator

Before we build a tree its important to understand how the tree iterator works. Normally the iterator is used to iterate over the structure’s data - in this case the iterator additionally acts as a ‘marker’ and points to the node at which we may modify the tree.
Also, the tree iterator is somewhat special, because it allows you to iterate through the tree in two directions: horizontally and vertically. Therefore it has to manage two node references simultaneously, making it more complex than other iterators.

In the figure below, the purple colored node is the vertical iterator and is used to move up and down the tree using the treeNodeInstance.parent property, while the blue node is obviously the horizontal iterator and can only step left and right through the node’s children.

I think a simple demonstration is worth more than thousand words, so you can try it yourself by playing around with the tree using the keys below (first click the flash to get focus):

up/down, left/right: moves the vertical (V) and horizontal (H) iterator
home: deletes the whole tree
a: appends a child node to the (V) node
i: inserts a node after the (H) node
d: recursively removes all child nodes from the (V) node
r: removes the (H) node

Building a simple tree

Now let’s look how to build a tree in ActionScript. First we create the root of the tree and get an iterator pointing to this node:

var tree:TreeNode = new TreeNode("root");
var itr:TreeIterator = tree.getTreeIterator();

The root has three children, so lets add them:

for (var i:int = 0; i < 3; i++)
{
    itr.appendChild("node" + i);
}

Now the root’s second child (’node1′) has children by itself. To insert them, we first have to adjust the vertical iterator so it points to ‘node1′. First one step to the right, then one step down the tree:

itr.nextChild();
itr.down();

Now we can add ‘node3′ and ‘node4′, this time in a reverse order:

itr.prependChild("node" + 3);
itr.prependChild("node" + 4);

The first time we add a child node to an empty node, the horizontal iterator is automatically initialized to point to the first child, which in this case is ‘node4′. So to create ‘node5′ and ‘node6′ we only need to go another step down.

itr.down();
itr.appendChild("node" + 5);
itr.appendChild("node" + 6);

Finally we want to add ‘node7′. Therefore we ‘bubble up’ the tree until we arrive at the root node, go to the rightmost child, one step down and add it:

itr.root();
itr.childEnd();
itr.down();
itr.appendChild("node" + 7);

The dump() method invoked on the root node prints out the complete tree, as you can see it matches the tree above.

[TreeNode > (root) has 3 child nodes, data=root]
+---[TreeNode > (leaf), data=node0]
+---[TreeNode >  has 2 child nodes, data=node1]
|    +---[TreeNode >  has 2 child nodes, data=node4]
|    |    +---[TreeNode > (leaf), data=node5]
|    |    +---[TreeNode > (leaf), data=node6]
|    +---[TreeNode > (leaf), data=node3]
+---[TreeNode >  has 1 child nodes, data=node2]
|    +---[TreeNode > (leaf), data=node7]

Preorder and postorder traversal

Now that you have created a tree structure, you need a way of traversing the nodes so you access the node’s data. There are two common recursive algorithms for doing this. The preorder function first visits the node that is passed to the function and then loops through each child calling the preorder function on each child. The postorder on the other hand does the opposite: It visits the current node after its child nodes.
To see this in action just click a node in the demo below. The numbers indicate the order in which the nodes are visited.

The TreeNode class also supports a regular iterator using hasNext() and next(). This matches the preorder iterator, but is implemented in a non-recursive way.

See also:
Linked lists
The queue class
The graph class

Data Structures released

I’ve just released the first version of my data structures package for AS3.
There is no example code included, but I have started writing some simple demonstrations which I’ll post successively.

‘Data Structures For Game Development’ finished

My data structures library is finished and will be released next week as open source under the MIT-license. It has been converted to AS3, enhanced and simplified in numerous ways. What’s left to do is writing some code examples and improving documentation.

The library, of course, can be used for anything, not just games. But I have developed it with games in mind, where each structure is designed to be as simple and fast as possible, leaving only a minimum implementation (which also means that I didn’t care much about applying strict design patterns and OOP-rules).