Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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 Besenham's 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?

EDIT:

Definition of visible (in my opinion): 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.

share|improve this question
1  
Whoops, my mistake, NetHack was not messing with line-of-sight :) –  Rogach Jan 4 '12 at 23:01

5 Answers 5

up vote 10 down vote accepted

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:

enter image description here

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

share|improve this answer
    
Should I just "walk" along each ray by a fixed distance (say, 0.3 points) or do I need to run something like Besenham's algorithm on each ray? –  Rogach Jan 4 '12 at 23:32
    
If you advance just by a fixed distance you'll get problems with missed tiles. Check this tutorial on raycasting. I'll edit that resouce into my answer too. You basically check for horizontal and vertical collisions separatedly. –  David Gouveia Jan 4 '12 at 23:40

I also found this which has a working demo:

http://www.redblobgames.com/articles/visibility/

share|improve this answer
    
Excellent example! Thanks! –  Rogach Oct 31 '12 at 18:05

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://roguebasin.roguelikedevelopment.org/index.php/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://roguebasin.roguelikedevelopment.org/index.php/Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds

share|improve this answer
    
Really good and complete summary! –  Rogach Feb 20 '12 at 18:39

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:

Space partitioning example

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:

choose the nearest obstacle

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

Now lets consider the upper cone edge:

candidate tiles

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:

extended check

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.

share|improve this answer
    
Interesting approach and probably a better idea because of its subtractive nature. After reading this I'd probably implement it this way too. –  David Gouveia Jan 5 '12 at 16:29
    
I can foresee problems in situations like this. Player in yellow, obstacles in blue and purple. The player should be able to see the purple obstacle (as the green ray shows). But the red shadow ray passing through the blue obstacle rejects the purple tile. But I guess the line of sight version has the potential to have bigger problems than this. –  David Gouveia Jan 5 '12 at 16:43
    
This problem comes from the definition of "hidden": when a ray intersects a tile it will (almost) never cover this fully. The same problem is solved with aliasing when render line segments. Personally i think that a tile is hidden when the major part of it is covered, one can define it hidden is is fully covered, you may find if it expose a side that potentially may make the shadow cone wider... Anyway, you may delist only the blocks that are fully covered. –  FxIII Jan 6 '12 at 1:14
    
@DavidGouveia - what bigger problems? –  Rogach Jan 6 '12 at 4:02
    
@DavidGouveia - I already tried approach with shadow "cones", and it was very inefficient. As for precision of visibility rays - ~5500 rays is enough to see the wall 20 tiles in each direction if you are standing directly near it, and as distance in which just a single tile is visible is much more. And as for missing some tiles at bigger distance - well, not everybody has prefect eyesight, eh? –  Rogach Jan 6 '12 at 4:18

Your Answer

 
discard

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.