Implementation and test of a path planning algorithm in a real time strategy game

O planejamento de caminhos faz parte dos principais módulos de um sistema multiagente com ambientes dinâmicos, e tem como objetivo ajudar a garantir um nível mínimo de autonomia de movimentação aos agentes. Simulações contendo sistemas multiagente em ambientes dinâmicos são muito empregadas em jogos eletrônicos, e com o crescimento do segmento comercial de jogos, incluindo jogos para dispositivos portáteis e celulares, as tecnologias empregadas em sistemas multiagentes ficaram em evidência, a fim de garantir os diversos níveis de detalhe exigidos pelo público usuário da simulação. O objetivo deste trabalho foi realizar a implementação e análise de um planejador de caminhos que usa campos potenciais em um jogo de estratégia em tempo real (RTS), de forma a permitir uma comparação com outro planejador de caminhos, e verificação da qualidade e demais características do método proposto. Durante o trabalho, são apresentadas as informações técnicas sobre o planejador de caminhos usado, além de dados à respeito do jogo utilizado para os testes, e os detalhes de integração referentes à implementação do novo algoritmo no jogo. Também são descritos os testes realizados, que envolveram verificações de desempenho e qualidade, além de um teste de vantagem estratégica. Os testes de desempenho mostram a capacidade de escalabilidade e limites gerais do algoritmo planejador de caminhos novo em comparação ao planejador de caminhos de referência. Os testes de qualidade mostram os caminhos gerados pelos dois planejadores em diversas situações diferentes, permitindo que seja feita uma comparação em termos de naturalidade dos caminhos. Por fim, os testes de vantagem estratégica apresentam resultados de combates entre os dois planejadores distintos, com o objetivo de apurar a possível existência de vantagens ou desvantagens entre o uso de cada método.The path planning is part of the main modules of a multi-agent system with dynamic environments, and aims to help ensure a minimum level of autonomy to mobile agents. Multiagent simulations in dynamic environments are widely used in electronic games, and accompanying the growth of commercial games industry, including games for hand-held devices and mobile phones, the technology of multi-agent system gains importance, in order to ensure the various levels of detail required by the public and users of simulations. The objective of this work is the implementation and analysis of a path planner which uses potential fields in a real time strategy (RTS) game, to allow a comparison with another path planner, and checking of quality and other characteristics of the proposed method. During the work, we present the technical information about the path planner used, along with general data about the game used for testing, and integration details concerning the implementation of the new algorithm in the RTS game. We also describe the tests that are involved, which are checks of performance and quality, plus a test of strategic advantage. Performance tests show the scalability of the method, along with general limits of the new path planner algorithm in comparison to the reference path planner. The quality tests show the paths generated by the two planners in several different situations in game, allowing a comparison in terms of the naturalness of the paths. Finally, tests of strategic advantage presented results of battles between the two different path planners, with the aim of investigating the possible existence of advantages or disadvantages on using each method