A 2D shadow algorithm

Question

I am planning on making a game that utilizes light (and shadows) as part of the gameplay, however I can't think of an efficient algorithm to implement them and I'm sure there is an elegant solution.

The white area is directly illuminated by light, light grey is illuminated by the walls that are directly illuminated and dark grey is darkness.

I wish to find those areas in an efficient manner. (real time, with the light being able to move)

Although not realistic, that is the simplest way I could think of my problem, any other implementation that includes direct light and reflected light is welcome.

...

My first attempt would be to draw lines from the light to the perimeter of the screen and find the first wall they intersect. But repeating this algorithm for every illuminated part of the wall to mark "ambient" light is not feasible.

Also note, the game is in Flash so I don't think I can utilize the gpu.

Answer 1

Inspired by Ryan's answer.

In a 2d grid, mark every point of the screen as lit. Then for every wall on the screen (in order of closeness to point) draw a shadow behind them as such: Before going to the next wall, first check which parts of it are lit and which are not, as to not draw the shadow twice. Mark all the walls for which the shadow was drawn for the next step, as these are the probably lit walls. (we should check again before the next part)

For every lit line segment (wall) first check if any wall intersect the segment. For every intersection split the lit segment in 2 at the intersection.

For the end points of every line segment, repeat the first part in a temporary array, and at the end add all the lit points into the final array.

The first part should go over all the points on the screen and all the points on the walls once. So O(area+length of walls), and depending on the complexity of the scene (number of walls, and interesections the second part should apply the first part about 20 times.

This may work in real time, however make sure to store the lit areas while the lights are not moving.