How can I implement voxel-based lighting with occlusion in a Minecraft-style game?

Question

I am using C# and XNA. My current algorithm for lighting is a recursive method. However, it is expensive, to the point where one 8x128x8 chunk calculated every 5 seconds.

• Are there other lighting methods that will make variable-darkness shadows?
• Or is the recursive method good, and maybe I am just doing it wrong?

It just seems like recursive stuff is fundamentally expensive (forced to go through around 25k blocks per chunk). I was thinking about using a method similar to ray tracing, but I have no idea how this would work. Another thing I tried was storing light sources in a List, and for each block getting the distance to each light source, and using that to light it to the correct level, but then lighting would go through walls.

My current recursion code is below. This is called from any place in the chunk that does not have a light level of zero, after clearing and re-adding sunlight and torchlight.

world.get___at is a function that can get blocks outside of this chunk (this is inside the chunk class). Location is my own structure that is like a Vector3, but uses integers instead of floating point values. light[,,] is the lightmap for the chunk.

    private void recursiveLight(int x, int y, int z, byte lightLevel)
    {
        Location loc = new Location(x + chunkx * 8, y, z + chunky * 8);
        if (world.getBlockAt(loc).BlockData.isSolid)
            return;
        lightLevel--;
        if (world.getLightAt(loc) >= lightLevel || lightLevel <= 0)
            return;
        if (y < 0 || y > 127 || x < -8 || x > 16 || z < -8 || z > 16)
            return;
        if (x >= 0 && x < 8 && z >= 0 && z < 8)
            light[x, y, z] = lightLevel;

        recursiveLight(x + 1, y, z, lightLevel);
        recursiveLight(x - 1, y, z, lightLevel);
        recursiveLight(x, y + 1, z, lightLevel);
        recursiveLight(x, y - 1, z, lightLevel);
        recursiveLight(x, y, z + 1, lightLevel);
        recursiveLight(x, y, z - 1, lightLevel);
    }

Answer 1

1. Every light has a precise (floating point) position, and bounding sphere defined by a scalar light radius value, LR.
2. Every voxel has a precise (floating point) position at it's centre, which you can easily calculate from its position in the grid.
3. Run through every one of 8192 voxels once only, and for each, see if it falls within each of N lights' spherical bounding volumes by checking |VP - LP| < LR, where VP is the voxel's position vector relative to origin and LP is the light's position vector relative to origin. For each light whose radius the current voxel is found to be in, increment it's light factor by the distance from the light centre, |VP - LP|. If you normalise that vector and then get its magnitude, this will be in range 0.0->1.0. The maximum light level a voxel can reach is 1.0.

The runtime is O(s^3 * n), where s is the side length (128) of your voxel region and n is number of light sources. If your light sources are static, this is no problem. If your light sources move in real time, you can work solely on deltas rather than recalculating the whole shebang every update.

You could even store the voxels which each light affects, as references within that light. This way, when the light moves or is destroyed, you can go through just that list, adjusting light values accordingly, rather than having to traverse the entire cubic grid again.

Answer 2

Minecraft itself doesn't do the sunlight this way.

You simply fill the sunlight from the top to the bottom, every layer is gathering light from neighbor voxels in the previous layer with attenuation. Very fast - single pass, no lists, no data structures, no recursion.

You have to add torches and other non-flooding lights in a later pass.

There are so many other ways to do this, including fancy directional light propagation etc. , but they are obviously slower and you have to figure out if you want to invest in the additional realism given those penalties.

Answer 3

Someone said to answer your own question if you figured it out, so yeah. Figured out a method.

What I am doing is this: First, create a 3d boolean array of "already changed blocks" overlayed over the chunk. Then, fill in sunlight, torchlight, etc (just lighting up the block that its on, no flood filling yet). If you changed something, hit the "changed blocks" in that location to true. Also go though and change every solid block (and therefore no need to calculate lighting for) to "already changed".

Now for the heavy stuff: Go though the entire chunk with 16 passes (for each light level), and if its 'already changed' just continue. Then get the light level for the blocks around itself. Get the highest light level of them. If that light level equals the current passes' light level, set the block you are on to the current level, and set "already changed" for that location to true. Continue.

I know its kind of complicated, I tried to explain my best. But the important fact is, it works and is fast.

Answer 4

I'd suggest an algorithm that sort of combines your multi-pass solution with the original recursive method, and is most likely quite a bit faster than either of them.

You'll need 16 lists (or any kind of collections) of blocks, one for each light level. (Actually, there are ways to optimize this algorithm to use fewer lists, but this way is easiest to describe.)

First, clear the lists and set the light level of all blocks to zero, and then initialize light sources as you do in your current solution. After (or during) that, add any blocks with a non-zero light level to the corresponding list.

Now, go through the list of blocks with light level 16. If any of the blocks adjacent to them have light level less than 15, set their light level to 15 and add them to the appropriate list. (If they were already on another list, you can remove them from it, but it doesn't do any harm even if you don't.)

Then repeat the same for all the other lists, in decreasing order of brightness. If you find that a block on the list already has a higher light level than it should for being on that list, you can assume it was already processed and not even bother checking its neighbors. (Then again, it might be faster to just check the neighbors — it depends on how often that happens. You should probably try it both ways and see which way is faster.)

You may note that I haven't specified how the lists should be stored; really pretty much any reasonable implementation ought to do it, as long as inserting a given block and extracting an arbitrary block are both fast operations. A linked list should work, but so would any halfway decent implementation of variable-length arrays too. Just use whatever works best for you.

---

Addendum: If most of your lights don't move very often (and neither do the walls), it might be even faster to store, for each lit block, a pointer to the light source that determines its light level (or to one of them, if several are tied). That way, you can avoid global lighting updates almost entirely: if a new light source is added (or an existing one brightened), you only need to do a single recursive lighting pass for the blocks around it, while if one is removed (or dimmed), you only need to update those blocks that point to it.

You can even handle wall changes this way: when a wall is removed, just start a new recursive lighting pass at that block; when one is added, do a lighting recalc for all blocks that point to the same light source as the newly walled block.

(If several lighting changes happen at once — e.g. if a light is moved, which counts as a removal and an addition — you should combine the updates into a single one, using the algorithm above. Basically, you zero out the light level of all blocks pointing to removed light sources, add any lit blocks surrounding them as well as any new light sources (or existing light sources in the zeroed out areas) to the appropriate lists, and run the updates as above.)