Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a 2d grid of tiles, and an approximated sphere of coordinates - centered on the player - that represents line of sight. The goal is to block the line of sight beyond obstacles (ie walls).

It's relatively simple to determine if an individual cell in the sphere of sight is visible: cast a ray from the player to the target cell, using Bresenham's - if one of the overlapping cells between the player and the target is an obstacle, the target cell is not visible.

Now, my first thought was to iterate through all grid cells in the line of sight - but this seems inefficient to me. For example, if the player is standing next to a wall, and you determine that the cell beyond the wall isn't visible, you can determine all cells on the ray after that won't be visible.

Also considered casting a ray to each cell along the perimeter of the sphere of sight, and iterating each cell along each ray - but then I'd be processing some cells more than once.

Is there a more efficient way to do this?

While iterating ~50 cells per turn is a relatively lightweight calculation, I'm going for speed - the goal is to be able to cycle a few turns per second on auto-play. So, the more efficient I can make this, the better.

share|improve this question
"Best" questions don't usually do well. Since the best way is very specific to your goals and other features you need to support. I recommend you just profile the code and see if it's good enough for your needs now. Profiling will also show you the parts of your code you need to improve first for better performance. – Byte56 Jan 17 '13 at 19:38
How many cells are you expecting to have around the player? – Luis Estrada Jan 17 '13 at 19:44
@byte thanks for the tip - reworded the question – CodeMoose Jan 17 '13 at 20:26
You'll recall You can do it in an O(n) sweep. – Will Jan 17 '13 at 20:38
Are you sure that you need to optimise? Have you actually encountered a bottleneck that needs to be dealt with? Or are you simply guessing that it will be an issue in the future? If your code is relatively modular it should be the easiest thing in the world to develop a solution and then come back to it later IF optimisation is needed. – Djentleman Jan 17 '13 at 22:06
up vote 7 down vote accepted

You could try casting "shadow arcs" to cover larger areas at once. While the actual details are a bit involved, Eric Lippert has a very in-depth explanation (with live Silverlight demo) at

Example step of tracing out two rays.


share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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