Cobertura em ambientes 3D arbitrários: o problema da galeria de arte em jogos de tiro

Abstract

The Art Gallery Problem consists in determining the minimum number of observers required to cover an environment such that each point of space 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 work 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 methodology 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 complex spaces with a small number of agents observing.