Below are the required properties of the FOV algorithm. Most of them taken from discussion.
The 'realistic shadows' properties from the Roguebasin discussion are disregarded on the principle of gameplay over realism. The properties are even less important in games with no passwall monsters and a very small real world tile size (e.g., 1m by 1m), where we can realistically expect that heroes peek around the flimsy single pillars, room entrances, etc. If the engine is used for other kinds of games, we will have to reconsider the trade-offs.
Property 5 is only satisfied by algorithms that, to tell if a tile is visible from another, analyze visibility between continuous sections of each of the two tiles, not a small set of points in one of the tiles. Such algorithms are beam casting (e.g, parallel beams starting from diagonals of a tile), Digital FOV (DFOV, visibility from a cross dividing a tile into 4 squares) and Precise Permissive FOV (PFOV, visibility from an 'X' dividing a tile into 4 triangles). Beam casting is usually either costly or has artifacts. Digital FOV and Permissive FOV easily satisfy 4 and 6, which are not so natural for many other algorithms. Digital FOV satisfies 8 (walls are beveled and pillars are diamonds) and is more permissive than Permissive FOV, but the latter is reported to be much more efficient, at least in current implementations, and permissive lines are more visually straight than digital lines.
PFOV is clean-room implemented at https://github.com/Mikolaj/Allure/blob/last_standalone/src/FOV/Permissive.hs, according to the description in Precise Permissive FOV. Its general structure is modeled after recursive shadow casting and so it avoids inspecting tiles behind obstacles, which should make it much faster than a straightforward implementation on maps with long corridors. It is transformed into Digital FOV, at https://github.com/Mikolaj/Allure/blob/last_standalone/src/FOV/Digital.hs, as described in Digital field of view implementation. The DFOV implementations turns out to be much simpler and somewhat faster than PFOV implementation. It's faster especially for conventional dungeons, because it needs half as many sweeps for rectangular rooms with the hero in the middle. OTOH, it makes a bit more tiles visible, so the algorithm is run for more tiles and refreshing them all is more costly.
The required properties of the LOS algorithm:
By setting visible = targetable (that's the choice for this game) and the properties of FOV, we get properties 3, 4. By drawing lines to target with Bresenham's line algorithm, swerving one tile, whenever required, we get 1 and 2. Note that the distance a projective covers is calculated using the chessboard metric, but the trajectory is determined by a (quasi?)metric induced by digital lines. This is a discrepancy, but much less pronounced than if the FOV radious and LOS distance was calculated with the Angband or Euclidean metric.
Last edited by Mikolaj,