I am working on a 2D tile-based game, and right now I'm trying to get a 2d equivalent of shadow volumes to work. I'm having trouble finding the surfaces that should cast shadows. From any point in the game, I need to find either the unoccluded faces, or the whole tile.
My question is, is how can I find these tiles/edges as fast as possible given a point?
There's a lot of work done towards that problem in the roguelike community.
Here's a page that lists some algorithms and libraries that might help you. http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision
This is not a complete answer, but hopefully it will help.
Is your map/tile set static or dynamic? If it's static, I would strongly encourage you to do offline processing and precompute as much as you can that way. You can do it in any way you want (raycasting or something smarter), but you don't really care about making very fast because it will all happen offline while you "bake" your levels. You can either precompute exactly which tiles are visible from each spot, or create some kind of larger regions and all the tiles potentially visible from each region.
Then, at runtime, the query for the visible tiles should be very straightforward and very fast.
Of course, if you're having dynamically created levels, then this doesn't apply at all :-)
You can see how I implemented this for a C# roguelike here. The code isn't highly optimized, but it seems to be fast enough for me and (more importantly) should be fairly easy to read. It's basically doing a simple shadow casting algorithm that works one octant at a time.
I'm not sure what platform you're on, but I can't really think of any platform that wouldn't be fast enough to just grow a circle around your lightcasting entities (unless there's a lot of em) and detect whether the tile about to be 'plotted' in your circle algorithm is a solid tile and thus lightblocking. From there on it would be slightly trickier as you'd have to keep track of circle segments that are occluded or not, but it would be what I would do. Another option would be to cast rays in a circle (again pretty fast) in tile resolution space and stop each ray as it hits a solid tile.
