I just got back from GDC… Woo what a trip!

There were so many cool experiences it would be impossible to go through them all, so I’ll just hit the highlights.

This was my first year going to talks, and I’ll definitely be doing that again in future years. I’ve been mulling around the idea of writing some curriculum to expose middle and high-school students to technology through game dev, and there was an amazing talk by AP Thomson at NYU Game Center about teaching flexible system design with procedurally mixed student projects. If you’re interested in computer science education, I would highly recommend checking that out in the vault (it’s titled “Stone Soup: Procedurally Mixing Student Projects to Teach Flexible System Design”). I really think that the concept of orchestrator-designer schemes for teaching coding makes a ton of sense, and can really be scaled to any class size or skill. Modern tools are so unbelievably advanced, that with some setup you could easily abstract as much or as little as you’d like away from your students. There were so many good talks I can’t mention them all, which is too bad. To anyone looking to go to GDC in the future, spring for summits, you won’t regret it.

On Thursday, my thesis team presented our game Sky Shepherd at the Intel student showcase. I had the opportunity to act as the face of our team and present the game to browsing devs. It was amazing to see how far our game has grown over the 5 month development up to that point. We got tons of positive feedback, and I met a ton of interesting dev from all over the country. We were even stationed next to UT Austin (the city I grew up in). Public speaking is really difficult for me, but I really enjoy putting myself out there and practicing those skills.

I also had the opportunity to play Magic: The Gathering with a bunch of Wizards of the Coast employees and Magic content creators. I learned how to read with the help of Magic cards, so I’ve been playing for a very long time. It was awesome to get to see what those personalities are like and share the love of that game with people who make it happen.

On the note of being social, last year (my first GDC) I was totally overwhelmed and lost. I barely spoke to anyone. This year I was determined to put myself out there and meet as many people as possible. I smashed my own expectations and am really proud of myself. All in all, I had a blast.

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!