Lighting

[IntegratedQuantum]

The game should have some flood-fill based ambient lighting.

Difficulties

Minecraft's lighting algorithm is fairly simple, however it is also fairly limited due to only having 16 different light values and 2 light channels. This means that the light is not colored and a torch can at most light 16 blocks in one direction.

In Cubyz I would like to have colored lighting (e.g. colored light sources and colored light absorption through glass).

Additionally I would like to have long range interactions. Especially for larger caves minecraft's lighting model looks wrong because torch light cannot reach the opposite wall.

Now bother of these come at a heavy performance cost. 3 more color channels would increase the cost by 3×
Increasing the light range by 2× would increase the cost by 2³ = 8×

Solution Idea 1

Rather than doing lighting on a per-block level, it should be done at a larger scale.

This can be done with a coarse graph structure of the transparent volumes, and traversing that graph on light updates.

Problems with that approach

• how should the terrain be coarsened?
• which nodes should a given block sample to achieve proper smooth lighting?
• What happens at boundaries between different media, like colored glass and air? We wouldn't want white light to bleed through a colored glass pane.

Solution Idea 2

Store column-wise runlength-encoding data.
For each run we only need to store one light value, remaining values are inferred from the block properties and the distance to that light source.
When there is multiple lights that hit the run in different places, then the run should be split into 2 smaller runs.

Problems

• The number of runs will change often during the propagation. This means that a lot of memory should be preallocated, leading to wasted memory. One idea would be to store each run in a different array of 32² elements. As soon as one column exceeds the number of arrays, a new array would be allocated. This wastes a bit of memory, but should use less cache-memory than fragmented allocations.