How to quickly calculate the sight area in a 2D tiled game?

Question

I have a matrix of tiles, on some of that tiles there are objects. I want to calculate which tiles are visible to player, and which are not, and I need to do it quite efficiently (so it would compute fast enough even when I have a big matrices (100x100) and lots of objects).

I tried to do it with Bresenham's line algorithm, but it was slow. Also, it gave me some errors:

----XXX-        ----X**-     ----XXX-
-@------        -@------     -@------
----XXX-        ----X**-     ----XXX-
(raw version)   (Besenham)   (correct, since tunnel walls are 
                              still visible at distance)

(@ is the player, X is obstacle, * is invisible, - is visible)

I'm sure this can be done - after all, we have NetHack, Zangband, and they all dealt with this problem somehow :)

What algorithm can you recommend for this?

---

For my needs, I'll define visible like this: tile is visible when at least a part (e.g. corner) of the tile can be connected to center of player tile with a straight line which does not intersect any of obstacles.

Answer 1

Your definition of visible is the following:

tile is visible when at least a part (e.g. corner) of the tile can be connected to center of player tile with a straight line which does not intersect any of obstacles

You can implement this concept quite literally by tracing rays from your player tile and intersecting them with your scene. You break from each iteration once the ray hits an obstacle (or exceeds a certain distance threshold) since you're only interested on the tiles the player can see directly. I'll break up the process for you:

1. Specify the level of precision you'd like to give the algorithm. This will be the number of rays you will be tracing.
2. Divide the full 360 degrees circle by the chosen precision to know how many degrees to rotate between each ray.
3. Starting at 0 degrees and incrementing by the amount determined in step 2, create a ray with the origin at the center of the player tile, and the direction determined by the current angle.
4. For each ray, starting from the player tile, walk along the direction of the ray until you hit an obstacle tile. Add that tile to the visible tile list and proceed to the next ray. You might also want to add a maximum distance to "give up" in case no collision is found.

Here's a picture showing 3 example rays. The darker colored tiles are the "result" of each ray, i.e where the collision happened. You'd need to repeat this all around the circle though:

Tweak the maximum distance and number of rays for performance. Too little and you'll miss tiles, too much and your performance will suffer. Also, the furthest the rays have to travel, the larger the "error" will get, and the more precision you'll need.

Edit

Check the following tutorial on raycasting, in particular Step 3 and Step 4, to help you implement the intersection bit of the algorithm:

http://www.permadi.com/tutorial/raycast/rayc7.html

Answer 2

I'd rather cast shadow rays instead of line of sight rays.

Let's say this is your view area (the potentially visible area)

######################
#####.............####
###................###
##..................##
#....................#
#....................#
#..........@.........#
#....................#
#....................#
##..................##
###................###
#####.............####
######################

The # blocks are not visible while the . are visible

Let's put some obstacle X:

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXXX...........#
##..................##
###....X...........###
#####.............####
######################

You have a list of the X that are within the view area then you mark as hidden every tile that is behind each of this obstacle: when an obstacle is marked as hidden, you remove it from the list.

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXX*...........#
##......##..........##
###....*#..........###
#####.###.........####
######################

In the example above you can see the shadow casted by the rightmost of the bottom wall and how this shadow delete the hidden obstacle from the list of the obstacle you have to check (X have to check;*checked).

If you get sort the list using some binary partiton so the cosest X are checked first you may slightly speed up your check.

You may use a sort of "Naval Battles" algorithm to check block of Xs at once (basically looking for an adiacent X that is in a direction that can make the shadow cone wider)

[EDIT]

Two rays are needed to cast correctly a shadow and, since a tile is rectangular, a lot of assumptions can be done using the available symmetries.

The ray coordinates can be computed using a simple space partitioning around the obstacle tile:

Each rectangular area constitutes a choice about what of the tile's corner should be taken as shadow cone edge.

This reasoning can be pushed further to connect multiple adjacent tiles and let them cast a single wider cone as follow.

The first step is to ensure that no obstacles are toward the observer direction, in that case the nearest obstacle is considered instead:

If the yellow tile is an obstacle that tile becomes the new red tile.

Now lets consider the upper cone edge:

The blue tiles are all possible candidate to let the shadow cone wider: if at least one of them is an obstacle the ray can be moved using the space partioning around that tile as seen before.

The green tile is a candidate only if the observer is above the orange line that follows:

The same stands for the other ray and for the other positions of the observer about the red obstacle.

The underlying idea is to cover as much area as possible for each cone casting and to shorten as fast as possible the list of obstacles to check.

Answer 3

The problem you are trying to solve is sometimes called Field of View, FOV for short. As you mentioned roguelikes as examples, you should take a look at what the RogueBasin wiki has to say about the subject (there's even links to implementations): http://www.roguebasin.com/index.php?title=Field_of_Vision

There are quite a few different algorithms with different pros and cons - a very handy comparison is available also at RogueBasin: http://www.roguebasin.com/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds