VRscosity Dev Blog #2: 500 million bees

There is an old saying that a single bee sting hurts, but a thousand kills. If you ignore the reality of this idea (there are plenty of other factors that affect your reaction to bee stings) the premise is that enough of any small thing can eventually overwhelm.

In software, the developer is constantly wrestling with various factors. In game development, chief among them is performance. Memory and CPU usage has to be kept as low as possible for any given function and writing cheap, efficient code is paramount.

However, some things are simply unavoidable.

 

The Anatomy of a Voxel

There are many ways to build a Voxel system. Minecraft and many of their ilk rely on chunk-based systems and trees to build their dynamic worlds, wherein as the player loads in or expands the world, new areas are generated based on an algorithm in blocks. I mentioned before how VRscosity is not Minecraft, but the latter is a well optimised example of a Voxel system in action.

In Minecraft’s specific case, each chunk is 16x16x256, or roughly 16 bits of block registration. Each chunk is in itself separated into 16 render zones, and are updated based on this separation. Hard numbers for how much memory a single block in Minecraft requires are hard to come by, but it’s somewhere between 1.5 to 3 bytes per block pre-compression.

So at Minecraft’s maximum default loading configuration (which loads 25×25 chunks in memory, storing the rest on disk) is roughly 120mb of RAM for 3 Bytes/block. In practice it’s actually more, thanks to overhead from other concerns such as object referencing (8bytes per reference in 64bit systems) and entity loading, but as a pure system it’s reasonably compact.

 

The Issues of Exponential Growth

Unfortunately, any system that deals with squared numbers won’t stay small for long, and any addition to the world size dramatically increases the amount of memory used.

As with the given example above, just dealing with block usage of 3 Bytes each (so no referencing overhead or compression), loading a 33×33 section of chunks in Minecraft takes 204MB of RAM, but loading a 65×65 section of chunks (the maximum Minecraft allows) takes 792MB!

Suddenly a single bee (block) becomes a deadly swarm of memory usage.

 

VRscosity Voxels

Taking the above problem to heart, the fact that I am planning the maximum sandbox size in VRscosity to be 1024²*512 (1024*1024*512) is showing the problems involved with handling so many objects. Like Minecraft’s top estimate, currently each one of the Voxels in VRscosity takes 3 bytes. On paper, a 512³ box of Voxels should take around 384MB of RAM, whereas a 1024²*512 box takes 1536!

 

Memory Issues

It is a large jump, but not actually the biggest problem to consider. Without any measures to mitigate loading, there is the issue that a full box of voxels is a collection of just shy of 537 million individual objects. Storing and accessing these objects is a complicated dance to learn!

The first large problem is referencing. In the worst case, which is a 64bit system, any given memory reference requires 8 bytes of memory to hold in itself. If I were to reference each Voxel instance, I’d have to add  double the size of each Voxel to the memory cost calculation. This results in the ram usage for the given max size jumping from 1536MB straight to 5632 – almost 4GB purely used for references! Obviously, this isn’t tenable.

To really show the kind of scale I’m dealing with here, moving the Voxel from 4 bytes to 3 saved over half a gig of memory on its own…

One bee is fine. Millions are not!

 

Early Bird Solution

The solution I came up with was to scrap any pretence of building a Voxel as a class. While there are advantages to holding a reference pointer to a class – if only for mutability if nothing else – when making so many repeated class references the penalty is too high.

Thankfully, C# supports Structs.

Structs, for those who are unaware, are essentially data structures – collections of variables with, ideally, no other functionality other than access. They have no overhead associated with them, so their footprint is as large as the contents (a 3 Byte Voxel is a 3 Byte struct, but an 11 byte referenced class), and creation (as well as access) is very fast.

The disadvantage is that Structs are immutable. The situation that gives them their speed (the stack allocation without the heap) means that they cannot be directly modified without pulling some tricks that remove that advantage in the first place. Any changes I wish to make would require the creation of a new Voxel and then overwriting the old one. Thankfully, this in itself is incredibly quick.

So for now, the model is literally a 3D Array of Structs. It’s not pretty, and can be further refined (there is no need to have an “air” object really, as functionally air is empty space). It is, however, the best interim solution while I hammer out other problems. With compression, it may not even be that bad at the end of the day.

That is a future blog though!

Leave a Reply

Your email address will not be published. Required fields are marked *