É inevitável o estudo e a aplicação de IA (Inteligência Artificial) em jogos nos quais possuem inimigos (personagens) não controlados pelo jogador (humano). E o problema mais comum é encontrar uma maneira eficaz de delimitar áreas no cenário aonde o personagem pode se locomover sem aparentar ser um robô seguindo um rastro, ou seja, mais próximo possível da realidade.
Normalmente visualizamos o problema como um grafo e nas arestas distribuimos valores que medem o custo entre um nó e outro. E para saber qual o melhor caminho (de menor custo) utilizamos de algum algoritmo de caminho mínimo. Dentre os algoritmos existentes, os mais famosos são: A* (A Estrela), Algoritmo de Dijkstra, Branch-and-Bound e etc.
Não vou analisar a efeciência do algoritmo utilizado, já que o objetivo é mostrar o problema ao utilizar grafos e uma possível solução (já aplicada em vários jogos).
Esse grafo delimitando a trajetória que pode ser percorrida pelo cenário é denominado waypoint graphs. O termo waypoint ficou bastante conhecido no mod Counter-Strike, no qual para poder adicionar bots aos mapas para jogar “sozinho” era necessário antes percorrer todo o mapa criando marcaçöes (waypoints) que seriam utilizadas pelos bots para se locomoverem. Abaixo segue um vídeo mostrando alguns bugs envolvendo caminhos em jogos famosos:
Evitando o problema
Uma forma de evitar esse problema é utilizando polígonos para delimitar aonde os personagens podem andar. Venha as imagens abaixo:
[caption id=“attachment_171” align=“alignnone” width=“399” caption=“Cenário marcado com waypoints”]
[/caption]
[caption id=“attachment_172” align=“alignnone” width=“399” caption=“Cenário marcado com Navegation Mesh”]
[/caption]
O Navegation Mesh nada mais é que um grafo aonde cada nó é representado por um polígono, e ao invés de buscar por um ponto no cenário que se pode andar, verifica se o ponto do jogador está contido no polígono. Levando em consideração que os mesmos algoritmos utilizados com os waypoints podem ser utilizados para o navegation mesh efetuando pequenas modificações. Obviamente dessa forma será um pouco mais custosa (custo do algoritmo), em contrapartida, pode conseguir economizar uma quantidade enorme de waypoints.
[caption id=“attachment_176” align=“alignnone” width=“538” caption=“Waypoints: Saindo do ponto A para o ponto B”]
[/caption]
[caption id=“attachment_175” align=“alignnone” width=“538” caption=“NavMesh: Saindo do ponto A para o ponto B”]
[/caption]
Também nem sempre essa solução será a melhor para todos os tipos de jogos, é preciso antes de qualquer coisa, analisar com calma quais são as necessidades para não ter que utilizar um canhão para matar uma mosca.
Alguns jogos que utilizam navigation meshes
Algumas parte desse texto e imagens foram retirados do artigo publicado no site ai-blog e nesse mesmo blog há outra solução e um conteúdo muito mais robusto.