# Digital field of view

From RogueBasin

(Difference between revisions)

(update algorithms and games sections) |
(See discussions) |
||

(2 intermediate revisions by one user not shown) | |||

Line 9: | Line 9: | ||

* O(N<sup>2</sup>) algorithm available. | * O(N<sup>2</sup>) algorithm available. | ||

* More permissive than [[Permissive Field of View]]. | * More permissive than [[Permissive Field of View]]. | ||

+ | * Simpler and potentially faster than PFOV. | ||

* It is easy to check by hand whether there is a digital line connecting two points. | * It is easy to check by hand whether there is a digital line connecting two points. | ||

* Targeting line is easily drawn in case of ranged combat | * Targeting line is easily drawn in case of ranged combat | ||

Line 15: | Line 16: | ||

* Few implementations exist yet. | * Few implementations exist yet. | ||

− | * Could be too permissive. | + | * Could be too permissive, especially with 1-tile wide corridors and room entrances. |

==How do I implement it?== | ==How do I implement it?== | ||

* [[Digital field of view implementation]] is Zeb's explanation for his own algorithm, based on a method similar to beam casting. | * [[Digital field of view implementation]] is Zeb's explanation for his own algorithm, based on a method similar to beam casting. | ||

− | * An improvement over beam casting, where instead of beams, octants are cast in 8 directions, is a part of the 7DRL game Kusemono, with a freely available [http://www.interq.or.jp/libra/oohara/digital-fov/index.html C implementation]. | + | * An improvement over beam casting in the spirit of shadow casting, where instead of beams, octants are cast in 8 directions, is a part of the 7DRL game Kusemono, with a freely available [http://www.interq.or.jp/libra/oohara/digital-fov/index.html C implementation]. |

* Any working [[Permissive Field of View]] algorithm can be turned into a digital field of view algorithm by rotating the grid by 45 degrees, and changing some of the corner cases. | * Any working [[Permissive Field of View]] algorithm can be turned into a digital field of view algorithm by rotating the grid by 45 degrees, and changing some of the corner cases. | ||

− | * One such conversion of PFOV is based on the | + | * One such conversion of PFOV is based on the recursive shadow casting variant of the [[Precise_Permissive_Field_of_View]] algorithm that scans whole quadrants. Both the PFOV and DFOV implementations are a part of [[LambdaHack]] and [[Allure of the Stars]]. The DFOV implementation is simpler and faster than the PFOV implementation, because DFOV has less special cases and inspects tiles in an order matching horizontal dungeon walls. See [https://github.com/Mikolaj/Allure/wiki/Fov-and-los a discussion of this DFOV (and PFOV) algorithm] with links to the Haskell source code. |

==What games use it?== | ==What games use it?== | ||

− | + | * Kusemono ([[7DRL_Contest_2011_Reviews#Oohara_Yuuma.27s_Kusemono]], DFOV is good for sneaking in wide corridors) | |

− | * Kusemono ([[7DRL_Contest_2011_Reviews#Oohara_Yuuma.27s_Kusemono]]) | + | * [[Allure of the Stars]] |

− | * [[Allure of the Stars]] | + | |

==What libraries implement it?== | ==What libraries implement it?== |

## Latest revision as of 20:22, 3 January 2012

## Contents |

## [edit] What is Digital Field of View?

Digital Field of View is a method of determining Field of Vision based on Digital lines. Geometrically, all objects are considered to be diamond shaped, and the source diamond can see the destination diamond if there is an unobstructed line connecting them.

## [edit] Advantages

- Symmetric field of view.
- Completely artifact free.
- O(N
^{2}) algorithm available. - More permissive than Permissive Field of View.
- Simpler and potentially faster than PFOV.
- It is easy to check by hand whether there is a digital line connecting two points.
- Targeting line is easily drawn in case of ranged combat

## [edit] Disadvantages

- Few implementations exist yet.
- Could be too permissive, especially with 1-tile wide corridors and room entrances.

## [edit] How do I implement it?

- Digital field of view implementation is Zeb's explanation for his own algorithm, based on a method similar to beam casting.
- An improvement over beam casting in the spirit of shadow casting, where instead of beams, octants are cast in 8 directions, is a part of the 7DRL game Kusemono, with a freely available C implementation.
- Any working Permissive Field of View algorithm can be turned into a digital field of view algorithm by rotating the grid by 45 degrees, and changing some of the corner cases.
- One such conversion of PFOV is based on the recursive shadow casting variant of the Precise_Permissive_Field_of_View algorithm that scans whole quadrants. Both the PFOV and DFOV implementations are a part of LambdaHack and Allure of the Stars. The DFOV implementation is simpler and faster than the PFOV implementation, because DFOV has less special cases and inspects tiles in an order matching horizontal dungeon walls. See a discussion of this DFOV (and PFOV) algorithm with links to the Haskell source code.

## [edit] What games use it?

- Kusemono (7DRL_Contest_2011_Reviews#Oohara_Yuuma.27s_Kusemono, DFOV is good for sneaking in wide corridors)
- Allure of the Stars

## [edit] What libraries implement it?

None.