WEBVTT

00:11.460 --> 00:15.400
Seria impossível começar a falar sobre os meandros de A. EU.

00:15.420 --> 00:21.770
sem um breve histórico em 'Graph Theory'. Quase todos A. EU. As técnicas de uso

00:21.770 --> 00:27.870
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.

00:28.470 --> 00:31.950
Os nós são representados graficamente como círculos ... e arestas

00:31.950 --> 00:38.430
são as linhas que os conectam. Um gráfico pode ser visualizado como nós, representando locais e

00:38.430 --> 00:40.490
arestas como caminhos que os conectam.

00:40.650 --> 00:47.220
Um gráfico pode ser não direcionado (o que significa que os caminhos entre os nós podem ser percorridos nas duas

00:47.490 --> 00:51.480
direções) ou direcionado (nesse caso, os caminhos são de sentido único).

00:51.540 --> 00:54.260
Pense nisso como uma diferença

00:54.300 --> 01:00.810
entre ruas de mão dupla e mão única. Nós e arestas podem ser desenhados onde os nós representam coordenadas,

01:00.810 --> 01:06.520
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.

01:06.990 --> 01:09.930
Nós e arestas podem ter valores associados.

01:10.110 --> 01:15.720
Esses valores podem ser a distância entre os nós (como aqueles que representam distâncias no plano de vôo) ou

01:16.320 --> 01:20.850
o tempo necessário para concluir uma ação (como um nó no plano de ação).

01:21.180 --> 01:26.910
As maneiras pelas quais os gráficos são úteis no jogo A. EU. ficará evidente à medida que progredirmos neste curso.

01:27.630 --> 01:30.580
Se você acha que os gráficos parecem familiares, é porque eles são.

01:30.900 --> 01:36.990
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

01:36.990 --> 01:43.080
ser usados para uma infinidade de aplicativos em que você precisa passar de um estado para

01:43.080 --> 01:46.830
outro, seja um estado real ou um estado conceitual.

01:46.830 --> 01:52.710
Neste exemplo, um gráfico está sendo usado para definir os locais em um jogo baseado em blocos e a

01:52.710 --> 01:59.130
quantidade de esforço para mover de um bloco para outro. Os valores colocados nas bordas são geralmente chamados de 'Valores de

01:59.130 --> 02:02.140
Utilidade', independentemente de representarem tempos, distâncias, esforço, custos ou

02:02.160 --> 02:08.790
qualquer outro valor que um NPC possa usar para tomar uma decisão. Vamos considerar a situação em que

02:08.790 --> 02:13.300
um NPC deseja passar do bloco C2 para o A2.

02:13.590 --> 02:17.760
Existem 2 caminhos possíveis. Para decidir qual caminho seguir,

02:17.760 --> 02:22.700
o NPC pode adicionar todos os valores de utilidade ao longo de cada caminho.

02:22.730 --> 02:29.090
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

02:29.090 --> 02:35.240
o caminho mais longo (sobre a ponte) será menos esforço. Para trabalhar com um gráfico, é

02:35.240 --> 02:39.650
necessário haver um método eficiente de pesquisa nos nós.

02:39.650 --> 02:43.540
Existem dois algoritmos básicos de alto nível para pesquisar nos nós.

02:43.760 --> 02:51.350
O primeiro é chamado de 'Pesquisa em Largura-Primeira'. Em uma pesquisa abrangente, o NPC marca sua

02:51.410 --> 02:59.480
localização atual (ou nó) como 1, depois numera todos os nós adjacentes como 2, depois todos os

02:59.560 --> 03:04.590
nós adjacentes como 3 etc. até que o nó de destino seja alcançado.

03:04.610 --> 03:09.470
Em seguida, conta para trás, em 1s, para o início, para encontrar um caminho para a meta.

03:09.680 --> 03:16.280
A pesquisa abrangente examina todos os nós possíveis no gráfico para encontrar o melhor caminho, mas devido à

03:16.340 --> 03:23.630
sua minúcia, consome tempo e não é o ideal. Uma 'busca em profundidade' é muito mais simples e rápida, mas menos eficaz.

03:23.780 --> 03:31.250
Em vez de encontrar o MELHOR caminho, ele encontra um caminho. Começando na posição do NPC, um nó adjacente é

03:31.250 --> 03:33.770
encontrado e numerado. Em seguida, um

03:33.800 --> 03:35.390
nó adjacente é encontrado e numerado.

03:35.390 --> 03:41.630
Isso continua até que um beco sem saída seja atingido, quando retornamos ao último nó em que

03:41.630 --> 03:45.390
havia outra direção a tentar e seguimos nessa direção.

03:45.860 --> 03:51.560
É como a abordagem que você pode adotar para sair de um labirinto. Quando o destino é encontrado, os nós

03:51.560 --> 03:57.770
são contados novamente para trás, para fornecer o caminho. O algoritmo mais popular usado para encontrar caminhos nos

03:57.770 --> 04:03.300
gráficos usados nos jogos devido à sua eficiência em encontrar o caminho mais curto, é o algoritmo

04:03.350 --> 04:04.360
A *.

04:04.370 --> 04:08.230
É um pouco mais complexo que os outros dois métodos e funciona assim ...

04:08.240 --> 04:10.780
Primeiro, todos os nós no gráfico são numerados.

04:10.800 --> 04:15.050
Em seguida, criamos duas listas: uma lista 'aberta' e uma lista 'fechada'.

04:15.170 --> 04:18.620
Eles acompanharão os nós que visitamos e processamos.

04:18.710 --> 04:22.940
Cada nó recebe 4 valores que são usados no cálculo do caminho.

04:22.940 --> 04:26.750
Primeiro, eles recebem um valor 'heurístico' representado por 'H'.

04:26.870 --> 04:32.320
A 'heurística' é o custo estimado da transferência de um nó individual para o destino.

04:32.540 --> 04:35.980
Você pode usar qualquer método que desejar para calcular esse valor.

04:36.260 --> 04:42.060
Você pode usar uma 'distância linear' ou contar o 'número de linhas e colunas'.

04:42.190 --> 04:46.180
O segundo valor é 'Custo de Movimento' representado por 'G'.

04:46.450 --> 04:51.370
Esse valor é essencialmente o utilitário para mover para o nó a partir de outro nó.

04:51.370 --> 04:55.140
Isso pode se basear na distância real de um nó a outro ou no custo de

04:55.480 --> 05:02.660
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

05:02.660 --> 05:09.650
H e G e o chamamos de 'F' e armazenamos o nó pai, que é o nó

05:09.650 --> 05:12.240
mais próximo ao longo do caminho.

05:12.470 --> 05:14.490
Vamos dar uma olhada em um exemplo.

05:14.510 --> 05:16.490
Começamos colocando o nó inicial (neste

05:16.550 --> 05:23.180
caso, 50) na lista 'Fechado', pois esse é o local que visitamos. Em seguida, procuramos os vizinhos que não estão

05:23.180 --> 05:28.250
bloqueados e não estão na lista fechada e os adicionamos à lista 'Abrir'.

05:29.070 --> 05:35.640
Em seguida, calculamos a heurística para cada nó na lista aberta. Nesse caso, usaremos a

05:35.640 --> 05:39.830
distância linear do nó ao destino.

05:39.920 --> 05:43.820
Então calculamos nosso custo de movimento para ir do nó inicial ao vizinho.

05:44.060 --> 05:50.450
Novamente, usamos uma distância linear. Os vizinhos horizontais e verticais estão a uma distância de 1, enquanto os vizinhos

05:50.450 --> 05:57.230
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,

05:57.320 --> 06:00.340
'F', que é H + G, é calculado.

06:00.410 --> 06:05.120
Enquanto estamos fazendo isso, todos os vizinhos são vinculados ao nó

06:05.120 --> 06:11.420
atual, tornando o nó inicial seu pai. Sem mais nós para examinar na lista aberta, agora obtemos o nó na lista

06:11.420 --> 06:13.340
aberta com o menor valor de F.

06:13.370 --> 06:18.860
Este se torna um novo local para começar a procurar os vizinhos novamente. O novo nó de localização é

06:18.860 --> 06:25.880
adicionado à lista fechada como tendo sido visitado. Quaisquer vizinhos que não estejam bloqueados, fechados ou que já estejam na lista aberta

06:26.000 --> 06:27.350
serão adicionados à lista aberta.

06:27.350 --> 06:31.850
O valor H é calculado para quaisquer novos nós na lista aberta.

06:31.850 --> 06:38.380
O valor G também é calculado, mas desta vez é o 'custo de movimento + o custo de movimento anterior'.

06:38.660 --> 06:48.170
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 é

06:48.170 --> 06:48.790
1.

06:49.010 --> 06:57.680
Isso fornece um valor G final de 2 ... e para 32, seu valor F será 7. Para qualquer um dos vizinhos do local atual

06:57.680 --> 07:06.050
ainda na lista aberta (neste caso, 40), um novo valor G é calculado. Se o novo valor G for menor que o valor

07:06.050 --> 07:07.720
atual G, o

07:07.970 --> 07:13.880
valor G dos nós será alterado e seu pai será atualizado para o local atual.

07:13.970 --> 07:23.450
Neste exemplo, um novo valor G proveniente do nó 41 seria 1, mais um custo de

07:23.450 --> 07:29.020
movimento horizontal de 1, resultando em um valor 2.

07:29.150 --> 07:32.530
2 não é menor que 40s do valor G atual

07:32.690 --> 07:35.220
e, portanto, o nó permanece inalterado.

07:35.330 --> 07:41.840
Qualquer vizinho sem um pai é designado ao local atual e o processo começa novamente, procurando

07:41.840 --> 07:45.650
o nó com o menor valor F na lista

07:45.640 --> 07:50.360
aberta para visitar a seguir. O processo termina quando estamos a um nó do final.

07:50.480 --> 07:55.710
Neste ponto, temos um link de pais que levam todo o caminho de volta ao início, que, quando revertidos,

07:55.710 --> 08:02.440
fornecem um caminho desde o local de início até o destino. O Unity usa o algoritmo A * para encontrar caminhos

08:02.510 --> 08:03.980
em sua navmesh.

08:03.980 --> 08:09.590
Essa construção fornece uma maneira poderosa de programar a navegação e evitar em nossos projetos.

08:09.590 --> 08:15.340
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ê

08:15.680 --> 08:20.840
os verá surgir em todos os lugares, pois são um item básico da

08:20.840 --> 08:22.110
inteligência artificial.

08:22.340 --> 08:28.140
Embora existam numerosos algoritmos para percorrer gráficos, quando se trata de jogos, nada supera A *

08:28.370 --> 08:31.060
e você encontrará muitos recursos para suportá-lo.
