Me deparei com algum material interessante sobre inteligência artificial em jogos. Com uma explicação de coisas básicas sobre IA usando exemplos simples, e dentro dele há muitas ferramentas e métodos úteis para seu desenvolvimento e design convenientes. Como, onde e quando usá-los também está lá.
A maioria dos exemplos é escrita em pseudocódigo, portanto, nenhum conhecimento avançado de programação é necessário. Abaixo do corte estão 35 folhas de texto com fotos e gifs, então prepare-se.
Atualização. Peço desculpas, mas já fiz minha própria tradução deste artigo sobre Habré . Você pode ler a versão dele , mas por algum motivo o artigo passou por mim (usei a busca, mas algo deu errado). E como estou escrevendo em um blog dedicado ao desenvolvimento de jogos, resolvi deixar minha versão da tradução para os assinantes (alguns pontos estão formatados de forma diferente, alguns foram omitidos deliberadamente por conselho dos desenvolvedores).
O que é IA?
A IA do jogo concentra-se nas ações que um objeto deve realizar com base nas condições em que está localizado. Isto é comumente referido como gerenciamento de “agente inteligente”, onde um agente é um personagem do jogador, um veículo, um bot, ou às vezes algo mais abstrato: um grupo inteiro de entidades ou mesmo uma civilização. Em cada caso, é algo que deve ver o seu ambiente, tomar decisões com base nele e agir de acordo com ele. Isso é chamado de ciclo Sentir/Pensar/Agir:
- Sentido: O agente encontra ou recebe informações sobre coisas em seu ambiente que podem influenciar seu comportamento (ameaças próximas, itens para coletar, lugares interessantes para explorar).
- Pense: O agente decide como reagir (considera se é seguro o suficiente coletar itens ou se deve lutar/se esconder primeiro).
- Agir: o agente realiza ações para implementar a decisão anterior (começa a se mover em direção ao inimigo ou objeto).
- ...agora a situação mudou devido às ações dos personagens, então o ciclo se repete com novos dados.
A IA tende a se concentrar na parte Sense do loop. Por exemplo, carros autônomos tiram fotos da estrada, combinam-nas com dados de radar e lidar e interpretam-nas. Isso normalmente é feito por aprendizado de máquina, que processa os dados recebidos e lhes dá significado, extraindo informações semânticas como “há outro carro 20 metros à sua frente”. Estes são os chamados problemas de classificação.
Os jogos não precisam de um sistema complexo para extrair informações, pois a maior parte dos dados já é parte integrante dele. Não há necessidade de executar algoritmos de reconhecimento de imagem para determinar se há um inimigo à frente – o jogo já sabe e alimenta a informação diretamente no processo de tomada de decisão. Portanto, a parte Sentir do ciclo é muitas vezes muito mais simples do que a parte Pensar e Agir.
Limitações da IA do jogo
A IA tem uma série de limitações que devem ser observadas:
- A IA não precisa ser treinada antecipadamente, como se fosse um algoritmo de aprendizado de máquina. Não faz sentido escrever uma rede neural durante o desenvolvimento para monitorar dezenas de milhares de jogadores e aprender a melhor maneira de jogar contra eles. Por que? Porque o jogo não foi lançado e não há jogadores.
- O jogo deve ser divertido e desafiador, por isso os agentes não devem encontrar a melhor abordagem contra as pessoas.
- Os agentes precisam parecer realistas para que os jogadores sintam que estão jogando contra pessoas reais. O programa AlphaGo superou os humanos, mas as etapas escolhidas ficaram muito distantes do entendimento tradicional do jogo. Se o jogo simula um oponente humano, esse sentimento não deveria existir. O algoritmo precisa ser alterado para que tome decisões plausíveis em vez de decisões ideais.
- A IA deve funcionar em tempo real. Isso significa que o algoritmo não pode monopolizar o uso da CPU por longos períodos para tomar decisões. Mesmo 10 milissegundos é muito longo, porque a maioria dos jogos só precisa de 16 a 33 milissegundos para fazer todo o processamento e passar para o próximo quadro gráfico.
- Idealmente, pelo menos parte do sistema deve ser orientada por dados, para que os não codificadores possam fazer alterações e os ajustes possam acontecer mais rapidamente.
Vejamos as abordagens de IA que cobrem todo o ciclo Sentir/Pensar/Agir.
Tomando decisões básicas
Vamos começar com o jogo mais simples - Pong. Objetivo: mover a raquete para que a bola quique nela em vez de passar por ela. É como o tênis, onde você perde se não acertar a bola. Aqui a IA tem uma tarefa relativamente fácil – decidir em que direção mover a plataforma.
Declarações condicionais
Para a IA do Pong, a solução mais óbvia é tentar sempre colocar a plataforma sob a bola.
Um algoritmo simples para isso, escrito em pseudocódigo:
cada frame/atualização enquanto o jogo está rodando:
se a bola estiver à esquerda da raquete:
mova o remo para a esquerda
caso contrário, se a bola estiver à direita da raquete:
mova o remo para a direita
Se a plataforma se move na velocidade da bola, então este é o algoritmo ideal para a IA no Pong. Não há necessidade de complicar nada se não houver tantos dados e ações possíveis para o agente.
Essa abordagem é tão simples que todo o ciclo Sentir/Pensar/Agir é quase imperceptível. Mas está lá:
- A parte Sense está em duas instruções if. O jogo sabe onde está a bola e onde está a plataforma, então a IA procura essa informação.
- A parte Think também está incluída nas duas instruções if. Eles incorporam duas soluções, que neste caso são mutuamente exclusivas. Como resultado, uma das três ações é selecionada - mover a plataforma para a esquerda, movê-la para a direita ou não fazer nada se ela já estiver posicionada corretamente.
- A parte Act é encontrada nas instruções Move Paddle Left e Move Paddle Right. Dependendo do design do jogo, eles podem mover a plataforma instantaneamente ou a uma velocidade específica.
Essas abordagens são chamadas de reativas - existe um conjunto simples de regras (neste caso, instruções if no código) que reagem ao estado atual do mundo e agem.
Árvore de decisão
O exemplo do Pong é na verdade equivalente a um conceito formal de IA chamado árvore de decisão. O algoritmo passa por isso para chegar a uma “folha” – uma decisão sobre que ação tomar.
Vamos fazer um diagrama de blocos da árvore de decisão do algoritmo da nossa plataforma:
Cada parte da árvore é chamada de nó – a IA usa a teoria dos grafos para descrever tais estruturas. Existem dois tipos de nós:
- Nós de decisão: escolha entre duas alternativas com base no teste de alguma condição, onde cada alternativa é representada como um nó separado.
- Nós finais: a ação a ser executada que representa a decisão final.
O algoritmo começa no primeiro nó (a “raiz” da árvore). Ele toma uma decisão sobre para qual nó filho ir ou executa a ação armazenada no nó e sai.
Qual é a vantagem de ter uma árvore de decisão fazendo o mesmo trabalho que as instruções if da seção anterior? Existe aqui um sistema geral onde cada decisão tem apenas uma condição e dois resultados possíveis. Isso permite que o desenvolvedor crie IA a partir de dados que representam decisões em uma árvore sem precisar codificá-los. Vamos apresentá-lo em forma de tabela:
Do lado do código você obterá um sistema para leitura de strings. Crie um nó para cada um deles, conecte a lógica de decisão com base na segunda coluna e os nós filhos com base na terceira e quarta colunas. Ainda é preciso programar as condições e ações, mas agora a estrutura do jogo ficará mais complexa. Aqui você adiciona decisões e ações adicionais e, em seguida, personaliza toda a IA simplesmente editando o arquivo de texto de definição de árvore. Em seguida, você transfere o arquivo para o designer do jogo, que pode alterar o comportamento sem recompilar o jogo ou alterar o código.
As árvores de decisão são muito úteis quando são construídas automaticamente a partir de um grande conjunto de exemplos (por exemplo, usando o algoritmo ID3). Isso os torna uma ferramenta eficaz e de alto desempenho para classificar situações com base nos dados obtidos. Porém, vamos além de um simples sistema para os agentes selecionarem ações.
cenários
Analisamos um sistema de árvore de decisão que utilizava condições e ações pré-criadas. Quem projeta a IA pode organizar a árvore como quiser, mas ainda precisa contar com o codificador que programou tudo. E se pudéssemos dar ao designer as ferramentas para criar as suas próprias condições ou ações?
Para que o programador não precise escrever código para as condições Is Ball Left Of Paddle e Is Ball Right Of Paddle, ele pode criar um sistema no qual o designer escreverá condições para verificar esses valores. Então os dados da árvore de decisão ficarão assim:
Isto é essencialmente o mesmo que na primeira tabela, mas as soluções dentro de si têm o seu próprio código, um pouco como a parte condicional de uma instrução if. Do lado do código, isso seria lido na segunda coluna para os nós de decisão, mas em vez de procurar uma condição específica para executar (Is Ball Left Of Paddle), ele avalia a expressão condicional e retorna verdadeiro ou falso de acordo. Isso é feito usando a linguagem de script Lua ou Angelscript. Utilizando-os, um desenvolvedor pode pegar objetos em seu jogo (bola e remo) e criar variáveis que estarão disponíveis no script (ball.position). Além disso, a linguagem de script é mais simples que C++. Não requer um estágio de compilação completo, por isso é ideal para ajustar rapidamente a lógica do jogo e permite que “não programadores” criem eles próprios as funções necessárias.
No exemplo acima, a linguagem de script é usada apenas para avaliar a expressão condicional, mas também pode ser usada para ações. Por exemplo, os dados Move Paddle Right podem se tornar uma instrução de script (ball.position.x += 10). Para que a ação também fique definida no script, sem a necessidade de programar Move Paddle Right.
Você pode ir ainda mais longe e escrever toda a árvore de decisão em uma linguagem de script. Este será o código na forma de instruções condicionais codificadas, mas estarão localizadas em arquivos de script externos, ou seja, podem ser alteradas sem recompilar o programa inteiro. Muitas vezes você pode editar o arquivo de script durante o jogo para testar rapidamente diferentes respostas de IA.
Resposta ao Evento
Os exemplos acima são perfeitos para Pong. Eles executam continuamente o ciclo Sentir/Pensar/Agir e agem com base no estado mais recente do mundo. Mas em jogos mais complexos você precisa reagir a eventos individuais e não avaliar tudo de uma vez. Pong, neste caso, já é um mau exemplo. Vamos escolher outro.
Imagine um atirador onde os inimigos ficam imóveis até detectarem o jogador, após o que agem de acordo com a sua “especialização”: alguém correrá para “correr”, alguém atacará de longe. Ainda é um sistema reativo básico - "se um jogador for localizado, faça alguma coisa" - mas pode ser logicamente dividido em um evento visto pelo jogador e uma reação (selecione uma resposta e execute-a).
Isso nos traz de volta ao ciclo Sentir/Pensar/Agir. Podemos codificar uma parte Sense que verificará em cada quadro se a IA vê o jogador. Caso contrário, nada acontece, mas se detectar, o evento Player Seen é criado. O código terá uma seção separada que diz "quando o evento Player Seen ocorrer, faça", onde está a resposta necessária para abordar as partes Pensar e Agir. Assim, você configurará as reações ao evento Player Seen: para o personagem “corredor” - ChargeAndAttack, e para o atirador - HideAndSnipe. Esses relacionamentos podem ser criados no arquivo de dados para edição rápida sem necessidade de recompilação. A linguagem de script também pode ser usada aqui.
Tomando decisões difíceis
Embora os sistemas de reação simples sejam muito poderosos, há muitas situações em que não são suficientes. Às vezes você precisa tomar decisões diferentes com base no que o agente está fazendo no momento, mas é difícil imaginar isso como uma condição. Às vezes, há muitas condições para representá-las efetivamente em uma árvore ou script de decisão. Às vezes é necessário avaliar antecipadamente como a situação mudará antes de decidir o próximo passo. São necessárias abordagens mais sofisticadas para resolver estes problemas.
Máquina de estados finitos
Máquina de estados finitos ou FSM (máquina de estados finitos) é uma forma de dizer que nosso agente está atualmente em um dos vários estados possíveis e que pode fazer a transição de um estado para outro. Há um certo número desses estados – daí o nome. O melhor exemplo da vida é um semáforo. Existem diferentes sequências de luzes em locais diferentes, mas o princípio é o mesmo – cada estado representa algo (parar, caminhar, etc.). Um semáforo está em apenas um estado em um determinado momento e se move de um para outro com base em regras simples.
É uma história semelhante com NPCs em jogos. Por exemplo, tomemos um guarda com os seguintes estados:
- Patrulhamento.
- Atacante.
- Fugindo.
E estas condições para mudar seu estado:
- Se o guarda vir o inimigo, ele ataca.
- Se o guarda ataca mas não vê mais o inimigo, ele volta a patrulhar.
- Se um guarda ataca mas fica gravemente ferido, ele foge.
Você também pode escrever instruções if com uma variável de estado guardião e várias verificações: há um inimigo próximo, qual é o nível de saúde do NPC, etc.
- Ociosidade - entre patrulhas.
- Procurando - quando o inimigo notado desapareceu.
- Encontrar ajuda - quando um inimigo é avistado, mas é forte demais para lutar sozinho.
A escolha de cada um deles é limitada - por exemplo, o guarda não irá procurar um inimigo oculto se estiver com pouca saúde.
Afinal, há uma lista enorme de “se” , Que " pode se tornar muito complicado, por isso precisamos formalizar um método que nos permita manter em mente os estados e as transições entre estados. Para fazer isso, levamos em consideração todos os estados, e em cada estado anotamos em uma lista todas as transições para outros estados, juntamente com as condições necessárias para elas.
Esta é uma tabela de transição de estado – uma forma abrangente de representar o FSM. Vamos desenhar um diagrama e obter uma visão completa de como o comportamento do NPC muda.
O diagrama reflete a essência da tomada de decisão deste agente com base na situação atual. Além disso, cada seta mostra uma transição entre estados se a condição próxima a ela for verdadeira.
A cada atualização verificamos o estado atual do agente, examinamos a lista de transições e, se as condições para a transição forem atendidas, ele aceita o novo estado. Por exemplo, cada quadro verifica se o temporizador de 10 segundos expirou e, em caso afirmativo, o guarda passa do estado Idle para Patrolling. Da mesma forma, o estado Atacante verifica a saúde do agente - se estiver baixa, ele passa para o estado Fugindo.
Trata-se de lidar com transições entre estados, mas e o comportamento associado aos próprios estados? Em termos de implementação do comportamento real para um determinado estado, normalmente existem dois tipos de “gancho” onde atribuímos ações ao FSM:
- Ações que realizamos periodicamente para o estado atual.
- As ações que tomamos durante a transição de um estado para outro.
Exemplos para o primeiro tipo. O estado Patrolling moverá o agente ao longo da rota de patrulha em cada quadro. O estado de ataque tentará iniciar um ataque a cada quadro ou transição para um estado onde isso for possível.
Para o segundo tipo, considere a transição “se o inimigo estiver visível e for muito forte, vá para o estado Encontrando Ajuda. O agente deve escolher onde procurar ajuda e armazenar essas informações para que o estado Encontrando Ajuda saiba para onde ir. Assim que a ajuda for encontrada, o agente volta ao estado de ataque. Neste ponto, ele desejará contar ao aliado sobre a ameaça, para que a ação NotifyFriendOfThreat possa ocorrer.
Mais uma vez, podemos olhar para este sistema através das lentes do ciclo Sentir/Pensar/Agir. O sentido está incorporado nos dados usados pela lógica de transição. Pense - transições disponíveis em cada estado. E o Act é realizado por ações realizadas periodicamente dentro de um estado ou em transições entre estados.
Às vezes, as condições de transição de sondagem contínua podem ser dispendiosas. Por exemplo, se cada agente realizar cálculos complexos em cada quadro para determinar se pode ver os inimigos e entender se pode fazer a transição do estado Patrulhamento para Ataque, isso consumirá muito tempo da CPU.
Mudanças importantes no estado do mundo podem ser pensadas como eventos que serão processados à medida que ocorrem. Em vez de o FSM verificar a condição de transição “meu agente pode ver o jogador?” a cada quadro, um sistema separado pode ser configurado para verificar com menos frequência (por exemplo, 5 vezes por segundo). E o resultado é emitir Player Seen quando a verificação for aprovada.
Isso é passado para o FSM, que agora deve ir para a condição recebida do evento Player Seen e responder de acordo. O comportamento resultante é o mesmo, exceto por um atraso quase imperceptível antes de responder. Mas o desempenho melhorou como resultado da separação da parte Sense em uma parte separada do programa.
Máquina hierárquica de estados finitos
No entanto, trabalhar com grandes FSMs nem sempre é conveniente. Se quisermos expandir o estado de ataque para separar MeleeAttacking e RangedAttacking, teremos que alterar as transições de todos os outros estados que levam ao estado Attacking (atual e futuro).
Você provavelmente notou que em nosso exemplo há muitas transições duplicadas. A maioria das transições no estado Idle são idênticas às transições no estado Patrolling. Seria bom não nos repetirmos, especialmente se adicionarmos mais estados semelhantes. Faz sentido agrupar a marcha lenta e a patrulha sob o rótulo geral de “não-combate”, onde existe apenas um conjunto comum de transições para estados de combate. Se pensarmos neste rótulo como um estado, então Inatividade e Patrulhamento tornam-se subestados. Um exemplo de uso de uma tabela de transição separada para um novo subestado sem combate:
Principais estados:
Status fora de combate:
E em forma de diagrama:
É o mesmo sistema, mas com um novo estado de não-combate que inclui Inatividade e Patrulhamento. Com cada estado contendo um FSM com subestados (e esses subestados, por sua vez, contendo seus próprios FSMs - e assim por diante pelo tempo que for necessário), obtemos uma Máquina Hierárquica de Estados Finitos ou HFSM (máquina hierárquica de estados finitos). Ao agrupar o estado sem combate, eliminamos um monte de transições redundantes. Podemos fazer o mesmo para quaisquer novos estados com transições comuns. Por exemplo, se no futuro expandirmos o estado de ataque para os estados MeleeAttacking e MissileAttacking, eles serão subestados que transitam entre si com base na distância até o inimigo e na disponibilidade de munição. Como resultado, comportamentos e subcomportamentos complexos podem ser representados com um mínimo de transições duplicadas.
Árvore de comportamento
Com o HFSM, combinações complexas de comportamentos são criadas de forma simples. No entanto, existe uma ligeira dificuldade no facto de a tomada de decisões sob a forma de regras de transição estar intimamente relacionada com o estado actual. E em muitos jogos é exatamente isso que é necessário. E o uso cuidadoso da hierarquia de estados pode reduzir o número de repetições de transição. Mas às vezes você precisa de regras que funcionem independentemente do estado em que você se encontra, ou que se apliquem a quase todos os estados. Por exemplo, se a saúde de um agente cair para 25%, você vai querer que ele fuja independentemente de estar em combate, ocioso ou conversando - você terá que adicionar esta condição a cada estado. E se mais tarde o seu designer quiser alterar o limite de saúde baixo de 25% para 10%, isso terá que ser feito novamente.
Idealmente, esta situação requer um sistema em que as decisões sobre “em que estado estar” estejam fora dos próprios estados, a fim de fazer alterações apenas num local e não afetar as condições de transição. As árvores de comportamento aparecem aqui.
Existem várias maneiras de implementá-las, mas a essência é praticamente a mesma para todas e é semelhante a uma árvore de decisão: o algoritmo começa com um nó “raiz” e a árvore contém nós que representam decisões ou ações. Existem algumas diferenças importantes:
- Os nós agora retornam um dos três valores: Bem-sucedido (se o trabalho for concluído), Failed (se não puder ser iniciado) ou Running (se ainda estiver em execução e não houver resultado final).
- Não há mais nós de decisão para escolher entre duas alternativas. Em vez disso, eles são nós Decorator, que possuem um nó filho. Se tiverem sucesso, eles executam seu único nó filho.
- Os nós que executam ações retornam um valor Running para representar as ações que estão sendo executadas.
Este pequeno conjunto de nós pode ser combinado para criar um grande número de comportamentos complexos. Vamos imaginar a guarda HFSM do exemplo anterior como uma árvore de comportamento:
Com esta estrutura não deve haver nenhuma transição óbvia dos estados de Inatividade/Patrulhamento para Ataque ou quaisquer outros estados. Se um inimigo estiver visível e a saúde do personagem estiver baixa, a execução irá parar no nó Fuga, independentemente de qual nó ele estava executando anteriormente - Patrulhando, Idle, Atacando ou qualquer outro.
As árvores de comportamento são complexas – há muitas maneiras de compô-las, e encontrar a combinação certa de decoradores e nós compostos pode ser um desafio. Também há dúvidas sobre com que frequência verificar a árvore - queremos examinar todas as partes dela ou apenas quando uma das condições mudar? Como armazenamos o estado referente aos nós - como sabemos quando estivemos inativos por 10 segundos ou como sabemos quais nós estavam em execução da última vez para que possamos processar a sequência corretamente?
É por isso que existem muitas implementações. Por exemplo, alguns sistemas substituíram nós decoradores por decoradores inline. Eles reavaliam a árvore quando as condições do decorador mudam, ajudam a unir os nós e fornecem atualizações periódicas.
Sistema baseado em utilidade
Alguns jogos têm muitas mecânicas diferentes. É desejável que recebam todos os benefícios das regras de transição simples e gerais, mas não necessariamente na forma de uma árvore completa de comportamento. Em vez de ter um conjunto claro de escolhas ou uma árvore de ações possíveis, é mais fácil examinar todas as ações e escolher a mais adequada no momento.
O sistema baseado em utilitário ajudará exatamente nisso. Este é um sistema onde o agente realiza uma variedade de ações e escolhe quais executar com base na utilidade relativa de cada uma. Onde utilidade é uma medida arbitrária de quão importante ou desejável é para o agente realizar esta ação.
A utilidade calculada de uma ação com base no estado e ambiente atuais, o agente pode verificar e selecionar o outro estado mais apropriado a qualquer momento. Isto é semelhante ao FSM, exceto onde as transições são determinadas por uma estimativa para cada estado potencial, incluindo o atual. Observe que escolhemos a ação mais útil para seguir em frente (ou permanecer se já a tivermos concluído). Para maior variedade, esta poderia ser uma seleção equilibrada, mas aleatória, de uma pequena lista.
O sistema atribui uma faixa arbitrária de valores de utilidade – por exemplo, de 0 (completamente indesejável) a 100 (completamente desejável). Cada ação possui uma série de parâmetros que afetam o cálculo desse valor. Voltando ao nosso exemplo do guardião:
As transições entre ações são ambíguas – qualquer estado pode seguir qualquer outro. As prioridades de ação são encontradas nos valores de utilidade retornados. Se um inimigo estiver visível, e esse inimigo for forte, e a saúde do personagem estiver baixa, então Fleeing e FindingHelp retornarão valores altos diferentes de zero. Neste caso, FindingHelp será sempre maior. Da mesma forma, as atividades não-combatentes nunca retornam mais de 50, portanto serão sempre inferiores às de combate. Você precisa levar isso em consideração ao criar ações e calcular sua utilidade.
No nosso exemplo, as ações retornam um valor constante fixo ou um de dois valores fixos. Um sistema mais realista retornaria uma estimativa de um intervalo contínuo de valores. Por exemplo, a ação de Fuga retorna valores de utilidade mais altos se a saúde do agente estiver baixa, e a ação de Ataque retorna valores de utilidade mais baixos se o inimigo for muito forte. Por conta disso, a ação Fugir tem precedência sobre Atacar em qualquer situação em que o agente sinta que não tem saúde suficiente para derrotar o inimigo. Isto permite que as ações sejam priorizadas com base em qualquer número de critérios, tornando esta abordagem mais flexível e variável do que uma árvore de comportamento ou FSM.
Cada ação possui muitas condições para cálculo do programa. Eles podem ser escritos em linguagem de script ou como uma série de fórmulas matemáticas. The Sims, que simula a rotina diária de um personagem, adiciona uma camada adicional de cálculo – o agente recebe uma série de “motivações” que influenciam as classificações de utilidade. Se um personagem estiver com fome, ele ficará ainda mais faminto com o tempo, e o valor utilitário da ação EatFood aumentará até que o personagem a execute, reduzindo o nível de fome e retornando o valor EatFood a zero.
A ideia de selecionar ações com base em um sistema de classificação é bastante simples, portanto, um sistema baseado em utilidade pode ser usado como parte dos processos de tomada de decisão de IA, e não como um substituto completo para eles. A árvore de decisão pode solicitar uma classificação de utilidade de dois nós filhos e selecionar o mais alto. Da mesma forma, uma árvore de comportamento pode ter um nó Utilitário composto para avaliar a utilidade das ações para decidir qual filho executar.
Movimento e navegação
Nos exemplos anteriores, tínhamos uma plataforma que movíamos para a esquerda ou para a direita e um guarda que patrulhava ou atacava. Mas como exatamente lidamos com a movimentação dos agentes durante um período de tempo? Como definimos a velocidade, como evitamos obstáculos e como planejamos uma rota quando chegar a um destino é mais difícil do que apenas seguir em linha reta? Vejamos isso.
Управление
No estágio inicial, assumiremos que cada agente possui um valor de velocidade, que inclui a rapidez com que ele se move e em que direção. Pode ser medido em metros por segundo, quilômetros por hora, pixels por segundo, etc. Lembrando o loop Sense/Think/Act, podemos imaginar que a parte Think seleciona uma velocidade, e a parte Act aplica essa velocidade ao agente. Normalmente os jogos possuem um sistema de física que faz essa tarefa para você, aprendendo o valor da velocidade de cada objeto e ajustando-o. Portanto, você pode deixar a IA com uma tarefa - decidir qual velocidade o agente deve ter. Se você sabe onde o agente deve estar, será necessário movê-lo na direção certa a uma velocidade definida. Uma equação muito trivial:
viagem_desejada = posição_destino – posição_agente
Imagine um mundo 2D. O agente está no ponto (-2,-2), o destino está em algum lugar no nordeste no ponto (30, 20) e o caminho necessário para o agente chegar lá é (32, 22). Digamos que essas posições sejam medidas em metros - se considerarmos a velocidade do agente como 5 metros por segundo, escalaremos nosso vetor de deslocamento e obteremos uma velocidade de aproximadamente (4.12, 2.83). Com esses parâmetros, o agente chegaria ao destino em quase 8 segundos.
Você pode recalcular os valores a qualquer momento. Se o agente estivesse a meio caminho do alvo, o movimento seria na metade do comprimento, mas como a velocidade máxima do agente é de 5 m/s (decidimos isso acima), a velocidade será a mesma. Isso também funciona para alvos móveis, permitindo que o agente faça pequenas alterações à medida que se movem.
Mas queremos mais variação - por exemplo, aumentar lentamente a velocidade para simular um personagem passando de pé para correndo. O mesmo pode ser feito no final, antes de parar. Esses recursos são conhecidos como comportamentos de direção, cada um com nomes específicos: Busca, Fuga, Chegada, etc. A ideia é que forças de aceleração possam ser aplicadas à velocidade do agente, com base na comparação da posição e velocidade atual do agente com o destino em para usar diferentes métodos de avançar para o objetivo.
Cada comportamento tem um propósito ligeiramente diferente. Busca e Chegada são formas de mover um agente para um destino. Evitar Obstáculos e Separação ajustam o movimento do agente para evitar obstáculos no caminho para o gol. Alinhamento e Coesão mantêm os agentes trabalhando juntos. Qualquer número de diferentes comportamentos de direção pode ser somado para produzir um único vetor de caminho, levando em consideração todos os fatores. Um agente que utiliza os comportamentos de Chegada, Separação e Evitar Obstáculos para ficar longe de paredes e outros agentes. Essa abordagem funciona bem em locais abertos sem detalhes desnecessários.
Em condições mais difíceis, a adição de diferentes comportamentos funciona pior - por exemplo, um agente pode ficar preso em uma parede devido a um conflito entre Chegada e Evitar Obstáculos. Portanto, você precisa considerar opções mais complexas do que simplesmente somar todos os valores. O caminho é este: em vez de somar os resultados de cada comportamento, você pode considerar o movimento em diferentes direções e escolher a melhor opção.
Contudo, num ambiente complexo, com becos sem saída e escolhas sobre o caminho a seguir, precisaremos de algo ainda mais avançado.
Procure uma maneira
Os comportamentos de direção são ótimos para movimentos simples em uma área aberta (campo de futebol ou arena), onde ir de A a B é um caminho reto, com apenas pequenos desvios em torno de obstáculos. Para rotas complexas, precisamos de pathfinding, que é uma forma de explorar o mundo e decidir uma rota através dele.
O mais simples é aplicar uma grade em cada quadrado próximo ao agente e avaliar quais deles podem se movimentar. Se um deles for um destino, siga o percurso de cada quadrado até o anterior até chegar ao início. Este é o caminho. Caso contrário, repita o processo com outros quadrados próximos até encontrar o seu destino ou ficar sem quadrados (o que significa que não há rota possível). Isso é formalmente conhecido como pesquisa em largura ou BFS (algoritmo de pesquisa em largura). A cada passo ele olha em todas as direções (daí largura, “largura”). O espaço de busca é como uma frente de onda que se move até atingir o local desejado - o espaço de busca se expande a cada passo até que o ponto final seja incluído, após o qual pode ser rastreado de volta ao início.
Como resultado, você receberá uma lista de praças ao longo das quais é traçado o percurso desejado. Este é o caminho (portanto, pathfinding) – uma lista de lugares que o agente visitará enquanto segue o destino.
Dado que conhecemos a posição de cada quadrado do mundo, podemos usar comportamentos de direção para nos movermos ao longo do caminho - do nó 1 ao nó 2, depois do nó 2 ao nó 3 e assim por diante. A opção mais simples é ir em direção ao centro do próximo quadrado, mas uma opção ainda melhor é parar no meio da borda entre o quadrado atual e o próximo. Por causa disso, o agente será capaz de fazer curvas fechadas.
O algoritmo BFS também tem desvantagens - ele explora tantos quadrados na direção “errada” quanto na direção “certa”. É aqui que entra em ação um algoritmo mais complexo chamado A* (A estrela). Funciona da mesma maneira, mas em vez de examinar cegamente os quadrados vizinhos (depois vizinhos dos vizinhos, depois vizinhos dos vizinhos dos vizinhos e assim por diante), ele coleta os nós em uma lista e os classifica de modo que o próximo nó examinado seja sempre o aquele que leva ao caminho mais curto. Os nós são classificados com base em uma heurística que leva em conta duas coisas – o “custo” de uma rota hipotética para o quadrado desejado (incluindo quaisquer custos de viagem) e uma estimativa de quão longe esse quadrado está do destino (enviesando a pesquisa no quadrado desejado). direção correta).
Este exemplo mostra que o agente explora um quadrado de cada vez, escolhendo cada vez o adjacente que seja mais promissor. O caminho resultante é o mesmo do BFS, mas menos quadrados foram considerados no processo – o que tem um grande impacto no desempenho do jogo.
Movimento sem grade
Mas a maioria dos jogos não são dispostos em uma grade e muitas vezes é impossível fazê-lo sem sacrificar o realismo. São necessários compromissos. Qual deve ser o tamanho dos quadrados? Muito grandes e eles não serão capazes de representar corretamente pequenos corredores ou curvas, muito pequenos e haverá muitos quadrados para procurar, o que acabará por levar muito tempo.
A primeira coisa a entender é que uma malha nos dá um gráfico de nós conectados. Os algoritmos A* e BFS realmente funcionam em gráficos e não se importam com nossa malha. Poderíamos colocar nós em qualquer lugar do mundo do jogo: desde que haja uma conexão entre quaisquer dois nós conectados, bem como entre os pontos inicial e final e pelo menos um dos nós, o algoritmo funcionará tão bem quanto antes. Isto é muitas vezes chamado de sistema de waypoints, uma vez que cada nó representa uma posição significativa no mundo que pode fazer parte de qualquer número de caminhos hipotéticos.
Exemplo 1: um nó em cada quadrado. A busca inicia no nó onde o agente está localizado e termina no nó da praça desejada.
Exemplo 2: Um conjunto menor de nós (waypoints). A busca começa na praça do agente, passa pelo número necessário de nós e depois continua até o destino.
Este é um sistema completamente flexível e poderoso. Mas é necessário algum cuidado ao decidir onde e como colocar um waypoint, caso contrário os agentes poderão simplesmente não ver o ponto mais próximo e não conseguirão iniciar o caminho. Seria mais fácil se pudéssemos colocar pontos de referência automaticamente com base na geometria do mundo.
É aqui que aparece a malha de navegação ou navmesh (malha de navegação). Geralmente é uma malha 2D de triângulos sobreposta à geometria do mundo - onde quer que o agente possa andar. Cada um dos triângulos na malha se torna um nó no gráfico e possui até três triângulos adjacentes que se tornam nós adjacentes no gráfico.
Esta imagem é um exemplo do motor Unity - ele analisou a geometria do mundo e criou uma malha de navegação (na captura de tela em azul claro). Cada polígono em uma malha de navegação é uma área onde um agente pode permanecer ou mover-se de um polígono para outro. Neste exemplo, os polígonos são menores que os andares onde estão localizados - isso é feito para levar em consideração o tamanho do agente, que se estenderá além de sua posição nominal.
Podemos procurar uma rota através desta malha, novamente usando o algoritmo A*. Isso nos dará uma rota quase perfeita no mundo, que leva em conta toda a geometria e não requer nós desnecessários e criação de waypoints.
Pathfinding é um tópico muito amplo para o qual uma seção de um artigo não é suficiente. Se você quiser estudá-lo com mais detalhes, isso ajudará .
planejamento
Aprendemos com o pathfinding que às vezes não é suficiente apenas escolher uma direção e seguir em frente - temos que escolher uma rota e fazer algumas curvas para chegar ao destino desejado. Podemos generalizar esta ideia: atingir um objetivo não é apenas o próximo passo, mas toda uma sequência onde às vezes é preciso olhar vários passos adiante para descobrir qual deve ser o primeiro. Isso se chama planejamento. Pathfinding pode ser pensado como uma das várias extensões do planejamento. Em termos do nosso ciclo Sentir/Pensar/Agir, é aqui que a parte Pensar planeja múltiplas partes de Agir para o futuro.
Vejamos o exemplo do jogo de tabuleiro Magic: The Gathering. Vamos primeiro com o seguinte conjunto de cartas em nossas mãos:
- Pântano - Dá 1 mana preta (carta de terreno).
- Floresta - dá 1 mana verde (carta de terreno).
- Feiticeiro Fugitivo – Requer 1 mana azul para invocar.
- Elvish Mystic – Requer 1 mana verde para invocar.
Ignoramos as três cartas restantes para facilitar. De acordo com as regras, um jogador pode jogar 1 carta de terreno por turno, ele pode “virar” esta carta para extrair mana dela e então lançar mágicas (incluindo invocar uma criatura) de acordo com a quantidade de mana. Nesta situação, o jogador humano sabe que deve jogar Forest, virar 1 mana verde e então invocar Elvish Mystic. Mas como a IA do jogo pode descobrir isso?
Planejamento fácil
A abordagem trivial é tentar cada ação por vez até que não haja mais nenhuma ação adequada. Ao olhar as cartas, a IA vê o que o Swamp pode jogar. E ele joga. Ainda há alguma outra ação neste turno? Ele não pode invocar Elvish Mystic ou Fugitive Wizard, pois eles requerem mana verde e azul, respectivamente, para invocá-los, enquanto Swamp fornece apenas mana preta. E ele não poderá mais jogar Forest, pois já jogou Swamp. Assim, a IA do jogo seguiu as regras, mas o fez mal. Pode ser melhorado.
O planejamento pode encontrar uma lista de ações que levam o jogo ao estado desejado. Assim como cada quadrado num caminho tinha vizinhos (na localização de caminhos), cada acção num plano também tem vizinhos ou sucessores. Podemos procurar essas ações e as ações subsequentes até atingirmos o estado desejado.
Em nosso exemplo, o resultado desejado é “convocar uma criatura, se possível”. No início do turno, vemos apenas duas ações possíveis permitidas pelas regras do jogo:
1. Jogue Swamp (resultado: Swamp no jogo)
2. Jogue Floresta (resultado: Floresta no jogo)
Cada ação realizada pode levar a outras ações e encerrar outras, novamente dependendo das regras do jogo. Imagine que jogamos o Pântano - isso removerá o Pântano como a próxima etapa (já o jogamos) e também removerá a Floresta (porque de acordo com as regras você pode jogar uma carta de terreno por turno). Depois disso, a IA adiciona a obtenção de 1 mana preta como próxima etapa, porque não há outras opções. Se ele seguir em frente e escolher Tap the Swamp, ele receberá 1 unidade de mana preta e não poderá fazer nada com ela.
1. Jogue Swamp (resultado: Swamp no jogo)
1.1 Pântano “Tap” (resultado: Pântano “virado”, +1 unidade de mana preta)
Nenhuma ação disponível - FIM
2. Jogue Floresta (resultado: Floresta no jogo)
A lista de ações foi curta, chegamos a um beco sem saída. Repetimos o processo para a próxima etapa. Jogamos Forest, abrimos a ação “get 1 mana verde”, que por sua vez abrirá a terceira ação - convocar Elvish Mystic.
1. Jogue Swamp (resultado: Swamp no jogo)
1.1 Pântano “Tap” (resultado: Pântano “virado”, +1 unidade de mana preta)
Nenhuma ação disponível - FIM
2. Jogue Floresta (resultado: Floresta no jogo)
2.1 “Virar” Floresta (resultado: Floresta é “virada”, +1 unidade de mana verde)
2.1.1 Invocar Elvish Mystic (resultado: Elvish Mystic em jogo, -1 mana verde)
Nenhuma ação disponível - FIM
Finalmente, exploramos todas as ações possíveis e encontramos um plano que invoca uma criatura.
Este é um exemplo muito simplificado. É aconselhável escolher o melhor plano possível, ao invés de qualquer plano que atenda a alguns critérios. Geralmente é possível avaliar potenciais planos com base no resultado ou benefício global da sua implementação. Você pode ganhar 1 ponto por jogar uma carta de terreno e 3 pontos por invocar uma criatura. Jogar Swamp seria um plano de 1 ponto. E jogar Forest → Tap the Forest → convocar Elvish Mystic dará imediatamente 4 pontos.
É assim que o planejamento funciona em Magic: The Gathering, mas a mesma lógica se aplica em outras situações. Por exemplo, mover um peão para abrir espaço para o bispo se mover no xadrez. Ou proteja-se atrás de uma parede para filmar com segurança no XCOM assim. Em geral, você entendeu.
Planejamento aprimorado
Às vezes, há muitas ações potenciais para considerar todas as opções possíveis. Voltando ao exemplo de Magic: The Gathering: digamos que no jogo e na sua mão existam vários cards de terreno e de criatura - o número de combinações possíveis de movimentos pode chegar a dezenas. Existem várias soluções para o problema.
O primeiro método é o encadeamento reverso. Em vez de tentar todas as combinações, é melhor começar pelo resultado final e tentar encontrar um caminho direto. Em vez de ir da raiz da árvore até uma folha específica, movemo-nos na direção oposta – da folha à raiz. Este método é mais fácil e rápido.
Se o inimigo tiver 1 ponto de vida, você poderá encontrar o plano “causar 1 ou mais danos”. Para conseguir isso, uma série de condições devem ser atendidas:
1. O dano pode ser causado por um feitiço - ele deve estar em mãos.
2. Para lançar um feitiço, você precisa de mana.
3. Para obter mana, você precisa jogar uma carta de terreno.
4. Para jogar uma carta de terreno, você precisa tê-la em sua mão.
Outra maneira é a melhor pesquisa. Em vez de tentar todos os caminhos, escolhemos o mais adequado. Na maioria das vezes, esse método fornece o plano ideal sem custos desnecessários de pesquisa. A* é uma forma de melhor primeira busca – ao examinar desde o início as rotas mais promissoras, ele já consegue encontrar o melhor caminho sem precisar verificar outras opções.
Uma opção de pesquisa interessante e cada vez mais popular é o Monte Carlo Tree Search. Em vez de adivinhar quais planos são melhores que outros ao escolher cada ação subsequente, o algoritmo escolhe sucessores aleatórios em cada etapa até chegar ao final (quando o plano resultou em vitória ou derrota). O resultado final é então usado para aumentar ou diminuir o peso das opções anteriores. Ao repetir esse processo várias vezes seguidas, o algoritmo dá uma boa estimativa de qual é o melhor próximo movimento, mesmo que a situação mude (se o inimigo tomar medidas para interferir no jogador).
Nenhuma história sobre planejamento em jogos estaria completa sem o Planejamento de Ação Orientado a Objetivos ou GOAP (planejamento de ação orientado a objetivos). Este é um método amplamente utilizado e discutido, mas além de alguns detalhes distintivos, é essencialmente o método de encadeamento reverso de que falamos anteriormente. Se o objetivo era “destruir o jogador” e o jogador está protegido, o plano poderia ser: destruir com uma granada → pegá-la → jogá-la.
Geralmente existem vários objetivos, cada um com sua prioridade. Se o objetivo de maior prioridade não puder ser concluído (nenhuma combinação de ações cria um plano de “matar o jogador” porque o jogador não está visível), a IA retornará para objetivos de menor prioridade.
Treinamento e adaptação
Já dissemos que a IA de jogos geralmente não utiliza aprendizado de máquina porque não é adequada para gerenciar agentes em tempo real. Mas isso não significa que você não possa pedir algo emprestado nesta área. Queremos um oponente em um jogo de tiro com quem possamos aprender algo. Por exemplo, descubra as melhores posições no mapa. Ou um oponente em um jogo de luta que bloquearia os movimentos combinados frequentemente usados pelo jogador, motivando-o a usar outros. Portanto, o aprendizado de máquina pode ser bastante útil nessas situações.
Estatísticas e Probabilidades
Antes de entrarmos em exemplos complexos, vamos ver até onde podemos ir tomando algumas medidas simples e usando-as para tomar decisões. Por exemplo, estratégia em tempo real – como determinamos se um jogador pode lançar um ataque nos primeiros minutos do jogo e que defesa preparar contra isso? Podemos estudar as experiências passadas de um jogador para entender quais podem ser as reações futuras. Para começar, não temos esses dados brutos, mas podemos coletá-los – toda vez que a IA joga contra um humano, ela pode registrar o momento do primeiro ataque. Após algumas sessões, obteremos uma média do tempo que o jogador levará para atacar no futuro.
Há também um problema com os valores médios: se um jogador correu 20 vezes e jogou lentamente 20 vezes, então os valores exigidos estarão em algum lugar no meio, e isso não nos dará nada de útil. Uma solução é limitar os dados de entrada - as últimas 20 peças podem ser levadas em consideração.
Uma abordagem semelhante é usada ao estimar a probabilidade de certas ações, assumindo que as preferências passadas do jogador serão as mesmas no futuro. Se um jogador nos atacar cinco vezes com bola de fogo, duas vezes com raio e uma vez com corpo a corpo, é óbvio que ele prefere bola de fogo. Vamos extrapolar e ver a probabilidade de usar armas diferentes: bola de fogo=62,5%, raio=25% e corpo a corpo=12,5%. Nossa IA de jogo precisa se preparar para se proteger do fogo.
Outro método interessante é utilizar o Classificador Naive Bayes para estudar grandes quantidades de dados de entrada e classificar a situação para que a IA reaja da forma desejada. Os classificadores bayesianos são mais conhecidos por seu uso em filtros de spam de e-mail. Lá eles examinam as palavras, comparam-nas com onde essas palavras apareceram antes (em spam ou não) e tiram conclusões sobre os e-mails recebidos. Podemos fazer a mesma coisa mesmo com menos insumos. Com base em todas as informações úteis que a IA vê (como quais unidades inimigas são criadas, ou quais feitiços elas usam, ou quais tecnologias elas pesquisaram) e o resultado final (guerra ou paz, atacar ou defender, etc.) - escolheremos o comportamento desejado da IA.
Todos esses métodos de treinamento são suficientes, mas é aconselhável utilizá-los com base em dados de teste. A IA aprenderá a se adaptar às diferentes estratégias usadas pelos seus testadores. A IA que se adapta ao jogador após o lançamento pode se tornar muito previsível ou muito difícil de derrotar.
Adaptação baseada em valor
Dado o conteúdo do nosso mundo de jogo e as regras, podemos alterar o conjunto de valores que influenciam a tomada de decisão, em vez de simplesmente usar os dados de entrada. Nós fazemos isso:
- Deixe a IA coletar dados sobre o estado do mundo e os principais eventos durante o jogo (como acima).
- Vamos alterar alguns valores importantes com base nesses dados.
- Implementamos nossas decisões com base no processamento ou avaliação desses valores.
Por exemplo, um agente tem várias salas para escolher em um mapa de tiro em primeira pessoa. Cada quarto tem um valor próprio, que determina o quão desejável é a visita. A IA escolhe aleatoriamente para qual sala ir com base no valor. O agente então lembra em qual sala ele foi morto e reduz seu valor (a probabilidade de ele retornar para lá). Da mesma forma, para a situação inversa - se o agente destruir muitos oponentes, o valor da sala aumenta.
Modelo de Markov
E se usássemos os dados coletados para fazer previsões? Se nos lembrarmos de cada sala em que vemos um jogador durante um determinado período de tempo, preveremos para qual sala o jogador poderá ir. Ao rastrear e registrar os movimentos do jogador pelas salas (valores), podemos prevê-los.
Tomemos três quartos: vermelho, verde e azul. E também as observações que registamos enquanto assistíamos à sessão de jogo:
O número de observações em cada sala é quase igual - ainda não sabemos onde fazer um bom local para uma emboscada. A coleta de estatísticas também é complicada pelo reaparecimento dos jogadores, que aparecem uniformemente no mapa. Mas os dados sobre a próxima sala em que eles entram após aparecerem no mapa já são úteis.
Percebe-se que a sala verde combina com os jogadores - a maioria das pessoas passa da sala vermelha para ela, 50% das quais permanecem lá. O quarto azul, pelo contrário, não é popular; quase ninguém vai lá e, se vai, não fica muito tempo.
Mas os dados nos dizem algo mais importante: quando um jogador está em uma sala azul, a próxima sala em que o vemos será vermelha, não verde. Embora a sala verde seja mais popular que a sala vermelha, a situação muda se o jogador estiver na sala azul. O próximo estado (ou seja, a sala para a qual o jogador irá) depende do estado anterior (ou seja, a sala em que o jogador está atualmente). Como exploramos as dependências, faremos previsões mais precisas do que se simplesmente contássemos as observações de forma independente.
A previsão de um estado futuro com base em dados de um estado passado é chamada de modelo de Markov, e esses exemplos (com salas) são chamados de cadeias de Markov. Como os padrões representam a probabilidade de mudanças entre estados sucessivos, eles são exibidos visualmente como FSMs com uma probabilidade em torno de cada transição. Anteriormente, usávamos FSM para representar o estado comportamental em que um agente se encontrava, mas este conceito se estende a qualquer estado, esteja ele associado ao agente ou não. Neste caso, os estados representam a sala que o agente ocupa:
Esta é uma maneira simples de representar a probabilidade relativa de mudanças de estado, dando à IA alguma capacidade de prever o próximo estado. Você pode antecipar vários passos à frente.
Se um jogador estiver na sala verde, há 50% de chance de ele permanecer lá na próxima vez que for observado. Mas quais são as chances de ele ainda estar lá mesmo depois? Não só existe a chance de o jogador ter permanecido na sala verde após duas observações, mas também existe a chance de ele ter saído e retornado. Aqui está a nova tabela levando em consideração os novos dados:
Mostra que a chance de ver o jogador na sala verde após duas observações será igual a 51% - 21% de que ele será da sala vermelha, 5% deles de que o jogador visitará a sala azul entre eles, e 25% que o jogador não sairá da sala verde.
A tabela é simplesmente uma ferramenta visual – o procedimento requer apenas a multiplicação das probabilidades em cada etapa. Isso significa que você pode olhar para um futuro distante com uma ressalva: presumimos que a chance de entrar em uma sala depende inteiramente da sala atual. Isso é chamado de Propriedade de Markov – o estado futuro depende apenas do presente. Mas isto não é cem por cento preciso. Os jogadores podem mudar as decisões dependendo de outros fatores: nível de saúde ou quantidade de munição. Como não registramos esses valores, nossas previsões serão menos precisas.
N-gramas
E quanto ao exemplo de um jogo de luta e à previsão dos movimentos combinados do jogador? O mesmo! Mas em vez de um estado ou evento, examinaremos todas as sequências que compõem um ataque combinado.
Uma maneira de fazer isso é armazenar cada entrada (como Kick, Punch ou Block) em um buffer e escrever todo o buffer como um evento. Assim, o jogador pressiona repetidamente Kick, Kick, Punch para usar o ataque SuperDeathFist, o sistema de IA armazena todas as entradas em um buffer e lembra as três últimas usadas em cada etapa.
(As linhas em negrito são quando o jogador lança o ataque SuperDeathFist.)
A IA verá todas as opções quando o jogador selecionar Chute, seguido de outro Chute, e então perceberá que a próxima entrada é sempre Soco. Isso permitirá que o agente preveja o movimento combinado do SuperDeathFist e bloqueie-o, se possível.
Essas sequências de eventos são chamadas de N-gramas, onde N é o número de elementos armazenados. No exemplo anterior era um 3 gramas (trigrama), o que significa: as duas primeiras entradas são usadas para prever a terceira. Conseqüentemente, em 5 gramas, as primeiras quatro entradas predizem a quinta e assim por diante.
O designer precisa escolher cuidadosamente o tamanho dos N gramas. Um N menor requer menos memória, mas também armazena menos histórico. Por exemplo, um 2 gramas (bigrama) registrará Kick, Kick ou Kick, Punch, mas não será capaz de armazenar Kick, Kick, Punch, então a IA não responderá ao combo SuperDeathFist.
Por outro lado, números maiores requerem mais memória e a IA será mais difícil de treinar, pois haverá muito mais opções possíveis. Se você tivesse três entradas possíveis de Chute, Soco ou Bloqueio, e usássemos um de 10 gramas, seriam cerca de 60 mil opções diferentes.
O modelo bigrama é uma cadeia de Markov simples - cada par estado passado/estado atual é um bigrama, e você pode prever o segundo estado com base no primeiro. Os N-gramas de 3 gramas e maiores também podem ser considerados cadeias de Markov, onde todos os elementos (exceto o último no N-grama) juntos formam o primeiro estado e o último elemento o segundo. O exemplo do jogo de luta mostra a chance de transição do estado Kick and Kick para o estado Kick and Punch. Ao tratar múltiplas entradas do histórico de entrada como uma única unidade, estamos essencialmente transformando a sequência de entrada em parte de todo o estado. Isso nos dá a propriedade de Markov, que nos permite usar cadeias de Markov para prever a próxima entrada e adivinhar qual será o próximo movimento combinado.
Conclusão
Conversamos sobre as ferramentas e abordagens mais comuns no desenvolvimento da inteligência artificial. Também analisamos as situações em que eles precisam ser usados e onde são especialmente úteis.
Isso deve ser suficiente para compreender os fundamentos da IA do jogo. Mas, é claro, nem todos esses são métodos. Menos populares, mas não menos eficazes, incluem:
- algoritmos de otimização, incluindo subida de colinas, descida gradiente e algoritmos genéticos
- algoritmos de pesquisa/agendamento adversários (remoção minimax e alfa-beta)
- métodos de classificação (perceptrons, redes neurais e máquinas de vetores de suporte)
- sistemas para processar a percepção e memória dos agentes
- abordagens arquitetônicas para IA (sistemas híbridos, arquiteturas de subconjuntos e outras formas de sobrepor sistemas de IA)
- ferramentas de animação (planejamento e coordenação de movimento)
- fatores de desempenho (nível de detalhe, a qualquer momento e algoritmos de divisão de tempo)
Recursos relacionados à Internet:
1. GameDev.net tem E .
2. contém muitas apresentações e artigos sobre uma ampla variedade de tópicos relacionados ao desenvolvimento de IA de jogos.
3. inclui tópicos do GDC AI Summit, muitos dos quais estão disponíveis gratuitamente.
4. Materiais úteis também podem ser encontrados no site .
5. Tommy Thompson, pesquisador de IA e desenvolvedor de jogos, faz vídeos no YouTube com uma explicação e estudo de IA em jogos comerciais.
Livros sobre o tema:
1. A série de livros Game AI Pro é uma coleção de pequenos artigos que explicam como implementar recursos específicos ou como resolver problemas específicos.
2. A série AI Game Programming Wisdom é a antecessora da série Game AI Pro. Ele contém métodos mais antigos, mas quase todos são relevantes até hoje.
3. é um dos textos básicos para quem deseja compreender o campo geral da inteligência artificial. Este não é um livro sobre desenvolvimento de jogos – ele ensina o básico da IA.
Fonte: habr.com