Difference between revisions of "FastLOS"

From RogueBasin
Jump to navigation Jump to 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 ==
 
<pre>
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.
Each cell needs a blindmask and a sightmask.  These are two
  End for
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
  For each cell in the "border" list do
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.


    If there are no non-opaque neighbors other than those in the
Each cell also needs a 'status' variable.  This can take three
    "included" or "excluded" lists, remove the cell from the "border"
values; perfect, imperfect, and 'generator.'
    list.


    Otherwise add any non-opaque neighbors that are in neither the
In order to generate the sightmasks, we have this basic algorithm:
    "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
  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
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 18:49, 22 October 2011

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.
Retrieved from "http://roguebasin.com/index.php?title=FastLOS&oldid=25936"