LOS using strict definition
FOV using strict definition - BBQsauce [arthurhavlicek@gmail.com]
Introduction
This article aim for developers looking for an uncommon elegant line of sight solution to implement themselves.
When looking for line of sight and field of view 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 next chapter) 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 are going to focus on the corner-peeking behavior ; this really is the core problem of line of sight algorithmic.
Different definitions in a nutshell
######## .@...... ####O### ---#.#--
The above example is a typical line of sight algorithm dilemma ; in the geometry, we may or may not consider walls obstruct @'s view to O, as well as we may or may not consider the reverse is true. It depends on how one defines the fact of "being able to see" in a grid based world. Here are the 3 valid (i.e. deterministic) ways to think about the problem :
- @ and O should see each other. That is to say, if there is any unobstructed line from viewer square to the object square the object is seen. This is Permissive_Field_of_View approach.
Pros : easier to explore. Symmetrical behavior. Lot of existing implementations.
Cons : Cautious gameplay made easier. Hard to hide from ranged combat. Single pillars can cast uncontinuous shadow.
- @ should see O but not the reverse. That is to say if there is any line from the center of the viewer square to the object square the object is seen. This is called Shadow casting approach.
Pros : Fairly aesthetical. Asymetry can create interesting gameplay. Lot of existing implementations.
Cons : "Field" approch, which is ill-suited for some uses. Asymetric thus easily abused in ranged combat.
- @ and O shouldn't see each other. That is to say there must be center to center unobstructed line from viewer to object so that object is seen. We are going to discuss this approach.
Pros : Claustrophobic gameplay. Symetrical. Fairly aestetical. Fairly unique.
Cons : Sometimes can create uncontinuous ray of lights. Do-it-yourself implementation (although, the algorithm isn't complex).
The wall guessing problem
The main problem with the stricter solution is that the final display contain less information than the algorithm have used to calculate it. Let's use a simple example : We're standing on a corridor. We are going to mark lit walls as '#' and unlit as '-'. We see all the floor.
------###------ .......@....... ------###------
Since I can't draw any unobstructed line to corridor walls center, here I can only see a single line and 6 wall units. But the fact that my fov is reduced to a single line of floor clearly indicates me I stand on a corridor. If only the 6 lit walls were obstructing my vision, I'd see two clear cones of over 90 degrees each.
...._______.... ....._###_..... .......@....... ....._###_..... ...._______....
This makes exploration very tedious and counter intuitive, so we have to make our algorithm a tiny bit more permissive. First approach : lit any wall that obstruct the view and the player is able to guess.
----#######---- .......@....... ----#####+#----
Oh, I found a door ! But now, the fix breaks something else : if a monster opens the door, the door no longer obstruct my view, and it goes dark, thus allowing me predict a monster approach while a simple corridor shouldn't (chosen behavior in 1). That's why we need the most subtle approach : we are going to "flash" the walls and door i.e. mark them as seen in the memory map and display them as memorised tile. The player would not be able to know the door had opened at some point, since he doesn't see it - he just predicted it. Note that the player will still be able to guess a dark tile is not a wall in some cases, but this is a trouble we can't fix - if we flash floor tiles we allow the player to know door opens.
Implementation
The strength of this algorithm is that implementation is simple, exact (no artifact or asymmetry) and efficient CPU wise.
We will rely on iteration of a custom los algorithm. This los algorithm calculate points distance to a line using it's equation. If a wall tile is at less than 0.5 distance of source-destination line, then we know it's obstructed.
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. We must also flash the obstructing wall in case a line of sight is obstructed.
The following C++ code compute a radius-wide fov :
void fov(int x, int y)
{
int i,j;
for (i = -(int)radius; i <= radius; i++) //remember to iterate out of map bounds as well
for (j = -(int)radius; j <= radius; j++)
if(i * i + j * j < radius * radius && los(x, y, x+i, y+j))
lit(i,j);
};
bool los(int x0, int y0, int x1, int y1)
// Adapt the funtion to your needs; my current version takes x0 and y0 by reference, and updates them on last iteration
// This way I lit the obstructing walls out of los() so I can re-use the code for simple checks between two points
{
int sx,sy, xnext, ynext, dx, dy;
float denom, dist;
dx = x1-x0;
dy = y1-y0;
if (x0 < x1)
sx = 1;
else
sx = -1;
if (y0 < y1)
sy = 1;
else
sy = -1;
xnext = x0;
ynext = y0;
denom = sqrt(dx * dx + dy * dy);
while (xnext != x1 || ynext != y1)
{
// check map bounds here if needed, not on topest double loop, because we may lit a wall "aiming" out of map bounds
if (map[xnext][ynext] == WALL) // or any equivalent
{
flash(xnext, ynext); //obstructiong wall
return false;
}
if(abs(dy * (xnext - x0 + sx) - dx * (ynext - y0)) / denom < 0.5f)
xnext += sx;
else if(abs(dy * (xnext - x0) - dx * (ynext - y0 + sy)) / denom < 0.5f)
ynext += sy;
else
{
xnext += sx;
ynext += sy;
}
}
return true;
};
Efficiency
The complexity of the algorithm is O(radius ^ 3) which is acceptable in most cases. In case CPU is critical, which is rarely the case, we may need to avoid repeating full computing of big fields (for example, computing a full fov per npc per move may hurt responsiveness). Fortunately the full field isn't needed to determine visibility of a single tile ; when needed we can use a single call to the los function ; you can for example use it when you need to check if a monster can see another monster/an item on the floor without computing full field. Also note that because of the symmetry, you don't need to compute B to A los if you've already done A to B.