FastLOS

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
(Drastically simplified explanation of precalculation, changed heuristics to give improved results in most cases.)
Line 1: Line 1:
 
== Introduction ==
 
== 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.
+
FastLOS is an algorithm for rapid, approximate line-of-sight and field-of-view calculations.  Because it is constant-time per square, it can be used for FOV as efficiently as any FOV algorithm. But its main strength is that it can calculate Line of Sight between any two squares in constant time, so it is the most efficient Line Of Sight algorithm known.  
  
It is approximate.  Sometimes squares that ought to be visible in a full FOV algorithm are not visible in FastFOV.
+
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.  If your map is too complex, your sightmask bitfield too narrow, or your sight radius too large, sometimes squares that ought to be visible in a full FOV algorithm are not visible in FastLOS.  Proving that FastLOS is exact on a given map is hard.
  
 
It is conservative.  It will never reveal squares that ought not be visible.  
 
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.
+
It is symmetric.  If FastLOS 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.
+
With fastLOS, lineofsight 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 lineofsight 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.
  
 
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.
 
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:
+
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. 
  
== Precalculation ==
+
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. 
  
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.
+
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.
  
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
+
The method described below is a heuristic; there may be better heuristics.  
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.
+
== Precalculation ==
  
== Algorithm ==
+
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.
  
<pre>
+
Each cell also needs a 'status' variable.  This can take three
For each cell in the starting set:
+
values; perfect, imperfect, and 'generator.'
  add that cell to the "border" and "included" list.
+
  add its open neighbors to the "candidate" list.
+
End for
+
  
Repeat
+
In order to generate the sightmasks, we have this basic algorithm:
  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. 
 
</pre>
 
 
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.
 
  
 +
==Algorithm for generating sightmasks ==
 
<pre>
 
<pre>
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
+
Start by setting every sightmask and every blindmask to all-0's.  
  three or all of them are open, then the square is an "inner
+
Set the 'status' variable of every tile to 'generator'.   
  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
+
  neighborsThe 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
+
Repeat
  (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
+
   For all tiles whose status is 'generator',
  from which there is no line of sight to the inner corner.
+
  
  Each cell A in the southwestern quadrant is half a generator; the  
+
      generate a Field of view using the current sightmasks
  other half is the cell B in the northeastern quadrant such that:
+
      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.
  
   1) B is in line of sight from A.
+
   End for.
  
   2) The slope from A to B is greater than the slope from A to the  
+
   Pick the 'generator' tile from the above set whose difference is
      inner corner, and
+
      largest.
  
   3) Among the visible squares with higher slope, the slope to B is least.
+
   Use that tile as a generator to generate a View Area. (Algorithm below)
  
   Likewise, each cell C in the northeastern quadrant is half a  
+
   If there is a zero bit in the blindmasks of all the cells in the view
   generator: the other half is the cell D in the southwestern quadrant
+
   area, then
  such that:
+
      Set the corresponding bit in the sightmasks of all the cells in the  
 +
      View Area.
  
  1) D is in line of sight from C.
+
      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.'
  
  2) The slope from D to C is greater than the slope from D to the
+
Until there are no cells whose status is 'generator'.
      inner corner, and
+
</pre>
  
  3) among the visible squares with greater slope, the slope to D is
+
One thing we have to do in generating a View Area is field of view calculations.  It should be stressed that the 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 View Areas, when you want to find duplicates.
      least.
+
  
  Some of the (A, B) pairs will also be (C, D) pairs; order doesn't
+
In order to generate a field of view we use three lists of tiles: The first is "included," the second is "candidate," and the third is "priority."
  matter here.
+
</pre>
+
+
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.
+
== Algorithm for subroutine generating View Areas. ==
  
Now you select the FOV's that are most useful and populate your map with them.
+
<pre>
 +
Initialize the "included" set to include (only) the seed tile.
  
Here's how you do that.  
+
Perform a Field-of-View Calculation for the seed tile using some
 +
standard FOV algorithm and use the result as the "candidate" list.
  
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.
+
Perform a Field-of-View Calculation for the seed tile using
 +
FastLOS and any bits already assigned. The set of tiles in the  
 +
Candidate list which are NOT in this list is the "priority" list.
  
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.
+
Repeat
  
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.
+
  If there are any "Priority" cells left:
  
<pre>
+
      For each "Priority" tile, find the sum of its distances from all
While there are FOV's in the candidate FOV list do:
+
          the currently "Included" tiles. 
  
  While you haven't picked an FOV
+
      Add the highest-scored (most distant) "Priority" to the "Included"
    For each cell in the map whose sightmask is still zero
+
         list and remove it from the "candidate" and "Priority" lists.
      If you haven't picked an FOV
+
  else
         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 "Candidate" tile, find the sum of its distances from all
    For each cell in the map
+
          the currently "Included" tiles.
      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,
+
      Add the highest-scored (most distant) "Candidate" to the "Included"
    Pick one from among the highest-scoring as the next to accept.
+
          list and remove it from the "Candidate" list.  
  
  Else
+
    End If
    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.
+
  Find the set of tiles that is the Field of View for the new tile.
  Remove that FOV from the "candidates" list.
+
  
  Initialize empty list for affected sectors and neighboring sectors.
+
  Set the Candidate list to be set of tiles that are members of both
  Add all sectors that have cells in the FOV to "affected sectors."
+
      the current Candidate List and the new tile's FOV.
  Add all sectors adjoining an affected sector to "neighboring sectors."
+
  
  Pick one of the assignable bits from that sector's assignable-bits mask.  
+
  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.  
  
  Set that bit in the sightmap of each cell of the FOV.
+
Until the Candidate List is empty.
  clear that bit in the blindmap of each affected and neighboring sector.  
+
  
  For every FOV remaining in the candidate list do:
+
The "included" list now contains all the tiles in the generated View Area.
  
    Recalculate assignable bits by taking the "AND" of the blindmap of
+
</pre>
    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
 
</pre>
 
 
[[Category:FOV]][[Category:LOS]]
 
[[Category:FOV]][[Category:LOS]]

Revision as of 19:49, 22 October 2011

Contents

Introduction

FastLOS is an algorithm for rapid, approximate line-of-sight and field-of-view calculations. Because it is constant-time per square, it can be used for FOV as efficiently as any FOV algorithm. But its main strength is that it can calculate Line of Sight between any two squares in constant time, so it is the most efficient Line Of Sight algorithm known.

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. If your map is too complex, your sightmask bitfield too narrow, or your sight radius too large, sometimes squares that ought to be visible in a full FOV algorithm are not visible in FastLOS. Proving that FastLOS is exact on a given map is hard.

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

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

With fastLOS, lineofsight 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 lineofsight 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.

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.

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

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 field of view calculations. It should be stressed that the 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 View Areas, when you want to find duplicates.

In order to generate a field of view 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 a Field-of-View Calculation for the seed tile using some
standard FOV algorithm and use the result as the "candidate" list.

Perform a Field-of-View Calculation for the seed tile using 
FastLOS 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.

Personal tools