WEBVTT

00:02.860 --> 00:06.940
Na palestra anterior, começamos a trabalhar em nossa API gráfica.

00:06.970 --> 00:13.510
Agora estamos no ponto em que estamos prontos para colocar a funcionalidade de um algoritmo de busca de caminhos

00:13.510 --> 00:14.290
A estrela.

00:14.620 --> 00:20.940
Portanto, provavelmente faz sentido apenas revisar o algoritmo aStar que examinamos na seção anterior.

00:20.950 --> 00:28.870
Portanto, temos um labirinto ou temos uma série de pontos de passagem que estão conectados com bordas que não são diferentes

00:28.870 --> 00:30.020
de um labirinto.

00:30.040 --> 00:36.280
Assim, no labirinto, cada quadrado era basicamente um nó, e se você pudesse ir de um quadrado para outro, então

00:36.280 --> 00:39.220
isso era uma borda ou um caminho entre eles.

00:39.340 --> 00:41.500
Portanto, temos que começar a posição.

00:41.500 --> 00:43.000
Temos uma posição de objetivo.

00:43.000 --> 00:45.690
Temos que calcular como passar por isso.

00:45.700 --> 00:52.600
Agora, há três valores sobre os quais vamos avaliar cada posição, e esse é o valor de

00:52.600 --> 00:59.440
PH, que é o custo de chegar à meta daquele nó, o valor G, que é o custo de chegar àquele

00:59.440 --> 00:59.920
nó.

00:59.920 --> 01:02.860
Portanto, quanto já custa chegar a esse nó desde o início.

01:02.860 --> 01:09.850
E então temos um valor H, que é a adição de ambas as coisas que dão ao nó geral seu tipo

01:09.850 --> 01:17.380
de custo holístico, eu acho que sobre como ele é adequado, como é o melhor a ser feito.

01:17.380 --> 01:22.630
Portanto, vamos escrever alguns destes algoritmos em nossa classe gráfica.

01:23.680 --> 01:24.160
Certo.

01:24.160 --> 01:31.540
Portanto, antes de tudo, vamos criar nossa heurística, que é basicamente nosso método que determinará

01:31.540 --> 01:33.700
o quão adequado é cada nó.

01:33.700 --> 01:39.760
E neste caso, vamos usar a distância do nó até o local final, que vai ser mais ou

01:39.760 --> 01:42.160
menos como o vôo dos corvos.

01:42.280 --> 01:47.410
Então é por isso que é chamado de holístico, acho que é o melhor palpite que se pode fazer porque não

01:47.410 --> 01:47.920
sabemos.

01:47.920 --> 01:51.700
Na verdade, não podemos voar diretamente para a posição final.

01:51.700 --> 01:57.550
Podemos ser capazes, mas de cada nó, essa será nossa melhor maneira de medi-lo.

01:57.550 --> 02:00.220
Então vamos apenas criar algo que devolva um carro alegórico.

02:00.220 --> 02:03.160
Vamos chamar isso de distância e para dentro dela.

02:03.190 --> 02:07.740
Vamos passar o nó A e o nó B.

02:07.750 --> 02:13.900
Agora, é claro, este é um cálculo tão simples que você provavelmente não precisa escrever um método para isso, mas de qualquer

02:13.900 --> 02:15.940
forma, só para que você possa vê-lo.

02:15.940 --> 02:21.670
Portanto, o que vamos voltar aqui é a magnitude quadrática.

02:21.670 --> 02:24.850
Portanto, queremos um vetor de três dimensões ao quadrado.

02:24.850 --> 02:30.400
Agora a magnitude quadrada é mais rápida de calcular do que a magnitude real entre dois pontos,

02:30.400 --> 02:31.840
que é um vetor.

02:31.840 --> 02:37.930
E não importa se usamos uma magnitude quadrada, desde que estejamos avaliando cada nó com base no mesmo

02:37.930 --> 02:41.020
tipo de algoritmo de avaliação, que é este aqui.

02:41.020 --> 02:54.400
Assim, nossa magnitude quadrada será um ponto de identificação ou eu transformaria a posição do ponto menos e isso tem que estar

02:54.400 --> 03:00.460
em um suporte ao redor menos nosso outro nó, que é o nó B.

03:00.460 --> 03:09.160
Assim, B dot obter ponto de identificação, transformar posição do ponto assim.

03:09.160 --> 03:09.610
Certo.

03:09.610 --> 03:12.430
Portanto, isso será nosso heurístico.

03:12.610 --> 03:15.880
Agora, está faltando um colchete ali mesmo.

03:15.880 --> 03:16.340
Certo.

03:16.360 --> 03:25.090
Neste momento, uma vez que temos isso associado a cada nó, precisamos encontrar aquele que tem a distância mais curta, o que significa que

03:25.090 --> 03:28.660
precisaremos de outro algoritmo para encontrá-lo.

03:28.690 --> 03:37.870
Agora, na versão anterior de uma estrela que criamos, na última seção, usamos uma consulta de link para fazer

03:37.870 --> 03:38.920
isso.

03:39.280 --> 03:40.180
Não vamos fazer isso agora.

03:40.180 --> 03:42.280
Na verdade, vamos fazer isso manualmente.

03:42.280 --> 03:48.970
Portanto, este é o mesmo algoritmo, mas apenas um pouco, acho eu, mais mão na massa, mais maneira manual de datilografar

03:48.970 --> 03:49.600
tudo.

03:49.600 --> 03:55.270
Portanto, vamos chamar isto de F mais baixo e isto basicamente vai fazer nossa consulta LINQ de qualquer forma.

03:55.270 --> 04:05.830
Assim, o nó de lista passará por todos os nossos nós e então aqui vamos calcular e retornar a posição

04:05.830 --> 04:07.930
do nó mais baixo.

04:07.930 --> 04:21.940
Portanto, queremos que o f mais baixo seja igual a zero, a contagem de int é igual a zero na contagem do iterador é igual a zero.

04:22.720 --> 04:33.460
Agora vamos inicializar nosso valor f mais baixo para ser f mais baixo vai ser igual ao primeiro valor da nossa lista.

04:33.460 --> 04:40.270
Portanto, L zero ponto f e iterar conta é zero para isso.

04:40.270 --> 04:46.300
Portanto, temos que garantir que esta conta iterativa se alinhe com o que está neste L aqui, o que faremos

04:46.300 --> 04:47.410
no ciclo seguinte.

04:47.410 --> 04:50.560
Por isso, agora vamos percorrer todos eles e verificá-los para encontrar os mais baixos.

04:50.560 --> 04:59.230
Portanto, para int i igual a um I é menos do que l contagem de pontos i mais i mais.

05:00.820 --> 05:01.430
E depois aqui dentro.

05:01.480 --> 05:01.810
Aqui.

05:01.810 --> 05:03.700
Nós iremos se.

05:04.000 --> 05:21.790
L na posição I ponto f é menor ou igual ao mais baixo f então o mais baixo f é igual a l i ponto f e a contagem do iterador é

05:21.790 --> 05:25.750
igual a nossa contagem.

05:27.380 --> 05:27.690
Certo.

05:28.120 --> 05:28.840
Assim, nós.

05:28.840 --> 05:33.730
Então, aqui embaixo vá contar mais, mais.

05:34.900 --> 05:48.150
E depois disso retornamos nossa contagem de iteradores, que será nosso nó com o valor F mais baixo k.

05:48.160 --> 05:54.070
Agora, junto com essas duas coisas, precisamos agora implementar nossa estrela.

05:54.070 --> 05:59.080
Por isso, vamos subir acima de nossa distância e colocar essas coisas aqui dentro.

05:59.380 --> 06:05.440
K Então este é um algoritmo bastante longo que você teria notado quando passamos por ele antes,

06:05.530 --> 06:12.460
mas este será o mesmo, mas ligeiramente diferente, porque não estamos usando esse código de link aqui.

06:12.460 --> 06:38.530
Assim, um objeto público de jogo estrela começa um objeto de jogo id e i d e depois o início do nó é igual ao nosso ID de início do nó de encontro.

06:38.560 --> 06:43.090
Assim, estamos permitindo que objetos de jogo

06:43.090 --> 07:02.410
sejam passados e estamos usando nosso nó de busca que criamos antes para obter os nós corretos da lista, encontrar nó e id k e então, se o início é igual a nulo ou o fim é igual a nulo, apenas um pouco

07:02.410 --> 07:05.740
de verificação de erro.

07:05.740 --> 07:10.810
Se não conseguirmos encontrar esses nós, voltaremos falsos e diremos, bem, aqui não há caminho.

07:11.970 --> 07:15.850
Muito bem, então agora vamos entrar na verdadeira estrela.

07:15.850 --> 07:20.830
Portanto, precisamos de uma lista de nós que será nossa lista aberta.

07:20.830 --> 07:26.770
Portanto, o nó aberto é igual ao novo nó de lista.

07:28.970 --> 07:31.850
E então precisamos novamente da mesma coisa para o nosso fechamento.

07:31.850 --> 07:33.800
Portanto, vou apenas copiar e colar isso.

07:33.890 --> 07:35.810
Esta é nossa lista fechada.

07:37.250 --> 07:37.490
Certo.

07:37.550 --> 07:48.080
Então eu posso criar um flutuador para uma pontuação g tentativa e igual a zero.

07:48.110 --> 07:49.540
Agora o que era G?

07:49.550 --> 07:55.280
Bem, G é a nossa distância, que já fomos tão longe.

07:55.310 --> 08:04.310
Certo, então a pontuação G provisória é o que daríamos ao nó se estivéssemos prestes a colocá-lo em uma lista e realmente

08:04.310 --> 08:08.570
selecioná-lo como nossa próxima posição no gráfico.

08:08.570 --> 08:10.190
Portanto, precisamos calculá-lo primeiro.

08:10.190 --> 08:12.980
Basicamente, então vamos ter um bool.

08:13.280 --> 08:16.190
Tentativa é melhor.

08:16.190 --> 08:24.590
Portanto, se calcularmos a pontuação G provisória para ser realmente melhor do que a que já está no nó,

08:24.590 --> 08:27.050
então podemos usar a melhor.

08:27.560 --> 08:31.490
Portanto, vamos com ponto inicial g igual a zero.

08:31.490 --> 08:35.300
Agora, isto é antes de começarmos realmente a fazer looping em qualquer coisa, então estamos apenas estabelecendo

08:35.300 --> 08:36.080
estes dois valores.

08:36.080 --> 08:44.970
Começa em h igual à distância de partida e k.

08:45.200 --> 08:48.200
Portanto, H é nossa distância até o fim.

08:48.200 --> 08:52.910
G é o quão longe chegamos de todos os custos até agora, que vai ser zero porque ainda não fomos a lugar

08:52.910 --> 08:53.300
algum.

08:53.300 --> 09:02.930
E então o ponto inicial f é igual ao ponto inicial h porque não há nada para realmente somar neste ponto.

09:02.930 --> 09:09.650
Agora o anúncio aberto vai igualar nosso nó inicial dessa forma.

09:09.650 --> 09:21.770
Ok, então agora para nosso grande loop de parede, enquanto a contagem de pontos abertos é maior que zero,

09:21.770 --> 09:33.350
vamos fazer com que um t int i seja igual ao mais baixo f na lista aberta, porque queremos selecionar

09:33.350 --> 09:51.170
que nosso próximo nó vamos para que este nó seja igual à lista aberta na posição I, então, se este ponto este ID de ponto de nó for igual ao ID final, então isso

09:51.170 --> 09:56.390
significa que encontramos um caminho.

09:57.860 --> 10:02.690
Portanto, aqui dentro reconstruiremos o caminho que vou digitar em um momento.

10:02.690 --> 10:09.830
Portanto, reconstrua o caminho que será o nome de nosso método do início ao fim.

10:11.960 --> 10:16.070
Vamos fazer disso um capital e retornaremos.

10:16.790 --> 10:17.690
É verdade.

10:17.990 --> 10:24.020
Portanto, voltaremos e faremos as reconstruções mais tarde, entre parênteses, porque esse é um método.

10:24.260 --> 10:25.760
Então, vamos descer.

10:25.760 --> 10:27.660
E aqui ainda não encontramos o fim.

10:27.680 --> 10:31.060
Vamos continuar comparando as coisas tão abertas.

10:31.170 --> 10:33.170
Remover ponto em.

10:33.170 --> 10:35.390
Vamos remover o nó com o qual estamos trabalhando.

10:36.710 --> 10:37.520
I.

10:39.900 --> 10:41.700
Anúncio fechado.

10:42.820 --> 10:47.950
Este nó porque agora dissemos que o estamos explorando.

10:47.950 --> 10:49.990
Então, vizinho do nó.

10:49.990 --> 10:56.500
Assim, a partir desse nó em particular, vamos agora explorar todos os vizinhos.

10:56.500 --> 10:57.910
Então, vizinho do nó.

10:58.030 --> 11:04.330
Portanto, para cada borda E nesta lista de pontos de borda de nó.

11:04.330 --> 11:08.980
Portanto, estes são todos os caminhos que saem daquele nó em particular que acabamos de fechar.

11:09.730 --> 11:12.820
Vamos explorar todos esses vizinhos.

11:12.820 --> 11:19.030
Portanto, o vizinho vai igualar o nó final E.

11:20.980 --> 11:22.300
Agora se.

11:23.020 --> 11:27.580
Índice fechado de pontos do vizinho.

11:28.060 --> 11:35.410
Portanto, se o vizinho está meio fora dos limites porque já estivemos lá, continuaremos apenas olhando

11:35.440 --> 11:41.620
para os outros limites porque não adianta olhar para algo que já está sendo fechado.

11:41.770 --> 11:42.340
Certo.

11:42.340 --> 11:53.260
Portanto, agora também a pontuação tentativa g é igual a este nó ponto g mais distância deste nó para o vizinho.

11:54.370 --> 12:04.890
Então, se índice aberto de vizinho é igual a menos um, então não está na lista aberta.

12:04.900 --> 12:06.730
Queremos adicioná-la à lista aberta.

12:06.730 --> 12:15.250
Assim, abre-se o vizinho para que possamos realmente explorá-lo novamente

12:16.180 --> 12:35.080
da próxima vez e, em seguida, vamos definir tentativo é melhor igualar o verdadeiro se a pontuação de dez a2g for inferior ao ponto g do vizinho, então também diremos que

12:35.080 --> 12:37.990
tentativo é melhor.

12:38.860 --> 12:40.330
Igual a verdade.

12:40.510 --> 12:44.070
Caso contrário, tentar é melhor.

12:44.080 --> 12:45.850
Igual a falso.

12:47.280 --> 12:47.820
Certo.

12:47.820 --> 12:54.630
Assim, uma vez que passamos por esse processo, se tentarmos é melhor, se o valor g que acabamos de calcular for

12:54.630 --> 12:58.560
melhor do que apenas queremos dar a esse nó esse novo valor g.

12:58.560 --> 13:03.630
Portanto, se a tentativa for melhor do que aqui, iremos.

13:03.630 --> 13:20.970
O ponto vizinho veio de igual a este nó vizinho ponto g é igual ao ponto g provisório g pontuação vizinho ponto h

13:21.090 --> 13:37.140
é igual à distância deste nó até o nó final e então o ponto vizinho f é igual ao ponto vizinho g mais o ponto

13:37.500 --> 13:39.630
vizinho h.

13:41.370 --> 13:43.110
Muito bem, então isso está feito.

13:43.110 --> 13:54.840
Agora, se chegamos até aqui e não retornamos mais longe em nenhum lugar, então nós realmente queremos, que seria aqui onde

13:54.840 --> 14:00.720
construímos o caminho é sair daqui com um retorno falso, dizendo

14:00.720 --> 14:03.900
que ainda não há caminho.

14:03.900 --> 14:08.070
Não há nenhum caminho entre esses dois nós em qualquer lugar que possa ser encontrado.

14:08.370 --> 14:09.060
Muito bem.

14:09.060 --> 14:11.850
Portanto, este é nosso algoritmo A Star.

14:11.850 --> 14:22.680
Temos agora dentro de sua estrutura atual os nós todos ligados entre si com base neste valor aqui.

14:22.680 --> 14:28.710
Assim, quando passamos por isso, na verdade temos uma longa lista de nós como uma lista vinculada ou basicamente

14:28.710 --> 14:30.750
é uma lista vinculada de nós.

14:30.750 --> 14:33.870
Estamos no nó final, temos acesso ao nó final.

14:33.900 --> 14:39.960
Agora temos que fazer nosso caminho de volta para o início, para que realmente o caminho esteja na sua direção

14:39.960 --> 14:42.510
para frente, não na sua direção inversa.

14:42.750 --> 14:48.750
Assim, quando voltarmos na próxima palestra, continuaremos trabalhando nisto e escreveremos este método de reconstrução

14:48.750 --> 14:53.670
do caminho para que possamos realmente ter o caminho que estamos procurando.
