FastLOS

Introduction

FastFOV is an algorithm for rapid, approximate field-of-view calculations. It was designed for monsters but with a larger bitmask gives sufficiently good results that it may be used for the player characters too.

It is approximate. Sometimes squares that ought to be visible in a full FOV algorithm are not visible in FastFOV.

It is conservative. It will never reveal squares that ought not be visible.

It is symmetric. If FastFOV shows that A has line of sight on B, then it will also show that B has line of sight on A.

With fastFOV, lineofsight between any two cells can be 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 cells have lineofsight on each other. Each cell 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 cell.

It is not well suited for some dungeon layouts. Caves and very complex maps will make it work hard in the preprocessing stage and the results may be noticeably inaccurate without larger "masks" than the 64-bit bitmasks I describe. These problems can be mitigated if sight radiuses are short (< 16 tiles) or if larger bitmasks are used.

And now we get to the meaty bit:

Precalculation

One thing we'll be doing a lot of in the precalculation is generating a field of view from a small set of cells (usually one or two cells), so I'll start by defining that operation. The cells we're talking about are just map cells.

One thing we have to do in generating a field of view is line of sight calculations. It should be stressed that the line of sight calculations used for this purpose are otherwise standard, but NOT limited by range. The final sight check will be limited by range, so such a limitation is useless here and will introduce "fake" differences between FOV's when you want to find duplicates.

In order to generate a field of view we use four lists of cells: The first is "included" cells, the second is "excluded" cells, the third is "border" cells, and the fourth is "candidate" cells.

Algorithm

For each cell in the starting set:
   add that cell to the "border" and "included" list.
   add its open neighbors to the "candidate" list. 
End for

Repeat
   For each cell in the "candidate" list do

     Delete it from the "candidate" list.

     If there is LOS to *EVERY* cell in the "border" list then add it
     to the "border" and "included" lists,

     otherwise add it to the "excluded" list.
   End for
       
   For each cell in the "border" list do

     If there are no non-opaque neighbors other than those in the
     "included" or "excluded" lists, remove the cell from the "border"
     list.

     Otherwise add any non-opaque neighbors that are in neither the
     "included" nor the "excluded" list to the "candidate" list.

   End for
until candidate list is empty.  

The "included" list now contains the cells in the generated field of view.

The business of preprocessing the map comes down to finding a set of Fields of View to map and assigning them appropriate bit numbers. Finding the set of fields of view is done by considering a bunch of candidates and picking the most useful ones. So the first step is assembling a list of fields of view.

In principle, every cell in the dungeon can be used to generate a field of view, so you could add all of these to your initial list. In practice, you will probably want to speed this step up by using some heuristic to find generators likely to produce useful fields of view.

Here is a recommended heuristic for finding a set of good generators.

1) Consider the four orthogonal neighbors of every open square.  If
   two or three of them are rock, then the square is a "corner"
   square.  Every corner square should be considered as a generator
   by itself. 

2) Consider the four orthogonal neighbors of every rock square.  If
   three or all of them are open, then the square is an "inner
   corner."  I'm going to talk about a southeastern inner corner, ie,
   one that has open space in every quadrant but the southeast; the
   same logic can be rotated for the other cases of three open
   neighbors.  The case of four open neighbors requires four
   iterations of this logic, each rotated ninety degrees.

3) Two sets of cells now interest us; the southwestern quadrant
   (including cells in the same row as the inner corner) and the
   northeastern quadrant (including cells in the same column as the
   inner corner).  I recommend considering all squares within five
   steps of an inner corner; higher numbers of steps yield more
   accurate results.

   We eliminate from consideration those which are not open and those
   from which there is no line of sight to the inner corner.

   Each cell A in the southwestern quadrant is half a generator; the 
   other half is the cell B in the northeastern quadrant such that: 

   1) B is in line of sight from A.

   2) The slope from A to B is greater than the slope from A to the 
      inner corner, and 

   3) Among the visible squares with higher slope, the slope to B is least.

   Likewise, each cell C in the northeastern quadrant is half a 
   generator: the other half is the cell D in the southwestern quadrant 
   such that: 

   1) D is in line of sight from C.

   2) The slope from D to C is greater than the slope from D to the 
      inner corner, and 

   3) among the visible squares with greater slope, the slope to D is
      least.

   Some of the (A, B) pairs will also be (C, D) pairs; order doesn't 
   matter here. 

Those two heuristics will give you a set of generators; A singleton generator at each corner and a cluster of pair generators around each inner corner.

In a "rooms and corridors" dungeon these heuristics will save much work; in a cellular-automata cave dungeon, these heuristics won't save you much work over the alternative of just using all the open cells as singleton generators.

Anyway, once you have a list of generators, go ahead and generate fields of view from each generator and add them to a list of fields of view. But every time you're adding a field of view to your list, check to see if it's already there. Again, don't add duplicates. Some generators, although different, will produce identical fields of view.

Now you select the FOV's that are most useful and populate your map with them.

Here's how you do that.

Start by dividing the map into sectors, each as wide and tall as the maximum sight radius. Each sector will need a blindmask the same size as your sightmasks, which you will use to avoid unfortunate bit-to-FOV assignments. The blindmask starts as all-ones.

You will need a bitmask for each map cell. This is the cell's sightmask which will go in the final map. The sightmasks start as all-zeros.

Each FOV will need both a score and a mask of assignable bits. Start with the assignable bits set to all-ones. The score is zeroed each time through.

While there are FOV's in the candidate FOV list do:

  While you haven't picked an FOV
    For each cell in the map whose sightmask is still zero
      If you haven't picked an FOV 
         If there's only one candidate FOV containing that cell
            Pick that FOV as the next to accept.
  End While

  If you haven't picked an FOV yet: 
    For each cell in the map 
      If the cell's sightmap is zero 
         Add one to the score of each FOV containing that cell
    End For
  End if

  If some FOV's now have nonzero scores, 
    Pick one from among the highest-scoring as the next to accept.

  Else 
     For each FOV in the candidate set
        For each FOV in the accepted set
           Calculate score = number of cells in Union minus 
               number of cells in Intersection. 
        End for
        Pick accepted FOV generating the lowest score
           and assign that score to the candidate FOV. 
     End For
     Pick a candidate FOV with the highest score to be the next to accept.
  End If/Else

  You now have a candidate FOV chosen as the next to accept. 
  Remove that FOV from the "candidates" list.

  Initialize empty list for affected sectors and neighboring sectors. 
  Add all sectors that have cells in the FOV to "affected sectors." 
  Add all sectors adjoining an affected sector to "neighboring sectors."

  Pick one of the assignable bits from that sector's assignable-bits mask. 

   Set that bit in the sightmap of each cell of the FOV. 
   clear that bit in the blindmap of each affected and neighboring sector. 

  For every FOV remaining in the candidate list do: 

     Recalculate assignable bits by taking the "AND" of the blindmap of 
     all sectors containing its cells.  

     If the assignable-bits of the FOV is zero, the FOV cannot now be
     accepted, so eliminate it from the list.

End While