QubeKwest Blog

It’s been a while since I’ve talked about what I’ve been working on.  Mostly the reason was that I felt it would get a bit repetitive.  Development has definitely been plowing along (something like 2500 more lines of code have been added to the project since the last update) but the actual “things” I’ve been working on are from the same list.

• I’m still trying to “get something on the screen.”
• I’m still trying to “make a texture atlas.”
• I’m still “messing with serialization.”

Mostly it’s been a lot of serialization lately.  There are really two types of serialized objects in QubeKwest.  The first is the type that is a fixed size.  These are things like Blocks that always take the same amount of data.  That makes them easy to deal with on pretty much every level when serializing them.  They simply have the data they have and it’s always in the same place.

The other type is variable sized.  Most of the structures in the game are actually this type.  For example, even though a Cluster always holds the same number of Chunks and should therefore theoretically be a fixed size, the Chunks themselves can actually be one of three types, each with their own fixed size.  That means that a Cluster can actually be anywhere from just over 2 KB all the way up to about 33.5 MB.  That’s obviously pretty variable.

The reason for my dive back into serialization was actually the difficulties involved with serialization and deserialization of variable sized objects that contain a variable number of variable sized objects.  (Which is unfortunately exactly what a TextureAtlas is.)  That led me to create a deserialization factory system.  Which in turn led me to making a bunch of tests for the deserialization factory, because you just have to know it’s going to work correctly.  Which in turn led me to the realization that I had a bunch of objects that had the methods needed to be serializable, but that didn’t do anything.

If you’ve read my previous posts, this probably sounds like rehashing things about texture atlases, checklists of things that need finishing, or solving problems that led to other problems.  Naturally, I’ve been buried in the coding of all the missing serialization functions instead of progressing toward fun goals.  I figure I’ll have enough code in this project for it to either become self aware or get something on the screen, what I’m not sure of is which one will happen first.

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.

The initial goal was “to get something on the screen.”  It seemed like a fairly straightforward goal really.  I wasn’t even especially picky about what was on the screen once I’d gotten it there.  A singe block floating in space with a texture on it would have made me very happy.  As it turns out, my simple goal ended up being little more than a good place to start.

As I read more of my OpenGL book and printed shader tutorials, I found the scope of this simple goal expanding.  The progression went a little bit like this:

• Get something on the screen.
• That something should have a texture on it.
• There’s no point building the entire framework for getting a texture on something when it’ll just be wrong immediately afterwards.
• That meant putting my textures into a proper texture atlas.
• Which meant I would need a way to store and sort my textures so I could arrange them into that texture atlas.
• Which meant I had a binary tree structure to build.
• Once that was built, I needed to be able to iterate over the rectangles in that tree.
• Which meant I’d need to make a Linked List class that could act as a stack or a queue.
• And so on…

So now, roughly 47 layers removed from my original problem, I’m effectively in a Computer Science Data Structures class.  I figure I’ll eventually unravel this mess and get back to working on the actual problem that started it.  I look forward to that time.

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.