# Best way to read expandable voxel world (hashmap) such as in Minecraft

I'm building a 3D multiplayer Roguelike-style engine (tile and turn-based) and I'd like to make the worlds virtually "infinite", similar to what you would see in Minecraft.

I'm storing data in a manner I'm assuming to be pretty similar to Minecraft based on what I've read so far. Chunks of 16x16x16, stored in arrays that are X amount high based on world height. These arrays are stored in a hashmap indexed as integers based on a z-order / morton curve implementation (to flatten them from 2d for easier storage.)

Everything is working well so far, but I've been coding everything assuming the active world will all fit into one square (based on view distance or something along those lines) instead of multiple areas (difference illustrated here).

But once I start assuming different areas will be loaded and active in the world, it brings a huge performance issue: in order to check individual cubes I'd have to see if it's parent chunk is active and loaded in order to avoid some kind of null pointer exception.

Aside from trying to somehow do pathfinding / world interaction in batches within individual chunks (which would be really hard to think around and I'm trying to just grab individual cubes from the "world" object that handles navigating the hash map) I can't think of any way around the issue except doing a hashMap.containsKey(int) for every single world read operation. So, in other words, if 8 players are on the server in entirely different active areas in the world, every block read would require checking if the Morton Code of the chunk the requested block is in falls into the currently loaded area of Players * Active Area, so 8*(8*8) individual chunks in this example.

So I'm curious if my Hashmap-based setup is incorrect for solving this problem, or if there is any other way around this issue.

You can use a "default" chunk. Wrap your hash map accessor so if if getReadOnlyChunk is called on a key that doesn't exist then instead of returning null it returns the cached instance of DefaultChunk, which is either empty or full of a special "impassible mist" block or whatever you deem to be best for your game. The getWritableChunk method should instantiate a chunk with whatever generation algorithm you use. Or have a single getChunk that returns a "read-only view" of a chunk which can be converted writable. Or just check if you have the DefaultChunk before writing.

Short version: don't return null, return a place-holder.

• That's a great idea! For some crazy reason I didn't think the hash map wouldn't return null for nonexistent keys. – and0 Jul 4 '13 at 21:11

• Pathfinding, etc, should be tree-aware
• Checking to see if a block is loaded is cake
• The client and server will handle unloaded data differently

## Tree Aware

You've mentioned that you're storing data in 16x16x16 chunks. Pathfinding and world interaction should operate on those chunks (in addition to their contained blocks). For example, pathfinding starts with "hey world, gimme the chunk that this block is in" but, from there, should proceed along the lines of "does the path terminate in this chunk? If not, what's the next chunk?" You should only go to the hashmap for chunks, not for individual blocks. Once you have a chunk, you should be able to operate within it without having to go back to the hashmap.

You mention this sort of solution in your post. Yes, it's hard. The alternative is, yes, hitting the world hashmap for every single block read. (Note that a chunk already provides locality of data.)

Converting a block's coordinates into its Morton index should be a trivial computation. Then, checking to see if that chunk is in the currently-loaded hashmap is, generally

bool hashmap::contains_key(T& key)


or some similar computation of typically trivial order, O(1) or O(log n). There's no reason to iterate over all of the loaded areas and to check to see if the chunk is in any of those areas; just ask the hashmap. They're very fast at that sort of test.

If your pathfinding (etc) code works on chunks, then you don't need to keep doing the "is this block loaded?" test for every single block. Do it once for the chunk, pathfind through the chunk, then do the test for the next chunk.