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 close to a dozen of fov implementations to choose from. 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###
---#.#--

Thre majors definition of fov are facing :

- @ and O should see each other : see Permissive_Field_of_View

- @ should see 0 and the reverse is false : see Shadow casting

- Neither @ and O 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:

fov(int x0, int y0, float radius)
{
  int i,j
  for (i = x0-radius; i <= x0+radius; i++)
    for (j = y0-radius; j <= y0+radius; j++)
      line(x0,y0, i, j);

}

void line(x0, y0, x1, 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 efficiency is comparable to most fov computing algorithm, which are in general O(radius ^ 3). This is fairly high and should be avoided to be fully calculated for non-PC characters. Instead, you should only calculate visibility of a single tile when needed.

Fortunately, you don't have to build walls list for a single tile check ; instead, build a line from source to destination with Bresenham's Algorithm. If the line go through a wall, it's obstructed; simple isn't it ?