LOS using strict definition

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

Introduction

This article aim for developers looking for 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 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 algorithmics.

What we want

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

This example is a typical fov algorithm dilemna ; 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 roguelike. Here are the 3 valid (i.e. deterministic) ways to think about the problem :

- @ 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.

There is several reasons to make one choice over another, but the main factor is how we are considering ranged interaction (or combat) in our game. If it's an unimportant part, then any fov fit. If it is important, we should be more inclined to chose a symetrical behavior ; be warned it's easy to exploit flaws of being able to see without being seen in asymetrical context (it is a recurrent flaw in games with poor fov algorithms). It also depends on the dungeon architecture and movement. The stricter is the fov, the more cramped are the rooms, and the more we are going to see ambushes, forcing an unlucky player to step very next a monster that a corner was hiding. That is why in my opinion a strict symetrical behavior is best.

However this imply the following :

Im sometimes able to tell a certain tile don't obstruct my view even if not seeing it. Since we lit walls that obstruct view, in the @ -> O example above, with a big enough radius @ would see the walls at left and right of O with O's tile being dark; @ can then guess it's floor. Since floors may hide content (objects, monster etc.) this is not really a problem ; but may be a bit disorienting to someone used to other ways to proceed.

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

Unless I have a big fov radius, I won't see the room corner here either, because I'm too close to the wall. This is realistic, but that also mean your rooms won't lit completly as soon as you enter it.

How we do

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. Obstructing walls are lit.

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

void fov(int x, int y)
{
    int i,j;
    for (i = -(int)radius; i <= radius; i++)
        for (j = -(int)radius; j <= radius; j++)
            unlit(i,j);
    for (i = -(int)radius; i <= radius; i++)
        for (j = -(int)radius; j <= radius; j++)
            if(i * i + j * j < radius * radius)
                if (los(x, y, x+i, y+j, true))
                    lit(i,j);
};

bool los(int x0, int y0, int x1, int y1, bool litwalls) // liting walls may not be needed for all los comuptings
{
    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, becauce we may lit a wall "aiming" out of map bounds
        if (map[xnext][ynext] == WALL) // or any equivalent
        {
            if(litwalls)
                lit(xnext, ynext); //lit 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 comparable to most fov computing algorithm, which are in general O(radius ^ 3). This is high and we in general need to avoid repeating full computing of big fovs (for example, computing a full fov per npc per move costs too much) . Fortunately we can calculate visibility of a single tile when needed with the los method ; 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 symetry, you don't need to compute B to A los if you've already done A to B.