Category: Development

I was talking to a coworker about the trouble I’ve been having with coding the network engine for QubeKwest and his comment at the end was simply “The struggle is real.”  While the response was intended to be a joke, it turned out to be accurate too.  I’ve previously written about networking and how I’d utterly blown up what I’d written.  While that is true, there is actually a little more to the story and it took a very long time before I got back to trying again.

I have a deep and passionate dislike for Windows 8 (any of the various flavors) and I had a laptop that I was coding on that came with Windows 8.  The result of this was that I wanted almost nothing more than to have any other operating system on it.  When Microsoft presented the opportunity to preview Windows 10, I jumped at the chance the very day they allowed it and had it installed on that laptop that very evening.  Within fairly short order after that I’d gotten all my various development tools set up again and was ready to go.

The first project was coding a chat server and client that was written using the synchronous java.net package with Swing as the UI toolkit.  It actually worked quite well after about 2 days and never made it anywhere near source control before a Windows 10 preview release caused me to lose it just a couple of days later.  I wasn’t willing to let that be the end of the story, so once things were up and running again, I started over, this time using the asynchronous java.nio package with JavaFX as the UI toolkit.  It was like stepping into the future.  A vastly different and obscenely confusing future, but the future none-the-less.

To get this version of a chat server and client working took closer to 2 weeks and at the end it was only sort of working.  I was proud of what I had managed to pull off, and once again it never made it anywhere near source control.  Those of you out there that are picking up on a pattern here are highly accurate in your observation, but at the time I wasn’t really thinking about source control for a simple proof of concept side project.  Well, this version was also lost.  As it turns out, this time the Windows 10 preview patch actually bricked my laptop.  After 3 days of nearly constant attempts to boot the laptop at all, I finally managed to unbrick it and in the process was forced to fully wipe the drive.  Yep, lost that version too.

Then, with the hope of stopping this hideous pattern, I decided my next attempt would be directly inside the QubeKwest code base and would be checked in to source control over and over as I developed it.  This is the version that the other blog post referred to when I said “I managed to substantially break it.”  In the end, that version was turned into a single massive code comment just so I could get it to compile at all.  That was the final fate of the third version of the network code.  It lived on as a giant comment for a long time, and was eventually removed entirely from the code to make room for the fourth attempt.

The fourth version was started from scratch and has been through a real struggle of what I call refactoring and unrefactoring.  Yes, I’ve decided unrefactoring is an actual word.  I’m defining it as the action required to undo the effects of having refactored things.  In this case, several parts of the server and client code were refactored to share a common base class.  As it turns out, they aren’t quite as similar as I first imagined when I went down the refactoring path and I ended up fighting the results of that refactor almost constantly.  Thus, I unrefactored the code and eliminated the base class putting the necessary bits back into the server and client code where they probably belonged anyway.

After all the work involved in the unrefactoring, I am back to where I can try to continue the process of coding the network engine.  Fear not, the code is solidly and repeatedly checked in to source control so it’s not going anywhere.  I have quite a ways to go to get the networking code to work the way I need it to, but I’m working on it and making good progress.  The struggle is real.

This post may have a bit of repeated information for those that follow along closely.  A whole lot of Chunk related refactoring happened because I had a new idea about how to do some things.  Thus, to make sure everyone is on the same page, I’m going to explain the way it was, and the way it ended up, and why.  Feel free to skip around if that suits you.

Chunks are collections of blocks that are 16x16x16 and before the refactoring there were three kinds of them in QubeKwest under the covers.  The first is an EmptyChunk, it is a chunk where the whole thing is air.  It gives the ability to represent vast empty sections of sky with virtually no storage space.  The second is a UniformChunk, it is a chunk where the whole thing is made out of a single material.  For example, under a mountain where the whole thing is rock or way underground where you might encounter all lava.  Technically, there is nothing stopping you from using a UniformChunk full of air instead of an EmptyChunk but it will take a little more space, so it’s a bit of a waste.  The third kind is called a FullChunk (formerly called just Chunk).  It details every single block individually and can thus hold anything in any arrangement.  All of these types of chunks extend ChunkParent as their base class so they can be treated as the same thing.

The basic concept behind all these different kinds of chunks was that they could be promoted to other types based on blocks being changed inside them.  For example if you have an EmptyChunk or a UniformChunk and you change even a single block within it, you have to also change it into a FullChunk.  One of the problems with this was that the space it takes to store a chunk has no middle ground.  You go from just a few bytes for either an EmptyChunk or a UniformChunk to around 65,000 bytes for a FullChunk.  The other problem is, where does this promotion occur so it’s easy to deal with?

The first problem inspired thought about how to make a chunk that can store somewhere between a single type of block and one that has all 4096 individually detailed.  This got me thinking back to something I’d coded as a kid.  The original Doom saved screen shots in the PCX graphics file format.  This ancient format was both palettized and run-length encoded.  I learned the inner workings of the PCX file format and coded a PCX decoder so I could make little stop motion movies using Doom screen shots.  For QubeKwest, I’d originally considered run-length encoding for blocks in a chunk, but ruled it out because of the constant heavy updates to the encoding when changes are made.  This left the idea of using a block palette to reduce the space needed to save a chunk.  Basically it’s like an artist’s palette that has things like “1 = air” and “2 = granite” in it so I can reference all of the pieces of granite in a chunk just by using the number 2 instead of a whole block description.

The new PalettizedChunk was born.  First, I considered using a palette that used a short (16-bit) index.  This was a bad choice because it would actually allow enough entries in the palette to represent every single block in a chunk individually, and could thus result in chunks that take more storage than the original FullChunk did.  Next, I considered using a byte (8-bit) index.  This would limit the number of blocks in the palette pretty heavily, but it would drastically reduce the space needed to store a chunk.  I further realized that because java uses stupid signed bytes, I decided to limit the indexes to 0 to 127.  I could have applied a bit of math to the index to use all 256 possible spots in a byte, but I didn’t like all of the primitive type promotion it would involve so I didn’t end up doing it that way.  This new version can store 128 kinds of blocks and only takes about 10% of the space as a FullChunk.

The promotion can now go from either EmptyChunk or UniformChunk to a PalettizedChunk when a single block is changed, and then to be promoted to a FullChunk only when the chunk has more than 128 different types of blocks in it.  This still leaves the problem of where do the promotions between chunk types occur?  And when they occur, how do the various references to chunks get updated without taking a lot of work?  The answer to both questions is the idea of a ChunkProxy object (later renamed simply “Chunk” so I didn’t have to type “Proxy” in a million places in the code).

This new object wraps any child of the ChunkParent class (which all 4 types of chunk are) and provides access to the various methods that are actually on the chunk inside.  This proxy knows which kind of chunk it is wrapping, and promotes it as needed automatically when an action performed on it requires it.  Now the rest of the codebase can just use ChunkProxy objects where they previously used ChunkParent objects.  If a chunk gets promoted, the proxy that wraps it stays the same.  That means that other things that refer to it don’t actually need to change, and in fact have no idea the promotion has occurred.  It’s the best of both worlds.

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.