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?

Image showing general line of sight and affected tiles

up vote 13 down vote accepted

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.

  • Well, I mostly do Flash and Javascript games, but currently, I do a sort of brute force method which starts to bog down after a bit. I figure if I can figure out how to optimize it, I can get this game running fairly smooth. – Ryan Speets Jul 25 '10 at 17:10
  • It should be easily doable in flash, maybe your brute force could be optimized. Also, in general, you don't have to update it every frame, so you could precalculate the next situation over a couple of frames – Kaj Jul 26 '10 at 0:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.