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:

1. Symmetry. Everything you see can see you, and vice versa.
2. Expanding pillar shadows. Standing directly next to a pillar produces an expanding shadow.
3. Efficiency. Reasonably fast code can be produced to implement the FOV, etc.
4. No blind corners. Moving diagonally around a corner does not place you in melee range of a previous non-visible tile.
5. Expansive visible walls. You can see all of a room's walls while while standing anywhere inside of it, and all walls of a long, straight corridor. Special cases could be used to give the player extra information about walls for a system which does not inherently possess this property.
6. No hidden ghosts. Passwall monsters inside of visible walls are always visible.

Targeting properties:

1. Visible = Targetable. You can target any visible tile.
2. Non-exploitable. No trick shots required or possible to hit monsters that you can't target directly.
3. No lost targeting. Casting stone-to-mud on a walled, targetable ghost does not cause you to lose targeting on that tile.

Combining expansive visible walls with no hidden ghosts and visible = targetable would produce a system where pass-wall monsters had a significant threat advantage over the player, much more so than even in the current Angband system.

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, expansive visible walls, no hidden ghosts. A demo implementation already exists, and has no known visibility artifacts.

Possible disadvantages

DFOV lacks expanding pillar shadows. 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.

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 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. Additionally, 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

Suggested by jv123.

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

Suggested by Marble Dice

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)

First mentioned by Atanvarno

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.

Intentionally unsymmetrical

Suggested by will_asher

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.)

• Digital FOV and half-width walls.

Fig 27. @ can see the wall, and monsters in the wall, for as far as it goes.

################################################################################################
.@..............................................................................................

---

• Monsters occupy half the width and Center to Center, subdivided grid

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).

See also

Field of Vision