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

Question

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.

Answer 1

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.

Answer 2

I've got three comments:

• 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.)

Is this block loaded?

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.

Handling Unloaded Data

Pathfinding (for e.g. AI) should probably only attempt to run within loaded areas; that is, it should be clipped to the currently-loaded regions that you mention in your Question. Sometimes mobs will be confused; the alternative is loading more data. You'll have to choose where this tradeoff happens. Hence, pathfinding itself should never run into this null exception error.

All active areas of your would should be in memory at any given time. This is more dependent on the number of players in the game and how large of an active area each player induces than it is on the size of the world. When your server needs to process "the player is attempting to move North by one tile", you don't want to go "oh, oops, I completely forgot to load that." Plus there's no reason to even check to see if the chunk is loaded if the player isn't moving out of the current chunk.

The server should always have data available. If the player is teleported to a new region of the map, many AAA titles will lag the player until the server is done loading the new player-local region. In other words, a player steps into the portal and then sees a loading or waiting screen until the server has caught up; on the server side, it's waiting for IO to complete loading new chunks.

On the client side, sadly, sometimes network traffic happens. The player wants to do something which would cause client-side computation with blocks in a chunk that the server hasn't yet told the client about. The basic solutions here: (1) lag the player, ie prevent them from moving until relevant data is loaded; (2) fake it, perhaps by adding in "impassible mist" as Sean suggested; or (3) discard the player request. Again, you'll have to decide which solution best fits your game.