Seria impossível começar a falar sobre os meandros de A. EU.
sem um breve histórico em 'Graph Theory'. Quase todos A. EU. As técnicas de uso
de jogos dependem de os programadores entenderem gráficos. Os gráficos neste contexto referem-se a uma coleção de nós e arestas.
Os nós são representados graficamente como círculos ... e arestas
são as linhas que os conectam. Um gráfico pode ser visualizado como nós, representando locais e
arestas como caminhos que os conectam.
Um gráfico pode ser não direcionado (o que significa que os caminhos entre os nós podem ser percorridos nas duas
direções) ou direcionado (nesse caso, os caminhos são de sentido único).
Pense nisso como uma diferença
entre ruas de mão dupla e mão única. Nós e arestas podem ser desenhados onde os nós representam coordenadas,
como aquelas em um plano de vôo ou como estados simbólicos em que a localização física no gráfico não faz sentido.
Nós e arestas podem ter valores associados.
Esses valores podem ser a distância entre os nós (como aqueles que representam distâncias no plano de vôo) ou
o tempo necessário para concluir uma ação (como um nó no plano de ação).
As maneiras pelas quais os gráficos são úteis no jogo A. EU. ficará evidente à medida que progredirmos neste curso.
Se você acha que os gráficos parecem familiares, é porque eles são.
Nós já fizemos um gráfico de waypoints e tivemos nosso NPC entre eles. Os gráficos são tão flexíveis que podem
ser usados para uma infinidade de aplicativos em que você precisa passar de um estado para
outro, seja um estado real ou um estado conceitual.
Neste exemplo, um gráfico está sendo usado para definir os locais em um jogo baseado em blocos e a
quantidade de esforço para mover de um bloco para outro. Os valores colocados nas bordas são geralmente chamados de 'Valores de
Utilidade', independentemente de representarem tempos, distâncias, esforço, custos ou
qualquer outro valor que um NPC possa usar para tomar uma decisão. Vamos considerar a situação em que
um NPC deseja passar do bloco C2 para o A2.
Existem 2 caminhos possíveis. Para decidir qual caminho seguir,
o NPC pode adicionar todos os valores de utilidade ao longo de cada caminho.
Nesse caso, os valores de utilidade não são sobre distância, são sobre dificuldade no terreno. A soma dos valores ao longo de cada caminho revela que
o caminho mais longo (sobre a ponte) será menos esforço. Para trabalhar com um gráfico, é
necessário haver um método eficiente de pesquisa nos nós.
Existem dois algoritmos básicos de alto nível para pesquisar nos nós.
O primeiro é chamado de 'Pesquisa em Largura-Primeira'. Em uma pesquisa abrangente, o NPC marca sua
localização atual (ou nó) como 1, depois numera todos os nós adjacentes como 2, depois todos os
nós adjacentes como 3 etc. até que o nó de destino seja alcançado.
Em seguida, conta para trás, em 1s, para o início, para encontrar um caminho para a meta.
A pesquisa abrangente examina todos os nós possíveis no gráfico para encontrar o melhor caminho, mas devido à
sua minúcia, consome tempo e não é o ideal. Uma 'busca em profundidade' é muito mais simples e rápida, mas menos eficaz.
Em vez de encontrar o MELHOR caminho, ele encontra um caminho. Começando na posição do NPC, um nó adjacente é
encontrado e numerado. Em seguida, um
nó adjacente é encontrado e numerado.
Isso continua até que um beco sem saída seja atingido, quando retornamos ao último nó em que
havia outra direção a tentar e seguimos nessa direção.
É como a abordagem que você pode adotar para sair de um labirinto. Quando o destino é encontrado, os nós
são contados novamente para trás, para fornecer o caminho. O algoritmo mais popular usado para encontrar caminhos nos
gráficos usados nos jogos devido à sua eficiência em encontrar o caminho mais curto, é o algoritmo
A *.
É um pouco mais complexo que os outros dois métodos e funciona assim ...
Primeiro, todos os nós no gráfico são numerados.
Em seguida, criamos duas listas: uma lista 'aberta' e uma lista 'fechada'.
Eles acompanharão os nós que visitamos e processamos.
Cada nó recebe 4 valores que são usados no cálculo do caminho.
Primeiro, eles recebem um valor 'heurístico' representado por 'H'.
A 'heurística' é o custo estimado da transferência de um nó individual para o destino.
Você pode usar qualquer método que desejar para calcular esse valor.
Você pode usar uma 'distância linear' ou contar o 'número de linhas e colunas'.
O segundo valor é 'Custo de Movimento' representado por 'G'.
Esse valor é essencialmente o utilitário para mover para o nó a partir de outro nó.
Isso pode se basear na distância real de um nó a outro ou no custo de
atravessar um tipo de trem, como no exemplo de ladrilhos que vimos com a ponte. Em seguida, armazenamos um cálculo que adiciona os valores
H e G e o chamamos de 'F' e armazenamos o nó pai, que é o nó
mais próximo ao longo do caminho.
Vamos dar uma olhada em um exemplo.
Começamos colocando o nó inicial (neste
caso, 50) na lista 'Fechado', pois esse é o local que visitamos. Em seguida, procuramos os vizinhos que não estão
bloqueados e não estão na lista fechada e os adicionamos à lista 'Abrir'.
Em seguida, calculamos a heurística para cada nó na lista aberta. Nesse caso, usaremos a
distância linear do nó ao destino.
Então calculamos nosso custo de movimento para ir do nó inicial ao vizinho.
Novamente, usamos uma distância linear. Os vizinhos horizontais e verticais estão a uma distância de 1, enquanto os vizinhos
diagonais estão a uma distância de 1. 4) O custo da mudança para esses nós se torna seu valor G. A partir disso,
'F', que é H + G, é calculado.
Enquanto estamos fazendo isso, todos os vizinhos são vinculados ao nó
atual, tornando o nó inicial seu pai. Sem mais nós para examinar na lista aberta, agora obtemos o nó na lista
aberta com o menor valor de F.
Este se torna um novo local para começar a procurar os vizinhos novamente. O novo nó de localização é
adicionado à lista fechada como tendo sido visitado. Quaisquer vizinhos que não estejam bloqueados, fechados ou que já estejam na lista aberta
serão adicionados à lista aberta.
O valor H é calculado para quaisquer novos nós na lista aberta.
O valor G também é calculado, mas desta vez é o 'custo de movimento + o custo de movimento anterior'.
Portanto, nesse caso, o nó 32 obtém o 'movimento G' de 41 + o 'custo da movimentação' de 41 para 32, que também é
1.
Isso fornece um valor G final de 2 ... e para 32, seu valor F será 7. Para qualquer um dos vizinhos do local atual
ainda na lista aberta (neste caso, 40), um novo valor G é calculado. Se o novo valor G for menor que o valor
atual G, o
valor G dos nós será alterado e seu pai será atualizado para o local atual.
Neste exemplo, um novo valor G proveniente do nó 41 seria 1, mais um custo de
movimento horizontal de 1, resultando em um valor 2.
2 não é menor que 40s do valor G atual
e, portanto, o nó permanece inalterado.
Qualquer vizinho sem um pai é designado ao local atual e o processo começa novamente, procurando
o nó com o menor valor F na lista
aberta para visitar a seguir. O processo termina quando estamos a um nó do final.
Neste ponto, temos um link de pais que levam todo o caminho de volta ao início, que, quando revertidos,
fornecem um caminho desde o local de início até o destino. O Unity usa o algoritmo A * para encontrar caminhos
em sua navmesh.
Essa construção fornece uma maneira poderosa de programar a navegação e evitar em nossos projetos.
Quando você pensa sobre isso, gráficos e seus nós e arestas são realmente uma coisa muito simples. À medida que progredimos no curso, você
os verá surgir em todos os lugares, pois são um item básico da
inteligência artificial.
Embora existam numerosos algoritmos para percorrer gráficos, quando se trata de jogos, nada supera A *
e você encontrará muitos recursos para suportá-lo.