New Algorithms for Computing Field of Vision over 2D Grids
Abstract
In many computer games checking whether one object is visible from another is very important. Field of Vision (FOV) refers to the set of locations that are visible from a specific position in a scene of a computer game. Once computed, an FOV can be used to quickly determine the visibility of multiple objects from a given position.
This thesis summarizes existing algorithms for FOV computation, describes their limitations, and presents new algorithms which aim to address these limitations. We first present an algorithm which makes use of spatial data structures in a way which is new for FOV calculation. We then present a novel technique which updates a previously calculated FOV, rather than re-calculating FOV from scratch. We then compare our algorithms to existing FOV algorithms and show that they provide substantial improvements to running time and efficiency of memory access.