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 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. Note that @ will lit walls around junction and be able to guess there is a tile floor at O's position, but he won't see it's content ; this is important, because on the contrary, O dont see @ surrounding and can't guess @ is standing on solid ground.

This imply the following :

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

Unless I have a big fov radius, I won't see the room corner here, 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)// check map bounds here if needed
                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)
    {
        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.