Month: February 2017

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.