A B C D E F G H I J K L M N O P Q R S T U V W X Y Z All
Debenham, Evan R. M.
- Efficient Field of Vision Algorithms for Large 2D Grids
Authors
1 Department of Computer Science, The University of Western Ontario, CA
Source
AIRCC's International Journal of Computer Science and Information Technology, Vol 13, No 1 (2021), Pagination: 1-20Abstract
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.Full Text
References
- 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.