QubeKwest Blog

I’ve now put in a rather large amount of work on the underpinnings of the game, but have essentially nothing to show for it. To ensure I have the motivation to continue with this project, I have once again resumed my efforts of learning OpenGL. I figured if I could see some part of a virtual world on the screen then I would be instantly motivated to keep plowing along. To that end, I have started reading OpenGL Programming Guide: The official Guide to Learning OpenGL, Version 4.3 (8th Edition).  Amazingly, even though the title of the book is crazy long, the book itself is even longer.  It’s a monster 984 page tome that covers basically the entire OpenGL API.

It’s a serious undertaking to plan to read a book of this size cover to cover, but as a 3D graphics noob, I need everything it can offer me.  I’m presently something like 165 pages in and I’ve learned a lot so far, but I’m having some trouble because I feel like the order the information is presented in needs a bit of help and the book needs an editor pretty badly.  Shortcomings of the book aside, I have a long way to go on my reading.  Sorry this post isn’t especially interesting, but it has been a lot of reading and studying and trying to internalize hundreds of very dense pages of a book.  Hopefully in the future I’ll learn enough to get something on the screen and my posts will start including screen shots.

I finally stumbled upon an area of the code for the game that would benefit greatly from a bit of proper planning.  As previously discussed, the world is made up of clusters, each of which is stored in its own file.  As not previously discussed, my original plan was to unceremoniously dump the files into a single directory.

For most worlds this poorly planned approach would cover you pretty well.  For example, a world that was as tall as Minecraft’s world is (256 blocks), and covers 4096 blocks in each direction on the surface (a pretty big world actually), we’re only talking about 2048 cluster files.  Most file systems can handle that without any issues at all.  What happens when a group of avid explorer types start wandering around with the goal of expanding the known world?

What happens if over the span of weeks they explore the world to 16,384 or so in all 4 directions (32,768 blocks across), and they dig holes and build towers that result in a world that is twice as tall as in Minecraft.  Now we are talking about 262,144 files in the world’s data directory.  For most modern file systems, this won’t result in anything blowing up, but the performance will typically drop off pretty badly.  That’s not really a good thing for a game designed from the ground up to make pretty heavy use of the storage system.

A simple pattern of X_Y_Z.qkc (QubeKwest Cluster) will work nicely, but how do I arrange those files so that the 79,228,162,514,264,337,593,543,950,336 possible cluster files don’t melt file systems way before you get to that number?  What I came up with is using the nibbles of X, Y, and Z to build a directory structure.

A random file name holding a cluster might be:

01234567_89abcdef_f0e1d2c3.qkc

If I take each of the nibbles in turn from the X, Y and Z coordinates and combined them, I would end up with the following 3 character values:  08f, 190, 2ae, 3b1, 4cd, 5d2, 6ec, and 7f3.  Next, if I ignore the last group of characters, I would end up with 7 values.  When I string them all together as a 7 layer nested directory, what I get is:

08f/190/2ae/3b1/4cd/5d2/6ec

Because each of those values is 12 bits, that means I now have a directory structure where no single directory will ever have more than 4096 files or directories in it.  This should make everyone’s file system happy and prevent slow down.  I decided that even though the file name only actually needs to have the last nibbles in the name, I would use the whole coordinate anyway.  This means that our sample cluster file now has the complete path of:

worlds/WORLDNAME/data/08f/190/2ae/3b1/4cd/5d2/6ec/01234567_89abcdef_f0e1d2c3.qkc

In case that doesn’t make it clear, each world has the same directory structure.  In the example above, the name of the world the user created is WORLDNAME.  I’ll need a way to ensure worlds have names that aren’t too long, and don’t include any characters that are invalid as directory names, but that’s a problem for a different day.

As I worked on the concept of a Feature, I also came up with the idea of a FeatureCursor to make drawing in a Feature a little easier to do.  A cursor is a lot like what you are probably thinking.  It’s a system for tracking a position within a Feature.  You can move it around and place blocks as you go.  There are also fun bulk block placement methods for drawing lines and quickly putting up walls and that sort of thing.

At first, I imagined this cursor thing would only be useful in a Feature, but then I got to thinking a similar thing would be useful for drawing in the world directly too.  Then another one for filling in the blocks in a raw chunk came to mind.  That means these cursor things became something useful for all sorts of generators when constructing the world.

There are several different concepts of geography space in QubeKwest.  The world itself operates in 3-tier geography space (blocks in chunks in clusters), Features operate in 2-tier geography space (blocks in chunks), and raw Chunks operate in 1-tier geography space (just the blocks they contain).  What that means is that the trickiest parts of getting cursors to work are making sure they move in the appropriate number of tiers correctly, that they follow the bounds of the space they are working in, and of course that placing blocks follows the correct rules.  That meant a little bit of refactoring was in order.

I didn’t want to have to rewrite the various line drawing and wall placing functions for each new type of cursor that I ended up making, which meant the creation of a new parent class called BlockCursor.  It is abstract and holds all the bulk placement methods so child cursors only need to provide how the cursor moves around and how blocks are placed for all of the same drawing methods to work across multiple cursors.

For that to work however, I had to make sure none of the methods in BlockCursor ever tried to directly set the position of the cursor (because it can’t know what geography space is being used) or to draw anything using methods other than the ones provided by child cursors.  When I found a C++ implementation of Bresenham’s line algorithm in 3D it became especially important that I didn’t have to maintain multiple versions of that method after I’d rewritten it in Java and made it work with cursors.  It’s a pretty hairy algorithm it get right and maintaining multiple versions of it for different cursors would be a terrible idea.

After a bit of work, I am satisfied that my pattern for cursors is sound.  Whether that remains true mostly depends on whether or not actually using these cursors in the various generators proves to be a pain.  That is a bridge I will cross some other time so I can remain focused on actual progress.

After a bit of working on things, I tried to write a little code that I just expected would work.  When what I tried didn’t exist yet on the other object, I got to thinking.  How many of the things that I just expect to be there are actually written?  This started a code audit that I initially hoped would be two or three days, but quickly turned into a two week long adventure.  This process was exactly as tedious and boring as you are probably imagining and involved several rather elaborate tables of check marks in my QubeKwest notebook.

As it turns out, a lot of my objects were missing a lot of the things I wanted them to have, and some other ones actually had completely different ways of doing the same thing.  (For example, a clone method instead of a copy constructor.)  That meant coding things that were missing, recoding things that I felt were weird, removing things that should never have been there in the first place, and adding tests to cover all of the things that changed.  While I was working on the various audits I was performing, I came up with a few new patterns I wanted in place and added them to my notes.  I even had a few columns for whether or not the files had all the JavaDocs I wanted them to have.

I’d like to say this was just a bit of “Hey, my Vector4 should have a static isEqual on it.” followed by coding it and calling it a day, but that’s not really how this process went at all.  Each time I’d bump into another thing that made me sad, I’d make another list with more check marks.  This in turn led me to wander into the code again from a different angle.  For example, once I’d added serialization to my math library, I realized that I originally wanted all of the functions to have both “static” and “with this” versions of all the math functions on all the objects, and that what I had was a bit of pot luck.  More check lists, more coding things, more writing tests to get code coverage back to where I want it.  This in turn inspired a test audit that made sure everything was tested correctly and where the tests themselves were named correctly (following the pattern I’d established anyway).

In the end, after weeks of checking out the code, working on new bits, typing JavaDocs, and adding tests for things I didn’t even realize were missing, I think the math and data packages are in a much better place.  That makes me happy on a deep fundamentally nerdy level, even if the process of getting there was sort of terrible to have gone through.

Serialization is the conversion of an object into a magical stream of data that can be deserialized later back into an object.  At first glance you could probably be convinced that this is a totally unnecessary thing for objects to be able to do.  For most simple projects this sort of thing never even comes up, so you’d be right if you figured they’re useless.  For QubeKwest however, they aren’t just needed, they’re needed a lot.

Consider for a moment all the data in QubeKwest.  Everything from the world you are walking around in to chat messages between players is just data at the end of the day.  If the objects in the game can be easily converted to data and then can be easily restored, you suddenly have lots of fun new options for how they can be used.  Pure data versions can be shuttled down a network wire or stored away in files on the disk.  Later when you need the objects again they can be easily loaded from the disk or reconstructed by the client on the other end of the network.

There are loads of different ways to serialize data.  Some are crazy flexible, some are practically automatic, some involve elaborate frameworks, and others are hard coded.  Some make serialized data that is large and fluffy and others are small and concise.  Due to the vastness of the worlds I’m trying to build with QubeKwest, it makes sense to make sure my serializer makes as little data as possible.  That loses me some flexibility, but it means I can store larger worlds in less space and that I can use less bandwidth when you’re playing.

I set out to make my own serialization patterns and to say it’s been an evolutionary process isn’t giving it proper credit.  My first idea involved saving things into 32-bit integers.  I built a collection of functions for aligning data into the integers and started making the basic patterns of how my serialization would work.  Almost immediately I realized that serializing things into integers was a total pain in the butt, and really not worth the trouble.  With that, version 1 died a horrible death.

Later, while learning the finer points of NIO and LWJGL, I realized that both of those make rather heavy use of ByteBuffers.  My integer pattern could be adapted fairly easily to use bytes and that allowed me to throw away all the issues with aligning data in integers and all the masking and shifting that involves.  Even more conveniently, ByteBuffers already have methods for storing and retrieving every type of data I could possibly need.  They even let you add other ByteBuffers to them so objects that have other serializable objects in them are easier to deal with.  This was version 2 and it died when I tried to deserialize things without any direct knowledge of what I was deserializing.  

The next version added the idea of a header to the serialized data.  I could use that to identify what type of data it is I’m looking at when it’s still in its serialized form.  The header data itself was only defined by a collection of constants and the way several helper methods dealt with it.  This wasn’t a great solution, but it lined up with the mess I’d been crafting.  This version also started to add the idea of variable sized data objects.  I freely admit that it was wishful thinking to pretend that everything could be a fixed size, but I knew that variable sized things were going to add a lot of complexity.

Before long, I realized that I would probably need multiple versions of a particular type of object over time.  I know I saw this coming, but for some reason I didn’t include this feature into the header data I was using.  The problem is that if I can’t identify which version I’d serialized, I wouldn’t be able to load it properly.  With that, version 3 also passed on.

The evolution continued when I realized I didn’t just want versions, but also that I’d created an honest to goodness mess of things for serialization.  My interface had static methods on it to avoid creating dummy objects just for the sake of asking them questions about serialization.  The problem with that, is that the static methods were literally on the interface and while they could be overridden they were not enforceable.  Every time I implemented a new object, I had to remember to create those too.  As mentioned before, my header data was a twisted jumble of constants and helper methods.  To fix that I created actual serialization header classes.  That meant a bunch of my helper methods now had a proper place to live and all the constants that told where things go could just be removed.

Attempt number 4 was born as I cleaned up all of the serialization patterns that were broken and sad.  It was a total refactor.  To make the use of the serialization more logical in other packages, I also pulled it into its own package.  All these changes were just the tip of a pretty serious ice burg because after I started the refactor, all of the objects that I had already created the serialization functions for had to be revised to follow the new patterns I’d just established.  Now two days later, I think I’ve finally finished and I’m actually really happy with how it all works.  Hopefully this version will be the last one, but if I’m being honest, I sort of doubt it.