In this assignment, we were tasked with building the framework to generate graphs (which I will refer to as navmeshes from here on), localize and quantize them, and pass the pathfinding functionality to our boid agents. I used this assignment as an excuse to learn more about template classes by writing a flexible priority queue and optimizing a graph structure using a map with Node IDs (int) service as indices with a child vector containing the edges leaving that node. During this assignment, I spent a lot of time doing things in what I considered an ‘ideal’ way. I’ve found that this isn’t always effective strategy, since you can only accomplish so much in a finite amount of time. Getting something to work is sometimes more important than designing it to be the most robust. Because each of these assignments build upon each other, I thought that remaining flexible was key. This assignment has helped me realize that—as a result of the way this class is structured—I can forget about jumping through certain hoops in favor of assignment portions that I feel offer a greater opportunity for learning. I’ll be updating my code (and this post) as I complete features for this system.

The backbone of this entire assignment are the graphs and their periphery data structures. If these are constructed thoughtfully, they can be both flexible and have a small memory footprint. This memory footprint was important to me, since I knew that I wanted my navmesh to be able to perform even when the resolution of the mesh is really high.

DirectedWeightedGraph and Edge functions

DirectedWeightedEdge Struct

Node struct

Drawing the graph structures would help me debug behavior later and give me something neat to show, so I liberally used the #ifdef macros shown to make sure that the size of a Node and DirectedWeightedEdge would only be as big as strictly necessary. This is made even more important when you consider that a DirectedWeightedGraph has vectors of both Nodes and DirectedWeightedEdges which will contain a very large number of objects (especially DirectedWeightedEdge). Some quick math shows that with debug draw on, a DirectedWeightedEdge takes at least 52 bytes, and without the debug draw only 16. When we consider a navmesh with approximately 10000 nodes, and approximately 80000 edges, we’re saving ~2.9 Mb of memory. I know that may seem insignificant, but a 70% reduced memory footprint becomes really significant as map geometry gets more complex and the maps get larger. Another small note is that when a DirectedWeightedGraph is instantiated, the desired number of Nodes is taken as an argument and used to initialize the vectors of Nodes and Edges. Because these grow dynamically by a factor of two, it’s conceivable that these vectors end up much larger than we’d need. By taking this argument at initialization we can potentially save a lot of memory later.
Actually constructing the map, given that it was never a 2D array had some fun moments. Here are a few images of incorrect versions…

After some stumbling I ended up with two graph versions, one with randomly assigned weights and edges to neighbors, and one that is ‘flat:’ weights scaled with distance. Each of these methods use Euclidean distance as heuristics, but Manhattan distance is also available. They behave the same way with a flat navmesh.

You might think that with these nicely thought out data structures I would have a beautiful implementation for A* and Dijstra’s. I’m not happy with them, however. There are a few problems, most of which can be attributed to time. The first is a problem with my priority queue. For it to be able to use functionality like “find” and “sort,” the operator < and == need to be defined. The < operator is easy, since each element has a priority. The == isn’t particularly difficult either, if you thought to use a pointer for the priority queue’s elements instead of the actual objects. This isn’t a huge change, but I didn’t have the time to correct that design decision. As it is now, I need to overload the == operator for each potential type that could go in the priority queue. This really defeats the purpose of a templated priority queue. I should instead be comparing the data’s memory address. I’d also like to go through and implement this using smart pointers, so that we never have to worry about dangling references or access violations.

I was thoroughly rushed on this assignment, and will continue to update it in the coming weeks. I’m excited to construct a dynamic environment. I plan to add AABB collision obstacles that are randomly generated when you play. Stay tuned!