Data structures are everywhere. There are piles of them that make up the world in QubeKwest, but those are all specialized ones. What happens when you need an advanced data structure for holding any random thing at all? As previously mentioned I’m working my way back up to the point where I get a block on the screen with a texture on it, and I’m finally getting closer to where I can start to write my texture packing algorithm. The reason for the progress is that I’ve made some more data structures.
Since I last checked in with an update on the blog, I’ve coded a few. First, because it’s super easy, I made a doubly Linked List. Then, once that was working the way I liked, I added some extra bits to let that linked list act as a Stack or a Queue. Next, I moved on to coding a “Left Leaning Red Black Tree.” That is a super fancy version of a binary search tree that specializes a Red Black Tree with some additional constraints that are supposed to make it easier to code and to understand. Naturally, I failed to code it or even remotely understand it.
With the Red Black Tree removed from my code base, I spent a bit of time picking over Wikipedia to find a different binary search tree that I liked better. (And more importantly had any hope of understanding and coding.) This led me to the AVL Tree. Unlike a Red Black Tree which has a seemingly arbitrary collection of color rules to determine whether a node is red or black, AVL Trees simply use the height of the tree to determine whether or not some part of the tree is out of balance by too much. In other words, still a binary search tree that self-balances, but this time with rules based on easy to understand things that are easily defined in a tree structure.
While I expound on the logical virtues of the AVL Tree over the Red Black Tree, I must take a moment to clarify that neither is a simple thing to code correctly. In my case, writing a functioning and unit test passing AVL Tree required over a week and 26 pages of densely packed notes with everything from diagrams of rotation algorithms, notes on edge cases, and tables of balance factors to examples of hand drawn and hand rotated inserts and deletes. The core tree code is 618 lines and 19 KB and 20 unit tests to cover all the edge cases I could think of. (That doesn’t include the code for the tree nodes, iterators, or the tests for those.)
To make things more complicated, my tree implementation also uses nodes that hold references to their parents. It’s not a required feature, and it definitely makes all the functions a bit more complicated, but it allows easier traversal of the tree. Lastly, my base implementation acts as a key-value pair. So the tree is ordered by the key, and searched through by key, but most functions return the value. This makes it act a bit like Java’s HashMap, but without the actual hashing or bucketing or any of the other things that data structure does. Ok, that means it’s essentially nothing like a HashMap except for the key-value part.
Once my tree was functioning properly, I used it as the basis of my Priority Queue. Object oriented coding is entertaining in that way, because I got everything I need out of a Priority Queue for only 70 lines of code, and almost all of those lines are either curly braces or elaborate JavaDoc comments.
One of the primary reasons to write your own data structures as a game programmer is to give yourself a place to manage memory better. Whether that’s through custom memory allocations, object pools, or some other creative means to dodge the garbage collector, you often can’t integrate those things without having coded something yourself. My data structures do not yet have any of those fun memory optimizations. For now, they just let Java handle the job with the built in garbage collection routines but if I start getting stutters in my game I’ve now provided myself a convenient place to hook in object pools. Also, while there may well be other general purpose advanced data structures I need to write before the game is done, I figure this collection will get me well on my way.