Diferença entre Árvores de Decisão e Árvores de Comportamento para Game AI

64

Quais são algumas diferenças entre as árvores de decisão e as árvores de comportamento para o desenvolvimento de jogos de IA? Para quais aplicativos você usaria um sobre o outro?

Trabalhador autonomo
fonte

Respostas:

80

Os dois são bem diferentes. O indicador real está nos nomes. As árvores de decisão são apenas para tomar decisões. As árvores de comportamento são para controlar o comportamento. Permita-me explicar. Uma grande diferença nos dois é a maneira como eles são percorridos, da mesma forma que são dispostos e os 'tipos' de nós são diferentes.

As árvores de decisão são avaliadas da raiz à folha, sempre. Para que uma árvore de decisão funcione corretamente, os nós filhos de cada pai devem representar todas as decisões possíveis para esse nó. Se um nó puder ser respondido "Sim, Não, Talvez", deverá haver três filhos, nó Sim, Nenhum nó e Talvez. Isso significa que sempre há um nó inferior para percorrer, até atingir um nó final. O percurso está sempre baixo. Forma gráfica:

insira a descrição da imagem aqui

Bem simples. Começamos pela raiz e, com base em alguma avaliação, escolhemos 1, 2 ou 3. Nós escolhemos 3. Em seguida, fazemos outra avaliação e escolhemos B ou B ... Bem, reutilizei o gráfico abaixo, desculpe. Finja que o B à esquerda é mágico B.

As árvores de comportamento têm uma avaliação diferente. Na primeira vez em que são avaliados (ou redefinidos), iniciam da raiz (os nós pais agem como seletores) e cada filho é avaliado da esquerda para a direita. Os nós filhos são ordenados com base em sua prioridade. Se todas as condições de um nó filho forem atendidas, seu comportamento será iniciado. Quando um nó inicia um comportamento, esse nó é definido como 'em execução' e retorna o comportamento. Na próxima vez em que a árvore for avaliada, ela verifica novamente os nós de maior prioridade e, quando se trata de um nó 'em execução', sabe continuar de onde parou. O nó pode ter uma sequência de ações e condições antes de atingir um estado final. Se alguma condição falhar, a travessia retornará ao pai. O seletor pai passa para o próximo filho prioritário. Vou tentar uma forma gráfica aqui:

insira a descrição da imagem aqui

A travessia começa na raiz, vai para o filho 1, verifica a condição do filho (algo como "algum inimigo por perto?"). A condição falha e a travessia volta para a árvore para avançar para o nó dois. O nó 2 tem uma ação que é executada (talvez algo como encontrar um caminho). Depois, um comportamento (algo como seguir o caminho). O caminho a seguir está definido para execução e a árvore retorna seu estado como executando. Os nós que falharam ou foram concluídos são retornados para 'Pronto'. Então, da próxima vez que verificarmos, começaremos novamente com o nó de maior prioridade. Como falha novamente, prosseguimos para o nó dois. Lá descobrimos que temos um comportamento em execução. Também descobrimos que o comportamento foi concluído, portanto, marcamos como concluído e retornamos isso. A árvore é redefinida e pronta para ser usada novamente.

Como você pode ver, as árvores de comportamento são mais complexas. As árvores de comportamento são mais poderosas e permitem comportamentos mais complexos. As árvores de decisão são fáceis de entender e simples de implementar. Portanto, você usaria árvores de comportamento quando quiser um comportamento mais complexo ou mais controle sobre o comportamento. As árvores de decisão podem ser usadas como parte de uma árvore de comportamento ou usadas sozinhas para IA simples.

Alguma boa compreensão de como as árvores de comportamento são analisadas pode ser encontrada aqui .

MichaelHouse
fonte
Ótima explicação e ilustrações. Então, quando você diz "Se todas as condições de um nó filho forem atendidas ...", Seletores e Sequências contêm condições ou apenas nós folha, ou seja, as Ações?
Free Lancer
11
Os nós filhos são comportamentos, ações, condições ou seletores com mais filhos. Eles são avaliados da esquerda para a direita.
MichaelHouse
Ótimo post, apesar de achar que ainda tenho uma pergunta pendente (postarei separadamente). O que você usou para criar os GIFs animados?
me--
0-2-A não deve ser reproduzido novamente se 0-2-B estiver em execução ??? github.com/pirobot/pi_trees/issues/1
devside
@ nopnop77 Não se o condicional 0-2 ainda for avaliado como 0-2-B. Você pode ver que 0-2 é reavaliado, mas mais uma vez não resulta em A sendo selecionado.
MichaelHouse