Fast Line Of Sight with FASTLOS

FastLOS is a heuristic algorithm for rapid approximate line-of-sight and field-of-view calculations. It can be used for FOV with an order of complexity as low as any member of the fastest class of precise FOV algorithms (and it is faster than most).  It can calculate Line of Sight between any two squares in constant time without checking the intervening squares at all, so it is the most efficient Line Of Sight algorithm known.

That said, it is only the most efficient line of sight algorithm known once the preprocessing is done.  The preprocessing is significant, and can add a detectable delay to map generation.  The preprocessed line of sight information can be stored with the map, but will need to be recalculated locally whenever the map is modified (if the player can move around objects that block sight, or remove walls by digging, this can be important).

While player field of view operations can always be cached to give monsters “free” information about whether they have line of sight on the player,  FASTLOS can give monsters equal freedom to find line of sight to each other, or indeed to any arbitrary point, for the cost of a distance calculation and a bitmask operation.  With FASTLOS, you can have any creature in the dungeon doing a fast cheap line of sight operations to anywhere.

It is approximate. If your map is too complex, your sightmask bitfield too narrow, or your sight radius too large, sometimes you will find ‘imperfect’ tiles. These are tiles from which some other tiles that ought to be visible in a perfect Line of sight algorithm are not visible using FastLOS.

Finally, you will need a conventional field of view implementation to do the preprocessing.  FASTLOS is mainly a way to cache and access FOV results rather than a ‘magical’ way to do line of sight without benefit of a conventional Line of Sight or Field of View implementation.

Because FastLOS is a heuristic, it has some limitations. You can deal with its limitations in any of several ways.  First, you can just ignore it.  Occasionally, squares that ought to be visible if someone actually did geometry will not be revealed.  This is good enough for monsters, certainly; it’s up to you whether it’s good enough for players.

Second, you can alter the parameters.  You can reduce the sight distances available, or bump up the size of the sightmasks.  If you get imperfect squares at a 32-bit sight mask size, try 64-bits.  Or 128.   If you get imperfect squares at a sight radius of 16 tiles, try a sight radius of 13 tiles instead.  As far as the players are concerned, the sight radius can be reduced because the lighting is dim or the air is foggy.

Third, you can detect imperfect squares (squares where FastLOS may fail to reveal everything) when you’re doing map generation, and patch up the map by adding or removing sight obstructions.  This avoids the issue, but makes some types of map impossible.

Fourth, you can detect the situation during play. The precalculation process allows you to know exactly which tiles are imperfect, so even though there are things FastLOS can’t do, you can know exactly when you can trust it and exactly when you can’t.  When you’re calculating LOS between two tiles in sight range of each other, BOTH of which are marked imperfect, and FastLOS says they don’t have LOS,  You can check a ‘standard’  precise Line of Sight algorithm because in that case FastLOS might be wrong.

With FastLOS, line of sight between any two tiles is checked using a distance check and a check of the result of an “and” operation on a bitmask to see if it is nonzero. If both checks succeed, the two tiles have line of sight on each other. Each tile has a “sight mask” or bitfield that is used for this check. Most of this article is about how to find suitable values for the sight mask for each tile.

Here is the complete code for doing line of sight with FastLOS.

/* if LOS exists, return distance.  If no LOS, return 0. */

int Map_FastLOS(loctype loc1, loctype loc2, int sightrange){
   int distance = Map_Distance(loc1, loc2);
   /* check upper limit on sightrange. */
   assert(sightrange <= SIGHT_RADIUS);
   /* if they're not in sight range it doesn't matter 
      (note STATUS_BLIND creatures have sightrange 0) */
   else if (distance > sightrange)
      return 0;   
   /* In range, any mutual view area means they have LOS */
   else if (GetSightMap(loc1) & GetSightMap(loc2))
      return distance;
   /* Otherwise, iff BOTH squares are imperfect, check SlowLOS.
      Note, if either square is perfect, the status of the other 
      does not justify this test. */
   else if (FastLos_imperfect(loc1) && FastLos_imperfect(loc2))
       return (Map_SlowLOS(loc1, loc2);
   /* otherwise they are not in LOS.  */
   else return 0;
}

The work is in the precalculation.  Some dungeon layouts are harder work. Large irregular caverns and very complex maps with long sight lines and many partial obstructions will make it work very hard in the preprocessing stage.   You can adjust the size of the bitmasks upward, or adjust sight ranges downward, or decrease the complexity of your maps, until you get acceptably low numbers of ‘imperfect’ squares.

I find that with a sight radius of 16 tiles and a sight mask of 64 bits, there are very few imperfect squares.  In fact there are none except in pathologically complex maps.

The basic concept on which FastLOS is based is the “View Area.” A View Area is a set of dungeon tiles having the property that from any tile in the View Area, all other tiles in the same View Area are visible. Any two squares that have Line of sight on each other, have at least one View Area that they are both members of.

Each View Area is assigned its own bit in the sight mask. Thus, when the bitwise AND of the sightmasks of two different tiles has a nonzero result, it means that there exists at least one View Area which both tiles are members of. Thus the two tiles have line-of-sight on each other.

The bigger your dungeon map gets, the more View Areas there are. But because sight is limited to a particular range, the bits in the sightmask can be reused for any different View Areas A and B if they are far enough apart that no Line-of-sight could possibly exist between a square in A and a square in B.

The method described below is a heuristic; there may be better heuristics.

Precalculation

Start by doing an extended field-of-view calculation for each square in the dungeon and cache the results. You will need all of them multiple times when finding view areas. It helps even more if you find the most efficient way you can to represent them and calculate intersections between them.

Each cell needs a blindmask and a sightmask. These are two bitfields the same size. In a given cell, a bit is mapped to a particular view area (marking that cell as a member of it) if the bit is nonzero in the sightmask. The bit is available for mapping to a View Area if and only if it is nonzero in the blindmask.

Each cell also needs a ‘status’ variable. This can take three values; perfect, imperfect, and ‘generator.’

In order to generate the sightmasks, we have this basic algorithm:

 

Algorithm for generating sightmasks

Start by setting every sightmask and every blindmask to all-0's. 
Set the 'status' variable of every tile to 'generator'.  

Repeat

   For all tiles whose status is 'generator', 

      generate a Field of view using the current sightmasks 
      generate a Field of View using a standard FOV algorithm. 
      If they match, set the status to 'perfect'.
      Otherwise count the number of tiles difference. 

   End for.

   Pick the 'generator' tile from the above set whose difference is 
       largest.

   Use that tile as a generator to generate a View Area. (Algorithm below)

   If there is a zero bit in the blindmasks of all the cells in the view 
   area, then
       Set the corresponding bit in the sightmasks of all the cells in the 
       View Area.

       Set the corresponding bit in the blindmasks of all the cells within 
       sight radius of any cell in the View Area.
   Otherwise
       Set the 'status' of that tile to 'imperfect.'

Until there are no cells whose status is 'generator'.

One thing we have to do in generating a View Area is Extended Field of View calculations. This is a standard Field of View, but not limited by sight radius.
In order to generate a View Area we use three lists of tiles: The first is “included,” the second is “candidate,” and the third is “priority.”

Algorithm for subroutine generating View Areas.

Initialize the "included" set to include (only) the seed tile.

Perform an Extended Field-of-View Calculation for the seed tile 
and use the result as the "candidate" list.

Perform a Field-of-View Calculation for the seed tile using 
FastLOS (limited to sight radius) and any bits already assigned.  
The set of tiles in the Candidate list which are NOT in this 
list is the "priority" list.

Repeat

   If there are any "Priority" cells left:

      For each "Priority" tile, find the sum of its distances from all 
          the currently "Included" tiles.  

      Add the highest-scored (most distant) "Priority" to the "Included"
         list and remove it from the "candidate" and "Priority" lists.  
   else 

      For each "Candidate" tile, find the sum of its distances from all
          the currently "Included" tiles.

      Add the highest-scored (most distant) "Candidate" to the "Included"
          list and remove it from the "Candidate" list.   

    End If

   Find the set of tiles that is the Field of View for the new tile.

   Set the Candidate list to be set of tiles that are members of both
       the current Candidate List and the new tile's FOV.

   Set the Priority list to be the set of tiles that are members of both
       the current Priority List and the new tile's FOV. 

Until the Candidate List is empty.

The "included" list now contains all the tiles in the generated View Area.