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.

What we want

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

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

- @ 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. This page is about this approach.

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. In any game with strong distance interaction we should be more inclined to chose a symmetrical behavior ; be warned it's easy to exploit flaws of being able to see without being seen in asymmetrical 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. Finally, it's also a matter of personal taste and aesthetic preferences.

The wall guessing problem

The main problem with the solution is that the final display contain less information than the algorithm have used to calculated 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 - with only the 6 lit walls obstructing, 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, becauce 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 comparable to most unoptimized fov computing algorithm, which are in general O(radius ^ 3). This is above average complexity and we in general need to avoid repeating full computing of big fovs (for example, computing a full fov per npc per move may hurt responsiveness). 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.