QubeKwest Blog

As I progress on the data structures and the tests for them, I’m expanding further and further the things the engine will need to be able to handle and how those things will probably happen.  This results in a fair bit of thinking and refactoring as I go.  The most recent development is with work around the concept of a Feature.  These things represent a way I came up with to simplify how generators for the world work.

At its core, the world is randomly generated with noise maps that are all combined to make decisions about how the world looks at a particular spot.  These maps include things like coarse height (general massive scale waves in the landscape like mountain ranges), fine height (smaller scale variances that help to define rolling plains or hills or valleys), variance height (turbulence in the landscape), moisture (how wet or dry an area is), temperature (how hot or cold an area is), age (how old or young an area is), vitality (how vitally alive or dead and crumbling an area is), and possibly others I haven’t defined in my head yet.

This pattern works very well for landscapes and biomes, but makes for rather complicated generators for things that aren’t part of a natural landscape.  That in turn brought me to the idea of a Feature.  In a nutshell, a Feature is something like a castle, mine, dungeon, or village.  Something large and non-landscape based that exists in the world that some piece of code will have to generate.

Imagine with me for a moment that the world you are walking around in is being created as you walk a little ways out ahead of you.  By extension, if you are walking through totally uncharted areas, the same thing is happening out to the sides of you as well.  Now imagine that way off to your left is a castle, but it’s mostly on land that doesn’t exist yet because you weren’t close enough to it.  That means there is a little corner of a castle out there in the landscape, but that the rest of the castle doesn’t exist yet because it doesn’t need to.  With that scenario nicely gelled in your brain, now try to imagine how you would make a generator that knows how to make just a corner of a castle.  It has to be able to do that without the context of the rest of the castle, and when you can see the rest of the castle because you walked over to it, the new parts have to all properly line up with the old parts (walls, doors, rooms, decorative carpet, whatever).

This brings us back to the idea of a Feature.  A Feature holds the whole castle and lets you make it all at once.  This allows you to write your castle generator in a way that doesn’t need to care about building a small part of a castle at a time.  So now we have castles that can be built as one whole thing and the game engine just needs to be able to merge them into the landscape as it needs to.  This comes with a bit of complexity for the engine itself, but it should greatly simplify the task of making generators for anything that is man made.

The revision of my world geography objects inspired a lot of other thought about how my world was going to work.  Specifically how I was going to represent or store the important parts of my world.  This in turn resulted in me digging in with a notebook and a pen and starting to try to figure out what I would need and how it would work.

Once I had my basics in place on paper, I started making all of the changes needed to make them possible.  The first was to start making loads of additional data structures.  After all the talking about clusters, I needed to finish creating the class that represents them.  I had additional ideas about world features as an external structure, which led me to the idea of a BitList for storing large numbers of booleans efficiently without all the extra features or auto-sizing that Java’s BitSet provides.  The idea of having lots of features meant that keeping some sort of index to help know when to use them would be handy so the FeatureIndex and WorldVolume classes were born.  And so on…

Next, my current design of IByteBufferSerializable was missing the idea of data structures that were variable size so I added that.  Also, I wanted to remove the serialization header from the size the objects reported for their serialized size.  As it turned out, this change to support variable sized objects meant it was actually helpful to have two different functions for reporting the size of serialized objects.  One for the size of the data, and the other for the size of the data plus the header (because the header is a variable size too).  This makes slightly different hoops to jump through with serializing and deserializing, but in the end I believe them to be simpler hoops than remembering to include the header every time in my reported size.  Several of my data classes didn’t even support IByteBufferSerializable and others needed to be revised to match the new patterns.

Finally, I wanted to add piles and piles of tests to ensure all the various parts of my fancy data structures worked the way I expected.  It would be a shame to be writing a world generator later on and to think something not appearing in the world correctly was because I screwed something up in the generator when in fact the error is in the way the data structure is holding the data.  You could literally waste hours or days trying to figure out where you went wrong all because you thought you got your data structures correct.  For that reason, similar to the massive numbers of math library tests, the data structure tests need to be extremely careful and complete.  If you can’t trust they are behaving properly when you are using them somewhere else, you don’t know where the actual problem you are encountering is coming from.

Next I get to try to figure out how the heck things actually spatially line up in all these structures when considering the “real world” rendering of the places you will walk around.  My three dimensional chunk structure makes that frustratingly difficult to draw on paper, so it’s going to be a bit of mental gymnastics before I have the actual graphics pipeline working.

 

The original layout of the geometry for QubeKwest was simply blocks in 16x16x16 block chunks in the world.  This was designed to accommodate bulk network transmissions.  After all, sending 4,096 blocks in a neat little package is a good deal more efficient than sending them one at a time.  At the moment, that means that a chunk is around 65 KB of data.  As I was working on the idea of how to store chunks in permanent storage on the server, I got to thinking about how obnoxious it would be to have vast numbers of 65 KB chunks all over the disk.

Instead of making an artificial storage construct for chunks on the disk drive, I got to thinking about how to best manage it and came up with an honest to goodness layer of physical space that can be used directly.  This may end up being handy for generation of the world as well since it gives a slightly more impressive physical space into which I can easily render advanced features.  The idea is that above chunks, we now have clusters.  These hold 8x8x8 chunks (512 chunks total) and are designed to be the way of storing the world on a hard disk.  These presently average something near 26 MB each in their uncompressed form, but they will likely be stored as compressed gzip streams so the world doesn’t take over your whole drive after 20 seconds of exploring.

These clusters are also designed to be a semi-sparse structure.  In other words, they have a hard list of 512 Chunks in them, but those chunks are allowed to be “EmptyChunk” objects instead of real ones.  This type of chunk takes approximately 4 bytes instead of 50,000.  After all, if there are parts of the cluster that haven’t been generated yet, then there is no need to store massive amounts of block data that is just waiting to be replaced by the generator later on.  This is especially likely in the vast depths of the underground.  If you haven’t dug down close to it, it really doesn’t need to have been generated yet.  If it hasn’t been generated yet, don’t waste the hard drive space yet either.

There were a few different trade offs on the sizing of a cluster before I settled on 8x8x8 chunks.  My first theory was 16x16x16 chunks in a cluster (after all I’d already done the math for storing 16x16x16 blocks in a chunk), but I soon realized that would mean way too much memory to load them off the disk to make them active on the server.  After that, I briefly toyed with the idea of getting rid of clusters altogether.  In the end, I decided they would still be useful to prevent the need for obscene numbers of individual chunk files.

Consider for a moment a world that is a small 128x128x32 blocks.  If it was nice and flat and you were running at 6m/s it would still take you over 20 seconds to walk end to end of this tiny world.  If I got rid of the cluster concept, that volume of world data would be stored in 128 files.  With an 8x8x8 chunk cluster, that world fits neatly into a single file with loads of room to spare for more vertical exploring.  This is much friendlier to the storage system on the server, especially as the worlds get larger.

 

 

In my head, QubeKwest is always a client/server program.  Meaning that even a single player local game is going to be the client program connecting to the server program over localhost.  The fun part there is that it means that the client and the server can be located anywhere.  On a powerful computer, they talk to each other over a localhost network with both parts running on the same computer.  On lesser computers they talk to each other over an actual network with the client and server each being their own computer.  And in the case of playing with your friends, they talk to each other over the internet.  If I code it right, the game not only “won’t care” but it actually won’t even know the difference.

Networking is a tricky beast and starting with the server makes the most sense.  A server can be coded in tons of different ways I’m sure, but the two that I have personally coded are the threaded approach and the asynchronous approach.  The threaded approach just uses the normal java.net.* things while the asynchronous approach uses java.nio.*.  If you’ve ever tried to code your own NIO version without help and pulled it off you are better at coding than me.  Simply put, I get the java.net.* stuff and my brain skips a step and stumbles the rest of the way down the stairs to end in a heap at the bottom when I try to understand the java.nio.* stuff.  Ok, that’s not fully true anymore, but it certainly was for previous attempts.

For a little background on the differences between the two approaches, I present a couple of paragraphs that get a little deep.  In the threaded approach, your server has a full blown operating system thread to handle every single incoming connection from a client, and another one to act as the server thread itself.  This is extremely heavy, not terribly scalable, and puts a pretty hard limit on the number of clients that can be connected at the same time.  Most modern operating systems support thousands of concurrent threads, but long before you get anywhere near that number, you start slamming into the overhead of switching between the threads you are using.  This approach is easy to code, easy to understand (if you understand how to play nicely with threads at least), and completely useless for large numbers of client connections.

In the asynchronous approach, you create a semi-magical server with just a thread or two to handle all the work of responding to clients.  The magical part is that it doesn’t matter if there is one client connected or 1000, the number of threads the server uses to manage the whole thing doesn’t change.  For a most excellent explanation of how this works, go check out the Rox Nio Server Tutorial.  I used that tutorial to craft how my game server works and it is the best description of how to make Java NIO stuff work correctly that I’ve ever bumped into.  This approach is a little trickier to code, vastly more complicated to get your head around, and scales well since you don’t need tons of threads to make it work.

This brings me to my diversion.  In all of the refactoring and playing with and confusing things and in general just blowing up of code that I did while writing an NIO server for QubeKwest, I managed to entirely lose track of how to use it and then I managed to substantially break it.  After seven months without looking at the code, I came back to discover that my network code was well and truly busted and that I had no clue how to fix it.  I started trying to follow the Rox Tutorial again on the code I had, but quickly found that my code was so different from the original that even that wasn’t useful.

Then an idea popped into my head.  Start over.  I know, great idea…  but sometimes it’s just what you have to do.  In this case I decided to simply make a stand alone server that wasn’t connected to the QubeKwest code at all.  This approach eliminated the QubeKwest package structure, the broken code, the refactors I’d incorporated, and it allowed me to learn how the whole thing was supposed to work again.  All without further destroying the networking in QubeKwest.

It took me a couple of days to get it to work properly because I was taking my time and making sure I understood the code I was writing.  When I thought I was done, I found that I was exactly one line of code short of having it work properly.  The code I’d produced was pegging an entire CPU core to 100% (even without requests coming in) and didn’t respond to the client.  This is obviously not an ideal server since the goal would be to use essentially 0% of the CPU unless you are responding to something and of course to actually respond to things.

Once I found the one line of code I’d missed, added it in, recompiled, and fired it up again, everything was suddenly behaving correctly.  Now I just need to refactor the code a bit in the stand alone version so it is a little cleaner, and then start integrating it into the QubeKwest network package.  It was an interesting couple of days, but at least I learned something and have functional code again.

 

So there I was, completely stalled on QubeKwest for roughly seven months.  Sure, I thought about it from time to time, but that never managed to inspire me to actually work on it.  Naturally that means that thinking about it tended to make me a little sad.  The cycle continued and the project languished.

Then a couple of interesting things happened.  I started to realize that part of the reason I was never working on QubeKwest was that I would come home from my normal job and not be able to find the motivation.  I even mentioned that in one of the previous posts on this blog so it was clearly something I was aware of at least subconsciously.  A few things happened at work that made me blindingly unhappy with the company I was working for and it hit me like a ton of bricks.  My job was making me miserable.

There are a couple of paths you can choose to follow when you make a realization like that.  You can complain about it, a lot, to everyone that will listen.  This approach tends to not make anyone any happier.  You aren’t solving anything by grumbling and your friends get sick of hearing about it.  This path tends to be the one used early on before you realize the depth of the problem you are complaining about.

The second approach is to do something about it.  This way is hard.  At least partially because change is hard and not many people (myself included) like change much.  It is however the only way to actually solve anything.  My eventual solution was to find a new job.  This didn’t immediately provide me more time to code QubeKwest, but it did immediately improve my general happiness.

Now, as a happier guy in a new job, I still wasn’t fully motivated to start development again.  At this point, I honestly hadn’t even thought about QubeKwest in a while.  Then something happened that made me immediately think of it.  The Raspberry Pi 3 was released.  I got to thinking, “Hey, I was totally going to try to get QubeKwest to work on a Raspberry Pi 2 and now a new one is out.”

As the proud owner of virtually every model of Raspberry Pi and someone that was very impressed with the new updates to the Raspberry Pi 3 (now with 64-bit CPU, and with built in WiFi and Bluetooth!) I immediately ordered several of them hoping they would be the last little nudge to resume for real.  Or, if not the last little nudge, at least a nudge in the right direction.

The Raspberry Pi 3s came in and instead of starting development again I was inspired to reinstall Windows on my main development machine.  Long story I won’t bother telling, but it needed it.  That took almost a whole weekend.  I was still a little nervous about starting again but I was starting to have fewer and fewer excuses.  I hadn’t looked at the code in seven months and that meant trying to figure out what I was working on and what the heck I was thinking when I wrote that piece and where I go from here.  But at least now I was ready.

I fired up Eclipse, I got annoyed at Eclipse, again.  I started the hunt for another IDE.   I grabbed IntelliJ IDEA and I like it so far.  Last night I attacked the code for the first time and I found there were loads of things I needed to fix.  I grabbed the latest LWJGL, but they had moved things around and renamed things and removed things so I had to fix my code to line up with their code again.  I also had to figure out how to fix the various broken bits of code that I’d checked in when I put the project to sleep seven months ago.

After about an hour, I had a shiny new IntelliJ project set up, I had my external libraries configured, I had the worst parts of my busted code commented out or repaired, and I got my ugly red triangles back on the screen.  I was in business again.  I think the first thing I need to do is revisit the extremely sad network code and try to figure out what I was doing there.  I am going to officially call that a plan!  Let the coding begin.