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.

The other thing that took so long was that I kept rewriting the UI portion. The original version was for an isometric game, and used shaders to project the light map onto the 3d world. Next I wrote a Haxe + Canvas implementation to run as part of the article, but decided that I should write the UI in Javascript directly because I was more familiar with it. I kept the core algorithm in Haxe (shared with my Flash projects) and wrote the UI in Javascript + d3.js + SVG. It was easier to work with but it ran too slowly on the iPad, and as much as I love d3, this isn't a great fit. So I then wrote a JqueryUI + Canvas implementation. That too was slow but after learning more about Canvas I was able to speed it up to run reasonably on the iPad. I learned a lot by trying different languages and libraries; I hope not to spend several months on the next tutorial.

Other articles

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!). I've also added to the list after posting my page.

Labels: ,

– Amit – Thursday, July 05, 2012

1 comment:

Dan Gries wrote at July 09, 2012 1:36 PM

Beautiful! I know you are mainly illustrating an algorithm, but I really enjoy the aesthetics of the examples you put together.

Post a Comment

Subscribe to: Post Comments ( Atom )