AIRCC's International Journal of Computer Science and Information Technology

Open Access Open Access  Restricted Access Subscription Access

Efficient Field of Vision Algorithms for Large 2D Grids


Affiliations
1 Department of Computer Science, The University of Western Ontario, Canada
 

This paper presents new algorithms for Field of Vision (FOV) computation which improve on existing work at high resolutions. FOV refers to the set of locations that are visible from a specific position in a scene of a computer game.

We review existing algorithms for FOV computation, describe their limitations, and present 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 an FOV from scratch.

We compare our algorithms to existing FOV algorithms and show they provide substantial improvements to running time. Our algorithms provide the largest improvement over existing FOV algorithms at highresolutions, thus allowing the possibility of the creation of high resolution FOV-based video games.


Keywords

Field of Vision (FOV), Computer Games, Visibility Determination, Algorithms.
User
Notifications
Font Size

  • League of Legends. [Online]. Riot Games, 2020. Available: https://na.leagueoflegends.com/en/

  • Jung, J. (2016), “A story of fog and war”, [Online]. Available: engineering.riotgames.com/news/story-fog-and-war [Accessed Sept. 12, 2020] [3] Defense of the Ancients 2. [Online]. Valve Software, 2020. Available: http://blog.dota2.com

  • Bergström, B. (2001), “FOV using recursive shadowcasting”, [Online]. Available:www.roguebasin.com/index.php?title=FOV_using_recursive_shadowcasting [Accessed Sept. 12, 2020]

  • Duerig, J. (2007), “Precise permissive field of view”, [Online]. Available: http://www.roguebasin.com/index.php?title=Precise_Permissive_Field_of_View [Accessed Sept. 12, 2020]

  • Scherzer, D., Wimmer, M., &Purgathofer, W. (2011) “A survey of real‐time hard shadow mapping methods”, Computer graphics forum, Vol. 30, No. 1, 169-186.

  • Liu, N., & Pang, M. Y. (2009) “A survey of shadow rendering algorithms: Projection shadows and shadow volumes”, 2009 Second International Workshop on Computer Science and Engineering, Vol. 1, 488-492.

  • Moreau, P., Pharr, M., &Clarberg, P. (2019) “Dynamic many-light sampling for real-time ray tracing”, High-Performance Graphics - Short Papers, 21-26.

  • Theoharis, T., Papaioannou, G., &Karabassi, E. A. (2001) “The magic of the z-buffer: A survey”, Ninth International Conference in Central Europe on Computer Graphics Visualization and Computer Vision, 379-386.

  • de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008) “Binary space partitions: The painter’s algorithm”, Computational Geometry: Algorithms and Applications, 259-281.

  • Assarsson, U., & Moller, T. (2000) “Optimized view frustum culling algorithms for bounding boxes”, Journal of Graphics Tools, 5(1), 9-22.

  • Luebke, D., & Georges, C. (1995) “Portals and mirrors: Simple, fast evaluation of potentially visible sets”, Proceedings of the 1995 Symposium on Interactive 3D graphics, 105-106.

  • Jice. (2009), “Comparative study of field of view algorithms for 2D grid based worlds”, [Online]. Available: http://www.roguebasin.com/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds [Accessed Sept. 12, 2020]

  • Debenham, E., Solis-Oba, R. (2019) “New Algorithms for Computing Field of Vision over 2D Grids” Electronic Thesis and Dissertation Repository. 6552. The University of Western Ontario. Available: https://ir.lib.uwo.ca/etd/6552 [Accessed Sept. 12, 2020]

  • Ohtsuki, T. (1982, May) “Minimum dissection of rectilinear regions”, IEEE International Symposium on Circuits and Systems, 1210-1213.

  • Samet, H. (1984). “The quadtree and related hierarchical data structures”, ACM Computing Surveys, 16(2), 187-260.


Abstract Views: 439

PDF Views: 180




  • Efficient Field of Vision Algorithms for Large 2D Grids

Abstract Views: 439  |  PDF Views: 180

Authors

Evan R. M. Debenham
Department of Computer Science, The University of Western Ontario, Canada
Roberto Solis-Oba
Department of Computer Science, The University of Western Ontario, Canada

Abstract


This paper presents new algorithms for Field of Vision (FOV) computation which improve on existing work at high resolutions. FOV refers to the set of locations that are visible from a specific position in a scene of a computer game.

We review existing algorithms for FOV computation, describe their limitations, and present 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 an FOV from scratch.

We compare our algorithms to existing FOV algorithms and show they provide substantial improvements to running time. Our algorithms provide the largest improvement over existing FOV algorithms at highresolutions, thus allowing the possibility of the creation of high resolution FOV-based video games.


Keywords


Field of Vision (FOV), Computer Games, Visibility Determination, Algorithms.

References