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.
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:
- Mark the starting node and enqueue it.
- Process the node by calling a user-defined function on it.
- Mark all connected nodes and also put them into the queue.
- Remove the node at the front of the queue.
- Repeat steps 2-5 with the node that is now at the front of the queue.
- 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!