Representing a world in memory

Question

I'm attempting to write a chunk based map system for a game, where as the player moves around chunks are loaded/unloaded, so that the program doesn't run out of memory by having the whole map in memory.

I have this part mostly working, however I've hit a wall regarding how to represent the contents of each chunk in memory because of my so far limited understanding of OOP languages.

The design I have currently has a ChunkManager class that uses a .NET List type to store instances of Chunk classes. The "chunks" consist of "blocks". It's similar to a Minecraft style game.

Inside the Chunk classes, I have some information such as the chunk's X/Y coordinate etc, and I also have a three dimensional array of Block objects. (Three dimensional because I need XYZ values)

Here's the problem:

The Block class has some basic properties, and I had planned on making different types of blocks inherit from this "base" class. So for example, I would have "StoneBlock", "WaterBlock" etc.

So because I have blocks of many different types, I don't know how I would create an array with different object types in each cell.

This is how I currently have the three dimensional array declared in my Chunk class:

private Block[][][] ArrayOfBlocks;

But obviously this will only accept Block objects, not any of the other classes that inherit from Block.

How would I go about creating this? Or am I doing it completely wrong and there's a better way?

Answer 1

The problem you're asking about is a non-problem, but the structure you've come up with is very inefficient.

Consider a simple 128x128x128 chunk. That will require 2097152 instances of Block. You want Block to be as small as possible. One thing that is easy to get rid of is the position. The position is implicit in the array containing the Block instance. Nobody can retrieve the block without knowing its position. Hence, the position field of Block is redundant and can be removed.

Another thing you want is to keep the structure fast. That's a lot of blocks per chunk you'll be working with for rendering, physics, gameplay, etc. One of the simplest things to keep in mind when working with performance is the CPU cache and memory accesses. Accessing random locations in memory is not free; they usually incur a pipeline stall in the CPU that can be quite a heavy hit on modern CPUs. The easiest way to combat this is to keep all your data contiguous in memory. Thankfully, this is what a List or arrays do already. However, if you have a List or array of classes, the data structure is technically only keeping references to the objects in its contiguous memory. The actual objects themselves could be strewn all over the place. C# was well-designed and includes the idea of a struct as an alternative to a class (unlike Java; Minecraft has to jump through more hoops to keep things contiguous in memory). Converting Block to a struct will make accessing them faster. However, structs will actually cause the inheritance problem you were originally worried about, since a List<Block> (where Block is a struct) actually wouldn't be able to hold subclasses.

The final trick then is to simply not use classes and inheritance where they aren't needed, and this is one such place. In general, inheritance is a very, very poor tool for such problems. Use inheritance when you want to model is-a relationships, keeping in mind how a computer works/things - the computer has no reason to care that a stone block is a type of block. That's a human taxonomy problem. The computer only cares whether a stone block exposes the behavior of a block. That is, inheritance to a computer is mostly valuable only when you're modeling interfaces and behaviors.

Furthermore, inheritance starts to cause some serious issues. Say you have an ice block that has sliding behavior and a puzzle block that can be pushed and then want to add an ice puzzle block. Does it inherit from PuzzleBlock or IceBlock? Do you move all the common functionality up into Block and make every single block pay the price for the excess bloat? The concept of aggregation solves this nicely. You can make an IceBlockComponent and a PuzzleBlockComponent and now an individual BlockType can contain a list of these components, allowing you to mix-and-match behaviors however you want.

Alternatively, if you don't feel you need the full flexibility (and resulting complexity) of component-based design, move your inheritance structure out of Block and into a BlockType hierarchy. So you'd have a BlockTypeStone or BlockTypeIce and still only a single Block.

Going back to the data-structure problem, not that each Block does not need to contain all the behavior and methods of its type. In such a system, it needs only point back to its BlockType. This can be done efficiently by storing all the BlockTypes in an array or List and then storing a small integer (say a byte or a short) in the Block object. Now you no longer have any need for inheritance in Block and you've reduced the size from before (no need for 4-8 byte references in your Chunk array of blocks but rather a compact struct containing a small integer... or just the integer itself with no struct!).

The remaining hassle then is data. Thankfully, most data in these games are going to be per type rather than per block instance. That is, your IceBlockComponent may have a slipperiness attribute which would apply to all blocks of that type. There's no need to store the value on each individual block.

For the few bits of data you do need per block, just use a few bits (or a couple bytes). If your Block is just an 8-bit index to a BlockType, you could toss in another 8 or 16 bits and still have Block stay relatively small and compact. These extra bits of data would be interpreted as needed by the block type (managing the meaning of the bits in a component/aggregation model is a little tricky, but doable).

The end result of all these is that you've got a very compact Chunk that uses much less memory and is much faster to process than what you had before. You've also simplified your use of the type system and (if you play your cards right) made the game easier to mod and extend in the future.