Avaliação de algoritmos de detecção de colisão em jogos

Abstract

Collision Detection deals with the objects overlap problem in a virtual environment, it is a major tool to simulate real world physics in a virtual world composed of various geometric shapes and polygons. Games are applications that demand a lot of processing and collision detection is responsible for much of this demand. This work aims to conduct and analyze performance tests and collision accuracy tests using players. For both tests were implemented two java games. The algorithms that will be tested are Euclidean distance, Manhattan distance, overlapping rectangles, pixel perfect, hierarchical detection and overlapping rectangles combined with pixel perfect.Performance tests were done collecting the time it takes to perform the collision detection routine and also how long it takes to go through a pre-programmed route with various numbers of elements to collide. The game for precision tests consists of a quiz game where the player, colliding with objects, answers how realistic was the collision. The results show a great efficiency of hierarchical detection in all tests while perfect pixel shown to be extremely costly in performance issue. The overlapping rectangles method has demonstrate the worst accuracy for the player.