Discussion:Field of Vision
Tenants
These were originally posted by PaulBlay, and were later expanded. All of these are not necessarily desirable, and some of them may be mutually exclusive.
Visibility properties:
- Symmetry. Everything you see can see you, and vice versa.
- Expanding pillar shadows. Standing directly next to a pillar produces an expanding shadow.
- Efficiency. Reasonably fast code can be produced to implement the FOV, etc.
- No blind corners. Moving diagonally around a corner does not place you in melee range of a previous non-visible tile.
- Expansive wall display. You can see all of a room's walls while while standing anywhere inside of it, and all walls of a long, straight corridor. This can either be a natural property of the algorithm used (in which case the walls are visible) or handled as a special case (considered displayed but not generally visible or targetable).
- No hidden ghosts. Passwall monsters inside of visible walls are always visible.
Targeting properties:
- Visible = Targetable. You can target any visible tile.
- Non-exploitable. No trick shots required or possible to hit monsters that you can't target directly.
- No lost targeting. Casting stone-to-mud on a walled, targetable ghost does not cause you to lose targeting on that tile.
Expansive visible walls with no hidden ghosts, visible = targetable and symmetry may allow pass-wall monsters to target players from a lot further away than now (see DFOV).
Terminology
Field of View
The field of view refers to the set of squares that are considered visible. For the current discussion, this should not include squares that are known to the player due to ESP, detection, etc. FOV algorithms under discussion all operate by determining if a line-of-sight (LOS) exists between the player and each other game square; actual implementations will probably optimize this calculation. One can imagine FOV algorithms which do not use LOS.
Line of Sight
A path between the player and a visible square. Different LOS algorithms will use different strategies for specifying what part(s) of the source and destination squares are eligible to have lines between them (e.g. the center of the square), what part(s) of wall squares will block LOS, and how many lines must be drawn to have LOS.
Projectile Path
Projectile path refers to the path that a projectile (e.g. an arrow) will travel on its way from a player to a visible square. This is important if intervening monsters can possibly block a projectile from reaching its destination. Some systems may not allow this (in which case LOS == projectile path is trivial) and some will check a path of squares in a given order which are either guaranteed to absorb the shot (as Angband does now), or have a percentage chance to do so. If LOS == targetability then it's important that squares which didn't block LOS not block a projectile. However, some systems may want to those squares absorb projectiles when occupied. Thus, in addition to LOS, it's important to be clear how projectile paths should work.
NOTE: Many of these systems don't make clear how they expect to handle projectile path; it would be great to add this, since implementing FOV/LOS changes in Angband without modifying project_path() won't result in useful changes to gameplay.
Algorithms
Digital FOV
Description
Digital field of view was first mentioned by Atanvarno. The player and monsters are treated as diamonds, with the four points centered on the containing tile's edge. Drawing an unobstructed line from any part of one diamond to another diamond implies visibility. Walls may be treated as diamonds as well, both for visibility and obstruction.
Properties and advantages
Symmetry, efficiency, no blind corners, naturally expansive visible walls, no hidden ghosts. A demo implementation already exists, and has no known visibility artifacts.
Possible disadvantages
- DFOV lacks expanding pillar shadows. Small groups of adjacent wall will still produce a conical shadow effect.
- From any location inside a corridor, the player can see 1 tile around the corner. By standing on the corner, the player can see all the way down both corridors, including walls. Combined with a targeting system that implements Visible = targetable, pass-wall monsters may become significantly more challenging because they could use breath and spells from the safety of a wall tile at great distances, unless the player is given the ability to return fire with spells and/or ranged attacks. Being able to target the pass-waller is not enough; currently player ranged attacks fail when entering a ghost-occupied wall tile.
- This method can produce regions of discontinuous shadows at oblique angles and large distances.
Consequences
Fig 1. Digital FOV ex. %'s are walls out of sight.
%%%%#%% % . %% ###%% % ...# ##....# @.....#%%%% ##........#% % ...###... % ..# %%%% %%%%##
Fig 2. Narrow and discontinuous pillar shadows
...@... @...... @............ @.................. ...#... .#..... ..#.......... ...#............... ... ... .. .... .... ........ ...... ............ ... ... ... ... ...... ...... ......... ......... ... ... .... .. ........ .... ............ ...... ... ... ..... . .......... .. ............... ... ... ... ...... ............ ..................
Fig 3. A room 25% full of pillars.
.. ... .. #.# #.# #.#
. .# #.# #. . ... ... ...
.. .. ... .. .. #.# #.# #.#
#. .# #.# #. .# ... ... ...
.. ....... .. #.# #.# #.#
#. .#.#. .# .........
.. ... .. .#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#. .....................
........@........ #@#
.#.#.#.#.#.#.#.#. .....................
.. ... .. .#.#.#.#.#.#.#.#.#.#.
#. .#.#. .# .........
.. ....... .. #.# #.# #.#
#. .# #.# #. .# ... ... ...
.. .. ... .. .. #.# #.# #.#
. .# #.# #. . ... ... ...
.. ... .. #.# #.# #.#
Diamond walls, point visibility
Description
Walls are considered diamond-shaped obstructions, with the 4 points of the diamond centered on the edges of the containing tile. Visibility between two tiles is implied by drawing an unobstructed line between the centers of the two tiles. The four points of the obstructing diamond do not obstruct visibility unless that point is adjacent to another wall tile (this allows extra visibility around corners, but prevents sight through walls).
Properties and advantages
Symmetry, expanding pillar shadows, efficiency, no blind corners, no hidden ghosts. Ghosts are not visible in corridor walls from great distances, and thus pose no problem for a targeting system that uses visible = targetable.
Possible disadvantages
This method lacks naturally expansive visible walls which means part of a room's walls will not be visible to a player standing inside the room, if he is close to a wall or a corner. This is more pronounced the closer to a wall, and the larger the room. This could be corrected by automatically adding map memory for the walls of lit rooms, so while only some of the walls would be visible (and marked with a special color) all the walls of the room would appear to the player.
A second point-to-diamond "tile visibility" check could be made to add extra visibility for wall tiles, but this would break no hidden ghosts and possibly no lost targeting.
This method can produce regions of discontinuous visibility at oblique angles (see below).
Consequences
Fig 4. Conical pillar shadows
...@... @...... @............ @.................. ...#... .#..... ..# ........ ...# ............. ... ... .. ... ... ..... ..... ....... .. .. .. . ..... . ....... . .. .. ... ...... ......... . . ... ....... ........... . . .... ......... .............
Not all walls (or doors/monsters in those locations) are visible from all locations inside of a room.
Fig 5. Non-visible room walls.
####????? #####???? ?#####??? ??#####?? #@....... #.@...... #..@..... #...@.... #........ #........ #........ #........ #........ #........ #........ #........ ?........ #........ #........ #........ ?........ #........ #........ #........ ?........ ?........ #........ #........ ?........ ?........ #........ #........
Fig 6. Discontinuous point visibility
@#?????
...
###.#
.
?.?
?.?
Half-width walls, center to center
Suggested by Eddie(PowerDiver).
This is a symmetrical system.
Consequences:
Fig 7. Corridor walls / monsters seen forever.
################D @
@ can see D, D can see @
Fig 8. Indeterminate (resolve to not visible).
##D ## @
Fig 9. Diagonal move safety.
#m # @#
Vital that @ can see m in this case.
Fig 10. Pillar blocking sight.
...................... .@# M ......................
@ cannot see M (by zero-width blockage sub-rule - see fig 5)
Fig 11. Discontinuous gaps in viewable area (by zero-width blockage)
....... .@..... ...#... ..... . .......
Monsters occupy half the width/height of grid
Monsters, characters, items are in the center of their grid's square taking up one-quarter of it's area (half the width/height). If lines from any point in the @'s sub-square can go to any point in the M's sub-square without crossing a wall then each is visible by the other. Walls take up the full grid square.
This is a symmetrical system.
Consequences.
Fig 12. @ cannot see D.
#####D###### @
Fig 13. It is indeterminate whether @ can see D or not (zero-width cross).
####D####### @
Fig 14. @ can see D and D can see @
###D######## @
Center to Center, subdivided grid
Any tile that can have a line drawn from the center of the @ to the center of the tile is without crossing an obstructed point is visible. Each wall takes up the middle 2x2 of the 4x4 sub-divided grid.
For visibility purposes a monster on a wall-tile is not treated differently from a monster on a floor tile.
Consequences.
Fig 15. From the entrance of a room.
#######.####### #######@####### ????.......???? ?.............?
Fig 16. @ cannot see M.
................? .........???????? .@.###?????M????? .........???????? ................?
Fig 17. Expanding shadow triangle from pillar.
@........... ...#?....... .....????... .......????? .........???
Fig 18. @ cannot see D.
####D @...
Fig 19. @ can just see D (by allowing zero width cross).
###D# @...
Traditional (Angband)
Trick shots are possible (e.g. you can shoot at indirectly targeted grids that you cannot see or target directly).
Consequences.
Fig 20. A cannot see X but can hit it by shooting at B.
###X.B A.....
Zaiband FOV and targetting
Fig 21. One pillar cases.
.....? ...??? @#???? ...??? .....?
...?? ...?? ..??? ..??. .#... @....
In a plain rectangular room: identical to V, except you can target anything you can see that isn't in a wall. The projection path enabling visibility will automatically swerve as needed, thanks to Tyrecius' Permissive Field of View techniques.
Fig 22. Entering a room
T-intersections and entering rooms are a bit more dangerous in Zaiband:
??. ??. ?.. #.. @.. #.. ?.. ??. ??.
has a reasonable ambush by D:
### #D. #.. #.. #.. @.. #.. #.. #.. #..
Problem being that that with all trick shots being handled automatically, all visible/targetable floor squares are fair game for ground zero of a ball spell; @ can be targeted by D but not conversely.
Fig 23. Symmetrized viewability/projection algorithm
(As not used by Zaiband?)
?## ?D. ?.. ?.. #.. @.. #.. #.. #.. #..
Fig 24. No hockypucks.
Zaiband abolishes the hockey puck by allowing off-diagonal projections to start diagonally:
??o ?x# #x# @.#
In V, this fails because the first step is into the wall to the north.
Pete Mack's Desiderata
Here's a summary of what I understand from this discussion, along with some of my preferences.
I will assume that walls are convex hulls around diamond-shaped wall grids--it makes more sense than anything else.
Definitions: LOS(p1, p2) line from point p1 to point p2 misses (or is tangent to) any intervening wall diamonds.
T(a, b) grid b is targetable from grid a. (Targeting Line of Sight TLOS)
V(a, b) grid b is visible from grid a. (Visual Line of Sight VLOS)
C(a) center point of grid a
These are my desiderata:
1. Target symmetry
1a. assuming a is not a wall and b is not a wall.
- T(a, b) == T(b, a)
##o# If @ can target o then o can target @. @..# ####
1b. For ghosts in the wall, ghost is treated as in an empty square for T(G,@), but is treated as a wall block for T(@, G)
##D# D can target @ but @ can't target D. @... ####
2. LOS symmetry
- V(a, b) == V(b, a)
##o# If @ can see o then o can see @. @..# ####
3. Dominance of V over T. This guarantees VLOS for reverse T(G,@)
- T(a, b) ⇒ V(a, b)
##### All targetable o can be seen .@ooo (but may not be able to target every o that can be seen). ###oo
4. Unpermissive TLOS (I lean towards 4a)
4a By center:
- LOS(C(a), C(b)) ⇔ T(a, b) [ ⇔ T(b, a) ]
4b Existential:
- ∀p1 ∈ a ∃p2 ∈ b LOS(p1, p2) ⇔ T(a, b)
5. Permissive VLOS. (I lean towards 5a)
5a. By center
- LOS(C(a), p2 ∈ b) | LOS(C(b), p1 ∈ a) ⇔ V(a, b)
5b. Existential:
- ∀p1 ∈ a , p2 ∈ b LOS(p1, p2) ⇔ V(a, b)
Am I missing anything in this? In this case, a picture may be worth a thousand words, but a little math is worth a thousand pictures. (You may conclude what you will by transitivity :D )
Intentionally unsymmetrical
Monsters caught in open hallway have no where to hide. Intelligent @'s can peek round corners without being spotted.
Fig 25. @ can see M, but M can't see @.
#.# #####@# ..M...# #######
Other points for consideration
Should @'s and M's have an infinite field of view?
Fig 26. Should @ see M ? How long should maximum sight range be?
################################################################################################# .@.............................................................................................M. #################################################################################################
Special cases for walls (etc.)
Fig 27. @ can see the wall, and monsters in the wall, for as far as it goes.
################################################################################################ .@..............................................................................................
Fig 28. @ can see #, % are walls he can't see, ? is indeterminate
####?%%%%%% .@.........
The question is whether walls (but not monsters in walls) should be filled in when they are not visible, but are adjacent to room / corridor tiles that are visible and lit.
Fig 29. Special case wall visibility
#####G##### .@.........
@ can't see G (but can see wall G is in).