Search code examples
algorithmraytracinglighting

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

  • 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