Planejamento de caminhos em tempo real aplicado a jogos digitais

Abstract

Digital games are increasingly becoming a very important area in the computing industry. Thus, game's artifical intelligence (AI) is also growing in importance.Pathplanning is, among all problems involved in a game's artificial intelligence, probably the most common. We have to deal with it in every game where the computer needs to move things around independently.When we have static and completely observable environments, pathplanning is relatively an easy problem, which has been widely studied. However, when the agent needs to take decisions fast (move in real time) and the environment is unknown, the problem can be much harder. The list of games with such characteristics is extensive, but the most famous are the Real-Time Strategy (RTS) games.Many studies have been conducted, and several algorithms have been proposed to allow pathplanning in partially observable environments with real-time constraints. However, choosing which of these algorithms to use can be a difficult task. Different studies show algorithms and results in different ways, using different benchmarks and evaluation metrics.In this work we make a comparison between the major existing algorithms to solve the pathplanning problem in partially observable environments with real-time constraints.