Permissive-fov

A library for Permissive Field of View.

This is a loose adaptation of libfov to the problem of Permissive Field of View. It can be found as either a tarball or a zip file. The usage and API are described there.

A more complete description of the algorithm used in permissive-fov can be found at Precise Permissive Field of View.

The following is reproduced from the overview of the README file of the library:

Overview

This library provides an implementation of precise permissive field of view calculations on coarse-grained maps. A map is a grid where squares are either completely open or completely obstructed.

Permissive field of view means that a destination square is visible from a source square if and only if there exists an unobstructed line from some point in the source square to some point in the destination square. This is equivalent to finding the shadows cast by an area (as opposed to point) light source.

Precise field of view means that the algorithm does not make any approximations, nor does it make use of floating point numbers. This means that the algorithm (assuming it is bug-free) will produce neither inaccuracies nor anomalies. It also means that there will be no possibility of a rounding error.

The algorithm has a complexity of approximately O(n^2) where n is the radius. I say approximately, because it is difficult to come up with a worst case scenario. Generally, it will tend to perform worse on open areas and better on cramped areas. On a completely open area, it performs at exactly O(n^2).