Learning from other game devs 3: Minecraft networking

While reading Notch's tumblr, I came across a post that bothered me. Really bothered me. The post is about the implications of increasing the world (chunk) height.


http://notch.tumblr.com/post/7799649091/sharing-an-interesting-email

Designing programs is a huge tradeoff space, and trying to get to a local maximum rather than a global maximum in terms of optimization is a major pitfall for programmers. What do I mean by local maximum? Say that I have a game, and I want to increase frame rate, and with some minor violence to the graphics engine part of the code the best I can increase FPS is by 20%. Pretty good right? Now, I'll tell you if I scrapped the graphics engine, getting rid of all the assumptions (and therefore restrictions) I made previously and wrote a fresh graphics engine, I could increase FPS by 200%. Wow!

So, sticking with my assumptions already baked into my code, I'm limited in what I can do. Obviously, I've showed an extreme here. The reality is that sometimes handful of assumptions need to change, leading to little code change. The larger questions are: How do I know what needs to change in order to get a big benefit? Is it worth it (time, resources, expected results) to make the change?

Ok, back to the the post. There are a few things that bothered me, mostly related to assumptions that are being made. Please note I may not get this right, as I have a limited understanding of MC and opengl. Feel free to correct me. The point of this is to help me learn by getting my thoughts out into the blog, anyways :).



"- Network Implications: On SMP, Chunks need to be sent to many more people many times more often than in SSP. It can be taken for granted, from a client’s perspective, just how much data needs to be shoved around by the server...."  (all formatting is mine)

This argument seems like another Achilles heel for the proposal to grow the world height. However, there is a huge assumption that bothers me. Generally speaking, chunks do not need to be sent to many people many times. Initially (at creation time) they do, but only specific voxel updates (addition/removal) need to be sent to client.The benefit to arranging voxels in chunks is storage space, but you can imagine updating a chunk via a small packet says which voxels in which chunk need to change. This is an incredibly small amount of data, as very few voxels can change at any time, relative to the chunk size. Of course, I'm baking in my own assumption as well, namely that the client has a copy of the entire chunk (world) locally to begin with. This seems pretty reasonable to me, and there are a number of ways to accomplish this. Still, there doesn't appear to be a ton of traffic by increasing world height.

"- CPU Implications: Chunk terrain generation occurs in pieces ... Nonetheless, it’s still a cache-thrashing memory-fill operation. .... While this is relatively cheap for things like ore, it’s eclipsed by the idea that cave generation would need to occur along the entire Y axis, and being a recursive function, this has the potential to get very costly very quickly." (all formatting is mine)

This is a huge negative for trying to increase world height. Cache thrashing is horrible, and cave generation (when new chunks are constructed) can get intensive. However, there are a number of assumptions here. It is a big assumption that increasing chunk height will increase cache thrashing. In Notch's own words, a single chunk is 16x16x128 bytes = 32KB, already enough to thrash an L1 cache. You may be able to fit 8 regular chunks in the L2, and 128 in L3. Doubling the height would likely not cause any additional cache thrashing. Regarding cave generation, the assumption is that the same code scheme still needs to exist. In reality, there are a number of options. Manage the CPU resource by creating a thread just for terrain generation, and only activate it when you have spare cycles. Cave generation in particular is likely off the critical path anyway. In the worst case re-architect it and move away from a pure recursive (read CPU intensive) algorithm.

I'll leave the readers to think about and question the specific comments I've made. However, the suggestion of understanding what assumptions you are making can help put design decisions in perspective. The whole goal is to know what the options are. Its up to you can decide if trying to get closer to the global maximum is worth it.