Fov and los
Clone this wiki locally
Below are the required properties of the FOV algorithm. Most of them taken from discussion.
- symmetry (everything you see can see you, and vice versa)
- digital lines (there is a digital line to every visible tile)
- efficiency (we have to allow battles involving many friendly units)
- expansive wall display (you can see all of a room's walls while standing anywhere inside of it)
- retreating is safe (if you keep retreating into a corridor, once you are hidden from an immovable monster's sight, you stay hidden; this applies for arbitrarily twisted corridors of width 1 (probably enough to consider digital lines); with symmetry, this implies that retreating doesn't improve your sight, either)
- no blind corners (moving diagonally around a corner does not place you in melee range of a previous non-visible tile)
- permissive (important if we have areas with lots of pillars, because exploring them is tedious if the pillars cast wide shadows)
- realistic physical interpretation of walls, so that visible implies reachable by walking, if no translucent obstructions. (Note however that digital lines are not the only curves with minimal distance in the chessboard metric between two points, so there is a limited agreement between the movement metric and FOV metric. But at least digital lines are a subset of shortest lines and their length counted as the number of tiles is equal to the movement distance between their start and end. If the Angband metric (longer axis plus half of the shorter axis) or Euclidean metric is used, the discrepancy is much wider, resulting in complex game mechanics, so that, e.g., melee characters prefer to approach their foes diagonally and ranged characters prefer vertical and horizontal lines.)
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/AllureOfTheStars/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/AllureOfTheStars/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:
- symmetry (including the line to target, which should be the same as line from target)
- digital lines
- can be hit = is visible and directly targetable (no trick shots required)
- retreating is safe
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 radius and LOS distance was calculated with the Angband or Euclidean metric.