Fov and los

Visibility (FOV)

Below are the required properties of the FOV algorithm. Most of them taken from discussion. The 'realistic shadows' properties from the discussion are disregarded because of the principle of gameplay over realism and because this game has a very small real world tile size (1m by 1m), so we can realistically expect that heroes peek around the flimsy single pillars, room entrances, etc. The absence of passwall monsters relaxes requirements, too.

1. symmetry (everything you see can see you, and vice versa)
2. digital lines (there is a digital line to every visible tile)
3. efficiency (we'll have battles involving many friendly units)
4. expansive wall display (you can see all of a room's walls while standing anywhere inside of it)
5. 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)
6. no blind corners (moving diagonally around a corner does not place you in melee range of a previous non-visible tile)
7. permissive (we'll have strange randomly filled areas, exploring them is tedious if there's lots of shadows)
8. realistic physical interpretation of walls, so that visible = reachable by walking, if no translucent obstructions

Property 5 is only satisfied by algorithms that analyze visibility between continuous sections of each of the two tiles, spanning the width of the corridor, 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 (visibility from a cross dividing a tile into 4 squares) and Precise Permissive FOV (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 the digital lines to the invisible tiles are the less straight ones.

PFOV is clean-room implemented at https://github.com/kosmikus/LambdaHack/blob/master/src/FOV/Permissive.hs, according to the description in Precise Permissive FOV, but with general structure modeled after recursive shadow casting and so faster. It is transformed into Digital FOV, at https://github.com/kosmikus/LambdaHack/blob/master/src/FOV/Digital.hs, as described in Digital field of view implementation. The DFOV turns out to be much simpler and somewhat faster than PFOV. 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. DFOV will be used for the game; it already plays very nicely for random pillars rooms. In the game, press 'V' to cycle among DFOV, PFOV and a very restrictive Shadow Casting, in that order. Set up a configuration file to make the first level totally random, if you want to test the algorithms.

Targeting (LOS)

The required properties of the LOS algorithm:

1. symmetry (including the line to target, which should be the same as line from target)
2. digital lines
3. can be hit = is directly targetable (no trick shots required)
4. retreating is safe

By setting visible = targetable (still under debate) 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.