Search code examples
language-agnosticartificial-intelligencepath-findingraytracing

Ray trace a whole 2D grid from a single light source

In a 2D grid world with known boundary, there are :-

  1. a light source (blue org)
  2. walls (grey)

How to ray trace from center of every white block in the grid to center of org efficiently?
For each block, I want a single boolean - whether it is lit.

In other words, I want the determine whether org can see each block (for whole world) directly or not.

enter image description here

My poor solution

Use standard ray tracing to trace each and every white block toward org, but its performance is very bad. I feel that a lot of computation is redundant.

Related : https://en.wikipedia.org/wiki/Any-angle_path_planning : The algorithm is still for one white block - not the whole world.

Solution

  • You can use Line algorithms like Bresenham's line algorithm or Xiaolin Wu's line algorithm to find the pixels in the path.

    1. Start from the pixel where you want to calculate whether it is lit or not.
    2. Traverse through the pixels in the direction of the light.
    3. If you hit the light first, then it is lit.
    4. If you hit a blocked pixel, then it is dark.

    The same can be used for multiple lights as well. This will be efficient, as you only calculate one line for each pixel.