Collision Avoidance in Computer Games

• Thesis title in Czech: Vyhýbání se kolizím při pohybu agentů v prostředí počítačových her
• Thesis title in English: Collision Avoidance in Computer Games
• Key words: agent|vyhýbání se kolizím|počítačové hry
• English key words: agent|collision avoidance|computer games
• Academic year of topic announcement: 2023/2024
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Software and Computer Science Education (32-KSVI)
• Supervisor: Mgr. Jakub Gemrot, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 28.11.2023
• Date of assignment: 20.12.2023
• Confirmed by Study dept. on: 15.04.2024
• Date and time of defence: 11.06.2024 09:00
• Date of electronic submission: 30.04.2024
• Date of submission of printed version: 02.05.2024
• Date of proceeded defence: 11.06.2024
• Opponents: doc. Mgr. Martin Pilát, Ph.D.

Guidelines

Agent movement in virtual worlds such as games is typically divided into planning a path in a static environment and then following the path while avoiding collisions with dynamic obstacles and other agents.
Most of the current games use purely reactive techniques for collision avoidance such as velocity obstacles or Reynolds’ boids. These have problems of no future vision and often result in agents being stuck in situations such as moving through narrow corridors in opposite directions.
The aim of this thesis is to explore alternative techniques that can be applied to collision avoidance in games with many simulated agents. Main focus will be on local optimization using genetic algorithms to search local space multiple steps ahead of the current simulation state. Results should be presented visually.

References

Reynolds, C. W. (1987). Flocks, Herds, and Schools: A Distributed Behavioral Model, in Computer Graphics, 21(4) (SIGGRAPH '87 Conference Proceedings) pages 25-34. Retrieved from http://www.red3d.com/cwr/boids/
van den Berg, J., Lin, M., Manocha, D. (2008). Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation. Retrieved from http://gamma.cs.unc.edu/RVO/
Browne, C., Powley, E. J., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Liebana, D. P., Samothrakis, S. & Colton, S. (2012). A Survey of Monte Carlo Tree Search Methods. IEEE Trans. Comput. Intellig. and AI in Games, 4, 1-43. Retrieved from https://www.lamsade.dauphine.fr/~cazenave/A+Survey+of+Monte+Carlo+Tree+Search+Methods.pdf
Van Den Berg, J., Guy, S. J., Lin, M., & Manocha, D. (2011, August). Reciprocal n-body collision avoidance. In Robotics Research: The 14th International Symposium ISRR (pp. 3-19). Berlin, Heidelberg: Springer Berlin Heidelberg.