1. Introdução

Este artigo apresentará uma ampla gama de conceitos de inteligência artificial em jogos ("IA de jogos"), para que você entenda quais ferramentas podem ser usadas para resolver problemas de IA, como elas funcionam juntas e como começar a implementá-las no mecanismo selecionado.

Suponho que você esteja familiarizado com videogames, um pouco versado em conceitos matemáticos como geometria, trigonometria etc. A maioria dos exemplos de código será escrita em pseudocódigo, portanto, você não precisa conhecer um idioma específico.

O que é uma "IA de jogos"?

A IA do jogo lida principalmente com a seleção de ações de uma entidade, dependendo das condições atuais. Na literatura tradicional da IA, isso é chamado de gerenciamento de " agentes inteligentes ". O agente geralmente é um personagem do jogo, mas pode ser uma máquina, um robô ou até algo mais abstrato - um grupo inteiro de entidades, um país ou uma civilização. De qualquer forma, é um objeto que monitora seu entorno, toma decisões com base nele e age de acordo com essas decisões. Às vezes, isso é chamado de ciclo percepção-pensamento-ação (Sentir / Pensar / Agir):

Percepção: o agente reconhece - ou é informado sobre ele - informações sobre o ambiente que podem afetar seu comportamento (por exemplo, perigos próximos, itens coletados, pontos importantes etc.)
Pensando: o agente decide como responder (por exemplo, decide se é seguro coletar itens, se deve lutar ou se deve se esconder primeiro)
Ação: o agente executa ações para implementar suas decisões (por exemplo, começa a se mover ao longo da rota para o inimigo ou para o sujeito, e assim por diante)
... então, devido às ações dos personagens, a situação muda, então o ciclo deve ser repetido com novos dados.

As tarefas de IA do mundo real, especialmente aquelas que são relevantes hoje em dia, geralmente se concentram na "percepção". Por exemplo, veículos não tripulados devem receber imagens da estrada à sua frente, combinando-os com outros dados (radar e lidar) e tentando interpretar o que veem. Normalmente, essa tarefa é resolvida pelo aprendizado de máquina, que funciona especialmente bem com grandes matrizes de dados barulhentos do mundo real (por exemplo, com fotos da estrada em frente ao carro ou alguns quadros de vídeo) e dá a eles algum significado, extraindo informações semânticas, por exemplo, “existem 20 metros à minha frente outro carro. Tais tarefas são chamadas de problemas de classificação .

Os jogos são incomuns, pois não precisam de um sistema complexo para extrair essas informações, pois elas são parte integrante da simulação. Não há necessidade de executar algoritmos de reconhecimento de imagem para detectar o inimigo à sua frente; o jogo sabe que existe um inimigo e pode transmitir essas informações diretamente ao processo de tomada de decisão. Portanto, a “percepção” nesse ciclo é geralmente bastante simplificada e toda a complexidade surge na implementação de “pensamento” e “ação”.

Limitações do desenvolvimento da IA do jogo

A IA de jogos geralmente leva em consideração as seguintes restrições:

Ao contrário do algoritmo de aprendizado de máquina, ele geralmente não treina com antecedência; ao desenvolver um jogo, não é prático escrever uma rede neural para monitorar dezenas de milhares de jogadores, a fim de encontrar a melhor maneira de jogar contra eles, porque o jogo ainda não foi lançado e não possui jogadores!
Geralmente, supõe-se que o jogo deve divertir e desafiar o jogador, e não ser “ideal” - portanto, mesmo que você possa treinar agentes para resistir da melhor maneira possível, os designers precisam de algo diferente deles.
Freqüentemente, os agentes precisam ter um comportamento "realista" para que os jogadores sintam que estão competindo com oponentes semelhantes aos humanos. O programa AlphaGo acabou sendo muito melhor que as pessoas, mas os movimentos escolhidos estão tão distantes do entendimento tradicional do jogo que adversários experientes falavam dele como um jogo contra um alienígena. Se o jogo fingir ser um oponente humano, isso geralmente é indesejável; portanto, o algoritmo precisa ser configurado para tomar decisões plausíveis , e não ideais .
A IA deve ser executada em tempo real. Nesse contexto, isso significa que o algoritmo não pode, por decisão, monopolizar os recursos do processador por um longo tempo. Mesmo 10 milissegundos para tomar uma decisão é demais, porque a maioria dos jogos possui de 16 a 33 milissegundos para concluir todas as operações para o próximo quadro do gráfico.
Idealmente, pelo menos parte do sistema deve depender dos dados e não deve ser codificado para que não-programadores possam fazer alterações mais rapidamente.

Tendo aprendido tudo isso, podemos começar a considerar abordagens extremamente simples para a criação de IA, que implementam todo o ciclo de "percepção-pensamento-ação" de maneira a garantir eficiência e permitir que os designers de jogos escolham comportamentos complexos semelhantes às ações humanas.

Tomada de decisão fácil

Vamos começar com um jogo muito simples, como o Pong. A tarefa do jogador é mover a raquete para que a bola salte dela, em vez de passar voando. As regras são semelhantes ao tênis - você perde se perder a bola. A IA tem uma tarefa relativamente simples de tomar decisões sobre a escolha da direção do movimento da raquete.

Construções condicionais codificadas

Se quisermos escrever AI para controlar a raquete, existe uma solução intuitiva e simples - basta mover constantemente a raquete para que fique embaixo da bola. Quando a bola atinge a raquete, ela já está em posição perfeita e pode atingi-la.

Um algoritmo simples para isso, expresso em pseudo-código, pode ser:

  em cada quadro / atualização enquanto o jogo está em execução:

 se a bola estiver à esquerda da raquete:

	 mova a raquete para a esquerda

 caso contrário, se a bola estiver à direita da raquete:

	 mova a raquete para a direita

Se assumirmos que a raquete não pode se mover a uma velocidade menor que a bola, esse será o algoritmo perfeito para o jogador de IA em Pong. Nos casos em que não existem tantos dados de "percepção" para processamento e poucas ações que o agente possa executar, não precisamos de nada mais complicado.

Essa abordagem é tão simples que mal mostra todo o ciclo da "percepção-pensamento-ação". Mas ele é .

As percepções são duas declarações if. O jogo sabe onde estão a bola e a raquete. Portanto, a IA pede ao jogo sua posição, “sentindo” se a bola está à esquerda ou à direita.
O pensamento também é construído em duas declarações if. Eles contêm duas soluções, que neste caso são mutuamente exclusivas, levando à escolha de uma das três ações - mova a raquete para a esquerda, mova para a direita ou não faça nada se a raquete já estiver localizada corretamente.
Uma "ação" é "mover a raquete para a esquerda" ou "mover a raquete para a direita". Dependendo de como o jogo é implementado, isso pode assumir a forma de mover instantaneamente a posição da raquete ou definir a velocidade e a direção da raquete para que ela possa ser alterada corretamente em outro código do jogo.

Tais abordagens são frequentemente chamadas de "reativas" porque existe um conjunto simples de regras (no nosso caso, são declarações "if" no código) que respondem ao estado do mundo e decidem instantaneamente como proceder.

Árvores de decisão

Este exemplo de Pong é realmente semelhante ao conceito formal de IA chamado árvore de decisão . Este é um sistema no qual as decisões são organizadas na forma de uma árvore e o algoritmo deve contorná-lo para alcançar uma "planilha" contendo a decisão final sobre a ação escolhida. Vamos desenhar uma representação gráfica da árvore de decisão para o algoritmo de raquete Pong usando um fluxograma:

Pode-se ver que se assemelha a uma árvore, apenas de cabeça para baixo!

Cada parte da árvore de decisão é geralmente chamada de "nó" porque, na IA, a teoria dos grafos é usada para descrever essas estruturas. Cada nó pode ser um de dois tipos:

Nós de soluções: a escolha de duas alternativas com base na verificação de uma condição. Cada alternativa é apresentada como seu próprio nó;
Nós finais: uma ação executada que representa a decisão final tomada pela árvore.

O algoritmo inicia a partir do primeiro nó designado pela "raiz" da árvore, após o qual decide para qual nó filho acessar com base na condição ou executa a ação armazenada no nó e para de funcionar.

À primeira vista, a vantagem da árvore de decisão não é óbvia, porque ela faz exatamente o mesmo trabalho que as instruções if da seção anterior. Mas existe um sistema muito geral no qual cada solução tem exatamente 1 condição e 2 resultados possíveis, o que permite ao desenvolvedor criar AI a partir dos dados que representam as soluções na árvore e evitar escrevê-las no código. É fácil imaginar um formato de dados simples para descrever uma árvore:

Número do nó	Decisão (ou "fim")	Acção	Acção
1	A bola à esquerda da raquete?	Hein? Verifique o nó 2	Não? Verifique o nó 3
2	O fim	Mover raquete para a esquerda
3	A bola à direita da raquete?	Hein? Vá para o nó 4	Não? Vá para o nó 5
4	O fim	Mova a raquete para a direita
5	O fim	Não faça nada

Do ponto de vista do código, precisamos forçar o sistema a ler cada uma dessas linhas, criar para cada nó, anexar a lógica de decisão com base na segunda coluna e anexar nós filhos com base na terceira e quarta colunas. Ainda precisamos definir manualmente manualmente as condições e ações, mas agora podemos imaginar um jogo mais complexo no qual você pode adicionar novas soluções e ações, além de configurar toda a IA alterando o único arquivo de texto que contém a definição da árvore. Podemos transferir o arquivo para o designer do jogo, que poderá personalizar o comportamento sem a necessidade de recompilar o jogo e alterar o código - desde que o código já tenha condições e ações úteis.

As árvores de decisão podem ser muito poderosas quando são construídas automaticamente com base em um grande número de exemplos (por exemplo, usando o algoritmo ID3 ). Isso os torna uma ferramenta eficaz e de alto desempenho para classificar a situação com base nos dados recebidos, mas este tópico está além do escopo dos designers para criar sistemas simples para selecionar ações para agentes.

Script

Acima, examinamos um sistema de árvore de decisão que usa condições e ações pré-criadas. O desenvolvedor de IA pode reconstruir a árvore da maneira que precisar, mas deve confiar no fato de que o programador já criou todas as condições e ações necessárias para ele. Mas e se dermos ao designer ferramentas mais poderosas que lhe permitem criar suas próprias condições e talvez suas ações?

Por exemplo, em vez de forçar o codificador a escrever as condições "Bola à esquerda da raquete?" e "A bola à direita da raquete?", ele pode simplesmente criar um sistema no qual o designer escreve independentemente as condições para verificar esses valores. Como resultado, os dados da árvore de decisão podem ficar assim:

Número do nó	Decisão (ou "fim")	Solução	Acção
1	ball.position.x <paddle.position.x	Hein? Verifique o nó 2	Não? Verifique o nó 3
2	O fim	Mover raquete para a esquerda
3	ball.position.x> paddle.position.x	Hein? Verifique o nó 4	Não? Verifique o nó 5
4	O fim	Mova a raquete para a direita
5	O fim	Não faça nada

O mesmo de antes, mas agora as soluções têm seu próprio código, semelhante à parte condicional da instrução if. O código lerá os nós de decisão da segunda coluna e, em vez de procurar uma condição específica (por exemplo, “a bola à esquerda da raquete?”), Calcule a expressão condicional e retorne verdadeiro ou falso. Isso pode ser implementado incorporando uma linguagem de script , como Lua ou Angelscript, que permite ao desenvolvedor pegar objetos do jogo (por exemplo, uma bola e uma raquete) e criar variáveis acessíveis a partir do script (por exemplo, ball.position). Geralmente, é mais fácil escrever em uma linguagem de script do que em C ++, e não requer um estágio completo de compilação; portanto, é adequado para fazer alterações rápidas na lógica do jogo e permite que membros da equipe com menos conhecimento técnico criem funções de jogo sem a intervenção de um codificador.

No exemplo acima, a linguagem de script é usada apenas para avaliar a expressão condicional, mas as ações finais também podem ser descritas no script. Por exemplo, essas ações do tipo “mover a raquete para a direita” podem se tornar uma construção de script como ball.position.x += 10 , ou seja, a ação também é definida no script sem escrever o código da função MovePaddleRight.

Se você der outro passo à frente, poderá (e isso geralmente é feito) chegar à sua conclusão lógica e escrever toda a árvore de decisão em uma linguagem de script, e não como uma lista de linhas de dados. Este será um código semelhante às construções condicionais mostradas acima, apenas que não são "codificadas" - elas estão em arquivos de script externos, ou seja, podem ser alteradas sem recompilar o programa inteiro. Muitas vezes, é até possível modificar o arquivo de script durante a execução do jogo, o que permite que os desenvolvedores testem rapidamente várias abordagens para a implementação da IA.

Reação a eventos

Os exemplos mostrados acima destinam-se à execução de quadro único em jogos simples como o Pong. A idéia é que eles realizem continuamente um ciclo de "percepção-pensamento-ação" e continuem a agir com base no último estado do mundo. Mas em jogos mais complexos, em vez de computar, geralmente é mais razoável reagir a "eventos", isto é, a mudanças importantes no ambiente do jogo.

Isso não é particularmente aplicável ao Pong, então vamos escolher outro exemplo. Imagine um jogo de tiro em que os inimigos ficam imóveis até encontrar um jogador, após o que começam a executar ações dependendo da classe - os lutadores corpo a corpo podem correr em direção ao jogador, e os franco-atiradores ficam à distância e tentam mirar. Em essência, este é um sistema reativo simples - “se vemos um jogador, fazemos alguma coisa” - mas pode ser logicamente dividido em um evento (“ver um jogador”) e reação (selecione uma resposta e execute-a).

Isso nos leva de volta ao ciclo percepção-pensamento-ação. Podemos ter um fragmento de código, que é um código de "percepção", que verifica em cada quadro se o inimigo vê o jogador. Caso contrário, nada acontece. Mas se ele vê, isso cria um evento "veja o jogador". O código terá uma parte separada, que diz: "quando o evento" ver o jogador "ocorrer, faremos" xyz "e" xyz "é qualquer resposta que queremos processar pensamento e ação. Para um lutador de personagens, você pode conectar a resposta de corrida e ataque ao evento "ver o jogador". Para o atirador, conectaremos a função de resposta "ocultar e apontar" a esse evento. Como nos exemplos anteriores, podemos criar essas associações no arquivo de dados para que possam ser alteradas rapidamente sem reconstruir o mecanismo. Além disso, é possível (e isso geralmente é usado) escrever essas funções de resposta em uma linguagem de script para que elas possam criar soluções complexas quando ocorrerem eventos.

Melhor tomada de decisão

Embora os sistemas reativos simples sejam muito poderosos, há muitas situações em que não são suficientes. Às vezes, precisamos tomar decisões diferentes com base no que o agente está fazendo no momento e apresentá-lo como uma condição é inconveniente. Às vezes, existem simplesmente muitas condições para apresentá-las efetivamente na forma de uma árvore ou script de decisão. Às vezes, precisamos pensar com antecedência e avaliar como a situação mudará antes de decidir o próximo passo. Para tais tarefas, são necessárias soluções mais complexas.

Máquinas de estado

Uma máquina de estados finitos (FSM) é uma maneira de dizer em outras palavras que algum objeto - digamos, um de nossos agentes de IA - está atualmente em um dos vários estados possíveis e pode ir de um estado para outro. Há um número finito de tais estados, daí o nome. Um exemplo do mundo real é o conjunto de semáforos, passando de vermelho para amarelo, depois para verde e novamente para trás. Em lugares diferentes, existem sequências diferentes de luzes, mas o princípio é o mesmo - cada estado significa algo ("stand", "eat", "stand, se possível" etc.), a qualquer momento existe apenas um estado, e as transições entre eles são baseadas em regras simples.

Isso se aplica bem aos NPCs nos jogos. O guarda pode ter os seguintes estados claramente separados:

Patrulha
Assalto
Vôo

E podemos criar as seguintes regras para a transição entre estados:

Se o guarda vê o inimigo, ele ataca
Se o guarda ataca, mas não vê mais o inimigo, ele volta a patrulhar
Se um guarda ataca mas está gravemente ferido, ele escapa

Esse esquema é bastante simples e podemos anotá-lo com operadores "se" estritamente definidos e uma variável na qual o estado do guarda de segurança e várias verificações serão armazenados - a presença de inimigos próximos, o nível de saúde do guarda de segurança etc. Mas imagine que precisamos adicionar mais alguns estados:

Esperando (entre patrulhas)
Pesquisa (quando o inimigo visto anteriormente se escondeu)
Escapar por ajuda (quando o inimigo é visto, mas ele é forte demais para lutar com ele sozinho)

E as opções disponíveis em cada estado são geralmente limitadas - por exemplo, um guarda provavelmente não vai querer procurar por um inimigo que se perdeu de vista se sua saúde estiver muito baixa.

Cedo ou tarde, a longa lista de "se <x e y, mas não z> então <p>" se torna muito embaraçosa, e uma abordagem formalizada para a implementação de estados e transições entre eles pode ajudar aqui. Para fazer isso, consideramos todos os estados e, em cada estado, listamos todas as transições para outros estados, juntamente com as condições necessárias para eles. Também precisamos indicar o estado inicial para que possamos saber por onde começar antes de aplicar outras condições.

Condição	Condição de transição	Nova condição
Esperando	esperado por 10 segundos	Patrulha
	o inimigo é visível e o inimigo é muito forte	Ajuda Pesquisa
	o inimigo é visível e muita saúde	Assalto
	o inimigo é visível e com pouca saúde	Vôo
Patrulha	rota de patrulha concluída	Esperando
	o inimigo é visível e o inimigo é muito forte	Ajuda Pesquisa
	o inimigo é visível e muita saúde	Assalto
	o inimigo é visível e com pouca saúde	Vôo
Assalto	o inimigo não é visível	Esperando
Assalto	pouca saúde	Vôo
Vôo	o inimigo não é visível	Esperando
Pesquisar	procurou por 10 segundos	Esperando
	o inimigo é visível e o inimigo é muito forte	Ajuda Pesquisa
	o inimigo é visível e muita saúde	Assalto
	o inimigo é visível e com pouca saúde	Vôo
Ajuda Pesquisa	amigo ver	Assalto
Estado inicial: aguardando

Esse esquema é chamado de tabela de transição de estado. É uma maneira complexa (e pouco atraente) de representar uma espaçonave. A partir desses dados, você também pode desenhar um diagrama e obter uma representação gráfica complexa de como pode ser o comportamento dos NPCs.

Ele captura a própria essência de tomar decisões para o agente com base na situação em que ele está. Cada seta indica uma transição entre estados se a condição ao lado da seta for verdadeira.

A cada atualização (ou “ciclo”), verificamos o estado atual do agente, observamos a lista de transições e, se a condição de transição for atendida, passamos para um novo estado. O estado Pendente verifica em cada quadro ou ciclo se o temporizador de 10 segundos expirou. Se expirado, inicia a transição para o estado "Patrulha". Da mesma forma, o estado "Ataque" verifica se o agente tem muita saúde e, nesse caso, faz a transição para o estado "Vôo".

É assim que as transições de estado são tratadas - mas e os comportamentos associados aos próprios estados? Do ponto de vista da execução das próprias ações para um estado, geralmente existem dois tipos de ações anexadas a uma espaçonave:

Ações para o estado atual são realizadas periodicamente, por exemplo, em cada quadro ou "ciclo".
As ações são executadas durante a transição de um estado para outro.

Um exemplo do primeiro tipo: o estado "Patrulha" em cada quadro ou ciclo continua a mover o agente ao longo da rota de patrulha. O estado "Ataque" em cada quadro ou ciclo tenta iniciar um ataque ou movê-lo para uma posição de onde é possível. E assim por diante

Um exemplo do segundo tipo: considere a transição "se o inimigo estiver visível e o inimigo for muito forte → Procure ajuda". O agente deve escolher para onde se deslocar para procurar ajuda e armazenar essas informações para que o estado “Pesquisa de Ajuda” saiba para onde ir. Da mesma forma, no estado "Pesquisa de Ajuda", quando a ajuda é encontrada, o agente retorna ao estado "Ataque" novamente, mas neste momento ele deseja informar o personagem amigável sobre a ameaça, para que possa haver uma ação "informe um amigo sobre o perigo" realizada durante essa transição.

E aqui podemos novamente considerar esse sistema do ponto de vista da "percepção-pensamento-ação". A percepção é incorporada nos dados usados pela lógica de transição. O pensamento está incorporado nas transições disponíveis para cada estado. E a ação é executada por ações realizadas periodicamente em um estado ou durante a transição entre estados.

Esse sistema simples funciona bem, embora algumas vezes as condições de transição da sondagem constante possam ser um processo caro. Por exemplo, se cada agente precisar executar cálculos complexos em cada quadro para determinar a visibilidade dos inimigos e decidir sobre a transição do patrulhamento para o ataque, isso poderá levar muito tempo no processador. Como vimos anteriormente, é possível perceber mudanças importantes no estado do mundo como "eventos" que são processados após a ocorrência. Portanto, em vez de verificar explicitamente a condição de transição "meu agente pode ver o player?" Em cada quadro, podemos criar um sistema de visibilidade separado que executa essas verificações com menos frequência (por exemplo, 5 vezes por segundo) e cria o "player ver ”quando o teste é acionado. Ele é transmitido para a máquina de estado, que agora tem a condição para a transição "Recebeu o evento" jogador vê "" e responde a isso de acordo. O comportamento resultante será semelhante, com exceção de um atraso de reação quase imperceptível (e até crescente), mas a produtividade aumentará devido à transferência de "percepção" para uma parte separada do programa.

Máquinas de estado hierárquico

Tudo isso é bom, mas com grandes máquinas de estado, torna-se muito inconveniente trabalhar. Se quisermos expandir o estado de "Ataque", substituindo-o por estados separados de "Ataque corpo a corpo" e "Ataque de longe", teremos que alterar as transições recebidas de cada estado, presente e futuro, que precisa da capacidade de mudar para o estado "Ataque".

Você provavelmente também percebeu que em nosso exemplo existem muitas transições duplicadas. A maioria das transições no estado "Pendente" é idêntica à do estado "Patrulha", e seria bom evitar a duplicação deste trabalho, especialmente se queremos adicionar estados ainda mais semelhantes. Será lógico combinar “Waiting” e “Patrolling” em algum grupo “Non-combat states”, que possui apenas um conjunto comum de transições para combater estados. Se apresentarmos esse grupo como um estado, podemos considerar o item “Aguardando” e “Patrulhando” como “subestados” desse estado, o que nos permitirá descrever de maneira mais eficaz o sistema inteiro. Um exemplo de uso de uma tabela de conversão separada para um novo subestado que não seja de combate:

As principais condições:

Condição	Condição de transição	Nova condição
Não combate	o inimigo é visível e o inimigo é muito forte	Ajuda Pesquisa
	o inimigo é visível e muita saúde	Assalto
	o inimigo é visível e com pouca saúde	Vôo
Assalto	o inimigo não é visível	Não combate
Assalto	pouca saúde	Vôo
Vôo	o inimigo não é visível	Não combate
Pesquisar	procurou por 10 segundos	Não combate
	o inimigo é visível e o inimigo é muito forte	Ajuda Pesquisa
	o inimigo é visível e muita saúde	Assalto
	o inimigo é visível e com pouca saúde	Vôo
Ajuda Pesquisa	amigo ver	Assalto
Estado inicial: não combate

Status de não combate:

Condição	Condição de transição	Nova condição
Esperando	esperado por 10 segundos	Patrulha
Patrulha	completou a rota de patrulha	Esperando
Estado inicial: aguardando

E em forma de gráfico:

De fato, esse é o mesmo sistema, só que agora existe um estado de não combate que substitui "Patrulha" e "Espera", que por si só é uma máquina de estado com dois subestados de patrulha e espera. Se cada estado puder potencialmente conter uma máquina de estado de subestados (e esses subestados também podem conter sua própria máquina de estado e assim por diante), teremos uma máquina de estado hierárquica (HFSM). Ao agrupar comportamentos que não são de combate, cortamos várias transições desnecessárias e podemos fazer o mesmo para quaisquer novos estados que possam ter transições comuns. Por exemplo, se no futuro expandirmos o estado "Ataque" para os estados "Ataque corpo a corpo" e "Ataque de projétil", eles podem ser subestados, cuja transição se baseia na distância do inimigo e na presença de munição, que têm transições de saída comuns com base nos níveis de saúde e outras coisas Assim, com um mínimo de transições duplicadas, comportamentos e sub-comportamentos complexos podem ser representados.

Árvores de comportamento

Com o HFSM, conseguimos criar conjuntos de comportamentos bastante complexos de uma maneira bastante intuitiva. No entanto, é imediatamente perceptível que a tomada de decisão na forma de regras de transição está intimamente relacionada ao estado atual. Muitos jogos exigem exatamente isso. E o uso cuidadoso da hierarquia de estados reduz o número de transições duplicadas. Mas, às vezes, precisamos de regras que se apliquem independentemente do estado atual ou em quase todos os estados. Por exemplo, se a saúde do agente caiu para 25%, ele pode querer fugir, independentemente de estar em batalha, esperando ou conversando ou em qualquer outro estado. Não queremos lembrar que precisamos adicionar essa condição a cada estado que possamos adicionar ao personagem no futuro. Portanto, quando o designer posteriormente disser que deseja alterar o valor do limite de 25% para 10%, não precisaremos resolver e alterar cada transição correspondente.

Ideal em tal situação, era um sistema no qual as decisões sobre qual estado existisse separadamente dos próprios estados, para que pudéssemos alterar apenas um elemento e as transições ainda fossem processadas corretamente. É aqui que as árvores de comportamento são úteis.

Existem várias maneiras de implementar árvores comportamentais, mas a essência é a mesma para a maioria e muito semelhante à árvore de decisão mencionada acima: o algoritmo começa a funcionar a partir do "nó raiz" e há nós na árvore que indicam decisões ou ações. No entanto, existem diferenças importantes:

Os nós agora retornam um dos três valores: "bem-sucedido" (se o trabalho for concluído), "sem êxito" (se o trabalho não foi concluído) ou "realizado" (se o trabalho ainda estiver sendo concluído e não tiver sido completamente bem-sucedido ou falhar).
Agora, não temos nós de decisão nos quais escolhemos duas alternativas, mas existem nós decoradores com um único nó filho. Se eles forem "bem-sucedidos", eles executam seu único nó filho. Os nós do decorador geralmente contêm condições que determinam se a execução foi concluída com êxito (o que significa que você precisa executar a subárvore) ou falha (então nada precisa ser feito). Eles também podem retornar "em andamento".
Nós de ações em execução retornam um valor "running" para indicar o que está acontecendo.

Um pequeno conjunto de nós pode ser combinado, criando um grande número de comportamentos complexos e, muitas vezes, esse esquema é muito breve. Por exemplo, podemos reescrever a CA hierárquica da guarda do exemplo anterior na forma de uma árvore de comportamento:

Ao usar essa estrutura, não há necessidade de uma transição explícita dos estados "Em espera" ou "Patrulha" para os estados "Ataque" ou outros - se a árvore for atravessada de cima para baixo e da esquerda para a direita, a decisão correta será tomada com base na situação atual. Se o inimigo estiver visível e o personagem tiver pouca saúde, a árvore completará a corrida no nó "Vôo", independentemente do nó completo anterior ("Patrulha", "Espera", "Ataque" etc.).

Você pode perceber que ainda não temos uma transição para retornar ao estado "Aguardando" de "Patrulha" - e aqui os decoradores incondicionais serão úteis. O nó do decorador padrão é "Repetir" - ele não tem condições, apenas intercepta o nó filho que retorna "com êxito" e executa o nó filho novamente, retornando "executado". A nova árvore fica assim:

As árvores comportamentais são bastante complexas porque geralmente existem muitas maneiras diferentes de criar uma árvore, e encontrar a combinação certa de decorador e nós de componentes pode ser uma tarefa assustadora. Também há problemas com a frequência com que precisamos verificar a árvore (queremos atravessá-la a cada quadro ou quando algo acontece que possa afetar as condições?) E como armazenar o estado em relação aos nós (como sabemos que esperamos 10 segundos? descobriremos quantos nós foram executados pela última vez para concluir corretamente a sequência?) Portanto, existem muitas implementações diferentes. Por exemplo, em alguns sistemas, como o sistema de árvore de comportamento do Unreal Engine 4, os nós do decorador são substituídos por decoradores de sequência de caracteres que verificam a árvore somente quando as condições do decorador mudam e fornecem "serviços",que pode ser conectado aos nós e fornecer atualizações periódicas mesmo quando a árvore não é verificada novamente. As árvores comportamentais são ferramentas poderosas, mas aprender a usá-las corretamente, especialmente com tantas implementações diferentes, pode ser uma tarefa assustadora.

Sistemas Baseados em Utilitários

Alguns jogos exigem a existência de muitas ações diferentes; portanto, exigem regras de transição mais simples e centralizadas, mas não precisam do poder de implementar completamente a árvore de comportamento. Em vez de criar um conjunto explícito de opções ou uma árvore de ações em potencial com posições implícitas de fallback definidas pela estrutura da árvore, talvez seja melhor simplesmente examinar todas as ações e escolher a que é mais aplicável no momento.

É isso que os sistemas baseados em utilidade fazem - esses são sistemas nos quais o agente tem muitas ações à sua disposição e ele escolhe executar uma baseada em utilidade relativatoda ação. A utilidade aqui é uma medida arbitrária de importância ou conveniência para um agente executar essa ação. Escrevendo funções de utilitário para calcular a utilidade de uma ação com base no estado atual do agente e seu ambiente, o agente pode verificar os valores do utilitário e selecionar o estado mais apropriado no momento.

Isso também é muito parecido com uma máquina de estados finitos, exceto que as transições são determinadas por uma avaliação de cada estado potencial, incluindo o atual. Vale a pena notar que, no caso geral, escolhemos a transição para a ação mais valiosa (ou estar nela, se já estamos realizando essa ação), mas, para maior variabilidade, pode ser uma escolha aleatória ponderada (priorizando a ação mais valiosa, mas permitindo a escolha de outras pessoas) , uma escolha de ação aleatória entre as cinco principais (ou qualquer outra quantidade) etc.

O sistema padrão baseado em utilidade atribui um certo intervalo arbitrário de valores de utilidade - digamos de 0 (completamente indesejável) a 100 (absolutamente desejável), e cada ação pode ter um conjunto de fatores que influenciam a maneira como o valor é calculado. Voltando ao nosso exemplo com o guarda, podemos imaginar algo assim:

Acção	Cálculo de utilidade
Ajuda Pesquisa	Se o inimigo estiver visível e o inimigo for forte e a saúde estiver baixa, retorne 100, caso contrário, retorne 0
Vôo	Se o inimigo estiver visível e tiver pouca saúde, retorne 90, caso contrário, retorne 0
Assalto	Se o inimigo estiver visível, retorne 80
Esperando	Se estamos em um estado de espera e já esperamos 10 segundos, retorne 0, caso contrário, 50
Patrulha	Se estivermos no final da rota de patrulha, retorne 0, caso contrário, 50

Um dos aspectos mais importantes desse esquema é que as transições entre ações são expressas implicitamente - de qualquer estado que você possa legitimamente ir para outro. Além disso, as prioridades de ação estão implícitas nos valores de utilidade retornados. Se o inimigo estiver visível, e se ele for forte e o personagem tiver pouca saúde, valores diferentes de zero retornarão a Pesquisa de Vôo e Ajuda , mas a Pesquisa de Ajuda sempre tem uma classificação mais alta. Da mesma forma, as ações que não são de combate nunca retornam mais de 50, por isso são sempre derrotadas pelos combates. Com isso em mente, as ações e seus cálculos de utilidade são criados.

No nosso exemplo, as ações retornam um valor constante da utilidade ou um dos dois valores constantes da utilidade. Um sistema mais realista usa um valor de retorno de um intervalo contínuo de valores. Por exemplo, a ação Getaway pode retornar valores mais altos de utilidade se a saúde do agente for menor e a ação Ataque pode retornar valores mais baixos de utilidade se o inimigo for muito forte. Isso permitirá que o Getaway tenha precedência sobre o assalto.em qualquer situação em que o agente sinta que não é saudável o suficiente para combater o inimigo. Isso permite alterar as prioridades relativas das ações com base em qualquer número de critérios, o que pode tornar essa abordagem mais flexível do que uma árvore de comportamento ou nave espacial.

Cada ação geralmente possui várias condições que influenciam o cálculo da utilidade. Para não definir tudo de forma rígida no código, você pode escrevê-los em uma linguagem de script ou como uma série de fórmulas matemáticas, reunidas de maneira compreensível. Muito mais informações sobre isso estão nas palestras e apresentações de Dave Mark ( @IADaveMark ).

Em alguns jogos que tentam simular a vida cotidiana do personagem, por exemplo, no The Sims, é adicionada outra camada de cálculos em que o agente tem "aspirações" ou "motivações" que afetam os valores da utilidade. Por exemplo, se um personagem tem a motivação de Fome, ele pode aumentar com o tempo e o cálculo da utilidade da ação Eat retornará valores cada vez mais altos até que o personagem possa executar essa ação, reduzindo a fome e a ação " Comer ”é reduzido a zero ou quase a zero o valor da utilidade.

A ideia de escolher ações com base no sistema de pontos é bastante direta, portanto, é óbvio que você pode usar a tomada de decisões com base na utilidade em outros processos de tomada de decisão da IA, em vez de substituí-las completamente. A árvore de decisão pode consultar o valor do utilitário de seus dois nós filhos e selecionar o nó com o valor mais alto. Da mesma forma, uma árvore de comportamento pode ter um nó de utilitário composto que conta o utilitário para selecionar o nó filho a ser executado.

Movimento e navegação

Nos exemplos anteriores, havia uma raquete simples, que pedimos para mover para a esquerda-direita, ou um personagem de guarda, que sempre recebia ordens para patrulhar ou atacar. Mas como exatamente controlamos o movimento de um agente por um período de tempo? Como podemos definir a velocidade, evitar obstáculos, planejar uma rota quando é impossível chegar diretamente ao ponto final? Agora vamos considerar esta tarefa.

Direção

No nível mais simples, geralmente é aconselhável trabalhar com cada agente como se ele tivesse um valor de velocidade que determine a velocidade e a direção de seu movimento. Essa velocidade pode ser medida em metros por segundo, em milhas por hora, em pixels por segundo e assim por diante. Se recordarmos nosso ciclo de "percepção-pensamento-ação", podemos imaginar que "pensar" pode escolher velocidade, após o que a "ação" aplica essa velocidade ao agente, movendo-o ao redor do mundo. Geralmente, nos jogos, existe um sistema de física que executa essa tarefa de forma independente, estuda o valor da velocidade de cada entidade e muda sua posição de acordo. Portanto, muitas vezes é possível atribuir esse trabalho a esse sistema, deixando a IA apenas a tarefa de escolher a velocidade do agente.

Se sabemos onde o agente quer estar, precisamos usar nossa velocidade para mover o agente nessa direção. De uma forma trivial, obtemos a seguinte equação:

 desejada_viagem = posição_estado - posição_agente

Imagine um mundo 2D no qual o agente está localizado nas coordenadas (-2, -2), e o ponto alvo está aproximadamente no nordeste, nas coordenadas (30, 20), ou seja, para chegar lá, você precisa se mover (32, 22). Vamos assumir que essas posições são indicadas em metros. Se decidirmos que o agente pode se mover a uma velocidade de 5 m / s, reduza a escala do vetor de deslocamento para esse valor e verifique se precisamos definir a velocidade aproximadamente (4,12, 2,83). Movendo-se com base nesse valor, o agente chegará ao terminal em menos de 8 segundos, conforme o esperado.

Os cálculos podem ser realizados novamente a qualquer momento. Por exemplo, se o agente estiver a meio caminho do alvo, o movimento desejado será a metade, mas após atingir a velocidade máxima do agente de 5 m / s, a velocidade permanecerá a mesma. Isso também funciona para mover alvos (dentro do motivo), o que permite ao agente fazer pequenos ajustes ao longo do caminho.

No entanto, muitas vezes precisamos de mais controle. Por exemplo, podemos precisar aumentar lentamente a velocidade, como se o personagem parasse primeiro, depois passasse para um passo e depois corresse. Por outro lado, podemos precisar desacelerá-lo à medida que ele se aproxima do alvo. Frequentemente, essas tarefas são resolvidas usando os chamados " comportamentos de direção""tendo nomes próprios como Procurar, Fugir, Chegada e assim por diante. (No Habré, há uma série de artigos sobre eles: https://habr.com/post/358366/ .) A ideia deles é que você possa aplicar a velocidade do agente forças de aceleração baseadas em uma comparação da posição do agente e da velocidade atual do movimento em direção ao alvo, criando várias maneiras de se mover em direção ao alvo.

Cada comportamento tem seu próprio objetivo ligeiramente diferente. Buscar e chegar são usados para mover o agente para seu destino. A prevenção e separação de obstáculos ajudam o agente a fazer pequenos movimentos corretivos para contornar pequenos obstáculos entre o agente e seu destino. O alinhamento e a coesão forçam os agentes a se moverem juntos, imitando os animais do rebanho. Quaisquer variações de diferentes comportamentos de direção podem ser combinadas, geralmente na forma de uma soma ponderada, para criar um valor total que leva em consideração todos esses fatores diferentes e cria um único vetor resultante. Por exemplo, um agente pode usar o comportamento de Chegada junto com os comportamentos de Separação e Prevenção de Obstáculos para ficar longe de paredes e outros agentes. Essa abordagem funciona bem em ambientes abertos que não são muito complexos e lotados.

No entanto, em ambientes mais complexos, simplesmente adicionar os valores de saída do comportamento não funciona muito bem - às vezes, o movimento próximo ao objeto é muito lento ou o agente fica preso quando o comportamento de chegada deseja passar pelo obstáculo, e o comportamento de evitar obstáculos empurra o agente para o lado de onde ele veio. . Portanto, às vezes faz sentido considerar variações no comportamento da direção que são mais complicadas do que simplesmente somar todos os valores. Uma das famílias de tais abordagens consiste em uma implementação diferente - não consideramos cada um dos comportamentos que nos dão orientação, seguidos de sua combinação para obter consenso (que por si só pode ser inadequado). Em vez disso, consideramos o movimento em várias direções diferentes - por exemplo, em oito direções da bússola ou em 5-6 pontos na frente do agente,após o que escolhemos o melhor.

No entanto, em ambientes complexos com becos sem saída e opções nas curvas, precisaremos de algo mais avançado e passaremos a isso em breve.

Localização de caminho

Os comportamentos de direção são ótimos para movimentos simples em uma área bastante aberta, como um campo ou arena de futebol, onde você pode ir de A a B em uma linha reta com pequenos ajustes para evitar obstáculos. Mas e se a rota para o ponto final for mais complicada? Então, precisamos de uma “busca de caminhos” - explorando o mundo e traçando um caminho ao longo dele para que o agente atinja o ponto final.

A maneira mais simples é colocar uma grade no mundo e, para cada célula ao lado do agente, olhar para as células vizinhas para as quais podemos nos mover. Se um deles é o nosso ponto final, volte a rota, de cada célula para a anterior, até chegarmos ao início, obtendo uma rota. Caso contrário, repita o processo com os vizinhos acessíveis dos vizinhos anteriores até encontrarmos o ponto final ou ficarmos sem células (isso significa que não há rota). Formalmente, essa abordagem é chamada de algoritmo de busca em largura (BFS), porque a cada etapa ela é exibida em todas as direções (ou seja, “ampla”) antes de sair das pesquisas. O espaço de busca é como uma frente de onda que se move até tropeçar no local que procurávamos.

Este é um exemplo simples de uma pesquisa em ação. A área de pesquisa se expande a cada estágio até que um ponto de extremidade seja incluído, após o qual você pode rastrear o caminho até o início.

Como resultado, obtemos uma lista de células da grade, compondo a rota que você precisa seguir. Geralmente é chamado de "caminho", caminho (daí a "pesquisa de caminhos", busca de caminhos), mas você também pode imaginá-lo como um plano, porque é uma lista de lugares que você precisa visitar para atingir seu objetivo, ou seja, o ponto final.

Agora que sabemos a posição de cada célula no mundo, você pode usar os comportamentos de direção descritos acima para se mover ao longo da rota - primeiro do nó inicial ao nó 2, depois do nó 2 ao nó 3 e assim por diante. A abordagem mais simples é mover-se em direção ao centro da próxima célula, mas também existe uma alternativa popular - mover-se em direção ao meio da costela entre a célula atual e a próxima. Isso permite que o agente faça curvas em curvas fechadas para criar um movimento mais realista.

Como você pode ver, esse algoritmo pode desperdiçar recursos porque examina tantas células na direção "errada" quanto na "certa". Além disso, não permite levar em conta os custos de movimento, nos quais algumas células podem ser "mais caras" do que outras. Aqui chegamos ao auxílio de um algoritmo mais complexo chamado A *. Funciona da mesma maneira que a pesquisa pela primeira vez, mas, em vez de explorar cegamente vizinhos, vizinhos, vizinhos, vizinhos, etc., coloca todos esses nós em uma lista e os classifica para que o próximo nó sob investigação seja sempre o único provavelmente leva à rota mais curta. Os nós são classificados com base em heurísticas (isto é, de fato, uma suposição razoável),que leva em consideração dois aspectos - o custo de uma rota hipotética para a célula (levando em consideração todos os custos necessários para se mover) e uma estimativa de quão longe essa célula está do ponto final (deslocando a pesquisa na direção certa).

Neste exemplo, mostramos que ele examina uma célula de cada vez, sempre escolhendo uma célula vizinha que tenha as melhores perspectivas (ou uma das melhores). O caminho resultante é semelhante ao primeiro caminho de pesquisa, mas menos células são examinadas no processo, e isso é muito importante para o desempenho do jogo em níveis complexos.

Movimento sem malha

Nos exemplos anteriores, uma grade sobreposta ao mundo foi usada, e estabelecemos uma rota ao redor do mundo através das células dessa grade. Mas a maioria dos jogos não se sobrepõe à grade e, portanto, a sobreposição da grade pode levar a padrões de movimento irrealistas. Além disso, essa abordagem pode exigir compromissos em relação ao tamanho de cada célula - se for muito grande, não será possível descrever adequadamente pequenos corredores e curvas, se for muito pequena, e a busca por milhares de células poderá ser muito longa. Quais são as alternativas?

A primeira coisa que precisamos entender é que, do ponto de vista matemático, a grade nos fornece um " gráfico ""de nós conectados. Os algoritmos A * (e BFS) funcionam com gráficos e não se importam com a grade. Portanto, podemos colocar nós em posições arbitrárias do mundo, e se houver uma linha reta entre dois nós conectados, mas houver uma linha entre o início e o fim se houver apenas um nó, nosso algoritmo funcionará como antes e, de fato, é ainda melhor, porque haverá menos nós. Isso costuma ser chamado de sistema de waypoints, pois cada nó indica uma posição importante no mundo que pode criar parte de qualquer número de pu hipotético s.

Exemplo 1: um nó em cada célula da grade. A pesquisa começa com o nó no qual o agente está localizado e termina com a célula final.

Exemplo 2: um número muito menor de nós ou pontos de referência . A pesquisa começa com o agente, passa pelo número necessário de waypoints e passa para o endpoint. Observe que mover para o primeiro ponto do caminho a sudoeste do jogador é uma rota ineficiente; portanto, geralmente é necessário algum pós-processamento do caminho gerado (por exemplo, para observar que o caminho pode ir diretamente para o waypoint no nordeste).

Este é um sistema bastante flexível e poderoso, mas requer uma localização cuidadosa dos pontos de referência, caso contrário, os agentes podem não ver o ponto de referência mais próximo para iniciar a rota. Seria ótimo se, de alguma forma, pudéssemos gerar waypoints automaticamente com base na geometria do mundo.

E então navmesh vem em socorro. Isso é abreviação de malha de navegação. Em essência, essa é (geralmente) uma malha bidimensional de triângulos, que se sobrepõe aproximadamente à geometria do mundo nos locais onde o jogo permite que o agente se mova. Cada um dos triângulos na malha se torna um nó do gráfico e possui até três triângulos adjacentes que se tornam nós adjacentes do gráfico.

Abaixo está um exemplo do mecanismo do Unity. O mecanismo analisou a geometria do mundo e criou a malha de navegação (azul), que é uma aproximação da geometria. Cada polígono de nammesh é uma área na qual um agente pode ficar e um agente pode passar de um polígono para qualquer outro adjacente. (Neste exemplo, os polígonos são mais estreitos que o piso em que se encontram, para levar em consideração o raio do agente, que se estende além da posição nominal do agente.)

Podemos procurar uma rota através de uma malha usando A * novamente, e isso nos dará uma rota ideal ao redor do mundo que leva em conta toda a geometria e não requer um número excessivo de nós extras (como seria com a grade) e participação humana na geração de pontos o caminho.

Encontrar caminhos é um tópico extenso, para o qual existem muitas abordagens, especialmente se você precisar programar detalhes de baixo nível. Uma das melhores fontes de informações adicionais é o site de Amit Patel (tradução do artigo em Habré: https://habr.com/post/331192/ ).

Planejamento

Usando a pesquisa de caminhos como exemplo, vimos que, às vezes, não basta escolher uma direção e começar a se mover nela - precisamos escolher uma rota e fazer vários movimentos antes de chegar ao ponto final desejado. Podemos generalizar essa idéia para uma ampla gama de conceitos em que o objetivo não é apenas o próximo passo. Para alcançá-lo, é necessário executar uma série de etapas e, para saber qual deve ser o primeiro passo, talvez você precise dar alguns passos adiante. Essa abordagem é chamada de planejamento . Encontrar caminhos pode ser considerado uma das aplicações específicas do planejamento, mas esse conceito tem muito mais aplicações. Retornando ao ciclo de “percepção-pensamento-ação”, esse planejamento é uma fase do pensamento que tenta planejar várias fases de ação para o futuro.

Vejamos o jogo Magic: The Gathering. Você tem seu primeiro movimento, há várias cartas em suas mãos, incluindo "Pântano", que fornece 1 ponto de mana preto, e "Floresta", que fornece 1 ponto de mana verde, "Exorcista", que requer 1 ponto de mana azul para chamar e " Elven Mystic ”, para chamar o que você precisa de 1 ponto de mana verde. (Por simplicidade, omitimos as três cartas restantes.) As regras dizem que um jogador pode jogar uma carta de terreno por turno, pode "tocar" em suas cartas de terra para obter mana com elas e pode lançar tantas magias (incluindo convocar criaturas) quanta mana ele tem. Nesta situação, é provável que o jogador jogue "Forest", toque nele para obter 1 ponto de mana verde e depois chame "Elven Mystic". Mas como uma IA de jogos sabe que essa decisão precisa ser tomada?

"Agendador" simples

Uma abordagem ingênua pode ser simplesmente iterar cada ação em ordem, até que existam. Olhando para a mão, a AI vê que pode jogar "Swamp" e, portanto, o faz. Restam mais ações após este turno? Ele não pode convocar Elven Mystic ou Exile Wizard, porque isso requer mana verde ou azul, e o pântano jogado fornece apenas mana negra. E não podemos tocar "Forest" porque já tocamos "Swamp". Ou seja, o jogador de IA fará a jogada de acordo com as regras, mas não será muito ideal. Felizmente, existe uma solução melhor.

Quase da mesma maneira que a busca de caminhos encontra uma lista de posições para se deslocar pelo mundo para chegar ao ponto certo, nosso planejador pode encontrar uma lista de ações que colocam o jogo no estado certo. Assim como cada posição no caminho possui um conjunto de vizinhos, que são possíveis opções para escolher o próximo passo, cada ação no plano tem vizinhos, ou "herdeiros", candidatos à próxima etapa do plano. Podemos procurar essas ações e as seguintes ações até atingir o estado desejado.

Suponha, por exemplo, que o resultado desejado seja "convocar uma criatura, se possível". No início da jogada, temos apenas duas ações em potencial permitidas pelas regras do jogo:

 1. Jogue “Swamp” (resultado: “Swamp” sai da mão e entra no jogo)
2. Jogue "Floresta" (resultado: "Floresta" sai da mão e entra no jogo)

Cada ação tomada pode abrir outras ações ou fechá-las, também de acordo com as regras do jogo. Imagine que escolhemos jogar “Swamp” - isso fecha a oportunidade de jogar esta carta como uma ação potencial de herança (porque “Swamp” já foi jogado), fecha a oportunidade de jogar “Forest” (porque as regras do jogo permitem que você jogue apenas uma carta de terra por turno) e adiciona a capacidade de tocar no “pântano” para obter 1 ponto de mana negra - e essa é, de fato, a única ação herdada. Se dermos mais um passo e selecionar "touch" Swamp "", obteremos 1 ponto de mana negra com o qual não podemos fazer nada, então isso não faz sentido.

 1. Jogue “Swamp” (resultado: “Swamp” sai da mão e entra no jogo)
            1.1 Toque em "Pântano" (resultado: tocamos em "Pântano", +1 mana preta está disponível)
                        Nenhuma ação restante - END
2. Jogue "Floresta" (resultado: "Floresta" sai da mão e entra no jogo)

Essa pequena lista de ações não nos deu muito e levou a um "beco sem saída", se usarmos a analogia com a busca de caminhos. Portanto, repetimos o processo para a próxima etapa. Nós escolhemos jogar Forest. Isso também remove a capacidade de "tocar floresta" e "tocar pântano" e abre como um potencial (e único) próximo passo "tocar a floresta". Isso nos dá 1 ponto de mana verde, que por sua vez abre o terceiro passo - "chame" Elven Mystic "."

 1. Jogue “Swamp” (resultado: “Swamp” sai da mão e entra no jogo)
            1.1 Toque em "Pântano" (resultado: tocamos em "Pântano", +1 mana preta está disponível)
                        Nenhuma ação restante - END
2. Jogue "Floresta" (resultado: "Floresta" sai da mão e entra no jogo)
            2.1 Toque em "Floresta" (resultado: tocamos em "Pântano", +1 mana verde está disponível)
                        2.1.1 Chame "Elven Mystic" (resultado: "Elven Mystic" no jogo, -1 mana verde está disponível)
                                    Nenhuma ação restante - END

Agora, investigamos todas as ações e ações possíveis resultantes dessas ações, encontrando um plano que nos permite convocar a criatura: “toque a floresta”, “toque a floresta”, “chame o“ elfo místico ””.

Obviamente, este é um exemplo muito simplificado, e geralmente você precisa escolher o melhorum plano, e não apenas um plano que atenda a alguns critérios (por exemplo, "convocar uma criatura"). Geralmente, você pode avaliar os planos em potencial com base no resultado final ou nos benefícios cumulativos de usar o plano. Por exemplo, você pode dar 1 ponto a um mapa de terreno e 3 pontos por chamar uma criatura. “Jogar“ Pântano ”” será um plano curto, com 1 ponto, e o plano de “jogar Floresta” → tocar em “Floresta” → chamar “Elven Místico” ”dá 4 pontos, 1 para o chão e 3 para a criatura. Este será o plano mais lucrativo disponível, portanto, você deve escolher se nomearmos esses pontos.

Acima, mostramos como o planejamento funciona em um movimento de Magic: The Gathering, mas também pode ser aplicado a ações em uma série de movimentos (por exemplo, "mova um peão para dar espaço ao desenvolvimento do bispo" no xadrez ou "se esconda em uma unidade" ele poderia atirar no próximo turno, estar seguro "no XCOM) ou com a estratégia geral de todo o jogo (por exemplo," construir postes em todos os outros edifícios protoss "no Starcraft ou" beber uma poção Fortify Health antes de atacar o inimigo "no Skyrim).

Planejamento aprimorado

Às vezes, existem muitas ações possíveis a cada etapa, e avaliar cada opção não é razoável. Vamos voltar ao exemplo de Magic: The Gathering - imagine que temos várias criaturas na mão, muitos terrenos já foram jogados, para que possamos chamar qualquer criatura, várias criaturas com suas habilidades jogadas e há mais algumas cartas de terrenos na mão - o número de permutações terra, uso da terra, convocação de criaturas e o uso das habilidades das criaturas podem ser iguais a milhares ou mesmo dezenas de milhares. Felizmente, existem algumas maneiras de resolver esse problema.

O primeiro é chamado de encadeamento reverso"(" Ida e volta "). Em vez de verificar todas as ações e seus resultados, podemos começar com cada um dos resultados finais desejados e ver se podemos encontrar um caminho direto para eles. Você pode comparar isso com a tentativa de alcançar uma folha específica em uma árvore - é muito mais lógico comece a partir desta folha e volte, estabelecendo uma rota ao longo do tronco (e nessa rota podemos seguir na ordem oposta), do que começar a partir do tronco e tentar adivinhar qual ramo escolher em cada etapa. Se você começar do final e seguir na direção oposta, então criou e plano será muito mais rápido e mais fácil.

Por exemplo, se o inimigo tiver 1 ponto de vida restante, pode ser útil tentar encontrar um plano para "infligir 1 ou mais pontos de dano direto ao inimigo". Nosso sistema sabe que, para alcançar esse objetivo, ele precisa lançar um feitiço de dano direto, o que, por sua vez, significa que ele deve estar em nossas mãos e precisamos de mana suficiente para pronunciá-lo. Por sua vez, isso significa que precisamos tocar em terreno suficiente para receber essa mana, o que pode exigir que você jogue um mapa de terreno adicional.

Outra maneira é pesquisar pela primeira melhor correspondência. Em vez de contornar todas as permutações por um longo tempo, medimos o quão “bom” é cada plano parcial (semelhante à maneira como escolhemos as opções de plano acima) e calculamos o mais bonito de todas as vezes. Geralmente, isso permite que você crie um plano ideal, ou pelo menos razoavelmente bom, sem a necessidade de considerar cada permutação possível de planos. A * é uma variação da busca pela primeira melhor correspondência - ela explora primeiro as rotas mais promissoras, para que ele possa encontrar o caminho para a meta sem precisar subir demais em outras direções.

Uma opção de pesquisa interessante e cada vez mais popular para a primeira melhor correspondência é a pesquisa em árvore Monte Carlo .. Em vez de adivinhar quais planos são melhores que outros ao escolher cada ação subseqüente, esse método escolhe ações subseqüentes aleatórias em cada etapa até chegar ao fim em que nenhuma ação é mais possível - provavelmente porque o plano hipotético levou a um estado de vitória ou perda - e usa esse resultado para dar mais ou menos peso às opções selecionadas anteriores. Se o processo for repetido várias vezes, o método poderá criar uma boa avaliação do melhor próximo passo, mesmo que a situação mude (por exemplo, se o inimigo tentar frustrar nossos planos).

Finalmente, nenhuma discussão sobre planejamento em jogos seria completa sem mencionar o planejamento de ações com base em objetivos(Planejamento de ações orientadas a objetivos, GOAP). Essa é uma técnica amplamente usada e amplamente discutida, mas se você ignorar alguns detalhes específicos da implementação, é essencialmente um planejador de ida e volta que começa com uma meta e tenta pegar uma ação que leva a essa meta ou, mais provavelmente, uma lista de ações que leva a para o objetivo. Por exemplo, se o objetivo era "matar o jogador" e o jogador estivesse coberto, o plano poderia ser: "Fume o jogador com uma granada" → "Puxe uma arma" → "Ataque".

Geralmente, existem vários objetivos, e cada um tem sua própria prioridade. Se os objetivos com a maior prioridade não puderem ser alcançados, por exemplo, nenhum conjunto de ações poderá formar o plano "Matar o jogador" porque o jogador não está visível, então o sistema retornará aos objetivos com prioridades mais baixas, por exemplo, "Patrulha" ou "Guarda no local".

Treinamento e adaptação

No início do artigo, mencionamos que a IA de jogos geralmente não usa “aprendizado de máquina” porque geralmente não é adequada para o controle em tempo real de agentes inteligentes no mundo dos jogos. No entanto, isso não significa que não possamos tomar emprestado algo dessa área onde faz sentido. Podemos precisar de um oponente de computador no atirador para descobrir os melhores lugares para se mover e obter o máximo de abates. Ou podemos querer o oponente em um jogo de luta. por exemplo, em Tekken ou Street Fighter, ele aprendeu a reconhecer um jogador usando os mesmos combos para começar a bloqueá-los, forçando-o a usar táticas diferentes. Ou seja, há momentos em que uma certa porcentagem de aprendizado de máquina é útil.

Estatística e Probabilidades

Antes de passarmos a exemplos mais complexos, vale a pena descobrir até onde podemos chegar, simplesmente medindo e usando esses dados para tomar decisões. Por exemplo, digamos que temos um jogo no gênero de estratégia em tempo real, e precisamos entender se o jogador começará a se apressar nos primeiros minutos para decidir se constrói mais defesa. Podemos extrapolar o comportamento anterior do jogador para entender qual pode ser o comportamento futuro. Inicialmente, não temos dados que possam ser extrapolados, mas cada vez que a IA joga contra um inimigo vivo, ela pode registrar a hora do primeiro ataque. Após algumas partidas, esse tempo pode ser medido e obteremos uma aproximação suficientemente boa do tempo de ataque do jogador no futuro.

O problema da média simples é que ela geralmente converge ao longo do tempo no centro. Portanto, se um jogador usou a estratégia de corrida nas primeiras 20 vezes e as próximas 20 vezes passaram para uma estratégia muito mais lenta, o valor médio estará em algum lugar no meio, o que não nos dará nenhuma informação útil. Uma maneira de melhorar os dados é usar uma janela de média simples que leve em consideração apenas os últimos 20 pontos de dados.

Uma abordagem semelhante pode ser usada para avaliar a probabilidade de certas ações, assumindo que as preferências anteriores do jogador continuem no futuro. Por exemplo, se um jogador atacou cinco vezes com uma bola de fogo, duas vezes com raios e mão a mão apenas uma vez, então provavelmente ele preferiria uma bola de fogo 5 em 8 vezes. Extrapolando esses dados, podemos ver que a probabilidade de usar uma arma é: Bola de fogo = 62,5%, Raio = 25% Corpo a corpo = 12,5%. Nossos personagens de IA perceberão que é melhor encontrar armaduras à prova de fogo!

Outro método interessante é usar o Classificador Naive Bayes para estudar grandes volumes de dados de entrada, a fim de classificar a situação atual para que o agente de IA possa responder adequadamente. Os classificadores bayesianos são provavelmente mais conhecidos por serem usados em filtros de email de spam, onde avaliam as palavras no email, comparam-nas com aquelas que foram encontradas com mais frequência em spam e em mensagens normais no passado. Com base nesses cálculos, eles decidem sobre a probabilidade de a última mensagem recebida ser spam. Podemos fazer algo semelhante, apenas com menos entrada. Ao registrar todas as informações úteis observáveis (por exemplo, unidades inimigas criadas,feitiços usados ou tecnologias de pesquisa) e rastreando a situação resultante (guerra / paz, estratégia de ataque / estratégia de defesa, etc.), podemos selecionar o comportamento apropriado com base nisso.

O uso de todas essas técnicas de ensino pode ser suficiente e frequentemente e preferencialmente aplicado aos dados coletados durante o teste de reprodução antes do lançamento do jogo. Isso permite que a IA se adapte às várias estratégias usadas pelos testadores e não mude após o lançamento do jogo. Uma IA que se adapta a um jogador após o lançamento de um jogo pode se tornar previsível ou complexa demais para ser derrotada.

Fácil adaptação baseada em peso

Vamos dar um passo adiante. Em vez de apenas usar os dados de entrada para escolher entre estratégias predefinidas discretas, você pode alterar o conjunto de valores que influenciam a tomada de decisão. Se entendermos bem o mundo do jogo e as regras do jogo, podemos fazer o seguinte:

( );
«» ;
.

Imagine um agente de informática que pode selecionar salas em um mapa em um jogo de tiro em primeira pessoa. Cada quarto tem um peso que determina a conveniência de visitar este quarto. Inicialmente, todos os quartos têm o mesmo significado. Ao escolher um quarto, a IA o seleciona aleatoriamente, mas com a influência desses pesos. Agora imagine que, quando um agente de computador é morto, ele se lembra em qual sala isso está acontecendo e reduz seu peso, de modo que é menos provável que volte a ele no futuro. Da mesma forma, imagine que um agente de computação cometeu um assassinato. Depois, ele pode aumentar o peso da sala em que está, a fim de levantá-la na lista de preferências. Portanto, se uma sala se torna especialmente perigosa para o jogador de IA, ele começa a evitá-la no futuro, e se alguma outra sala permitir que a IA tenha muitos assassinatos,então ele voltará para lá.

Modelos de Markov

E se quiséssemos usar os dados que coletamos para fazer previsões? Por exemplo, se gravarmos todas as salas em que vemos um jogador por um determinado período de tempo, podemos prever razoavelmente em qual sala ele pode passar. Ao rastrear a sala atual em que o jogador está e a anterior e registrar esses pares de valores, podemos calcular com que frequência cada uma das situações anteriores leva à próxima situação e usar esse conhecimento para obter previsões.

Imagine que existem três salas - vermelha, verde e azul, e que durante a sessão do jogo recebemos essas observações:

A primeira sala em que o jogador é visto	Total de observações	Próximo quarto	Quantas vezes visto	Percentagem
Vermelho	10	Vermelho	2	20%
		Verde	7	70%
		Azul	1	10%
Verde	10	Vermelho	3	30%
		Verde	5	50%
		Azul	2	20%
Azul	8	Vermelho	6	75%
		Verde	2	25%
		Azul	0 0	0%

O número de detecções em cada um dos quartos é razoavelmente uniforme, portanto, isso não nos dá uma idéia de qual dos quartos pode ser um bom lugar para uma emboscada. Os dados podem ser distorcidos pelo fato de os jogadores aparecerem uniformemente no mapa, com igual probabilidade de aparecer em qualquer uma dessas três salas. Mas os dados sobre a visita à próxima sala podem ser úteis e nos ajudar a prever o movimento do jogador no mapa.

Podemos notar imediatamente que a sala verde é muito atraente para os jogadores - a maioria dos jogadores da sala vermelha ficou verde e 50% dos jogadores vistos na sala verde permanecem lá durante a próxima checagem. Também podemos notar que a sala azul é um lugar pouco atraente. As pessoas raramente mudam de salas vermelhas ou verdes para azuis e parece que ninguém gosta de ficar nela por um longo tempo.

Mas os dados nos dizem algo mais específico - eles dizem que quando um jogador está na sala azul, depois dela é mais provável que escolha vermelho, em vez de verde. Apesar do fato de a sala verde ser um lugar muito mais popular do que a vermelha, a tendência é ligeiramente oposta se o jogador estiver na sala azul. Parece que o próximo estado (ou seja, a sala em que ele decide se mudar) depende do estado anterior (ou seja, a sala em que ele está agora), então esses dados nos permitem criar melhores previsões sobre o comportamento dos jogadores do que com contagem de observação independente.

Essa ideia de que podemos usar o conhecimento do estado anterior para prever o estado futuro é chamada de modelo de Markov, e exemplos semelhantes nos quais medimos com precisão os eventos (por exemplo, "em que sala o jogador está") são chamados de cadeias de Markov. Como eles representam a probabilidade de uma transição entre estados sucessivos, eles são frequentemente representados graficamente na forma de uma máquina de estados finitos, próximo a cada transição cuja probabilidade é indicada. Anteriormente, usamos uma máquina de estado para representar o estado de comportamento no qual o agente está localizado, mas esse conceito pode ser estendido a todos os tipos de estados, estejam eles associados ao agente ou não. No nosso caso, os estados indicam os quartos ocupados pelo agente. Ficará assim:

Essa é uma abordagem simples para indicar a probabilidade relativa de transição para diferentes estados, o que dá à IA a capacidade de prever o próximo estado. Mas podemos ir mais longe criando um sistema que olha para o futuro em duas ou mais etapas.

Se um jogador for visto na sala verde, usaremos dados que nos dizem que há 50% de chance de ele ainda estar na sala verde na próxima observação. Mas qual é a probabilidade de ele permanecer nele pela terceira vez? Essa não é apenas a probabilidade de ele permanecer na sala verde por duas observações (50% * 50% = 25%), mas também a probabilidade de que ele saia e retorne. Aqui está uma nova tabela com valores anteriores aplicados a três observações: uma atual e duas hipotéticas no futuro.

Observação 1	Observação hipotética 2		3
		30%		20%	6%
				70%	21%
				10%	3%
		50%		30%	15%
				50%	25%
				20%	10%
		20%		75%	15%
				25%	5%
				0%	0%
				:	100%

Aqui vemos que a probabilidade de ver um jogador na sala verde após 2 observações é de 51% - 21% do que ele virá da sala vermelha, 5% do que vemos o jogador visitando a sala azul e 25% do que ele é o tempo todo vai ficar na sala verde.

Uma tabela é apenas uma dica visual; um procedimento requer apenas uma multiplicação de probabilidades em cada estágio. Isso significa que podemos olhar para o futuro, mas com uma ressalva significativa: assumimos que a probabilidade de entrar em uma sala depende inteiramente da sala em que estamos no momento. Essa ideia de que o estado futuro depende apenas da corrente é chamada de propriedade Markov. Embora nos permita usar ferramentas poderosas como cadeias de Markov, geralmente é apenas uma aproximação. Os jogadores podem decidir visitar salas com base em outros fatores, como nível de saúde e quantidade de munição, e como não registramos essas informações como parte da condição, nossas previsões serão menos precisas.

N gramas

Vamos voltar ao nosso exemplo com reconhecimento de combinação em um jogo de luta. Essa é uma situação semelhante na qual queremos prever o estado futuro com base no passado (para decidir como bloquear ou evitar um ataque), mas em vez de estudar um único estado ou evento, consideraremos sequências de eventos que criam um movimento combinado.

Uma maneira de fazer isso é salvar a entrada de cada jogador (por exemplo, chute , mão ou bloco ) no buffer e gravar o buffer inteiro como um evento. Imagine que um jogador pressiona constantemente um chute , um chute , um chute para usar o ataque " Câncer da Morte " ", e o sistema de AI salva todas as entradas do jogador no buffer e lembra as últimas 3 entradas usadas em cada etapa.

Entrar	Uma sequência de entrada existente	Nova memória de entrada
Kick	Kick	não
Golpe de mão	Kick, Kick	não
Kick	Kick, Kick, Kick	Kick, Kick, Kick
Kick	Kick, Kick, Kick, Kick	Kick, Kick, Kick
Golpe de mão	Pontapé, pontapé, pontapé, pontapé, pontapé	Kick, Kick, Kick
Bloquear	Bloco, Pontapé, Pontapé, Pontapé, Pontapé, Bloco	Bloco, Pontapé, Pontapé
Kick	Pontapé, pontapé, pontapé, pontapé, pontapé, bloco, pontapé	Chute, bloqueie, chute
Kick	Pontapé, pontapé, pontapé, pontapé, pontapé, bloco, pontapé, pontapé	Bloquear, chutar, chutar
Golpe de mão	, , , , , , , ,	, ,

(Nas linhas em negrito, o jogador executa o ataque "Superbuck of Death".)

Você pode observar todos os momentos em que o jogador escolheu um chute no passado , seguido de outro chute , e perceber que a próxima entrada é sempre um chute . Isso permite que o agente de IA faça uma previsão de que, se um jogador acabou de escolher um chute, seguido de um chute, ele provavelmente selecionará um chute a seguir , lançando o Death Superkulak . Isso permite que a IA decida escolher uma ação que neutralize esse golpe, como bloqueio ou evasão.

Tais seqüências de eventos são chamadas N-gramas.onde N é o número de itens armazenados. No exemplo anterior, eram 3 gramas, também chamado de trigrama, ou seja, os 2 primeiros elementos são usados para prever o terceiro. Nos 5 gramas, o quinto é previsto para os 4 primeiros elementos, e assim por diante.

Os desenvolvedores devem escolher cuidadosamente o tamanho de N-gramas (às vezes chamado de pedido). Quanto menor o número, menos memória é necessária, porque quanto menor o número de permutações permitidas, mas menos histórico é salvo, o que significa que o contexto é perdido. Por exemplo, um grama de 2 gramas (também chamado de “bigram”) conterá registros de chutes , chutes e gravações de chutes , chutes , mas não poderá salvar um chute .chute , chute de mão , portanto, não pode acompanhar este combo.

Por outro lado, quanto maior a ordem, mais memória é necessária e o sistema provavelmente será mais difícil de treinar, porque teremos muito mais permutações possíveis, o que significa que nunca podemos encontrar o mesmo duas vezes. Por exemplo, se houver três entradas possíveis ( chute , mão e bloco ) e usarmos 10 gramas, haverá quase 60 mil permutações diferentes.

O modelo do bigram é essencialmente uma cadeia trivial de Markov - cada par "estado futuro / estado atual" é um bigram e podemos prever o segundo estado com base no primeiro. Trigramas e N-gramas grandes também podem ser considerados cadeias de Markov, onde todos os elementos do N-grama, exceto o último, formam o primeiro estado, e o último elemento é o segundo estado. No nosso exemplo de jogo de luta, é apresentada a probabilidade de transição do estado de chute e chute para o estado de chute e, em seguida, chute.. Percebendo vários elementos do histórico de entrada como um único elemento, transformamos essencialmente a sequência de entrada em um fragmento do estado, o que nos dá uma propriedade Markov, permitindo usar cadeias de Markov para prever a próxima entrada, ou seja, adivinhando qual movimento de combinação seguirá.

Representação do conhecimento

Discutimos várias maneiras de tomar decisões, criar planos e previsões, e todas elas são baseadas nas observações do agente sobre o estado do mundo. Mas como podemos observar efetivamente todo o mundo do jogo? Acima, vimos que a maneira de representar a geometria do mundo afeta muito o movimento ao longo dele, por isso é fácil imaginar que isso é verdade para outros aspectos da IA do jogo. Como podemos coletar e organizar todas as informações necessárias da maneira ideal (para que muitas vezes sejam atualizadas e acessíveis a muitos agentes) e práticas (para que as informações possam ser facilmente usadas no processo de tomada de decisão)? Como transformar dados simples em informação ou conhecimento ? Para jogos diferentes, as soluções podem ser diferentes, mas existem várias abordagens mais populares.

Tags / Tags

Às vezes, já temos uma quantidade enorme de dados úteis, e a única coisa que precisamos é de uma boa maneira de categorizá-los e procurá-los. Por exemplo, no mundo do jogo, pode haver muitos objetos, e alguns deles são um bom abrigo contra balas inimigas. Ou, por exemplo, temos várias caixas de diálogo de áudio gravadas que são aplicáveis em situações específicas e precisamos de uma maneira de descobri-las rapidamente. O passo óbvio é adicionar um pequeno pedaço de informação adicional que você pode usar para pesquisar. Esses fragmentos são chamados de tags ou tags.

Vamos voltar ao exemplo do abrigo; no mundo do jogo, pode haver um monte de objetos - caixas, barris, cachos de grama, cercas de arame. Alguns deles são adequados para abrigos, por exemplo, caixas e barris, outros não. Portanto, quando nosso agente executa a ação "Mover para abrigo", ele deve procurar objetos próximos e identificar candidatos adequados. Ele não pode simplesmente procurar pelo nome - talvez o jogo tenha Crate_01, Crate_02, até Crate_27, e não queremos procurar todos esses nomes no código. Não queremos adicionar outro nome ao código sempre que o artista criar uma nova variação da caixa ou barril. Em vez disso, você pode procurar qualquer nome que contenha a palavra "Caixa", mas um dia um artista pode adicionar "Broken_Crate" com um buraco enorme, inadequado como abrigo.

Portanto, em vez disso, criaremos uma tag "COVER" e solicitaremos que artistas e designers anexem essa tag a todos os objetos que podem ser usados como abrigo. Se eles adicionarem uma marca a todos os barris e caixas (inteiras), o procedimento de AI precisará apenas encontrar objetos com essa marca e ele saberá que os objetos são adequados para essa finalidade. A tag funcionará mesmo que os objetos sejam renomeados posteriormente e poderá ser adicionada a objetos no futuro sem fazer alterações desnecessárias no código.

No código, as tags geralmente são representadas como strings, mas se todas as tags usadas forem conhecidas, você poderá converter as strings em números exclusivos para economizar espaço e acelerar a pesquisa. Em alguns mecanismos, as tags são funcionalidades internas, por exemplo, no Unity e no Unreal Engine 4 , portanto, basta determinar a escolha das tags nelas e usá-las para a finalidade a que se destinam.

Objetos inteligentes

As tags são uma maneira de adicionar informações adicionais ao ambiente do agente, para ajudá-lo a descobrir as opções disponíveis, para que solicitações como "Encontre-me todos os lugares mais próximos para me esconder" ou "Encontre-me todos os inimigos próximos que possam lançar feitiços" sejam realizadas com eficiência e com o mínimo esforço trabalhado para novos recursos do jogo. Mas, às vezes, as tags não contêm informações suficientes para seu uso total.

Imagine um simulador de uma cidade medieval na qual os aventureiros vagam onde querem, se necessário, treinam, lutam e relaxam. Podemos organizar locais de treinamento em diferentes partes da cidade e atribuir a eles a tag "TREINAMENTO" para que os personagens possam encontrar facilmente um local para treinamento. Mas vamos imaginar que um deles seja um campo de tiro para arqueiros, e o outro é uma escola de magos. Em cada um desses casos, precisamos mostrar nossa animação, porque, sob o nome geral de "treinamento", eles representam ações diferentes, e nem todo aventureiro está interessado nos dois tipos de treinamento. Você pode se aprofundar ainda mais e criar tags ARCHERY-TRAINING e MAGIC-TRAINING, separar procedimentos de treinamento um do outro e incorporá-los em cada animação diferente. Isso ajudará a resolver o problema. Mas imagineque os designers declararão mais tarde "Vamos ter uma escola de Robin Hood, onde você pode aprender arco e flecha e luta com espadas"! E então, quando adicionamos a luta de espadas, eles pedem a criação da Academia de Magia de Gandalf e luta de espadas. Como resultado, teremos que armazenar várias tags para cada local e procurar animações diferentes com base em qual aspecto do treinamento o personagem precisa, etc.

Outra maneira é armazenar informações diretamente no objeto, juntamente com a influência que ele exerce sobre o jogador, para que o ator da IA possa simplesmente listar as opções possíveis e escolher entre elas de acordo com as necessidades do agente. Depois disso, ele pode ir para o local apropriado, executar as animações apropriadas (ou quaisquer outras ações obrigatórias), conforme indicado no objeto, e receber a recompensa apropriada.

	Animação em execução	Resultado do Usuário
Campo de tiro	Atirar-flecha	+10 Habilidade de Tiro com Arco
Escola de Magia	Duelo de Espadas	+10 Habilidade com espadas
Robin Hood School	Atirar-flecha	+15 de habilidade de tiro com arco
Robin Hood School	Duelo de Espadas	+8 Habilidade com espadas
Academia Gandalf	Duelo de Espadas	+5 Habilidade com espadas
Academia Gandalf	Lançar feitiço	+10 de habilidade mágica

O personagem arqueiro ao lado desses 4 locais terá 6 opções, 4 das quais não são aplicáveis a ele se ele não usar uma espada ou mágica. Comparando o resultado nesse caso com uma melhoria na habilidade, em vez de um nome ou tag, podemos expandir facilmente as possibilidades do mundo com novos comportamentos. Você pode adicionar hotéis para descansar e satisfazer sua fome. Você pode deixar os personagens irem à biblioteca e ler sobre feitiços e técnicas avançadas de arco e flecha.

O nome do objeto	Animação em execução	Resultado final
Hotel	Comprar	-10 a fome
Hotel	Dormir	-50 a fadiga
A biblioteca	Leia o livro	+10 de habilidade de conjuração
A biblioteca	Leia o livro	+5 Habilidade de Tiro com Arco

Se já tivermos o comportamento de “praticar arco e flecha”, mesmo se marcarmos a biblioteca como um local para ARCHERY-TRAINING, provavelmente precisaremos de um caso especial para processar a animação do livro de leitura em vez da animação usual de luta com espadas. Esse sistema nos dá mais flexibilidade, movendo essas associações para dados e armazenando dados no mundo.

A existência de objetos ou locais - bibliotecas, hotéis ou escolas - nos fala sobre os serviços que eles oferecem, sobre o personagem que pode obtê-los, permite que você use um pequeno número de animações. A capacidade de tomar decisões simples sobre os resultados permite criar uma variedade de comportamentos interessantes. Em vez de aguardar passivamente por uma solicitação, esses objetos podem fornecer diversas informações sobre como e por que usá-los.

Curvas de reação

Muitas vezes, há uma situação em que parte do estado do mundo pode ser medida como um valor contínuo. Exemplos:

"Porcentagem de saúde" geralmente varia de 0 (morto) a 100 (absolutamente saudável)
"Distância para o inimigo mais próximo" varia de 0 a algum valor positivo arbitrário

Além disso, o jogo pode ter algum aspecto do sistema de IA, exigindo a entrada de valores contínuos em algum outro intervalo. Por exemplo, para tomar uma decisão de fugir, um sistema de classificação de utilidade pode exigir a distância do inimigo mais próximo e a saúde atual do personagem.

No entanto, o sistema não pode simplesmente somar dois valores do estado do mundo para obter um certo nível de "segurança", porque essas duas unidades de medida são incomparáveis - os sistemas assumirão que um personagem quase morto a 200 metros do inimigo está na mesma segurança que é absolutamente saudável personagem a 100 metros do inimigo. Além disso, embora o valor percentual da saúde em sentido amplo seja linear, a distância não é assim - a diferença na distância do inimigo 200 e 190 metros é menos significativa do que a diferença entre 10 metros e zero.

Idealmente, precisamos de uma solução que pegue dois indicadores e os converta em intervalos semelhantes para que possam ser comparados diretamente. E precisamos que os designers possam controlar como essas transformações são calculadas para controlar a importância relativa de cada valor. Para este fim, são utilizadas curvas de reação (curvas de resposta).

A maneira mais fácil de explicar a curva de reação é como um gráfico com entrada ao longo do eixo X, valores arbitrários, por exemplo, “distância do inimigo mais próximo” e saída ao longo do eixo Y (geralmente um valor normalizado na faixa de 0,0 a 1,0). Uma linha ou curva no gráfico determina a ligação da entrada à saída normalizada, e os designers ajustam essas linhas para obter o comportamento necessário.

Para calcular o nível de "segurança", você pode manter a linearidade dos valores percentuais de saúde - por exemplo, 10% a mais de saúde - isso geralmente é bom quando o personagem é gravemente ferido e quando ele é ferido facilmente. Portanto, atribuímos esses valores ao intervalo de 0 a 1 de maneira direta:

A distância para o inimigo mais próximo é um pouco diferente; portanto, não somos incomodados por inimigos além de uma certa distância (digamos, 50 metros), e estamos muito mais interessados nas diferenças a uma curta distância do que a uma grande distância.

Aqui vemos que a saída de "segurança" para inimigos nos 40 e 50 metros é quase a mesma: 0,96 e 1,0.

No entanto, há uma diferença muito maior entre o inimigo a 15 metros (cerca de 0,5) e o inimigo a 5 metros (cerca de 0,2). Esse cronograma reflete melhor a importância de o inimigo se aproximar.

Ao normalizar esses dois valores no intervalo de 0 a 1, podemos calcular o valor total de segurança como a média desses dois valores de entrada. Um personagem com 20% de vida e um inimigo a 50 metros terão uma pontuação de segurança de 0,6. Um personagem com 75% de vida e um inimigo a apenas 5 metros de distância terão uma pontuação de segurança de 0,47. Um personagem gravemente ferido com 10% de vida e um inimigo de 5 metros terá um índice de segurança de apenas 0,145.

O seguinte deve ser considerado aqui:

— , .
— , , 50 — , , .
, ( ) . , — , Unity AnimationCurve , .

Blackboards

Muitas vezes, nos encontramos em uma situação em que a IA do agente deve começar a monitorar o conhecimento e as informações obtidas durante o jogo, para que possam ser usadas em outras decisões. Por exemplo, um agente pode precisar se lembrar de qual último personagem ele atacou para se concentrar nos ataques daquele personagem por um curto período de tempo. Ou ele deve se lembrar de quanto tempo se passou depois de ouvir um barulho, para que, após certo período de tempo, pare de procurar seus motivos e retorne aos estudos anteriores. Muitas vezes, o sistema de gravação de dados é fortemente separado do sistema de leitura de dados, portanto deve ser facilmente acessível a partir do agente e não incorporado diretamente em vários sistemas de IA. A leitura pode ocorrer algum tempo após a gravação; portanto, os dados precisam ser armazenados em algum lugar,para que possam ser recuperados mais tarde (e não calculados sob demanda, o que pode não ser viável).

Em um sistema de IA codificado, a solução pode ser adicionar as variáveis necessárias no processo da necessidade. Essas variáveis estão relacionadas a instâncias do personagem ou agente, integrando-se diretamente a ele ou criando uma estrutura / classe separada para armazenar essas informações. Os procedimentos de IA podem ser adaptados para ler e gravar esses dados. Em um sistema simples, isso funcionará bem, mas à medida que mais informações são adicionadas, elas se tornam complicadas e geralmente exigem a reconstrução do jogo a cada vez.

Uma abordagem melhor é transformar o data warehouse em uma estrutura que permita aos sistemas ler e gravar dados arbitrários. Essa solução permite adicionar novas variáveis sem a necessidade de alterar a estrutura dos dados, fornecendo a capacidade de aumentar o número de alterações que podem ser feitas a partir de arquivos e scripts de dados sem a necessidade de remontagem. Se cada agente simplesmente armazena uma lista de pares de valores-chave, cada um dos quais é um conhecimento separado, então diferentes sistemas de IA podem cooperar adicionando e lendo essas informações, se necessário.

No desenvolvimento da IA, essas abordagens são chamadas de "quadros-negros" ("quadros-negros"), porque cada participante - no nosso caso, os procedimentos de IA (por exemplo, percepção, encontrar um caminho e tomar decisões) - podem escrever no "quadro-negro", lido a partir do qual os dados para o desempenho de sua tarefa podem ser outros participantes. Você pode imaginar isso como uma equipe de especialistas reunidos em torno do quadro e escrevendo algo útil que você precisa compartilhar com o grupo. Ao mesmo tempo, eles podem ler as notas anteriores de seus colegas até chegar a uma decisão ou plano conjunto. Uma lista codificada de variáveis comuns no código às vezes é chamada de "quadro estático" (porque os elementos nos quais as informações são armazenadas são constantes durante a execução do programa), e uma lista arbitrária de pares de valores-chave é chamada "quadro dinâmico".Mas eles são usados aproximadamente da mesma maneira - como um link intermediário entre partes do sistema de IA.

Na IA tradicional, a ênfase é geralmente colocada na colaboração de diferentes sistemas para a tomada de decisões em conjunto, mas relativamente poucos sistemas estão presentes na IA do jogo. No entanto, um certo grau de cooperação ainda pode estar presente. Imagine o seguinte em um RPG de ação:

O sistema de “percepção” varre regularmente a área e grava as seguintes entradas no quadro-negro:
- Inimigo mais próximo: Goblin 412
- "Distância para o inimigo mais próximo": 35,0
- “Amigo próximo”: “Guerreiro 43”
- “Distância para o amigo mais próximo”: 55.4
- "Hora do último barulho observado": 12:45
Sistemas como um sistema de combate podem registrar eventos importantes em um quadro negro, por exemplo:
- Último dano causado: 12:34 pm

Muitos desses dados podem parecer redundantes - no final, você sempre pode distanciar-se do inimigo mais próximo, simplesmente sabendo quem é esse inimigo e atendendo a uma solicitação de posição. Porém, quando repetida várias vezes por quadro, para decidir se um agente está ameaçando algo ou não, isso se torna uma operação potencialmente lenta, especialmente se ela precisar executar uma consulta espacial para determinar o inimigo mais próximo. E os carimbos de hora do “último ruído notado” ou do “último dano recebido” ainda não poderão ser instantâneos - você precisa registrar a hora em que esses eventos ocorreram e o quadro-negro é um local conveniente para isso.

O Unreal Engine 4 usa um sistema de quadro dinâmico para armazenar dados transmitidos por árvores de comportamento. Graças a esse objeto de dados comum, os designers podem facilmente escrever novos valores no quadro-negro com base em seus blueprints (scripts visuais), e a árvore de comportamento pode posteriormente ler esses valores para selecionar o comportamento, e tudo isso não requer recompilação do mecanismo.

Mapas de influência

A tarefa padrão no AI é decidir para onde o agente deve se mover. No jogo de tiro, podemos escolher a ação "Mover para o abrigo", mas como decidir onde o abrigo está nas condições de mover inimigos? Da mesma forma que a ação "Escape" - onde é a maneira mais segura de escapar? Ou no RTS, podemos precisar das tropas para atacar um ponto fraco na defesa do inimigo - como podemos determinar onde está esse ponto fraco?

Todas essas questões podem ser consideradas tarefas geográficas, porque fazemos uma pergunta sobre a geometria e a forma do ambiente e a posição das entidades nele. No nosso jogo, é provável que todos esses dados já estejam disponíveis, mas dar sentido a eles não é uma tarefa fácil. Por exemplo, se queremos encontrar um ponto fraco na defesa do inimigo, simplesmente escolher a posição do edifício ou fortificação mais fraco não é bom o suficiente se eles tiverem dois poderosos sistemas de armas nos flancos. Precisamos de uma maneira de levar em conta a área local e fazer uma melhor análise da situação.

É para isso que serve a estrutura de dados do "mapa de influência". Descreve a “influência” que uma entidade pode ter na área ao seu redor. Combinando a influência de várias entidades, criamos uma visão mais realista de todo o cenário. Do ponto de vista da implementação, aproximamos o mundo do jogo sobrepondo uma grade 2D e, após determinar em qual célula da grade a entidade está, aplicamos uma avaliação de impacto a essa e às células circundantes, indicando o aspecto da jogabilidade que queremos simular. Para obter uma imagem completa, acumulamos esses valores na mesma grade. Depois disso, podemos realizar várias consultas à grade para entender o mundo e decidir sobre o posicionamento e os pontos de destino.

Tomemos, por exemplo, "o ponto mais fraco na defesa do inimigo". Temos um muro defensivo, no ataque do qual queremos enviar soldados de infantaria, mas há três catapultas atrás dele - duas próximas uma da outra à esquerda, uma à direita. Como escolhemos uma boa posição de ataque?

Para começar, podemos atribuir +1 de pontos de proteção a todas as células da grade dentro do ataque de catapulta. Desenhar esses pontos no mapa de influência para uma catapulta é assim:

O retângulo azul limita todas as células nas quais você pode iniciar um ataque na parede. Quadrados vermelhos indicam +1 influência de catapulta. No nosso caso, isso significa a área do ataque e a ameaça às unidades atacantes.

Agora adicionamos o efeito da segunda catapulta:

Temos uma área escura na qual a influência de duas catapultas é formada, o que dá proteção a essas células +2. A célula +2 dentro da zona azul pode ser um local particularmente perigoso para atacar a parede! Adicione a influência da última catapulta:

[Ícones: CC-BY: https://game-icons.net/heavenly-dog/originals/defensive-wall.html ]

Agora temos uma designação completa da área coberta pelas catapultas. Na zona de ataque em potencial, há uma célula com +2 influências de catapulta, 11 células com influência de +1 e 2 células com 0 influências de catapulta - esses são os principais candidatos à posição de ataque, pois podemos atacar a parede sem medo de fogo de catapulta.

A vantagem dos mapas de influência é que eles transformam um espaço contínuo com um conjunto quase infinito de posições possíveis em um conjunto discreto de posições aproximadas, sobre as quais podemos tomar decisões muito rapidamente.

No entanto, obtivemos essa vantagem apenas escolhendo um pequeno número de possíveis posições de ataque. Por que devemos usar o mapa de influência aqui em vez de verificar manualmente a distância de cada catapulta a cada uma dessas posições?

Em primeiro lugar, o cálculo de um mapa de influência pode ser muito barato. Depois que os pontos de influência são colocados no cartão, ele não precisa ser alterado até que as entidades comecem a se mover. Isso significa que não precisamos executar constantemente cálculos de distância ou interrogar iterativamente todas as unidades possíveis - nós “armazenamos” essas informações no mapa e podemos enviar solicitações para ele várias vezes.

Em segundo lugar, podemos sobrepor e combinar diferentes mapas de influência para atender a consultas mais complexas. Por exemplo, para selecionar um lugar seguro para escapar, podemos pegar um mapa da influência de nossos inimigos e subtrair o mapa de nossos amigos - as células da grade com o maior valor negativo serão consideradas seguras.

Quanto mais vermelho, mais perigoso e mais verde, mais seguro. Áreas em que a sobreposição de influência pode ser total ou parcialmente neutralizada para refletir áreas de influência conflitantes.

Por fim, é fácil visualizar mapas de influência ao renderizar no mundo. Eles podem ser uma dica valiosa para designers que precisam personalizar a IA com base em propriedades visíveis e podem ser observados em tempo real para entender por que a AI escolhe suas decisões.

Conclusão

Espero que o artigo tenha fornecido uma visão geral das ferramentas e abordagens mais populares usadas na IA de jogos, bem como das situações em que elas podem ser aplicadas. O artigo não considerou muitas outras técnicas (elas são usadas com menos frequência, mas poderiam ser igualmente eficazes), incluindo o seguinte:

algoritmos de tarefas de otimização, incluindo escalar para o topo, descida de gradiente e algoritmos genéticos.
algoritmos competitivos de pesquisa / planejamento, como minimax e alfa beta clipping
técnicas de classificação, por exemplo, perceptrons, redes neurais e o método do vetor de suporte
sistemas de percepção de agentes e processamento de memória
abordagens arquitetônicas da IA, como sistemas híbridos, arquiteturas predicativas (arquiteturas Brooks) e outras maneiras de decompor sistemas da AI em camadas
ferramentas de animação, como planejamento e correspondência de movimentos
tarefas relacionadas ao desempenho, como nível de detalhe, algoritmos a qualquer momento e pontualidade

Para ler mais sobre esses tópicos, bem como os tópicos discutidos neste artigo, você pode estudar as seguintes fontes.

GameDev.net tem artigos e tutoriais sobre inteligência artificial , bem como um fórum sobre inteligência artificial .
Em AiGameDev.com têm muitas apresentações e artigos sobre uma ampla gama de temas de inteligência artificial no contexto do desenvolvimento de jogos
O GDC Vault possui relatórios com o GDC AI Summit, muitos dos quais estão disponíveis gratuitamente: https://www.gdcvault.com/
Além disso, o AI Game Programmers Guild possui vários links para artigos e apresentações antigos desta cúpula: http://gameai.com/
O pesquisador de IA e desenvolvedor de jogos Tommy Thompson possui um canal no YouTube dedicado a explicar e explorar a IA em jogos comerciais: https://www.youtube.com/user/tthompso

Muitos dos materiais da mais alta qualidade podem ser encontrados nos livros, incluindo o seguinte:

A Game AI Pro Series é uma coleção de artigos curtos que explicam como implementar recursos específicos ou resolver problemas específicos. Em http://www.gameaipro.com/ postou trechos gratuitos de livros anteriores.
AI Game Programming Wisdom Game AI Pro. , . , !
Artificial Intelligence: A Modern Approach — , . , , , .

Além disso, existem vários bons livros sobre IA de jogos em geral, escritos por profissionais do setor. É difícil dar preferência a qualquer um - leia os comentários e escolha aquele que mais lhe convier.

Visão Geral das Técnicas de Implementação de Game AI

1. Introdução

O que é uma "IA de jogos"?

Limitações do desenvolvimento da IA do jogo

Tomada de decisão fácil

Construções condicionais codificadas

Árvores de decisão

Script

Reação a eventos

Melhor tomada de decisão

Máquinas de estado

Máquinas de estado hierárquico

Árvores de comportamento

Sistemas Baseados em Utilitários

Movimento e navegação

Direção

Localização de caminho

Movimento sem malha

Planejamento

"Agendador" simples

Planejamento aprimorado

Treinamento e adaptação

Estatística e Probabilidades

Fácil adaptação baseada em peso

Modelos de Markov

N gramas

Representação do conhecimento

Tags / Tags

Objetos inteligentes

Curvas de reação

Blackboards

Mapas de influência

Conclusão

More articles:

Visão Geral das Técnicas de Implementação de Game AI

1. Introdução

O que é uma "IA de jogos"?

Limitações do desenvolvimento da IA ​​do jogo

Tomada de decisão fácil

Construções condicionais codificadas

Árvores de decisão

Script

Reação a eventos

Melhor tomada de decisão

Máquinas de estado

Máquinas de estado hierárquico

Árvores de comportamento

Sistemas Baseados em Utilitários

Movimento e navegação

Direção

Localização de caminho

Movimento sem malha

Planejamento

"Agendador" simples

Planejamento aprimorado

Treinamento e adaptação

Estatística e Probabilidades

Fácil adaptação baseada em peso

Modelos de Markov

N gramas

Representação do conhecimento

Tags / Tags

Objetos inteligentes

Curvas de reação

Blackboards

Mapas de influência

Conclusão

More articles:

Limitações do desenvolvimento da IA do jogo