CODEWITHSUNDEEP
language-agnosticartificial-intelligencepath-findingraytracing
cppBeginner
cppBeginner

Reputation: 1212

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.

Upvotes: 1

Views: 1588

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59243

First make a std::map containing pairs of doubles. This will hold the angle ranges from which org is visible. Initially populate it with [0,2*PI]

Then, process squares in order of their distance from org. For each square:

  1. Use lower_bound to find the range that contains the angle from org to the center of the block, if any. If the angle is in one of the ranges, then the block is visible.
  2. If the block is grey, then remove, split, and/or adjust nearby ranges to remove the angles through which it hides the blocks behind it.

That will work in O(N log N) time, which is not bad. Once you're comfortable with how that works, there are a bunch of optimizations you can do. Most importantly, if you process squares in a predefined order, so that you will visit the set of ranges in order, then you can use vectors instead of a map, because you don't have to search. That will get the runtime down to O(N).

Upvotes: 1

codetiger
codetiger

Reputation: 2779

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.

Upvotes: 2

Related Questions