Month: May 2016

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.