title: Calculating which tiles are lit in a tile-based game ("raytracing")
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <pre><code>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 - - - - - - -
  </code></pre>
  
  <p>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.</p>
  
  <p>(Of course, there would be multiple light sources, but that's just a loop.)</p>
  
  <p>Any takers?</p>