Algorithmic approaches to finding cover in three-dimensional, virtual environments

Abstract

In order for an agent to be credible in simulating a human opponent in a first-person combat simulation, it must be able to find and use cover from direct fire weapons. The ability to find cover is fairly intuitive for humans, but current attempts at replicating this ability in computer simulations and video games have been either simplistic or totally missing. This thesis explores a range of algorithms which computer agents can use for finding cover from direct-fire weapons in high-detail, dynamic, three-dimensional environments. The first method treats the enemy as a point light source and uses binary space partition trees to create shadow volumes to find areas of cover. The second method uses a depth-mapping technique to find potential areas where the agent could get behind cover. The third method uses a sensor grid centered on the agent that allows it to check the area around it for cover locations. We implemented the sensor grid technique inside of the first-person shooter computer game America's Army: Operations as a proof of concept.