Virtual Chunks

Other resources

Here is another webpage on this website which discusses virtual chunks.

Download

Here is the demo package that this webpage describes.

What are Virtual Chunks?

Consider a chunk C1. Let C2 be its parent chunk. So C2 consists of 16x16x16 blocks. One of those blocks is C1.

Both C1 and C2 are examples of virtual chunks, but there are more virtual chunks in C2.

For example, the 2x2x2 regions of blocks in C2 (aligned appropriately) are virtual chunks. That is, C2 consists of 8x8x8 many 2x2x2 virtual chunks.

Also, C2 consists of 4x4x4 many 4x4x4 virtual chunks.

Finally, C2 also consists of 2x2x2 many 8x8x8 virtual chunks.

These are what virtual chunks are.

Note: here we see it is important that the default chunk width is 16. If it was not a power of 2, such as 13, the engine would be in trouble.

The Goal

The purpose of this guide is to explain one way that virtual chunks are used in procedural world generation. The main technical function we use is get_vchunk_data. We will explain how to use that function.

The "Chop" Number

Suppose we are procedurally generating a chunk C. Where N is a power of 2, it may be useful to consider the unique NxNxN virtual chunk which contains C.

The chunk C itself we call the chop = 0 chunk.

The unique 2x2x2 virtual chunk that contains C we call the chop = 1 chunk.

The unique 4x4x4 virtual chunk that contains C we call the chop = 2 chunk.

In general, the chop = k virtual chunk is 2^k by 2^k by 2^k chunks.

Where the name comes from is we have some sort of binary representation of the block path of C and we are "chopping off the end". The chop number is how many bits we chop off of each of the x,y, and z components.

Example 1: Basic Balls

In this example, we have every chunk contain a sphere of radius 10 with a small probability. What we do is iterate over the 3x3x3 nearby chunks (around the chunk being generated) and place spheres in them randomly. When we say random, we mean pseudo random where the random number generator seed comes from the path of that chunk. We call the process of getting these spheres harvesting.

In the following image, the blue chunk is the chunk that is being procedurally generated. The green box is a nearby virtual chunk (which in this example is actually a chunk) that contains a sphere that we want to harvest.

Note: If our spheres had a radius greater than 16.0, this technique would not work.

Once harvesting is complete, we are left with an array which consists of the positions (and radii) of spheres which are all "in the coordinate system of the chunk being generated". That is, in this coordinate system vectors go from (0.0, 0.0, 0.0) to (16.0, 16.0, 16.0).

Note: an optimization at this point would be to throw away all spheres that do not intersect the chunk being generated. We are NOT doing that in this example for simplicity.

Now using this array of spheres, we iterate over all 16x16x16 block positions in the chunk being generated. If the center of any position is within the radius of one of the spheres, we make the block solid. Warning: this can be slow if you are not careful!

Here is the code for the only block type used in this example:

--File: block_ball1_2.lua

function p.__get_is_solid() return true end
function p.__get_tex() return "block_default" end

-------------------------------------------------------------------------

--Lots of spheres.
function p.__main()
    set_default_block("e")

    --Getting all nearby spheres.
    local sphere_array = p.harvest_spheres()

    --Iterating over all block positions,
    --seeing which ones are close to a sphere.
    for x = 0,15 do
    for y = 0,15 do
    for z = 0,15 do
        local bp = std.bp(x,y,z)
        local vec = std.block_center(bp)
        for i = 1,#sphere_array do
            local obj = sphere_array[i]
            local r_sq = obj.radius * obj.radius
            if h.dist_sq(obj.vec, vec) < r_sq then
                set_pos(x,y,z, "s") --Making the position solid.
            end
        end
    end end end
end

--Iterating over the 3x3x3 region of chunks
--around the chunk being generated
--and getting all spheres in these chunks.
function p.harvest_spheres()
    local sphere_array = {}
    for dx = -1,1 do
    for dy = -1,1 do
    for dz = -1,1 do
        p.harvest_spheres2(sphere_array, dx, dy, dz)
    end end end
    return sphere_array
end

--Getting spheres from one virtual chunk.
function p.harvest_spheres2(
    sphere_array, dx, dy, dz)
--
    --Getting vchunk (virtual chunk) data.
    local chop = 0
    local vd = get_vchunk_data(chop, dx, dy, dz)

    srand(vd.seed)
    if( randf() > 0.2 ) then
        --No spheres in this virtual chunk.
        return
    end
    local new_sphere = {}
    --Note: randf() is between 0 and 1.
    new_sphere.vec = std.vec(
        16.0 * randf() + 16.0*dx,
        16.0 * randf() + 16.0*dy,
        16.0 * randf() + 16.0*dz)
    new_sphere.radius = 10.0 --Radius > 16.0 is a problem.
    sphere_array[#sphere_array+1] = new_sphere
end

To make the code above faster, we could precompute the radius squared of each sphere.

In the code above, dist_sq is the following function defined in WorldNodes/Helpers/h.lua:

--Distance squared between two vectors.
function p.dist_sq(v1, v2)
    local x = v1.x - v2.x
    local y = v1.y - v2.y
    local z = v1.z - v2.z
    return x*x + y*y + z*z
end

Feel free to replace

local bp = std.bp(x,y,z)
local vec = std.block_center(bp)

with

local vec = std.vec(x,y,z)

in the __main function (it would be slightly faster, but slightly different).

Frac coordinates

When we talk about the coordinate system of a chunk, we mean the coordinate system where (0,0,0) and (16,16,16) are at opposing corners.

Slightly different from this we have frac coordinates. These are vectors where (0,0,0) and (1,1,1) are at opposing corners of the chunk.

Intro to the get_vchunk_data function

We need to start talking about the get_vchunk_data function. We used this in Example 1 in the harvest_spheres2 function. In the picture below, the blue chunk is the chunk that is being procedurally generated. The green chunk is a nearby virtual chunk. We can get information about that virtual function by calling the get_vchunk_data function.

Forgiving the author that this is a 2D picture not a 3D picture, you would call the get_vchunk_data with a chop value of 1 (because the virtual chunk is 2^1 by 2^1) and you would also set dx = -1 and dy = -1. This is because the green virtual chunk is (-1,-1) from the virtual chunk that contains the blue chunk which corresponds to chop = 1.

The get_vchunk_data returns a Lua table with various members. We have just seen one member so far: seed. This is an integer which is somehow associated to the green virtual chunk. You pass this to the srand chunk generation API function to then generate pseudo random numbers.

This seed is actually what we call a "tail seed", because it only depends on the last few elements of the block path of the virtual chunk. Tail seeds are useful for the engine because there is an efficient way to find the tail seed of an adjacent chunk.

In this section let us discuss two other data members of the table returned by get_vchunk_data: the members min2 and max2. These are the coordinates of the corners of the green chunk but in the coordinate system of the blue chunk. Recall that in the coordinate system of the blue chunk, the vectors (0,0,0) and (16,16,16) are on opposing corners of the blue chunk.

So if you want a puzzle you can verify that in the 2D picture shown above, max2 would be the vector max2 = (-16,0) and min2 would be the vector min2 = (-48,-32).

Let us also mention that get_vchunk_data also has the members min and max. These are just like min2 and max2, except they are in frac coordinates instead of the chunk coordinates of the blue chunk. For example, min is the min corner of the green chunk, in the frac coordinate system of the blue chunk. Don't feel like you need to use min and max. Also, note that it is trivial to convert from min to min2 and from max to max2 (you just multiply by 16).

Example 2: Basic Balls Revisited

Using what we learned about the get_vchunk_data function, we can rewrite the harvest_spheres2 function to read as follows:

--Getting spheres from one virtual chunk.
function p.harvest_spheres2(
    sphere_array, dx, dy, dz)
--
    --Getting vchunk data.
    local chop = 0
    local vd = get_vchunk_data(chop, dx, dy, dz)

    srand(vd.seed)
    if( randf() > 0.2 ) then
        --No spheres in this virtual chunk.
        return
    end
    local new_sphere = {}
    local v1 = h.rand_unit_cube()
    local v2 = h.interp_box(vd.min2, vd.max2, v1)
    new_sphere.vec = v2
    new_sphere.radius = 10.0
    sphere_array[#sphere_array+1] = new_sphere
end

We have two helper functions for this, defined in WorldNodes/Helpers/h.lua:

--Random vector in the unit cube.
--The unit cube goes from (0,0,0) to (1,1,1).
function p.rand_unit_cube()
    return std.vec(
        randf(),
        randf(),
        randf())
end

and

--Box interpolating.
--If frac == (0,0,0), it will return v1.
--If frac == (1,1,1), it will return v2.
function p.interp_box(v1, v2, frac)
    return std.vec(
        v1.x * (1.0 - frac.x) + v2.x * frac.x,
        v1.y * (1.0 - frac.y) + v2.y * frac.y,
        v1.z * (1.0 - frac.z) + v2.z * frac.z)
end

Example 3: Big Balls

We will make a simple modification of Example 2: we will have the virtual chunks be 2x2x2 instead of 1x1x1. We will also have the radius of the spheres be 20 instead of 10. All we have to do is change the code of harvest_spheres2 to read as follows:

--Getting spheres from one virtual chunk.
function p.harvest_spheres2(
    sphere_array, dx, dy, dz)
--
    --Getting vchunk data.
    local chop = 1
    local vd = get_vchunk_data(chop, dx, dy, dz)

    srand(vd.seed)
    if( randf() > 0.2 ) then
        --No spheres in this virtual chunk.
        return
    end
    local new_sphere = {}
    local v1 = h.rand_unit_cube()
    local v2 = h.interp_box(vd.min2, vd.max2, v1)
    new_sphere.vec = v2
    new_sphere.radius = 10.0 * vd.scale
    sphere_array[#sphere_array+1] = new_sphere
end

That is, there are two modifications from before.

First, we have the line "chop = 1" instead of "chop = 0". This is what causes the virtual chunks to be 2x2x2 instead of 1x1x1.

Second, look at the line

new_sphere.radius = 10.0 * vd.scale

In our example, this is equivalent to setting the sphere radius to be 20, but we are doing it in a more general way. That is, the scale member of the Lua table returned by get_vchunk_data is the width of the virtual chunk divided by the width of the chunk being procedurally generated. In our case, because chop = 1, the value of scale is 2.

Example 4: Adding and Subtracting Balls

In this example, we will have large balls and then subtract small balls from them. It will look as follows:

We will harvest the large balls from 4x4x4 virtual chunks and will harvest the small balls from 1x1x1 virtual chunks.

Here is the code for the only block type for this example:

--File: block_ball4_2.lua

function p.__get_is_solid() return true end
function p.__get_tex() return "block_default" end

-------------------------------------------------------------------------

--Small spheres subtracted from large spheres.
function p.__main()
    set_default_block("e")

    --Getting all nearby (positive and negative) spheres.
    local pos_sphere_array = {}
    local neg_sphere_array = {}
    p.harvest_spheres(
        pos_sphere_array,
        neg_sphere_array)

    --Iterating over all block positions.
    --For each position, we see if it is in a positive sphere
    --but not a negative sphere.
    for x = 0,15 do
    for y = 0,15 do
    for z = 0,15 do
        local bp = std.bp(x,y,z)
        local vec = std.block_center(bp)
        local is_solid = false
        for i = 1,#pos_sphere_array do
            local obj = pos_sphere_array[i]
            local r_sq = obj.radius * obj.radius
            if h.dist_sq(obj.vec, vec) < r_sq then
                is_solid = true
            end
        end
        for i = 1,#neg_sphere_array do
            local obj = neg_sphere_array[i]
            local r_sq = obj.radius * obj.radius
            if h.dist_sq(obj.vec, vec) < r_sq then
                is_solid = false
            end
        end
        if( is_solid ) then
            set_pos(x,y,z, "s") --Making it solid.
        end
    end end end
end

--Iterating over the 3x3x3 region of chunks
--around the chunk being generated
--and getting all spheres in these chunks.
function p.harvest_spheres(
    pos_sphere_array,
    neg_sphere_array)
--
    --Adding positive spheres.
    for dx = -1,1 do
    for dy = -1,1 do
    for dz = -1,1 do
        p.harvest_pos_spheres(pos_sphere_array, dx, dy, dz)
    end end end
    
    --Adding negative spheres.
    for dx = -1,1 do
    for dy = -1,1 do
    for dz = -1,1 do
        p.harvest_neg_spheres(neg_sphere_array, dx, dy, dz)
    end end end
end

function p.harvest_pos_spheres(
    pos_sphere_array, dx, dy, dz)
--
    --Getting vchunk data.
    local chop = 2
    local vd = get_vchunk_data(chop, dx, dy, dz)

    srand(vd.seed)
    if( randf() > 0.2 ) then
        --No spheres in this virtual chunk.
        return
    end
    local new_sphere = {}
    local v1 = h.rand_unit_cube()
    local v2 = h.interp_box(vd.min2, vd.max2, v1)
    new_sphere.vec = v2
    new_sphere.radius = 10.0 * vd.scale
    pos_sphere_array[#pos_sphere_array+1] = new_sphere
end

function p.harvest_neg_spheres(
    neg_sphere_array, dx, dy, dz)
--
    --Getting vchunk data.
    local chop = 0
    local vd = get_vchunk_data(chop, dx, dy, dz)

    srand(vd.seed)
    if( randf() > 0.2 ) then
        --No spheres in this virtual chunk.
        return
    end
    local new_sphere = {}
    local v1 = h.rand_unit_cube()
    local v2 = h.interp_box(vd.min2, vd.max2, v1)
    new_sphere.vec = v2
    new_sphere.radius = 8.0 * vd.scale
    neg_sphere_array[#neg_sphere_array+1] = new_sphere
end

Example 5: Smooth Balls

In this example, we will make balls of radius 20, but when you shrink and approach the balls, you can see that they are smooth. So when you are small and right next to a ball, it will look huge.

The idea is that chunks on one level L will harvest spheres using chop = 1. Then, the chunks of level L+1 will harvest spheres using chop = 1 + 4. Why 4? This is because every time you shrink one level, the world grows by a factor of 16 = 2^4.

When writing worldgen code like this, there is a temptation to duplicate certain code. However for sanity, it is important that certain code is reused by multiple block scripts. We will indicate where this is important.

Here is the block script for the unique block type on level L:

--File: block_ball5_2.lua

function p.__get_is_solid() return true end
function p.__get_tex() return "block_default" end

-------------------------------------------------------------------------

--Lots of relatively normal sized spheres.
function p.__main()
    local solid_bt = "block_ball5_3_solid"
    local empty_bt = "block_ball5_3_empty"

    set_default_block(empty_bt)

    --Getting all nearby spheres.
    local sphere_array = p.harvest_spheres()

    --Iterating over all block positions,
    --seeing which ones are close to a sphere.
    for x = 0,15 do
    for y = 0,15 do
    for z = 0,15 do
        local bp = std.bp(x,y,z)
        local vec = std.block_center(bp)
        for i = 1,#sphere_array do
            local obj = sphere_array[i]
            local r_sq = obj.radius * obj.radius
            if h.dist_sq(obj.vec, vec) < r_sq then
                set_pos(x,y,z, solid_bt)
            end
        end
    end end end
end

--Iterating over the 3x3x3 region of chunks
--around the chunk being generated
--and getting all spheres in these chunks.
function p.harvest_spheres()
    local sphere_array = {}
    local chop = 1
    for dx = -1,1 do
    for dy = -1,1 do
    for dz = -1,1 do
        p.harvest_spheres_common(sphere_array, chop, dx, dy, dz)
    end end end
    return sphere_array
end

--Will be called from other scripts.
--Notice how chop is an arg.
function p.harvest_spheres_common(
    sphere_array, chop, dx, dy, dz)
--
    --Getting vchunk data.
    local vd = get_vchunk_data(chop, dx, dy, dz)

    srand(vd.seed)
    if( randf() > 0.2 ) then
        --No spheres in this virtual chunk.
        return
    end
    local new_sphere = {}
    local v1 = h.rand_unit_cube()
    local v2 = h.interp_box(vd.min2, vd.max2, v1)
    new_sphere.vec = v2
    new_sphere.radius = 10.0 * vd.scale
    sphere_array[#sphere_array+1] = new_sphere
end

So the __main function calls the harvest_spheres function, which in turn calls the harvest_spheres_common function. However the harvest_spheres_common function is written in such a way that it can be called from other block scripts. That is, it will be called by the block scripts for blocks on level L+1.

We see that the __main creates two types of blocks: the solid block_ball5_3_solid blocks (which look like solid blocks from a distance) and the empty block_ball5_3_empty blocks (which look like empty blocks from a distance).

This is what the block_ball5_3_solid block script looks like:

--File: block_ball5_3_solid.lua

function p.__get_is_solid() return true end
function p.__get_tex() return "block_default" end

-------------------------------------------------------------------------

--Will be called from another script.
function p.common_main()
    set_default_block("e")

    --Getting all nearby spheres.
    local sphere_array = p.harvest_spheres()

    --Iterating over all block positions,
    --seeing which ones are close to a sphere.
    for x = 0,15 do
    for y = 0,15 do
    for z = 0,15 do
        local bp = std.bp(x,y,z)
        local vec = std.block_center(bp)
        for i = 1,#sphere_array do
            local obj = sphere_array[i]
            local r_sq = obj.radius * obj.radius
            if h.dist_sq(obj.vec, vec) < r_sq then
                set_pos(x,y,z, "s")
            end
        end
    end end end
end

--Huge spheres.
function p.__main()
    p.common_main()
end

--Iterating over the 3x3x3 region of chunks
--around the chunk being generated
--and getting all spheres in these chunks.
function p.harvest_spheres()
    local sphere_array = {}
    --We add an extra 4 to chop because we are one level higher
    --than block_ball5_2.
    local chop = 1 + 4
    for dx = -1,1 do
    for dy = -1,1 do
    for dz = -1,1 do
        --Note: beware of duplicating certain worldgen code.
        block_ball5_2.harvest_spheres_common(sphere_array, chop, dx, dy, dz)
    end end end
    return sphere_array
end

So the main function of block_ball5_3_solid and block_ball5_3_empty will be identical. Rather than duplicate code (which in this case would be a bad idea) we just have the main function of both block scripts call a common helper function.

The main function of block_ball5_3_solid calls a harvest function in the same script. That harvest function calls the harvest_spheres_common function in block_ball5_2. This is a situation where if we duplicated code instead, it would be a nightmare to maintain.

All that remains is to talk about the block_ball5_3_empty script. Luckily, this is trivial:

--File: block_ball5_3_empty.lua

function p.__get_is_solid() return false end
function p.__get_tex() return "" end

-------------------------------------------------------------------------

--Huge spheres.
function p.__main()
    --Note: beware of duplicating certain worldgen code.
    block_ball5_3_solid.common_main()
end

Note: a clever optimization is to have 4 blocks on level L+1 instead of 2. That is, we could have the two we just described but also a truly empty block type and a truly solid block type. We would use the truly solid block type for the interior of the spheres. We would use block_ball5_3_solid and block_ball5_3_empty for blocks on the boundary of a sphere. For all blocks sufficiently outside the boundary, we would use the truly empty block type. Honestly, this 4 block approach seems like a hassle.