Updating lighting in a tile-based game

Question

I've been working on a lighting system for a block-based game I'm developing (think Terraria), and I'm a bit stumped on one point of it. When a block is updated, its light level is also updated based on that of its neighboring (adjacent) blocks.

Now consider this situation: a player digs a hole into the ground, exposing a block that is far down in the Earth to the sun. This gives it a light level of 16 out of 16, and its neighbors a light level of 15. However, if the player fills in the hole again, the block will remain with a light level of 16. My first thought was to "audit" a block's light level when it is updated by checking that it doesn't have a difference of more than one unit from that of its neighbors, but that proved ineffective.

The only solution I could think of would be to specifically check if a placed block is exposed to sunlight, and if so, update the light level of the block below it to 15 out of 16. However, this would not be effective in fixing the issue in certain situations, and the neighboring blocks would fail to decrease in light level due to their neighboring blocks. Perhaps I just need to step back a bit and look at the problem again, but I thought I might post here in the meantime. Does anyone have suggestions as to how to work around this?

Answer 1

In my experience the least error prone and (strangely) fastest method is simply to clear all the blocks of light within the maximum range that could be affected (+-16 in your case) and recalculate them all.

The iterative method when adding light gives nice results but I have found to be much slower; presumably due to the overhead of maintaining lists of blocks that need updating and adding/removing from it as you run through the algorithm. In removing light the iterative method is also bug prone as light can "leak back around" as you're finding; that a block previously at 14 light loses its connection to the sun and so is recalculated; finds a block of light 13 nearby and sets its own light to 12 (rather than all of them being set to zero).

The solution I have used is to clear all the light levels then make a sweep downwards; Gathering light from the 9 blocks (in 3D, 3 blocks in 2D) above each block. Light is decayed for the 8 (or 2 in 2D) blocks that aren't directly above and setting the light level to the maximum value from those 9 blocks. This allows light to travel downwards at up to a 45 degree angle; this can give quite harsh shadows which may or may not be what you want. Repeating the sweep going upwards can alleviate the harsh shadows as can imposing a minimum light level that all blocks have regardless of sunlight.

Answer 2

I think it would be easiest to explain with a flowchart: