Coverage in Arbit rary 3D Environments The Art Gallery Problem in Shooter Games
Eduardo Penha, Castro Fantini, Luiz Chaimowicz · 2013
The Art Gallery Problem consists in determining th e minimum number of observers required to cover an environment such that each point is seen by at least one observer. This is a NP-Hard problem well known in the field of computational geometry. In the literature, several restrictions are applied to 2D and 3D environments to study and solve the problem in polynomial time, for example the use of simple polygons, orthogonal and planar environments, etc. In this paper we present an approximate and polynomial solution based on metaheuristic genetic algorithms that can be applied to general 3D environments without any restriction and, therefore, applicable in shooter games and also real-world environments. The solution uses the techniques of (i) computer graphics to generate sample points in the environment, (ii) ray-mesh intersection test to generate a graph of visibility between the samples and (iii) genetic algorithms to find and optimize the minimum set of observers. The maps of the game Counter-Strike were used to analyze the placement of small groups of observers in complex environments with obstacles. The game engines Half- Life and Irrlicht were used to apply the ray-mesh intersection test in 3D environments. A series of experiments were performed and the results show that our methodology is capable of obtaining a good coverage of space with a small number of agents observing. Keywords—art gallery problem; co mputational geometry; visibility; natural computation; computer graphics; shooter games