Difference between revisions of "FastLOS"

From RogueBasin
Jump to navigation Jump to search
(Raw text starting point - not even wikified yet.)
 
m
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== 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. 


FastFOV is an algorithm for rapid, approximate field-of-view
It was designed for monsters but with a larger bitmask gives sufficiently good results that it may be used for the player characters too.
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
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.
full FOV algorithm are not visible in FastFOV.


It is conservative.  It will never reveal squares that ought not
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.
be visible.  


It is symmetric.  If FastFOV shows that A has line of sight on B, then
It is conservative.  It will never reveal squares that ought not be visible.  
it will also show that B has line of sight on A.


With fastFOV, lineofsight between any two cells can be checked using 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.
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
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.
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.


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.


And now we get to the meaty bit: the precalculation.  
The method described below is a heuristic; there may be better heuristics.  


One thing we'll be doing a lot of in the precalculation is generating
== Precalculation ==
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
Each cell needs a blindmask and a sightmask.  These are two
calculations.  It should be stressed that the line of sight
bitfields the same size.  In a given cell, a bit is mapped to
calculations used for this purpose are otherwise standard, but NOT
a particular view area (marking that cell as a member of it) if
limited by range.  The final sight check will be limited by range, so
the bit is nonzero in the sightmask.  The bit is available for
such a limitation is useless here and will introduce "fake"
mapping to a View Area if and only if it is nonzero in the
differences between FOV's when you want to find duplicates.
blindmask.


In order to generate a field of view we use four lists of cells: The
Each cell also needs a 'status' variable.  This can take three
first is "included" cells, the second is "excluded" cells, the third
values; perfect, imperfect, and 'generator.'
is "border" cells, and the fourth is "candidate" cells.


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


Algorithm:


For each cell in the starting set:
==Algorithm for generating sightmasks ==
  add that cell to the "border" and "included" list.
<pre>
  add its open neighbors to the "candidate" list.  
 
End for
Start by setting every sightmask and every blindmask to all-0's.  
Set the 'status' variable of every tile to 'generator'.


Repeat
Repeat
  For each cell in the "candidate" list do


    Delete it from the "candidate" list.
  For all tiles whose status is 'generator',


    If there is LOS to *EVERY* cell in the "border" list then add it
      generate a Field of view using the current sightmasks
    to the "border" and "included" lists,
      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.


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


    If there are no non-opaque neighbors other than those in the
  Pick the 'generator' tile from the above set whose difference is
    "included" or "excluded" lists, remove the cell from the "border"
      largest.
    list.


    Otherwise add any non-opaque neighbors that are in neither the
  Use that tile as a generator to generate a View Area. (Algorithm below)
    "included" nor the "excluded" list to the "candidate" list.


   End for
   If there is a zero bit in the blindmasks of all the cells in the view
until candidate list is empty.
  area, then
      Set the corresponding bit in the sightmasks of all the cells in the
      View Area.


The "included" list now contains the cells in the generated field of
      Set the corresponding bit in the blindmasks of all the cells within
view.
      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'.
</pre>


The business of preprocessing the map comes down to finding a set of
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.  
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.
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."


1) Consider the four orthogonal neighbors of every open square.  If
== Algorithm for subroutine generating View Areas. ==
  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
<pre>
  three or all of them are open, then the square is an "inner
Initialize the "included" set to include (only) the seed tile.
  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
Perform an Extended Field-of-View Calculation for the seed tile
  (including cells in the same row as the inner corner) and the
and use the result as the "candidate" list.
  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
Perform a Field-of-View Calculation for the seed tile using
  from which there is no line of sight to the inner corner.
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.


  Each cell A in the southwestern quadrant is half a generator; the
Repeat
  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
  If there are any "Priority" cells left:
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:
      For each "Priority" tile, find the sum of its distances from all
          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
         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
[[Category:FOV]][[Category:LOS]]

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"