Reimplement dynamic lighting using a multi-pass holistic algorithm.

[kevingranade]

It turns out that shadowcasting may be quite suboptimal for dynamic lighting, in particular because it's bad at culling redundant light sources.

It may be very superior (at least in the very important "half the map is on fire" use case) to instead perform a beam-casting approach as demoed here with code available here.

Short overview of algorithm is like this:

for direction d in [N, E, W, S, U, D]
  for angle = -n to n
    for y = 0 to h
      for r in rays:
          apply_ray(r,  y)
          if (obstacle(r, y))
             remove_ray(rays, r, y)
      for x =0 to w
          if (light_source(x,y))
             add_ray(rays, x,y)
      merge_rays(rays)

A single ray consists of: begin, width, intensity

• begin - offset from some origin, if the origin is static per iteration this does not need to update.
• width - the offset relative to begin that is illuminated.
• intensity - The intensity of the light, originates from the light source and can be adjusted by occlusion (from semi-transparent tiles) and beam merges.

Briefly, the algorithm iterates across the map N times per dominant direction [North, South, East, West, Up, Down], and for each pass, it evaluates a specific beam angle that is dominated by progression in that direction (i.e. it starts at -45degrees relative to the dominant direction and sweeps across to +45 degrees). It proceeds one-angle-at-a-time because it is coalescing beams as it goes, and only beams with the exact same angle can interact with each other. This keeps the working set size small, in fact it's strictly bounded at the number of beams that can fit in the width of the map. Beam intensity does not change over distance, linear falloff is achieved by the fact that beams near their origins overlap and apply light increases to tiles near origins more than they do to tiles distant from origins.

Each light source emits a single beam per ray direction at a specified intensity. As the algorithm progresses across the map, the beams can interact with each other and map features in several ways:

• bisection - a beam that spans cells with differing transparency will split, each beam will proceed independently.
• occlusion - a beam crossing a non-transparent tile will have its luminance reduced. A special case is an opaque tile, in which case one of the beams will terminate.
• merge - a beam that overlaps another beam may merge. Beam width is set to the sum of the contributing beam widths, and beam intensity is set to the weighted average of beam intensities.
• split - a beam that has become too large (width > 1 tile) will split the total width of the original beam and share their intensity value.

Efficiency of the algorithm is based on iteration in extremely cache-friendly ways (beams are stored adjacently and then evaluated in that same order), as well as aggressive culling of overlapping light sources (i.e. a large contiguous block of light sources emits beams relative to their surface area, not their volume).

Example code does not handle beamcasting in 3D, which may be significantly more complex. conceptually, "rays" in the above pseudocode increase significantly in size because they capture two dimensions of begin offset and two dimensions of width offset, but that can be mitigated by using fixed-point numbers for offsets and intensities instead of floats.

[CoroNaut]

I noticed that diagonal symmetry broke down with multiple light sources. Is this supposed to happen?

[kevingranade]

That's definitely a bug. If you highlight tiles near the opening you can see that the asymmetry appears immediately.

[kevingranade]

The plan for adopting this is going to be to port to c++ with a testbed similar to this one as well as wrapping it in some unit tests to make some assertions about light intensities in various scenarios. Verifying lateral symmetry in various contexts is a great example of something we can check.

[Aivean]

Problems with diagonal symmetry can be traced to the problems with horizontal symmetry.

For the Down direction only:

This algorithm is approximate, when beams are merged, some precision is inevitably lost. The trick is to find such merge implementation that reduces visual artifacts to the sane minimum while preserving complexity (keep the max number of active beams bounded).

[FulcrumA]

If light is being reworked, adding some sort of light refraction as well as reflection would be nice (only if not resource intensive). For example, in coronaut's first image, it seems like those obstacles provide nearly perfect shelter from the light, creating shadow often as deep as that in areas completely without light. In reality, while there'd be a considerably shade, areas behind those obstacles would get lighter several tiles away from them if the strength of the light is high enough to penetrate so far.

Possibly forcing tiles next to one with high enough brightness to get slightly brighter as well would do it here? If it's already in, fiddling a bit with values could also do it.

[CoroNaut]

All blocks in that diagonal line are solid walls, If you just place a single wall and remove all others behind the first, you will see that your thoughts are correct.

[kevingranade]

If you have a O(n) algorithm for refraction/reflection effects let us know, otherwise theres not a chance.

[Aivean]

It's possible to use the same generic lighting calculation algorithm to handle reflected light.

The idea is simple: after the first pass you have illumination level for every tile for the direct light from all light sources.

Then you can create "virtual" weak light sources for every illuminated tile and do the second pass. Unfortunately this second pass will almost always be the "worst case" (usually more than the half of the field will be illuminated after the first pass, so there will be more than N light sources).

So, unless C++ implementation is significantly faster than I expect, it won't be feasible.

[Aivean]

@OzoneH3 , here, I've created more readable version with the latest performance improvements: https://github.com/Aivean/efficient-2d-raycasting

I'm releasing it under the MIT license, so please include the copyright notice into the port.

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. Please do not bump or comment on this issue unless you are actively working on it. Stale issues, and stale issues that are closed are still considered.