Inaugurando a minha participação no blog do Vetta Labs, vou falar um pouco sobre mobilidade de agentes inteligentes.
Meu interesse por essa área se confunde com o surgimento dos primeiros jogos isométricos com pathfinding. Inicialmente, eu podia perder horas tentando tapear um NPC para ver se ele era inteligente de verdade. Claro que, com o tempo, a inteligência artificial nos jogos ficou mais elaborada, e eu passei a correr para me manter vivo mesmo.
Algoritmos de pathfinding consistem, basicamente, em um ou múltiplos agentes com destino definido distribuídos em um ambiente (mapa) determinado. Sendo assim, o agente deve se deslocar pelo ambiente respeitando suas restrições de movimento e obstáculos dinâmicos ou estáticos até atingir seu objetivo. Geralmente o algoritmo faz um cálculo de custo de deslocamento para definir a melhor direção ou trajetória a seguir. Além disso, o ambiente pode ter inúmeras características, o que viabiliza ou não a utilização de algoritmos de pathfinding específicos.
Path Planning
Muitos dizem que nada melhor do que um A* para começar. De fato, trata-se de um dos algoritmos mais utilizados no planejamento de caminhos em jogos e robótica. Diversos frameworks, controladores e game engines possuem esse algoritmo embutido; porém, são bastante enriquecedoras a sua implementação e a de algumas variações (RTA*, IDA*, GAA*, etc).
Em 2008, participei da elaboração de um artigo para o SBGames, fazendo experimentos com algoritmos de busca online e offline para MMOs. O objeto do meu estudo foi o path planning do jogo Ultima Online, o qual considero o melhor MMORPG de todos os tempos.
Como fruto desse experimento, pude entender de forma mais clara o porquê dos problemas de gameplay no pathfinding dos NPCs do jogo: era uma questão de otimização de recursos computacionais. Sendo assim, foi muito interessante estudar como os algoritmos clássicos de inteligência artificial são adaptados para melhorar o desempenho dos servidores, algo bastante exigido nesse gênero de jogo.
Path Follow
Outra estratégia bastante utilizada na mobilidade de agentes é a definição de trajetórias baseadas em checkpoints seqüenciais, gerando um caminho virtual. O agente, por sua vez, possui um atuador que corrige a sua direção e minimiza o desvio…
Continue a ler Mobilidade de agentes