Estudo sobre a performance de planejamento de caminhos utilizando Diagramas de Voronoi

Abstract

O planejamento de caminhos é a ação de levar um agente de um ponto a outro em um mundo virtual ou real. As técnicas utilizadas para atingir este objetivo devem, também, evitar colisões com os objetos e outros agentes. Neste estudo serão apresentados os algoritmos já usados e aceitos no mercado de jogos e simulações, assim como um novo baseado em diagramas de Voronoi. Este novo método apresenta como principais vantagens atualização dinâmica para cenários muito grandes e gera caminhos filtrados sem uma fase extra de refinamento. Com o objetivo de gerar resultados úteis para a comparação entre as técnicas apresentas e encontrar pontos em que a nova técnica pode melhorar foram desenvolvidos testes. O foco principal foi criar situações envolvendo cenários nos quais os algoritmos normalmente erram e simulações com um número grande de objetos para testar a performance e escalabilidade.

Path planning is the action of moving an agent from one point to another in a virtual or real world. The techniques used to solve this problem must also avoid collisions with objects and other agents. In this study we will show the algorithms that are most used in the game and simulation industry, as well as a new approach based on Voronoi diagrams. This new method’s greatest features are the dynamic update of large scale scenarios and the path smoothing without the need of an extra phase. With the objective of generating useful data to compare the techniques and finding out which points the new technique can be improved many tests were developed. The main focus was to create situations with scenarios where the algorithms are more likely to fail and simulations with a big number of objects to test the performance and scalability.