Light Flood

I said I would not do this, but then I thought it would be possible so I spent a couple of hours, i.e. too much time, to implement this for Bedrock worlds: block light. As I mentioned previously, Bedrock worlds does not store light maps as Java does. This means that I need to manually generate the lights for night mode. I thought it would be a simple algorithm:

1. Find min-max on world.

2. Iterate through world to locate light sources and put them into a queue according to their light intensity.

3. Flood the world with a modified version of BFS, reducing light for each step.

4. Apply to world.

As you can see, this sound pretty easy, right? One could be no more far off. The first part is straightforward, so no explanation here.

The second part sounds easy, but the difficult here is to both recognize actual light sources, and dance through the iteration with coordinate conversions. I really need to move out these type of functionalities and make it easier to convert (even though it might reduce performance a bit due to function calls).

The third is the most difficult, as now not only need you to dance the coordinates, you also need to make sure that while you locate all blocks in xyz position while making sure that you light up transparent blocks (currently only air) and not opaque blocks.

So acknowledging and fixing these issues, what is the real problem? BFS flooding is slow. While in 2D it should suffice plenty in most cases, in 3D it adds an additional 2 edges per node, leading to the increase of the flood area by 50%. The worse case scenario would be O(Blocks + Neighbors), which doesn’t sound that bad, but now imagine there are billions of blocks in a normal world, what about a huge one? While I only look through what’s necessary, if there’s enough light sources, like lava, it’s adding a substantial amount of time to locate them, flood the light and maybe only using about 1% of the block lights at all.

However, the way the algorithm currently is implemented is pretty crude (although I have optimized it severely with dynamic programming) and I think that it is possible to optimize it further. Currently it adds about 200-300% more processing than what all the else does, but I suspect the biggest reason of the slowdown is due to the memory handling. I currently am using std::queue, which has a fragmented memory handling, meaning there are going to be a lot of allocations and de-allocations. This should most probably not be the only reason why it is slow, but it is worth a shot when you lack proper profiling tools. What could be done is to use std::vector instead, putting data at the back of it as you go, but on each iteration on BFS, reserve the current size of the queue times 3(Due to how BFS works) plus the current size of the next queue, meaning there will a substantial less allocations than before, and we avoid big allocation movement that happens on large allocations. It is not perfect, but we will see if this could do it.

As this is only used in night mode, I have disabled the feature whenever it is unnecessary, so per default usage the performance is not affected by this addition.

Edit: Replacing std::queue with std::vector gave a boost at most 10%. It deviates a bit, so could be a fluke. I suspect that if I want to make this even faster, I need to find some other algorithm that does it for me.