24
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Whoops, my mistake, NetHack was not messing with line-of-sight :) \$\endgroup\$
    – Rogach
    Jan 4, 2012 at 23:01
  • \$\begingroup\$ You might find Link useful along with the rest of the series. \$\endgroup\$
    – Adam
    Feb 21, 2012 at 1:36
  • \$\begingroup\$ I also found this which has a working demo: redblobgames.com/articles/visibility \$\endgroup\$ Oct 31, 2012 at 17:31
  • \$\begingroup\$ Some older ideas can be found on fadden.com/tech/fast-los.html, though that harkens back to the days when CPUs were fairly slow and floating point computations were something best avoided. \$\endgroup\$
    – fadden
    Jan 21, 2016 at 22:18

3 Answers 3

10
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ 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? \$\endgroup\$
    – Rogach
    Jan 4, 2012 at 23:32
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 4, 2012 at 23:40
  • 1
    \$\begingroup\$ The algorithm is good, but it will require huge amount of rays to correcly work with long 1-tile-wide tunnels. \$\endgroup\$ Jan 22, 2016 at 11:54
  • \$\begingroup\$ @HolyBlackCat - that will be the case only if you send out rays at even angles in all directions. But you can avoid sending most of those rays and only throw them at line ends in your scene. Here's a good explanation: redblobgames.com/articles/visibility \$\endgroup\$
    – Rogach
    Jan 22, 2016 at 15:20
8
\$\begingroup\$

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.

\$\endgroup\$
12
  • \$\begingroup\$ Interesting approach and probably a better idea because of its subtractive nature. After reading this I'd probably implement it this way too. \$\endgroup\$ Jan 5, 2012 at 16:29
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 5, 2012 at 16:43
  • \$\begingroup\$ 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. \$\endgroup\$
    – FxIII
    Jan 6, 2012 at 1:14
  • \$\begingroup\$ @DavidGouveia - what bigger problems? \$\endgroup\$
    – Rogach
    Jan 6, 2012 at 4:02
  • \$\begingroup\$ @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? \$\endgroup\$
    – Rogach
    Jan 6, 2012 at 4:18
8
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ Really good and complete summary! \$\endgroup\$
    – Rogach
    Feb 20, 2012 at 18:39
  • \$\begingroup\$ That web site is a great resource, thanks for sharing that link. It also contains an amazingly understandable description of how A* pathfinding works :-) \$\endgroup\$
    – uliwitness
    Dec 3, 2014 at 10:31
  • \$\begingroup\$ Link in answer now goes to site home page -- roguebasin.com/index.php?title=Category:FOV appears to be a reasonable match. \$\endgroup\$
    – fadden
    Jan 21, 2016 at 22:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .