Author Topic: FastLOS (used to be FastFOV) for those who are interested.  (Read 2799 times)

Bear

  • Rogueliker
  • ***
  • Posts: 308
  • Karma: +0/-0
    • View Profile
FastLOS (used to be FastFOV) for those who are interested.
« on: October 22, 2011, 08:00:13 PM »
I've renamed the FastFOV algorithm to FastLOS, improved it a bit, and streamlined/clarified its roguebasin page a lot.

http://roguebasin.roguelikedevelopment.org/index.php/FastLOS

FastLOS is the only algorithm that can check Line-of-sight between any two tiles in constant time (with no need to touch any of the tiles between them).  It uses precalculation to generate a bitmask for each tile; in order to check line of sight, you just take the AND of the two bitmasks and check to make sure that the two tiles are in sight radius of each other.  If the AND result is nonzero and the tiles are within sight radius of each other, then there is Line of Sight between the two tiles.

Because it can check line-of-sight in constant time, it is the most efficient line-of-sight algorithm known.

It can be used for FOV, but being constant-time per square found, has the same efficiency as spiral-path or recursive shadowcasting, and is inferior to those algorithms if the map is one where FastLOS has any approximations.

It's always been approximate, in the sense that sometimes squares that ought to show in a perfect line-of-sight algorithm will not show if the bitmasks are too small or the map is too complicated. 

The recent improvements that I've put up in the FastLOS article at RogueBasin allow these imperfections to be detected.  The new bitmask generation heuristic (which is simpler than the old one anyway) automatically marks tiles whose field of view isn't perfectly represented by FastLOS. 

If FastLOS shows that line of sight exists, then it definitely exists.  If it shows that no line of sight exists, then up to now it was never really possible to know for sure.  With the new generation heuristic, you can tell more exactly; if either of the squares is NOT marked imperfect, then there is definitely no line of sight.  If BOTH are marked imperfect, and they're within sight radius of each other, then it's worth your time to check with a conventional LOS algorithm if you need perfection.

Other improvements in the precalculation method allow single tiles to be used as View Area generators, with both a much simpler, more elegant algorithm AND better results.  Also, single tiles may now be used to generate several View Areas rather than just one.


Bear

  • Rogueliker
  • ***
  • Posts: 308
  • Karma: +0/-0
    • View Profile
Re: FastLOS (used to be FastFOV) for those who are interested.
« Reply #1 on: October 26, 2011, 01:24:51 AM »
Well, darn.  I thought it was interesting.