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:

`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:

`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?