Calculating which tiles are lit in a tile-based game ("raytracing")

I'm writing a little tile-based game, for which I'd like to support light sources. But my algorithm-fu is too weak, hence I come to you for help.

The situation is like this: There is a tile-based map (held as a 2D array), containing a single light source and several items standing around. I want to calculate which tiles are lit up by the light source, and which are in shadow.

A visual aid of what it would look like, approximately. The L is the light source, the Xs are items blocking the light, the 0s are lit tiles, and the -s are tiles in shadow.

0 0 0 0 0 0 - - 0
0 0 0 0 0 0 - 0 0
0 0 0 0 0 X 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 L 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 X X X X 0 0
0 0 0 - - - - - 0
0 0 - - - - - - -

A fractional system would be even better, of course, where a tile can be in half-shadow due to being partially obscured. The algorithm wouldn't have to be perfect - just not obviously wrong and reasonably fast.

(Of course, there would be multiple light sources, but that's just a loop.)

Any takers?

Solution 1:

The roguelike development community has a bit of an obsession with line-of-sight, field-of-view algorithms.

Here's a link to a roguelike wiki article on the subject: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

For my roguelike game, I implemented a shadow casting algorithm (http://roguebasin.roguelikedevelopment.org/index.php?title=Shadow_casting) in Python. It was a bit complicated to put together, but ran reasonably efficiently (even in pure Python) and generated nice results.

The "Permissive Field of View" seems to be gaining popularity as well: http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View

Solution 2:

You can get into all sorts of complexities with calculating occlusion etc, or you can go for the simple brute force method: For every cell, use a line drawing algorithm such as the Bresenham Line Algorithm to examine every cell between the current one and the light source. If any are filled cells or (if you have only one light source) cells that have already been tested and found to be in shadow, your cell is in shadow. If you encounter a cell known to be lit, your cell will likewise be lit. An easy optimisation to this is to set the state of any cells you encounter along the line to whatever the final outcome is.

This is more or less what I used in my 2004 IOCCC winning entry. Obviously that doesn't make good example code, though. ;)

Edit: As loren points out, with these optimisations, you only need to pick the pixels along the edge of the map to trace from.

Solution 3:

The algorithms being presented here seem to me to be doing more calculations than I think are needed. I have not tested this but I think it would work:

Initially, mark all pixels as lit.

For every pixel on the edge of the map: As Arachnid suggested, use Bresenham to trace a line from the pixel to the light. If that line strikes an obstruction then mark all pixels from the edge to just beyond the obstruction as being in shadow.