Otimização de pathfinding em GPU

Abstract

Nos últimos anos, as unidades de processamento gráfico (GPU) têm apresentado um avanço significativo dos recursos computacionais disponíveis para o uso de aplicações não-gráficas. A capacidade de resolução de problemas envolvendo computação paralela, onde o mesmo programa é executado em diversos elementos de dados diferentes ao mesmo tempo, bem como o desenvolvimento de novas arquiteturas que suportem esse novo paradigma, como CUDA (Computed Unified Device Architecture), tem servido de motivação para a utilização da GPU em aplicações de propósito geral, especialmente em jogos. Em contrapartida, a performance das CPUs, mesmo com a presença de múltiplos núcleos (multi-core), tem diminuído, limitando o avanço tecnológico de diversas técnicas desenvolvidas na área de jogos e favorecendo a transição e o desenvolvimento das mesmas para a GPU. Alguns algoritmos de Inteligência Artificial que podem ser decompostos e demonstram certo nível de paralelismo, como o pathfinding, utilizado na navegação de agentes durante o jogo, têm sido desenvolvidos em GPU e demonstrado um desempenho melhor quando comparado à CPU. De modo semelhante, este trabalho tem como proposta a investigação e o desenvolvimento de possíveis otimizações ao algoritmo de pathfinding em GPU, por meio de CUDA, com ênfase em sua utilização na área de jogos, escalando a quantidade de agentes e nós de um mapa, possibilitando um comparativo com seu desempenho apresentado na CPU.