I’ve been working on a lot of tile-based games and thought I’d write up a series of tutorials on things I’ve learned. I’m going to try to keep these tutorials as concept-heavy as possible, but my implementation will always be in Python with Pygame. I’ll try to provide psudeocode whenever possible so that those of you who develop in other languages will have an easier time.

More below the cut.

Why Calculate Line of Sight?

Line of Sight is a concept that is extremely useful in not only Roguelikes, but strategy games of all sorts. In a game like Starcraft, where fog of war is an important part of the mechanics of the game, it is necessary to calculate what area of the map is ’seeable’ for each player.

Doing this is simple if we’re dealing with a terrain where there are no blocking obstacles: we simply use the distance formula to determine whether or not each cell is inside the line of sight radius for the particular unit we are examining. If it is, we mark that cell seeable; otherwise, we do not. In order to avoid iterating over the entire map, we can perform our operations on a subsection of the map of height R and width R, where R is the line of sight radius for the unit we’re examining. This algorithm will generate something like this:

where the blue tile is the player, the grey tiles are unseeable, and the box is the area of the map we are iterating over.

As I said above, this is great for games with no obstructing obstacles. When you start modeling walls, mountains, hills, and other types of terrain, this algorithm fails to work. You need to start thinking about raycasting.

What We Expect

In general, we can expect that walls in a level will block visibility whenever a line from the player’s cell to the cell in question intersects a wall.

In short, we want this:

This shows a wall being viewed by a player with an infinite vision radius. Some limitations probably apply here. You usually do not want to calculate LOS for your entire map; that would be too costly. It is usually reasonable to assume that your player has a fairly limited range of vision (in general, the more claustrophobic your setting, the more stingy you can be here). So what we will end up with is a situation like this:

Line of Sight

For each cell that encloses the field of view, we want to find all cells that lie along a line with its origin at the player. In other words, we want to walk along the lines starting at the player and ending at each square that encloses the field of vision. We will mark any cells visible that lie along these lines up until the point where we find a cell that blocks vision, at which point we will mark that cell visible and then stop traversing this line.

Here’s an illustration of a “line of sight” iteration in 2d:

Our main tool in drawing these lines will be Bresenham’s Algorithm, a well known method for choosing cells in a grid to represent lines. Here’s a brief summary of the algorithm in english:


### Initialization step:
Begin with x1, Y1 being the coordinates of the starting point, and X2, Y2 being the coordinates of the ending point.
  Initialize the flag steep to true, and begin with an empty list of coordinates.
  Calculate the delta values dx = (x2 - x1) and dy = (y2 - y1)
  If dx is greater than 0, set sx = 1. Otherwise, set sx = 0. This will be the direction we iterate over the x axis.
  If dy is greater than 0, set sy = 1. Otherwise, set sy = 0.
  If abs(dy) > abs(dx), swap the following values: x1 and y1, x2 and y2, dx and dy, sx and sy. This is responsible for making sure the line is drawn in the right direction (from start to finish). Set the flag steep to true.
  Calculate the starting offset d = (2 * abs(dy)) - abs(dx).
  Begin with x = x1 and y = y1.
  ### Main loop:
  For each value between 0 and abs(dx):
    If steep:
      Push (y, x) onto the result list.
    Else:
      Push (x, y) onto the result list.
    While d >= 0
      y = y + sy
      d = d - (2 * abs(dx))
    x = x + sx
    d = d + (2 * abs(dy))
  Push (x2, y2) onto the result list.
  Return the result list.


If you don’t follow this completely, don’t worry. You can find this algorithm written in most every programming language that exists. What matters is that you understand that when we feed Brensenham’s a start and end coordinate for a line, it will give us the series of coordinates that best correspond to a line between those points.

We could modify this algorithm to check the visibility of each coordinate before it is plotted, and then return the list if the coordinate blocks visibility. Alternatively, we can parse through the list after it’s plotted to check visibility. Here’s an example of that, in Python this time:


def lineofsight(x1, y2, x2, y2):
  for i in brensenham_line(x1, y2, x2, y2):
    x, y = i
    maptiles[x][y].seeable = True
    if (maptiles[x][y].obstructing):
      return False


This will step through the list of coordinates returned by Bresenham’s, setting map tiles seeable, and stop when it finds an obstructing tile.

Field of Vision

In order to turn our line of sight algorithm into a field of vision algorithm, we just have to draw LOTS of lines of sight. There are a number of ways to handle this, but I’ll just describe one of the simplest ones here.

iterate i from 0 to ((max_vision_length*2)+1):
  lineofsight(player.x, player.y, player.x-max_vision_length+i, player.y-max_vision_length)
  lineofsight(player.x, player.y, player.x-max_vision_length+i, player.y+max_vision_length)
  lineofsight(player.x, player.y, player.x-max_vision_length, player.y-max_vision_length+i)
  lineofsight(player.x, player.y, player.x+max_vision_length, player.y-max_vision_length+i)


You should be able to see on inspection that this code will generate something like this:

Which, when combined with the line of sight algorithm that we created above, is exactly what we want.

Next Steps

There’s a lot further to explore here. Here are some links that might help you further expand your ventures into this territory. One drawback to this technique is that as the visible radius is increased:

• more artifacts will begin to show up. (ie: walls that should be visible, but aren’t)
• the cells around the center will be visited multiple times.

There are many solutions to this, one of which is discussed here. Another solution is to draw lines to every square within the field of vision. This is more costly but will eliminate artifacting.

Other implementations of field of vision include creating raster shapes of shadows cast by different objects and combining them to make a custom raster based on the position of seeable objects. This can be super fast, because no actual math is done aside from copying the shadow map onto the field. A discussion of this can be found here.