Avaliação de algoritmos de detecção de colisão em jogos 2D para Android

Abstract

Electronic games became popular in the 70’s, forming a billionaire market. With the technological advance, this form of entertainment has reached the mobile devices. Due to the improved architecture of mobile devices and the creation of new operating systems, the development of games for this platform has become more attractive. Games are composed of several modules, among them the physics that is responsible for the simulation of the movement of objects. In this context collision detection addresses the problem of overlapping objects in a virtual environment and plays a key role in game development, but it can be very costly. In this sense, this work aims to evaluate different collision detection algorithms in 2D games for Android devices. The algorithms implemented and evaluated are euclidean distance, Manhattan distance, overlapping retangles, separation axis theorem (SAT) and pixel perfect. A literature search was performed to identify which mobile device features should be analyzed and how to evaluate different collision detection algorithms. The algorithms evaluation included to collect and to analyze the execution time of the algorithms and also, with the aid of the Gamebench app, to record frames per second, CPU and GPU usage, memory usage and device battery consumption. Considering different forms of sprites and routes, the results show that SAT is the algorithm based on bounding volumes that has the best accuracy. From resources analysed SAT had a high CPU usage which impacted on its performance, but still being the best alternative for games with few objects that need collision detection. For a large number of objects, the overlapping retangles algorithm performed better than SAT, and its accuracy is (most of the time) similar. The algorithm Manhattan distance had the worst accuracy with all sprites forms, and euclidean distance algorithm presented intermediate accuracy and performance.