Lighting

Analysis is based on the decompiled source of the vanilla b1.7.3 client.

Terms

Light Opacity is a value between [0, 255] which describes how opaque a block is. Opaque blocks (including lava) have a light opacity of 255. Other values for light opacity are between [0, 15].

Block Light Value is a value between [0, 15] which describes how bright a voxel is or how emissive a block type is (I will use this term in the context of describing Block Types as well as Voxels in the World). Sky Light Value is a value between [0, 15] which describes how much skylight a voxel receives. A voxel that is exposed to the sky has a sky light value of 15. Light Value will be used as a generalization of both these terms.

Analysis

Each chunk maintains a height map (a 2D array, byte[Z][X]). The value for each index is the y-coordinate of the first block (starting from the top, y=127) in that column for which the block below does not have a Light Opacity equal to zero. A separate per-chunk variable stores the y-coordinate of the lowest block but I'm currently unsure what it is used for.

(Re)Lighting is not a one step process. Rather, it occurs over multiple iterations, which may span multiple ticks of the game loop, until a new state of equilibrium has been reached.

The actual (re)lighting is handled by distinct LightingOperations objects which are essentially a bounding box + lighting logic. These objects are created by the World object in response to some other object requesting a lighting update for a given bounding box, and scheduled for later execution. For instance, when a block in a chunk is modified, the chunk requests a lighting update with a 1x1x1 bounding box corresponding to the modified coordinate.

A LightingOperation can be for either Block or Skylight. I shall refer to these distinct cases as BlockLightingOperation and SkyLightingOperation (though Notch used the same class for both, with conditional checks).

The World maintains a LIFO queue of scheduled LightingOperations (up to 1000000 before the game aborts). On each iteration of the game loop up to 500 LightingOperations are dequeued and executed. Note that the execution of a LightingOperations will likely cause additional LightingOperations to be enqueued. Because the this is a LIFO queue, these new LightingOperations will be executed before older LightingOperations. This subroutine returns a boolean indicating if it was able to completely empty the queue before reaching the 500 limit. This is necessary because world generation + initial simulation use this same subroutine to light the world but it will invoke it continuously until it returns true.

As discussed previously, LightingOperations are created and enqueued by the World in response to some other object requesting an update for a given BoundingBox (in world coordinates, of course). The algorithm is shown below. Notch's implementation includes checks which immediately returns from the subroutine if there are 50 or more levels of recursion. However, it is not clear how this subroutine could be invoked recursively.

World::ScheduleLightingUpdate(Kind, BoundingBox)
{
    // No idea
    if blockExists(BoundingBox.centerX, 64, BoundingBox.centerY) == false then
        return

    // Notch's implementation asks the chunk containing BoundingBox.Center if it wants to
    // prevent this update from being scheduled.  Only empty chunks return true.

    // Iterate over the last five scheduled lighting updates, but ignore SkyLightingOperations.
    for (lightingUpdate in scheduledLightingUpdates.reverseEnumerator[0..<5])
        if lightingUpdate is BlockLightingOperation then
            // Merge will only succeed the complement of BoundingBox and lightingUpdate.BoundingBox 
            // is two or fewer blocks along each axis AND 
            // MergedBoundingBox.Volume - lightingUpdate.BoundingBox.Volume <= 2.
            if lightingUpdate.tryToMergeWith(BoundingBox) then
                return

    if Kind == .Sky then
        scheduledLightingUpdates.enqueue( SkyLightingOperation(BoundingBox) )
    else if Kind == .Block then
        scheduledLightingUpdates.enqueue( BlockLightingOperation(BoundingBox) )
}

On execution of a LightingOperations, a new LightValue, C is computed for each voxel within the LightingOperations bounding box. The bounding box is enumerated in X->Z->Y order (X is outermost) starting from the minimum extent along each respective axis. If there the chunk containing (X,Z,Y) is empty, execution proceeds to the next voxel.

• For a BlockLightingOperation, C is computed as the maximum of the Block Light Value for the block type at (X,Z,Y), and the Block Light Value from its brightest neighboring voxel minus the Light Opacity for the block type at (X,Z,Y). If the block type at (X,Z,Y) has a Light Opacity >= 15 and a Block Light Value of 0, C is 0.

  If C is equal to the current Block Light Value for the voxel at (X,Z,Y), execution proceeds to the next voxel in the bounding box. Otherwise, C is stored as the new Block Light Value for the voxel at (X,Z,Y) and a Block Light Value of C - 1 is propagated to the voxel's preceding neighbors along each axis (X-1, Y-1, Z-1). A Block Light Value of C - 1 is also propagated to the voxel's succeeding neighbors along each axis (X+1, Y+1, Z+1) iff X+1, Y+1, and Z+1 are greater than the bounding box's maximum extents along each respective axis.

• For a SkyLightingOperation, this value is computed as the maximum of 15 (If the voxel is exposed to the sky), and the Sky Light Value from its brightest neighboring voxel minus the Light Opacity for the block type at (X,Z,Y). If the block type at (X,Z,Y) has a Light Opacity >= 15 and the voxel is not exposed to the sky, the computed Sky Light Value for the voxel is 0.

  If C is equal to the current Sky Light Value for the voxel at (X,Z,Y), execution proceeds to the next voxel in the bounding box. Otherwise, C is stored as the new Sky Light Value for the voxel at (X,Z,Y) and a Sky Light Value of C - 1 is propagated to the voxel's preceding neighbors along each axis (X-1, Y-1, Z-1). A Sky Light Value of C - 1 is also propagated to the voxel's succeeding neighbors along each axis (X+1, Y+1, Z+1) iff X+1, Y+1, and Z+1 are greater than the bounding box's maximum extents along each respective axis.