E aê pessoal!
Durante a reestruturação da engine do beat the plague eu me peguei pensando sobre o comportamento dos objetos, inimigos, plantas, entre outras coisas. Como eu estava mudando o código referente aos objetos, resolvi pesquisar sobre um jeito melhor de se fazer a inteligência artificial, e acabei descobrindo um tal de behaviour tree.
Primeiro vamos ver como estava a codificação dos inimigos do jogo…
Eles foram programados a partir de um conceito chamado “Maquina de Estados Finita”. Essa estrutura é baseada na escolha das ações a partir do estado atual do objeto, e a partir dessas ações, o estado também é alterado.
Segue um diagrama do comportamento do besouro no jogo a partir da máquina de estados.
Diagrama de Máquina de Estados
O Besouro começa no estado “Escolhendo Alvo”. Quando o alvo é escolhido, o estado muda para “Andando”. O inseto anda em direção ao alvo até que ele seja alcançado, mudando o estado para “Comendo” que será executado até que a planta morra, fazendo o estado mudar para “Escolhendo Alvo” e iniciando o ciclo novamente.
A maquina de estados finita é programada como um único bloco, normalmente estando contida na própria classe do objeto de jogo. Para quem está curioso como fica o código, aqui está um exemplo.
Código da Máquina de estados do Besouro
Esse código funciona muito bem quando eu já tenho todos os comportamentos definidos e não vou alterar. Mas, e se eu quiser colocar um novo comportamento? Vou ter que adicionar novos blocos de código na classe do Besouro até que ela fique grande demais, desorganizada demais, ou ruim demais para debugar.
Uma solução para esses problemas é a utilização de Behaviour Trees.
Uma Behaviour Tree
A Behaviour tree separa o comportamento de seus Agentes (objetos de jogo), deixando a estrutura mais organizada, mais fácil de se debugar e mais simples caso a inteligência de algum agente tenha que ser alterada.
A Behaviour Tree é uma estrutura de dados formadas por Nós de Comportamento. Existem 3 tipos de Nós:
Nó Folha ou Tarefa
Esse nó sempre está presente nas pontas da árvore, e ela representa um comportamento do Agente.
Tarefa
A tarefa é formada pela combinação de duas variantes: sua condição de execução, e sua ação propriamente dita. Um exemplo de Tarefa pode ser a seguinte: Se o inimigo estiver à minha esquerda (Condição), Correr para a direita (Ação).
Para aumentar as possibilidades sobre a árvore de comportamentos (Behaviour Tree) existem nós auxiliares, onde os mais comuns são o Seletor e o de Sequência.
Nó de Sequência
O nó de sequência permite que cada nó filho seja verificado e executado um após o outro, sendo que seu comportamento só será de sucesso caso todos os filhos obtenham sucesso.
Nó de Sequência
O Nó de Sequência inicia sua tarefa verificando o seu primeiro nó filho (podendo ser ele de qualquer tipo).
Caso o primeiro nó tenha sucesso na sua ação, o nó de sequência executará o filho seguinte.
Caso qualquer um dos nós filhos tenham fracassado ou sua condição não foi alcançada, o nó de sequência retorna ao nível acima com a informação de fracasso.
O nó de sequência terá sucesso apenas quando todos os filhos obtiverem sucesso na sua execução e condição.
Nó Seletor
O nó seletor faz com que APENAS UMA ação filha seja efetuada.
O nó seletor inicia da mesma forma que o de sequência, mas caso um nó filho tenha falhado, ele passa para o próximo até encontrar o primeiro nó filho que tenha sucesso.
Caso o nó filho tenha sucesso em sua execução, o nó seletor retorno para o nível acima com o estado de sucesso e não executa os filhos restantes.
O nó seletor só fracassa quando nenhum de seus filhos obtiverem sucesso.
Exemplo
No caso do jogo Beat the Plague eu posso utilizar a Behaviour Tree para fazer a inteligência do Besouro. Um exemplo com o comportamento atual seria esse:
A árvore teria um nó seletor raíz que selecionaria apenas uma dentre Tarefas filhas.
O seletor iniciará sua busca pelo primeiro nó filho.
Se o besouro não tiver um alvo, o Besouro executa a ação “Escolher Alvo” e retorna sucesso para o seletor, que para a sua busca.
Caso a tarefa 1 não tenha sucesso, o seletor verifica a tarefa 2: se eu não alcancei o alvo, então “Ande” em sua direção e retorne sucesso.
Caso as tarefas 1 e 2 tenham fracassado, verifique a 3. Caso o alvo estiver vivo, “Coma”.
Eu posso alterar a estrutura da árvore sem mexer na classe do besouro já que a mesma está desacoplada do Ator da ação. A estrutura das classes ficou mais ou menos assim:
E caso eu queira mudar a inteligência do Besouro, posso fazer sem nenhum problema. No caso, adiciono uma sequência de ações enquanto o Besouro não é ameaçado pelo jogador. Fazendo um esquema de patrulha (“fique um tempo parado” e “mova-se aleatoriamente”).
E é isso aê!
Caso alguém queira saber mais sobre o assunto pode acessar esses links:
http://aigamedev.com/open/article/bt-overview/
http://www.altdevblogaday.com/2011/02/24/introduction-to-behavior-trees/
(Behaviour Tree no jogo Halo 3)
http://www.bungie.net/images/Inside/publications/presentations/publicationsdes/engineering/nips07.pdf
(Apresentação da Crytek sobre Behaviour Trees. MUITO BOM!)
http://staff.science.uva.nl/~aldersho/GameProgramming/Papers/Coordinating_Agents_with_Behaviour_Trees.pdf
(Call Tree – Implementação de BT – A imagem (primeiro link) mostra uma behaviour tree pra um hadouken, e o segundo é um link pro projeto)
https://a248.e.akamai.net/camo.github.com/40da00b92e85ff9ff990c8b077a62fcc6a48c3f7/687474703a2f2f6a6a61636f6273736f6e2e6769746875622e636f6d2f63616c6c747265652f63747373732e706e67
https://github.com/jjacobsson/calltree
Comentem, xinguem, e deem sugestões entre outras coisas! Valeu!