Jade.Ai.Graphs ready for use
These last weeks I've been working on a very basic namespace for Jade.Ai: Jade.Ai.Graphs. This namespace contains the classes needed to execute graph-based algorithms. Currently it only supports Breadth-First-Search, Depth-First-Search and A*. In Jade 1.1 we had also Dijkstra algorithm but you can get the same result using A* with an heuristic that always returns 0.
I could have just ported the 1.1 code to 2.0, but I decided to rewrite it. I don't remember exactly how, but some time ago I found the Boost Graph Library (BGL) and I must admit I liked a lot how it was organized. After that I also found that there was a C# port of the BGL called QuickGraph (pretty amazing stuff). So I decided to port also the BGL to C# for Jade 2.0. Rest assured I didn't port the whole BGL to C# (it is pretty big), I only coded the classes I felt necessary for our needs (that's why I didn't simply use QuickGraph, it has too much stuff and there are some inner things I don't like much).
So, let's get a little overview of what you can find in Jade.Ai.Graphs (better read this looking at the Jade.Ai.Graphs code or you won't understand a thing :p):
- Root/Base folder: the interfaces ISomethingGraph represent several types of graphs. The hierarchy starts in IGraph, that gives nearly no information, and ends in IVertexAndEdgeListGraph, where you have several methods and properties to get the vertices, edges, out edges,... The interfaces IMutableSomethingGraph represent the same information as the ISomethingGraph interfaces, but also give you Add/Remove operations so you can modify the graph. The idea is that you use a Mutable graph to build the graph from your data and then the algorithm uses the non-mutable graph to perform the algorithm (as the algorithm shouldn't modify the graph data at all).
- Algorithms: here you can find the BFS, DFS and A* implementations. The algorithms are implemented so you can perform the full algorithm in one call (Compute() method) or you can execute step by step (Step() method). The Step() method is pretty useful for debugging and also for time-sliced searches (quite useful in games). Also, every Step the algorithms raise several events when interesting things happen: a vertex is discovered, an edge is examined,... The idea is that external classes will add handlers to those events to gather interesting data about the algorithm execution. I must admit that I'm not very happy with the BaseAlgorithm class, that's something I'll improve in the future for sure.
- Implementations: if the root folder was full of interfaces, here you'll find implementations of those interfaces. Currently there's only an AdjacencyList class, which performs as a directed mutable graph that can have parallel edges if needed. This class implements the IMutableVertexAndEdgeListGraph so it covers all the interfaces in the base namespace. I will probably add in the future an UndirectedAdjacencyList and an AdjacencyMatrix class, but for now on the AdjacencyList is more than enough.
- Observers: some useful classes that observe several events that the algorithms raise. PredecessorRecorderObserver tracks the predecessor of every vertex (useful to know the path to get from one vertex to another) and TargetObserver tracks if a given vertex has been reached. They are more an example than anything else, but they should work as inspiration for other custom observers when you are using the library.
And that's it :) But when I started the new AI library for Jade I did the promise of not writing a lot of code without tests and examples, so I have also added several examples in the AITestApplication project. To try them do the following:
- Run the project.
- Choose a source and a target vertex (target is not mandatory). For example if you want to try BFS and DFS choose source 0 and no target. If you want to try Dijkstra choose source A and target F.
- Click the button of the algorithm you want to execute. You'll get a file dialog where you have to choose a graph file. I have included 2 examples in AITestApplication/Graph/Examples. The file format is pretty easy if you want to create your own graphs to test the code.
- Once you choose the graph file the algorithm will execute and put the result in the big text box. You'll get the list of vertices in the order the algorithm examined them and if you set a target, the path from the source vertex to the target vertex.
Let's look a little at the code to give you an idea of what's happening (warning: code is very ugly right now, I'll clean it later on). The following code snippets are from GraphDemoPanel.cs, method buttonBFS_Click.
1: // Create the grpah
2: AdjacencyList<Vertex, Edge> graph = LoadGraph();
3: if (graph == null)
4: return;
5:
6: // Create the algorithm
7: BreadthFirstSearch<Vertex, Edge> algorithm = new BreadthFirstSearch<Vertex, Edge>(graph);
First we use LoadGraph() to create an AdjacencyList. It has two generic parametters: the vertex type and the edge type. Second we create the BreadthFirstSearch algorithm passing him the graph (and with the same generic parametters as the AdjacencyList).
One of the things we want to track in the example is the order in witch the algorithm examines the vertices, so we write a simple method:
1: private void ExamineVertex(object sender, VertexEventArgs<Vertex> e)
2: {
3: _examinedVertices.Add(e.Vertex);
4: }
_examinedVertices is a List<Vertex> where we add the vertices the algorithm discovers.
Now we should connect this method with our algorithm.
1: _examinedVertices.Clear();
2: algorithm.ExamineVertex += ExamineVertex;
Just add the method to the algorithm event and we are set :)
Let's add some other observers to the algorithm. First we declare them:
1: TargetObserver<Vertex> targetObserver = new TargetObserver<Vertex>();
2: PredecessorRecorderObserver<Vertex, Edge> predecessorRecorder = new PredecessorRecorderObserver<Vertex, Edge>();
We declare a TargetObserver to keep track of the target (if one is set) and a PredecessorRecorderObserver to keep track of the path to reach each vertex. Now time to connect them to the graph:
1: // Track the predecessors
2: predecessorRecorder.Attach(algorithm);
3:
4: // If there is a target, set it and attach the observer to the algorithm
5: if (textBoxTarget.Text.CompareTo(string.Empty) != 0)
6: {
7: foreach (Vertex v in graph.Vertices)
8: if (v.Label.CompareTo(textBoxTarget.Text) == 0)
9: {
10: targetObserver.Target = v;
11: targetObserver.Attach(algorithm);
12: break;
13: }
14: }
We just use the Attach method to connect the observer methods with the algorithm events. Easy :)
Time to initialize the algorithm:
1: // Initialize the algorithm
2: foreach (Vertex v in graph.Vertices)
3: if (v.Label.CompareTo(textBoxSource.Text) == 0)
4: {
5: algorithm.Initialize(v);
6: break;
7: }
You have to call to Initialize before executing the algorithm or it won't work!
And now let's execute the algorithm itself:
1: // Iterate through the algorithm
2: while (algorithm.State == AlgorithmState.Running && targetObserver.TargetFound == false)
3: algorithm.Step();
If we weren't tracking the target we could just call algorithm.Compute() and execute the full algorithm in one go, but we want to stop when we find the target so we have to execute it this way.
The rest of the code is just printing the data to the textbox, nothing special there.
And that's all about Jade.Ai.Graphs. I know it lacks an A* example; I'll do it, but I wanted something more spectacular as output instead of a simple textbox, so it will take me some time to put it up. Once the A* example is done I'll write some small tutorials for people who want to learn how to use the graphs and some explanations about the inner workings, but the code will be probably similar to the one I have just explained.
Now my next objective for Jade.Ai is to add Behavior Trees, Hierachical Task Networks and Planners. Most games nowadays use state machines and scripting for their Ai, but there has been a special interest lately in HTN and planners, specially after the game F.E.A.R. I have been following for quite time the excellent AI blog of Alex J. Champandard and I have decided that this kind of techniques would be really useful for Jade.Ai users. It's going to be a hard work as I know very little about the subject but I think it will be a worthwhile effort.
Next week don't expect something spectacular here: I have to make a big XNA demo with Kartones and Jorge so I'm going to be pretty busy :S