Minecraft-Style Voxel Sunlight Algorithm

Question

I'm implementing a pure Minecraft clone, and I want to implement sunlight. I have a basic sunlight algorithm working perfectly in 2D, and I understand how to scale it to 3D. But how do I make it so I don't have to recompute the entire sunlight every time I place a block?

Pseudocode, because the actual algorithm is not written very well :)

FUNC propogateSunlight(x,y,z):
    IF (x,y,z) is out of bounds then RETURN
    IF light_at(x,y,z) is <= 0 then RETURN

    # PROPOGATE
    IF light_can_spread(x,y-1,z) AND light_at(x,y-1,z)<light_at(x,y,z) then:
        set_light_at(x,y-1,z) to light_at(x,y,z)
        propogateSunlight(x,y-1,z)
    IF light_can_spread(x-1,y,z) AND light_at(x-1,y,z)<light_at(x,y,z) then:
        set_light_at(x-1,y,z) to light_at(x,y,z)-1
        propogateSunlight(x-1,y,z)
    *repeat above IF statement for (x-1,y,z), (x+1,y,z), (x,y,z-1), (x,y,z+1) and (x,y+1,z)

Then it sets the top layer to 16 (the max light level) and calls propogateSunlight on the top level.

This algorithm does what I want it to PERFECTLY. The only downside is that it is really really slow.

So what (psuedocode) algorithm is there to place / remove blocks (without transparency) that make it so I don't have to recalculate the entire world?

P.S. The coordinate system is standard 3d graphics, XZ is ground plane, +Y is up and -Y is down.

Answer 1

For each block that you visit as you're doing your light propagation, store an offset/direction to the brightest light shining onto it from a neighbour (eg. if a block is receiving a value of 5 from above and 4 from the left, its offset should point up). Do this for both empty cells and filled cells at the light's boundary.

Now, when you remove a block, you can propagate light again from this brightest neighbouring source, without recalculating the whole shebang.

When you place a block, you can inspect its neighbours to the sides and below. Any that were pointing to your now-occluded block as their brightest light source should search their immediate neighbours for a new light source, and update their brightness accordingly. If they get dimmer, then repeat, looking for neighbours that relied on this cell for their brightest light, and updating them in turn.

This keeps your lighting updates restricted to the "downstream" cone of light from the site you modified, pruning the edges where the lighting doesn't change due to occlusion / backup sources.

---

You can probably also make the initial light propagation faster by moving away from a recursive method that might touch the same cells many times, to one that processes the cells once each, in order. You could look at it as using Djikstra's algorithm to find the lowest-cost (least attenuation) path to each cell from the sun. Steps downward cost zero, steps sideways cost one, and the search bottoms-out at a light value of zero or on opaque cells.

You use a priority queue to handle the cells in order of brightness - so by the time you get to propagating light downward from a cell, you know you'll never have to do that a second time for that cell if a brighter light reaches it later in the algorithm: if there were a brighter source reaching this cell, it would have been evaluated already. In this form, the offset described above always points to the parent cell that last added/bumped this cell in the queue.

Answer 2

When you place/remove a block mark it and the surrounding blocks as dirty.

Every tick you compute n dirty block based on the neighbours.

Every time a light value changes in a block its neighbours get marked as dirty again.

This allows you to spread the work over time and the changes are localized.

However this does have the downside that darkness propagation is slow. Because you end up visiting each block that was at max up to max times until the light values stabilize.

FUNC propogateSunlight(x,y,z):
    IF (x,y,z) is out of bounds then RETURN
    IF light_at(x,y,z) is <= 0 then RETURN

    # PROPOGATE
    IF light_can_spread(x,y-1,z) AND light_at(x,y-1,z)<light_at(x,y,z) then:
        set_light_at(x,y-1,z) to light_at(x,y,z)
        SchedulePropogateSunlight(x,y-1,z)
    IF light_can_spread(x-1,y,z) AND light_at(x-1,y,z)<light_at(x,y,z) then:
        set_light_at(x-1,y,z) to light_at(x,y,z)-1
        SchedulePropogateSunlight(x-1,y,z)
    *repeat above IF statement for (x-1,y,z), (x+1,y,z), (x,y,z-1), (x,y,z+1) and (x,y+1,z)

FUNC SchedulePropogateSunlight(block):
    if lightQueue.contains(block) then:
       return
    lightQueue.add(block)

//call in main loop once
FUNC doPropagation():
    for 0...256 do:
        block = lightQueue.take()
        if block is null then:
            return
        propogateSunlight(block)