For one of my projects I wanted to calculate the areas that are visible from the player. In a 2d top-down game or an isometric game you can calculate visibility and lighting in 2 dimensions and store it in a bitmap. As usual I got distracted by writing about the algorithm. I've spent too much time on writing it up so I'm going to publish it even though I'm not quite happy with the explanation. I can revise it later.
Here's the algorithm for 2d visibility along with a demo and source code.
Notes about the process
Part of what took a long time was going back and forth between the demo and the tutorial. The demo showed some concepts, then the tutorial tried to explain them. Then I realized that I'm missing some concepts and need to update the demo to show them. This took quite a bit of iteration.
A nice side effect of trying to explain the algorithm is that it helped me improve the algorithm. In an earlier version, sorting lines of different sizes didn't work well. It wasn't a problem in my project because all the lines were the same size, but in the demo it was an issue. While trying to explain this I found a better way to sort the lines so that it worked on all lengths. Another corner case that doesn't work well is when the lines intersect. This also doesn't happen in my project but it can happen in the demo. I decided the solution would complicate the demo code too much (I want it to be reasonably readable) so I instead detected those corner cases and marked them in the demo.
After writing this for my project I decided to look around and see what other people have done. I didn't find a comprehensive survey of techniques but there are several interesting techniques out there. Here's the raw list from my notes; I haven't spent the time to categorize or evaluate them (sorry!):
- GPU implementation
- http://psvilans.wrongbananas.net/dynamic-2d-lighting/ includes a demo that runs in the browser, and source code
- http://www.byronknoll.com/visibility.html is a demo that runs in the browser, and also has a reusable library