Difference between revisions of "FastLOS"

From RogueBasin
Jump to navigation Jump to search
m (moved FastFOV to FastLOS: The algorithm described is an LOS algorithm not an FOV algorithm.)
m
 
(4 intermediate revisions by the same user not shown)
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 once the preprocessing is done.


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 you will get '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 in FastLOS. 
 
The precalculation process allows you to mark imperfect tiles.  If BOTH cells in an LOS calculation are marked imperfect, AND FastLOS shows no line-of-sight, and the two tiles are within the sight radius of one another, you may check using a conventional LOS algorithm if you need perfection.


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
==Algorithm for generating sightmasks ==
    to the "border" and "included" lists,
<pre>


    otherwise add it to the "excluded" list.
Start by setting every sightmask and every blindmask to all-0's.  
  End for
Set the 'status' variable of every tile to 'generator'. 
     
  For each cell in the "border" list do


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


    Otherwise add any non-opaque neighbors that are in neither the
  For all tiles whose status is 'generator',
    "included" nor the "excluded" list to the "candidate" list.


  End for
      generate a Field of view using the current sightmasks
until candidate list is empty.
      generate a Field of View using a standard FOV algorithm.  
</pre>
      If they match, set the status to 'perfect'.
      Otherwise count the number of tiles difference.


The "included" list now contains the cells in the generated field of
  End for.
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
  Pick the 'generator' tile from the above set whose difference is  
assembling a list of fields of view.
      largest.


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.
  Use that tile as a generator to generate a View Area. (Algorithm below)


Here is a recommended heuristic for finding a set of good generators.
  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.


<pre>
      Set the corresponding bit in the blindmasks of all the cells within
1) Consider the four orthogonal neighbors of every open square.  If
      sight radius of any cell in the View Area.
  two or three of them are rock, then the square is a "corner"
   Otherwise
   square.  Every corner square should be considered as a generator
      Set the 'status' of that tile to 'imperfect.'
  by itself.  


2) Consider the four orthogonal neighbors of every rock square.  If
Until there are no cells whose status is 'generator'.  
  three or all of them are open, then the square is an "inner
</pre>
  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
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.  
  (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  
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."
  other half is the cell B in the northeastern quadrant such that:


  1) B is in line of sight from A.
== Algorithm for subroutine generating View Areas. ==


  2) The slope from A to B is greater than the slope from A to the  
<pre>
      inner corner, and
Initialize the "included" set to include (only) the seed tile.


  3) Among the visible squares with higher slope, the slope to B is least.
Perform an Extended Field-of-View Calculation for the seed tile
and use the result as the "candidate" list.


  Likewise, each cell C in the northeastern quadrant is half a
Perform a Field-of-View Calculation for the seed tile using
  generator: the other half is the cell D in the southwestern quadrant
FastLOS (limited to sight radius) and any bits already assigned. 
  such that:
The set of tiles in the Candidate list which are NOT in this
list is the "priority" list.


  1) D is in line of sight from C.
Repeat


   2) The slope from D to C is greater than the slope from D to the
   If there are any "Priority" cells left:
      inner corner, and


  3) among the visible squares with greater slope, the slope to D is
      For each "Priority" tile, find the sum of its distances from all
      least.
          the currently "Included" tiles.


  Some of the (A, B) pairs will also be (C, D) pairs; order doesn't
      Add the highest-scored (most distant) "Priority" to the "Included"
  matter here.
        list and remove it from the "candidate" and "Priority" lists.
</pre>
  else
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.
      For each "Candidate" tile, find the sum of its distances from all
          the currently "Included" tiles.


Now you select the FOV's that are most useful and populate your map with them.
      Add the highest-scored (most distant) "Candidate" to the "Included"
          list and remove it from the "Candidate" list.  


Here's how you do that.
    End If


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.
  Find the set of tiles that is the Field of View for the new tile.


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.  
  Set the Candidate list to be set of tiles that are members of both
      the current Candidate List and the new tile's FOV.


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


<pre>
Until the Candidate List is empty.
While there are FOV's in the candidate FOV list do:


  While you haven't picked an FOV
The "included" list now contains all the tiles in the generated View Area.
    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:
</pre>
    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
[[Category:FOV]][[Category:LOS]]
    accepted, so eliminate it from the list.
 
End While
</pre>

Latest revision as of 07:53, 23 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 once the preprocessing is done.

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 you will get '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 in FastLOS.

The precalculation process allows you to mark imperfect tiles. If BOTH cells in an LOS calculation are marked imperfect, AND FastLOS shows no line-of-sight, and the two tiles are within the sight radius of one another, you may check using a conventional LOS algorithm if you need perfection.

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