Inteligência Artificial nos Games – Pathfinding

Olá gurizada,

Mesmo que no finalzinho da semana, trago o 3º post do arco sobre Inteligência Artificial para vocês. Como já mencionado no episódio anterior, o assunto hoje será o “famigerado” Pathfinding (busca de caminho). O algoritmo responsável por mover um agente de um ponto a outro, desviando de obstáculos, é famoso por tirar o sono de muitos programadores de games. Para desmestificá-lo, primeiro precisamos entender um pouco sobre a movimentação básica de agentes em games. Vamos lá!

A movimentação de agentes em games é um dos segmento da I.A. mais comuns na produção de games. Os chamados Steering Behaviors (Comportamentos de Direção) consistem em usar regras simples que juntas fornecem uma forma mais realista de movimentação aos agentes. É uma técnica que não preserva estado, economiza memória e reage em tempo real.

Os principais comportamentos desta técnica são destacados abaixo:

  • Comportamentos autônomos
    • Perseguição
    • Fuga
    • Perseguição com Linha de visão
    • Interceptação
  • Comportamentos em Grupo
    • Separação
    • Coesão
    • Alinhamento

Vamos conhecer com mais detalhes alguns deles.

Perseguição e Evasão

Um algoritmo de busca simples que envolve o decremento das distâncias entre as coordenadas do caçador e da presa.

Pra transformar o algoritmo de perseguição em um algoritmo de evasão, basta fazer exatamente o oposto, invertendo as  coordenadas da presa de modo que sua distância aumente em relação à caça.

//Perseguição
se (caçadorX maior caçaX)
caçadorX--;
senão se (caçadorX menor caçaX)
caçadorX++;
se (caçadorY maior presaY)
caçadorY--;
senão se (caçadorY menor presaY)
caçadorY++;
 
//Evasão
 
se (caçadorX menor caçaX)
caçadorX++;
senão se (caçadorX maior caçaX)
caçadorX--;
se (caçadorY menor presaY)
caçadorY--;
senão se (caçadorY maior presaY)
caçadorY++;

Observe na imagem abaixo, que representa uma matriz de pixels, a trilha percorrida.

Perseguição com Linha de Visão

Na perseguição com linha de visão, o predador move-se em direção à presa através de uma linha reta traçada entre os dois pontos. Se a presa estiver parada, o caminho será uma reta simples. Porém, se a presa estiver em movimento, o caminho será formado por curvas – já que, a cada iteração do laço do jogo, o predador traçará uma reta entre a sua posição e a posição da presa.

Um algoritmo interessante na implementação da perseguição com linha de visão é o algoritmo de Bresenham, que é muito utilizado na computação gráfica para o desenho de retas.

// Bresenham
Determina qual eixo é mais longo; x ou y
Divide um eixo menor pelo outro, encontrando a relação
Itera pelo maior a cada unidade acrescenta o quociente


Apesar de serem bastante úteis, os algoritmos de Steering Behaviors normalmente não consideram os elementos do cenário, ou seja, não levam em conta os obstáculos que possam estar no caminho do movimento.  Essa é uma limitação preocupante. Além disso, é possível perceber que estamos trabalhando diretamente com pixels. Em grandes distâncias, ou em cenário complexos, precisamos utilizar um sistema mais flexível e simples de coordendas. Para solucionar este problema, precisamos recorrer a técnica de mapear o cenário através de um grid. Essa abordagem “milenar” é utilizada até hoje em games AAA, sejam eles 2D ou 3D . Observe um exemplo abaixo:

Com a criação do grid, reduzimos significativamente os pontos que iremos trabalhar, e consequentemente, o nosso problema. Neste exemplo ao invés que trabalhar com uma matriz de pontos de 512 x 448 (resolução do Super Nintendo), reduzimos a área para uma algo em torno de 14 x 14.  Desta forma, o caminho a ser percorrido assemelha-se bastante ao demonstrado em pixel nas primeiras imagens deste post.  O próximo passo seria rotular quais espaços estão livres ou bloqueados. Podemos visualizar na segunda imagem do game que alguns quadrados estão ocupados por troncos ou pedras. Essa informação deve ficar armazenada no mapa para o algotirmo de Pathfinding poder utilizar.

PathFinding

Pathfinding, ou busca de caminhos, é um dos “problemas” mais comuns acerca do desenvolvimento de jogos, e está presente na maioria dos gêneros.

Boa parte dos agentes em IA, sejam elas controladas pelo computador ou um NPC, precisam de pathfinding: tanques, pessoas, veículo ou unidade de combate.

O pathfinding não é utilizado apenas para movimentação simples – podemos utilizá-lo também para resolver problemas como:

  • Patrulhamento: consiste na movimentação de uma unidade através de pontos pré-estabelecidos do cenário e em ordem. Isto faz com que as unidades pareçam mais ativas, aumentando as suas chances de encontrar inimigos;
  • Desvio de obstáculos: requer que a unidade tenha conhecimento do que está ao seu redor, de modo que evite colisões com este;
  • Perseguição: fazer com que a unidade vá em direção ao seu alvo;
  • Mirar e atirar: um problema que ocorre quando uma unidade tenta atingir a outra é que obstáculos podem interromper a trajetória. Uma unidade inteligente deverá prever a existência de um obstáculo na rota de colisão do tiro antes de efetuá-lo.

A* (A Star)

Oriundo de outras técnicas mais custosas como o algoritmo de Dijkstra’s, o A* atualmente é a mais popular escolha para pathfinding. Ele é considerado um algoritmo admissível, ou seja, para qualquer grafo ele encontrará um caminho ótimo entre os estados inicial e final.

Para entender mais claramente o funcionamento do algoritmo, vamos fazer um exemplo. Assumindo que temos um NPC que deseja ir do ponto A (verde) ao ponto B(vermelho). Porém, há uma parede separando os dois pontos .

Passo 1

  1. Definir que o nodo atual é o ponto inicial A (verde);
  2. Definir que o nodo final é o ponto B (vermelho);
  3. Criar uma lista chamada de Nodos Abertos;
  4. Ela é o conjunto com os nodos disponíveis para escolha de caminho;
  5. Criar uma lista chamada de Nodos fechados;
  6. Ela será o conjunto dos nodos já desconsiderados.
Passo 2

  1. Adicionar o nodo atual A na lista de abertos;
  2. Identifique todos os nodos “vizinhos” ao nodo atual;
  3. Calcular o custo de locomoção para cada um destes nodos;
  4. Aqui podemos utilizar várias formas de calcular a distância. Vou optar pela fórmula clássica (F = G + H)
  5. G : É o custo de deslocamento do ponto atual para o vizinho. Podemos aqui contar com a diagonal ou apenas o movimento ortogonal;
  6. H : É um valor heurístico que representa a distância do ponto em questão até o destino. O valor é heuristico pois não contempla os obstáculos (Manhattan, Euclidiana, etc)
  7. Adicionar o nodo atual (A) como pai de cada um de seus “vizinhos”;
  8. Acrescente os “vizinhos” a lista de abertos;
Passo 3

  1. Escolher da lista de abertos o nodo de menor custo;
  2. Remover o nodo atual da lista de abertos ;
  3. Adicionar o nodo atual na lista de fechados;
  4. Tornar o melhor nodo escolhido como nodo atual;
  5. O valor do canto esquerdo inferior representa o descolamento, 10 para vizinhos diretamente ligados ao nodo A e 14 para as diagonais.
  6. O valor no canto direito inferior representa a distância deste nodo em relação ao destino (10 para cada casa);
Passo 4

  1. Repetir o processo do passo 2;
  2. Em casos de nodos de mesmo custo, escolher aleatoriamente ;
  3. Em casos de nodos que já estejam na lista de abertos, analisar se o custo de G atual não seria menor que o anterior. (G é acumulativo);
  4. Repetir passo 3; *
Passo 5

  1. O processo se repete até que o nodo alvo seja incluído na listagem; *
  2. Como fazemos para encontrar o caminho?
  3. Basta, através do nodo atual, pegar o seu antecessor e assim recursivamente;
  4. Ao final precisamos apenas inverter o vetor para obter o melhor caminho.

A lógica do Algoritmo não é tão simples de ser entendida a primeira vista, já que utiliza recursividade. Para facilitar o entendimento dos leitores, eu elaborei um exemplo de implementação utilizando a linguagem Action Script 3. Vejam abaixo o código simplificado deste algoritmo.

Obs: Alguns métodos foram abstraídos para facilitar o entendimento.

// Retorna o caminho(trilha) a ser percorrido
function getPath():Vector
{
	//Lista para armazenar os nodos vizinhos
	var nodesAround:Array;
	//Lista para armazenar o caminho a ser percorrido
	var path:Vector = new Vector();
	//Adiciona na lista de abertos a posição inicial
	openList.push(startPoint);
 
	//Laço enquanto o passo atual não for igual ao final
	while(!stepPoint.equals(endPoint))
	{
		//Armazena em uma lista os vizinhos do nodo atual. O método getNodesAround retorna os vizinhos do ponto
		nodesAround = getNodesAround(stepPoint);
		//Para todos os vizinhos encontrados
		for(var i:uint=0;i < nodesAround.length;i++)
		{
			//Verifica se o vizinho é sólido
			if(!isSolidNode(nodesAround[i]))
			{
				//Verifica se o vizinho não está na lista de fechados, ou seja, se já não foi visitado antes.
                                //Se não, o adiciona a esta lista.
				if(!isCloseList(nodesAround[i]))
				{
					//Verifica se foi possível adicionar o vizinho na lista de abertos
					if(addOpenList(nodesAround[i]))
						//Registra o custo G do nodo e também já registra o seu pai (nodo atual)
                                                // O método registreNodeCost calcula o custo de deslocamente e armazena no objeto
						registerNodeCost(nodesAround[i],stepPoint);
					else
						//Recalcula o custo G do nodo
						testGCost(nodesAround[i],stepPoint);
				}
			}
		}
		//Seta que o nodo atual, é o vizinho de melhor custo (dá um passo)
		stepPoint = getBetterNode(openList);
		//Remove o melhor vizinho da lista de abertos
		removeOpenList(stepPoint);
		//Adiciona o melhor vizinho na lista de fechados
		addCloseList(stepPoint);
	}
 
	// Através do nodo final, percorre toda a listagem de trás para frente.
	while(getTileByPosition(stepPoint).nodeParent!= null)
	{
		path.push(stepPoint);
		//Armazena na variável refernte ao nodo atual o nodo pai deste.
		stepPoint = getTileByPosition(stepPoint).nodeParent;
	}
 
	//Retorna o array de nodos invertendo a ordem
	return path.reverse();
}

Para auxiliar ainda mais no entendimento deste importante algoritmo, elaborei um “simulador”, onde é possível definir um ponto de origem, outro de destino e visualizar o caminho ideal a ser percorrido. É possível também, visulizar o funcionamento do algoritmo passo a passo.

O assunto deste post é de nível avançado, sendo sugerido para programadores mais experientes. O que você achou? Não entendeu e gostaria de mais explicações? Podemos seguir com as dicas sobre o algoritimo no fórum. Lá temos um tópico exclusivo para ele. Não deixe de conferir e participar. ;)

Até a próxima.

Autor: Everton Vieira Ver todos os posts de
Sou Bacharel em Análise de Sistemas pela Universidade Católica de Pelotas (UCPel) no ano de 1999. Minha paixão por games é de longa data. Porém, em 2003 tornei essa paixão uma profissão. Durante oito anos atuei como Game Designer e Arquiteto de Software em mais de 30 projetos de Serious Games (simuladores) para grandes empresas do país. Atualmente sou sócio-fundador da Izyplay Game Studio, onde exerço o cargo de Diretor de Criação. Além do envolvimento corporativo, também participei da organização da Pós Graduação em Arquitetura e Desenvolvimento de Jogos Digitais na FATEC SENAC Pelotas. Minha área de interesse e especialização é Game Design e Inteligência Artificial.

13 Comentários em "Inteligência Artificial nos Games – Pathfinding"

  1. Francisco Prado 14/04/2012 at 09:26 - Reply

    Bacana esse artigo. Lembro que queria conhecer como funciona o algoritmo A*, encontrei um em AS3 pronto, mas era difícil de entender.

    Eu cliquei no link “tópico exclusivo” e não apareceu. abs

  2. Leandro Vian 18/04/2012 at 21:47 - Reply

    Muito bom essa série de posts, gostei em especial desse, pois estou mexendo com árvores pra implementar arvores de movimentos possíveis pra um jogo de damas que estou fazendo pra faculdade, e vi justamente isso que foi explicado, simplesmente aplicado de forma ideal pro jogo de damas. :)

    abraços

  3. Thiago 23/05/2012 at 17:49 - Reply

    Olá, bacana o artigo, gostaria de saber como foi calculada a heurística, ou seja, qual foi a lógica para determinar um bloco
    na diagonal?

  4. everton.vieira 23/05/2012 at 22:43 - Reply

    Olá Thiago,

    O cálculo pode ser feito de várias formas. Para simplificar o algoritmo e o seu peso, é sugerido que os blocos tenha 10 unidades de largura. Sendo assim, um deslocamento na diagonal custaria algo em torno de 14 unidades (hipotenusa).

  5. Thiago 03/06/2012 at 10:51 - Reply

    Obrigado pela resposta, mais ficou uma dúvida, na minha implementação o movimento diagonal “corta” pela parede ele não “da a volta”, como no exemplo do passo 5, qual foi a regra para estabelecer isso, ou qual seria os termos que eu deveria pesquisar para entender como resolver esse problema.

    Lembrando que eu estou considerando o movimento diagonal

    Mais uma vez obrigado!

    • everton.vieira 04/06/2012 at 10:57 - Reply

      Olá Thiago,

      A diferença seria que a implementação de exemplo do post não contempla movimentos na diagonal. Para fazer esta alteração, basta modificares o algoritmo que capta os “vizinhos” do ponto. O resto do algoritmo A* não sofre alteração.

  6. Patricia 27/05/2013 at 21:18 - Reply

    Olá,
    Existe algum lugar onde tenha o código do seu exemplo?
    Obrigada e parabéns pelo trabalho

    • Everton Vieira 30/05/2013 at 18:45 - Reply

      Olá Patrícia,

      Você pode ver um exemplo de implementação neste link. ;)

  7. Carlos 08/09/2013 at 19:44 - Reply

    Só não entendi como obter o valor de G, consegui o valor de F e H. Não entendi se G é o valor NodoPai.x – NodoFilho.x ou se usa algum algorítimo.

    • Everton Vieira 11/09/2013 at 13:27 - Reply

      Olá Carlos,

      O valor é G é simplesmente a distância entre os pontos. Quando mais distante o ponto A estiver do B, maior é o valor de G. Basicamente quantos “quadradinhos” eu tenho que caminhar até chegar no destino.

  8. Pablo Lopes 09/09/2013 at 11:13 - Reply

    Bom dia, sou graduando em Bacharelado em Sistemas de Informação, e gostei bastante do post, e queria alguma referência bibliográfica para dar continuidade aos estudos… parabéns pelo post, realmente excelente.

Deixar um Comentário