Category: Development

I’ve been thinking a lot about how UV maps (rules for how to stick textures on geometry) work, how I expect to use them, and how I can best optimize using them.  My first theory was that each mesh (a model made up of vertices and indexes) would have a single associated UV map for how to apply a texture to it.  With animated textures and blocks that look different based on what season it is and you start to get way too many meshes that are effectively actually the same mesh with a different way of putting textures on them.  Thus, it clearly doesn’t make sense to have only one UV map per mesh, especially when practically everything in the game is a block.

For normal games, a single UV map per model probably makes a lot of sense and is exactly how they work.  Normal games have loads and loads of meshes and each one has one way of putting textures on each of them.  Even if you have lots of different textures (skins), the mapping is the same.

In QubeKwest there are a small number of models (since virtually everything is made of blocks), and to optimize the amount of texture data being used, there are a lot of different ways to put textures on them.  Imagine a block for a moment.  I could make just one UV map that details how to put a separate texture onto each of the six sides of a block.  That way nearly all possible blocks could be textured the same way.  What happens if a block has the same texture on all six sides?  In QubeKwest this is actually a pretty common thing since a lot of types of rock look the same from all six directions.  If all six sides are placed onto the block separately as described above then there would need to be six copies of the same texture to make that happen.  Why have six copies of the same texture if the same thing can be done with just one?

With this in mind, I came up with several ways to texture blocks.  They all use the same actual geometry, but this approach improves how much actual texture is needed to make them pretty.  For the descriptions below, a block has six sides called North (N), East (E), South (S), West (W), Top (T) and Bottom (B).  These are some of the approaches I’ve come up:

1. A single texture on all 6 sides of the block (N, E, S, W, T, B).  (1 total texture.)
2. A single texture on each of the 4 edges of the block (N, E, S, W) and another on the Top and Bottom (T, B).  (2 total textures.)
3. A texture on each of the 4 edges of the block (N, E, S, W) and 2 different ones for the Top (T) and Bottom (B).  (3 total textures.)
4. A different texture on each of the six sides of the block (N, E, S, W, T, B).  (6 total textures.)
5. A single texture on all 6 sides of the block (N, E, S, W, T, B) where the texture changes for 4 seasons.  (4 total textures.)
6. A single texture on each of the 4 edges of the block (N, E, S, W) and another on the Top and Bottom (T, B) where the textures change for 4 seasons.  (8 total textures.)
7. A texture on each of the 4 edges of the block (N, E, S, W) and 2 different ones for the Top (T) and Bottom (B) where the textures change for 4 seasons.  (12 total textures.)
8. A different texture on each of the six sides of the block (N, E, S, W, T, B) where the textures change for 4 seasons.  (24 total textures.)
9. A single texture on all 6 sides of the block (N, E, S, W, T, B) where the texture is animated for 8 frames.  (8 total textures.)
10. A single texture on all 6 sides of the block (N, E, S, W, T, B) where the texture is animated for 8 frames and where the textures change for 4 seasons.  (32 total textures.)

This collection of UV maps allows me some interesting things without chowing down massive amounts of texture space for the same texture over and over.  Number 1 in the list allows simple things like blocks of rock that are exactly the same on all 6 sides.  Number 3 allows things like dirt with grass on it.  The top would be grass, the sides would be something like grassy roots and dirt, and the bottom is just dirt.  Number 10 allows something like water to be awesome.  Water is always animated because it’s water.  In the spring time, there could be little chunks of left over winter ice floating in the water.  In the summer it’s back to just water.  In the autumn, there could be leaves floating in it.  Winter it may be frozen solid with little icy glimmers as it catches the light.

This presents another problem however.  That’s a LOT of UV data to have to manually come up with (anyone that’s tried to sit there with pen and paper to try to come up with UV data knows what I mean).  To that end, I’ve created a way to wrangle together all of the UV maps into one fun self calculating collection.  Now when I provide a UV map for number 10 above, I can provide the data for when the season is spring and I’m showing animation frame 0 and all of the other related UV maps are derived mathematically.

With all this stuff in place, I’m getting ever closer to being able to get a textured block on the screen.  For the old fans of QubeKwest, you may remember when I created enough JavaFX code to get a textured block on the screen and how that took me about an hour.  Now roughly a year later (granted I wasn’t working on it for 7 months) I’m almost back to the point where I can get a textured block on the screen again, but this time with LWJGL.

 

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.