How do I dynamically grow a voxel world in all directions with chunks?

Question

I've organized a Voxel world already but the problem is that it can only "grow" outwards. As a result, there is a single corner where it grows from, then outwards from there on. I want to be able to grow the world from all directions.

I figured this would be best done by maintaining a list of chunks with their world position, but that would require iterating through each chunk just to find the one I'm looking for and checking which chunks need to be created (or just to do anything involving that chunk) and it would be a mess to figure out which ones are loaded and which ones aren't.

How do existing Voxel games (such as Minecraft) deal with this issue?

Answer 1

I once wrote a voxel game (clone of Minecraft). What I did was using of course using negative coordinates. To have on O(1) access time to the chunks, I used two mapping functions:

1. From Z (whole numbers) to N (natural numbers).
2. From (NxN) (couple of natural numbers) to N (natural numbers).

For (1), use a simple function that multiplies by 2 for positive and multiplies by -2 and adds 1 for negative numbers. For (2), take a look at Cantor's pairing function.

Answer 2

Basically its what @DanielHolst said, you can use negative coords and expand in all directions.

As for storing your loaded chunks for fast access and checking you could use std::unordered_map, Just #include <unordered_map>, then your code looks something like this:

std::unordered_map< std::pair< int, int >, Chunk* > ChunkMap;

// For adding a chunk, first checks if it exists.
if( ChunkMap.find( std::make_pair( newcoord.x, newcoord.y ) ) == ChunkMap.end() )
{
    ChunkMap[std::make_pair( newcoord.x, newcoord.y )] = new Chunk(newcoord);
}

Please note that you might want to use your own vec2 class directly, and might need to supply your own hash function for unordered_map to be able to use it as key. Also if you want 3D infinity, then you should use a vec3 not a vec2 obviously, and supply a hash function for that. (A hash function takes a coordinate and creates an unique ID from it.)