LOS using strict definition

FOV using strict definition - BBQsauce [arthurhavlicek@gmail.com]

Introduction

This article aim for developers looking for elegant fov solution to implement themselves.

When looking for fov algorithms i was sure hoping there was the "simple and obvious way" to do things. There is not. In fact, there is close to a dozen of fov implementations to choose from in the wiki only, trying to emulate three main definitions (see what we want) The choice you make must depend of your programming skills and the desired behavior of your algorithm - because there is several desired behaviors. If you haven't yet, check out Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds which is a great article to start with. In this article, we'll focus on corner-peeking behavior ; this is really the core problem of fov.

What we want

########
.@......
####O###
---#.#--

There is three major distincts ways to plan a fov computing algorithm :

- @ and O should see each other : see Permissive_Field_of_View

- @ should see 0 but not the reverse : see Shadow casting

- @ and O shouldn't see each other : you're at the right place.

This imply the following :

#......
#...@..
-######

I can't see the room corner here, because I'm too close to the wall. This is realistic, but that also mean your room won't lit completly as soon as you enter it.

How we do

We will rely on iteration of the Bresenham's line algorithm (that you can find on wikipedia).

Unlike ray casting, we won't lit the tiles we travel through when iterating a line ; for every target tile we have to build a line. The final tile is lit if and only if the line is unobstructed. If the line go through a wall then it's obstructed ; first obstructing wall is always lit.

The following C code compute a radius-wide fov assuming pc stands on x0 y0:

void fov(int x0, int y0, float radius)
{
  int i,j
  for (i = -(int)radius; i <= radius; i++)
    for (j = -(int)radius; j <= radius; j++)
      if(i*i + j*j < radius*radius) //also check map boundaries if needed
        line(x0,y0, i+x0, j+y0);
}

void line(int x0, int y0, int x1, int y1)
{
  int dx,dy,err,sx,sy,e2;
  dx = abs(x1-x0);
  dy = abs(y1-y0) ;
  if (x0 < x1)
    sx = 1;
  else 
    sx = -1;
  if (y0 < y1)
    sy = 1; 
  else 
    sy = -1;
  err = dx-dy;
 
  while (x0 != x1 || y0 != y1)
  {
    if(map[x][y] == WALL) //or any equivalent
    {
      unlit(x1, y1);
      break;
    }
    e2 = 2*err;
    if (e2 > -dy)
    {
      err = err - dy;
      x0 = x0 + sx;
    } 
    if (e2 <  dx)
    {
      err = err + dx;
      y0 = y0 + sy;
    } 
  }
  lit(x0,y0);
}

Efficiency

The complexity is comparable to most fov computing algorithm, which are in general O(radius ^ 3). This is high and should be avoided to be fully calculated for non-PC characters. Fortunately we can calculate visibility of a single tile when needed with the line method ; checking if a monster can see PC is done very quickly with this method.