Cached Supercover Field of View algorithm

[Omnivore]

Since I keep mentioning it in various contexts and at least one person has expressed an interest in it, here it is.

Cached Supercover Field of View algorithm

The cached supercover field of view algorithm is an optimized form of the obvious, brute force, 'check line of sight between origin and each cell in the area of interest' algorithm.  This yields a fully symmetric, zero artifact, result, assuming the use of a 'Supercover' rather than Bresenham, line generation algorithm.

This implementation preserves the invariants of the original but reduces the order of magnitude of the algorithm, increasing performance, by using classic memory for speed tradeoffs and taking advantage of the fundamental nature of the problem space.

Let us assume we have as inputs, a predicate DoesMapBlock(point), a function AllPointsBlockedBy(point) which returns a list of points 'behind' the indicated point, and an iterator SpiralWalk(bounds) which returns an ordered sequence of points from the origin through each point with a square bounding box 'bounds' where the dimensions of bounds are equal to 1 + 2*radius of vision.

We have a feedback predicate CanWeSee(point), and our output is an action WeDoNotSee(point), where the output is a map of booleans initially true for all points.

 For simplicity's sake we will only consider the case where viewpoint is equal to the origin (point 0,0), and we will not consider further optimizations such as quadrant (or even octant) folding.

Our field of view algorithm becomes simply:

Code: [Select]

for each point in SpiralWalk(bounds):
      if !CanWeSee(point):
        continue
      if DoesMapBlock(point):
        for each blocker in AllPointsBlockedBy(point):
          WeDoNotSee(blocker)

Both CanWeSee and WeDoNotSee are trivial lookups and get/set operations on a map of booleans initialized to true.  DoesMapBlock is application dependent.  SpiralWalk is just an iterator over the perimeter points of a rectangle where the rectangle is inflated by two in each dimension each cycle.  AllPointsBlockedBy is a lookup into a map that returns a list of points 'behind' (alternatively blocked by) the indicated point.

In order to construct the map consulted by AllPointsBlockedBy, we can create a universal map for a given maximum radius by evaluating each point in the bounding box described as having dimensions 1 + 2 * maximum vision radius.  We evaluate by iterating over the points generated by a Supercover line generator from start = origin, to end = each point in bounds.  Each point evaluated will be associated with a map of booleans that is initially set to false.

The basic cache generation algorithm is:

Code: [Select]

let cacheMap = map of list of points with map dimensions bounds
for each point in bounds:
  let evalmap = map of booleans with dimensions bounds initialized to false
  for each lineEndPoint in bounds:
    for each linePoint in GenerateSupercoverLine(origin, lineEndPoint):
      evalmap[linePoint] = true
      if linePoint == point:
        break
  for each evalPoint in bounds:
    if (!evalmap[evalPoint]):
      cacheMap[point] += evalPoint
The function AllPointsBlockedBy in the field of view algorithm then simply becomes 'return cacheMap[point]' for any given point.

There are a number of further optimizations that can be made.  Most notably, the size of the cache can be greatly reduced by quadrant or even octant folding and each evaluated point can be compressed to a pair of bytes or less for most roguelike purposes.

The iterator GenerateSupercoverLine used above is assumed to be a partial supercover variant based on Eugen Dedu's description of a modified Bresenham algorithm found at http://lifc.univ-fcomte.fr/home/~ededu/projects/bresenham/  The partial variant ignores exact crossings.

The most significant drawback of this algorithm, other than the increased memory requirements, is that it is only suitable for cases where a boolean result per cell is desired. 

Hope this is of interest,
Brian aka Omnivore

PS: Why Supercover and not Bresenham?

[Trystan]

Have you actually implemented this?

I've thought of something very similar but don't remember why I gave up on it. I assume others have thought of it too. So why isn't this used everywhere? I'm guessing it doesn't work quite right for some reason but I'd like to be proven wrong - a better FOV algorithm that's easier to understand and implement benefits everyone.

[Omnivore]

Yes I have implemented it.  I haven't used it in an actual game yet, at least not in a form I'm ready to release. 

It is quite easy to test, just do a simple non-folding implementation and the equivalent brute force implementation using the same line generator.  Then throw random maps at it and check that both have the same results.

While it is a simple algorithm, it is deceptively simple.  There are a few points that are easy to trip up on that I discovered along the way and there are, I'm sure, ways to mess it up that I haven't tried.

As to why it isn't commonly known or used, *shrug* who knows?  I suspect that, in years gone by, the memory requirements and processor cache behaviors may have made it undesirable.  I also suspect that, as it is derived directly from the brute force approach, many just simply overlooked it.

It is like asking why do people use unmodified Bresenham line drawing algorithm for line of sight?