WEBVTT

00:02.610 --> 00:09.780
O algoritmo estrela foi inventado pelos cientistas da computação Nils Nilsson, Peter Hart e Bertram Rafael enquanto

00:10.170 --> 00:16.620
trabalhavam no desenvolvimento de um sistema de navegação para o Shakey, o Projeto de Pesquisa de Robôs

00:16.620 --> 00:18.690
em Stanford em 1968.

00:19.440 --> 00:26.850
Eles tinham dois algoritmos que estavam trabalhando na época, tentando encontrar formas otimizadas de determinar caminhos

00:26.850 --> 00:28.680
através dos ambientes.

00:29.310 --> 00:32.370
Eles os chamavam de um e dois.

00:32.400 --> 00:38.790
Aconteceu que um dois era na verdade o mais ideal, e então eles simplesmente o chamaram de estrela.

00:39.330 --> 00:45.690
O algoritmo aStar é bastante sinônimo de A. I. em jogos e usados em todos os lugares, desde ações

00:45.690 --> 00:49.680
de planejamento e personagens até a determinação do melhor caminho através de um ambiente.

00:49.860 --> 00:55.500
O algoritmo estelar tende a ser algo um pouco assustador quando você entra na computação pela primeira

00:55.500 --> 01:02.220
vez e tem que desenvolver o seu próprio e muitas vezes você vai encontrar sua própria biblioteca e apenas usá-la porque vai

01:02.220 --> 01:06.750
funcionar e então você não terá que entender o que está acontecendo por baixo.

01:06.780 --> 01:12.990
Mas é um algoritmo muito intuitivo baseado na maneira como os humanos realmente pensam.

01:13.020 --> 01:17.850
Portanto, antes de mais nada, deixem-me dar-lhes um pouco de desafio.

01:17.940 --> 01:24.180
Dado este labirinto que já criei e, de fato, acho que é uma sala, mas você só pode se mover em movimentos

01:24.180 --> 01:28.440
retos para cima e para baixo ou de um lado para o outro.

01:28.440 --> 01:34.680
E quero que você pense sobre qual seria seu caminho desde esta posição inicial até esta posição final faça uma pausa

01:34.680 --> 01:40.110
no vídeo agora e talvez desenhe um pequeno diagrama para pensar no que você poderia fazer e, em seguida,

01:40.110 --> 01:43.290
o raciocínio sobre o motivo pelo qual o fez.

01:51.350 --> 01:51.920
Certo.

01:51.950 --> 01:52.970
Como você foi?

01:53.000 --> 01:55.490
Bem, há uma série de diferentes caminhos que você pode seguir agora.

01:55.490 --> 02:00.170
Você não pode ir em diagonal, que seria o caminho mais curto do início ao fim, porque temos que ir para cima

02:00.170 --> 02:05.170
e para baixo ou para a esquerda e para a direita, porque é assim que estamos construindo nosso labirinto.

02:05.180 --> 02:10.490
E assim, há uma variedade de padrões diferentes que você poderia ter criado, subindo e atravessando,

02:10.490 --> 02:13.910
nada atravessando até atingir aquele canto superior.

02:13.910 --> 02:15.830
E aqui está apenas um deles.

02:16.040 --> 02:22.790
Agora, você poderia ter atravessado e descido e depois atravessado algumas vezes e depois subido.

02:22.790 --> 02:25.130
Mas eu aposto que você não fez isso.

02:25.130 --> 02:31.100
E a razão é que se você descer a qualquer momento desde o início, você está realmente ficando

02:31.100 --> 02:32.660
mais longe do final.

02:32.690 --> 02:39.740
Portanto, sua escolha de qual passo a seguir deve ser aproximá-lo do final,

02:39.740 --> 02:41.720
e não mais longe.

02:42.140 --> 02:48.950
Certo, e agora se eu lhe dissesse que o labirinto realmente é assim e que há um pequeno problema com o

02:48.950 --> 02:50.720
caminho que você traçou?

02:50.720 --> 02:55.250
Na verdade, há um muro na estrada e, portanto, não se pode ir por ali.

02:55.280 --> 02:58.070
Para que lado você iria em vez disso?

02:58.190 --> 03:05.120
Bem, você desceria para começar e depois voltaria para cima novamente, porque esse é o único caminho que

03:05.120 --> 03:06.320
você pode seguir.

03:06.650 --> 03:12.260
Mas o problema é que, quando você não sabe, essas paredes estão lá, então você não pode realmente ver tão longe

03:12.260 --> 03:12.980
adiante.

03:12.980 --> 03:20.600
Você está querendo se aproximar de sua posição de objetivo porque esse parece ser o caminho mais intuitivo a

03:20.600 --> 03:21.590
ser seguido.

03:21.590 --> 03:26.240
E esta é realmente a base do algoritmo das estrelas.

03:26.240 --> 03:32.870
Ele quer continuar tentando quadrados que estejam mais próximos do objetivo final.

03:33.140 --> 03:37.310
Vamos passar por como funciona uma estrela, considerando este mapa.

03:37.400 --> 03:42.500
Começando no canto inferior direito, temos que decidir qual vizinho escolher.

03:42.620 --> 03:46.460
Lembre-se, estamos nos movendo apenas verticalmente e horizontalmente.

03:46.460 --> 03:52.070
Entretanto, se você permitisse um movimento diagonal, então você teria mais um vizinho a mais.

03:52.220 --> 03:57.980
O algoritmo funcionará da mesma forma, mas não estamos fazendo diagonais no momento para que possamos esquecer

03:57.980 --> 03:59.420
esse ponto em particular.

03:59.870 --> 04:03.320
Então, qual vizinho fazer parte do caminho?

04:03.650 --> 04:09.620
Bem, se você olhar de relance, a distância em linha reta de cada um desses vizinhos é praticamente

04:09.620 --> 04:10.550
a mesma.

04:10.550 --> 04:15.050
Bem, é exatamente a mesma coisa, mas um algoritmo de computador não consegue olhar para ele.

04:15.080 --> 04:20.660
Ele pode, entretanto, calcular a distância que o objetivo está longe de cada vizinho.

04:20.660 --> 04:25.460
Portanto, primeiro adicionamos ao nosso algoritmo estrela o valor de H.

04:25.670 --> 04:31.160
Agora H representa idealmente o custo de ir do vizinho para o objetivo.

04:31.160 --> 04:35.060
Neste caso, vamos utilizar a distância como nosso custo.

04:35.480 --> 04:41.360
Embora você pudesse incluir outras coisas no custo, como o caminho mais curto poderia levá-lo através

04:41.360 --> 04:46.880
de um pouco de amor e, portanto, você não consideraria apenas a distância como uma das coisas

04:46.880 --> 04:51.470
incluídas no custo, mas também quanto dano causará ao jogador.

04:51.470 --> 04:59.390
Portanto, neste caso, a distância para cada vizinho e, portanto, o valor h é 5. 8, que eu determinei usando o teorema de

04:59.390 --> 05:00.800
Pitágoras.

05:00.980 --> 05:10.280
Você também poderia determiná-lo usando o número de movimentos X, mais o número de movimentos Y entre o vizinho e o objetivo.

05:10.280 --> 05:15.980
Não importa realmente como você mede, desde que seja feito de forma consistente para que todos

05:15.980 --> 05:22.220
os vizinhos entendam o próximo valor utilizado no algoritmo, daremos uma rápida olhada em um exemplo.

05:22.220 --> 05:26.090
Digamos que duas pessoas estão viajando do clube de surf para o clube de golfe.

05:26.120 --> 05:33.650
Em algum momento, uma pessoa está aqui e a outra está aqui só de olhar para onde ela está.

05:33.680 --> 05:36.620
Você pode adivinhar qual deles tomou o caminho mais curto?

05:36.620 --> 05:41.780
Se você apenas levasse a distância deles até o objetivo, você não estaria conseguindo a história completa

05:41.780 --> 05:43.940
de quão longe eles já haviam viajado.

05:44.690 --> 05:51.200
Entretanto, se você combinar a distância dos pontos até o início com a distância restante, você teria uma idéia

05:51.200 --> 05:56.870
melhor da distância total percorrida por cada um, e então você poderia descobrir qual era o caminho

05:56.870 --> 05:58.340
mais curto.

05:58.340 --> 06:00.560
E é isso que o algoritmo de estar faz.

06:00.560 --> 06:06.530
Ela considera não apenas a distância do ponto ao objetivo, mas também a distância que você percorreu para

06:06.530 --> 06:07.730
chegar a esse ponto.

06:07.940 --> 06:12.770
Neste caso, a distância desde o início até cada vizinho é uma só.

06:12.770 --> 06:15.770
Este valor é denotado pela variável g.

06:16.620 --> 06:22.590
Depois combinamos H e G e obtemos um valor F, que é o total destes.

06:22.800 --> 06:29.580
Essencialmente, o F representa a aptidão daquele vizinho em particular para estar no caminho em direção ao

06:29.580 --> 06:30.290
objetivo.

06:30.300 --> 06:35.940
Uma vez calculados todos os valores vizinhos, o vizinho com o valor F mais baixo é escolhido

06:35.940 --> 06:41.040
como o próximo ponto no caminho para acompanhar quais pontos foram visitados.

06:41.070 --> 06:48.540
Há uma lista aberta e fechada, então obviamente START vai para a lista fechada depois que seus vizinhos forem gerados

06:48.540 --> 06:52.140
porque está bem, definitivamente no caminho.

06:52.170 --> 06:55.980
Em seguida, neste caso, temos vizinhos com os mesmos valores F.

06:55.980 --> 07:00.960
Portanto, podemos escolher uma das duas porque nenhuma delas é inferior à outra.

07:01.350 --> 07:03.150
Portanto, vamos subir.

07:03.210 --> 07:08.250
Acrescentamos este ponto à lista fechada e depois abrimos seus vizinhos.

07:08.880 --> 07:12.870
Quaisquer novos vizinhos são adicionados à lista aberta.

07:13.320 --> 07:18.690
Neste caso, seus valores H, G e F são calculados.

07:18.690 --> 07:22.890
Agora temos dois pontos na lista aberta.

07:23.040 --> 07:24.360
Para onde vamos a seguir?

07:24.360 --> 07:33.150
Bem, encontramos o ponto que tem o F mais baixo e voltamos para lá e damos uma olhada em seus vizinhos.

07:33.150 --> 07:36.690
Portanto, neste caso, nós realmente subimos um pouco.

07:36.690 --> 07:43.350
E então, como o valor F do Ponto Verde no fundo é o menor, voltamos para

07:43.350 --> 07:49.890
lá e o colocamos na lista fechada e depois abrimos seus vizinhos.

07:50.880 --> 07:55.500
E continuamos assim até atingirmos o local da meta.

07:56.750 --> 07:57.230
Certo.

07:57.230 --> 08:01.040
Vamos dar uma olhada em um exemplo deste trabalho.

08:01.080 --> 08:01.300
Certo.

08:01.310 --> 08:05.750
Assim, gerei um labirinto usando o método recursivo.

08:05.750 --> 08:13.010
Além disso, fiz um pouco de remoção aleatória da parede e coloquei aqui alguns marcadores para mostrar

08:13.010 --> 08:16.130
onde vai ser o início e o fim do nosso A Star.

08:16.130 --> 08:21.170
Portanto, o laranja é o começo e o amarelo aqui em baixo é a posição final.

08:21.320 --> 08:25.880
Assim, cada marcador vai lhe mostrar um valor G, H e F.

08:25.880 --> 08:33.410
Então G é a distância desde o início que está aqui você pode ver que é uma para aquele e uma para este.

08:33.410 --> 08:42.530
Portanto, estes eram os dois vizinhos para onde se podia ir e o valor h é a distância para o amarelo.

08:42.530 --> 08:47.870
Portanto, estou usando apenas um velho cálculo de distância em linha reta, teorema de Pitágoras.

08:47.870 --> 08:53.120
E assim, deste aqui é 4. 47 e deste aqui em baixo é 4. 24.

08:53.120 --> 08:54.730
Portanto, esta está obviamente mais próxima.

08:54.800 --> 09:04.310
O valor F, que é a adição desses dois, nos dá 5. 24 para este vermelho e 5. 47 para a roxa.

09:04.310 --> 09:12.410
Agora, ambos são colocados na lista aberta e depois aquele que tem o menor valor F neste caso, este é escolhido

09:12.410 --> 09:18.980
como o próximo ponto a ser analisado para gerar vizinhos a partir de agora.

09:18.980 --> 09:20.180
É por isso que ficou vermelho.

09:20.180 --> 09:23.960
Portanto, vai ficar imediatamente vermelho, pois seleciona o próximo a partir da lista aberta.

09:23.960 --> 09:28.790
Portanto, ela é retirada da lista aberta, o que significa que não pode voltar a essa.

09:28.910 --> 09:32.720
Certo, então agora vamos dar uma olhada nos próximos valores que são gerados.

09:32.990 --> 09:33.320
Certo?

09:33.320 --> 09:36.380
Portanto, este aqui gerou alguns vizinhos.

09:36.380 --> 09:41.390
Agora ele voltou e gerou um no início, o que não faz mal, porque neste caso eu não

09:41.390 --> 09:47.780
tenho meu início adicionado à lista aberta no início e, no entanto, não está marcado como fechado.

09:47.780 --> 09:50.570
Eu poderia fazer isso, mas isso ainda funciona de qualquer maneira.

09:50.570 --> 09:52.640
Vamos dar uma olhada nos valores de distância.

09:52.640 --> 10:02.870
Portanto, a distância deste desde o início será a distância de onde veio o pai, que

10:02.870 --> 10:07.160
foi uma mais a distância de lá.

10:07.160 --> 10:10.310
Certo, então agora temos dois, o que nos torna dois a partir daí.

10:10.310 --> 10:18.200
Então acrescentamos esta distância e esta distância, a distância é, então, esta distância até aqui.

10:18.230 --> 10:24.110
Agora isto também foi calculado, mas como está mais longe, basicamente vai ser ignorado.

10:24.620 --> 10:30.680
Este aqui teria então seus valores atualizados novamente.

10:30.680 --> 10:35.960
Portanto, ainda será um desde o início, que ainda está aqui.

10:36.350 --> 10:39.980
Agora, você deve estar se perguntando, por que isto diz 24g aqui em cima?

10:39.980 --> 10:47.390
Porque este era um nó ou um vizinho deste, e realmente foi o caminho de volta a este, foi como aqui

10:47.390 --> 10:49.280
e depois voltou para lá.

10:49.280 --> 10:50.810
Então é por isso que isso é um dois.

10:51.020 --> 10:55.580
E isso o coloca fora de discussão basicamente porque é um valor muito alto.

10:55.760 --> 10:56.150
Certo.

10:56.150 --> 10:59.690
Portanto, vamos dar uma olhada no que será escolhido a seguir.

10:59.900 --> 11:05.510
Este obviamente, porque já ficou vermelho e foi colocado na lista fechada, 5. 47 para o valor

11:05.510 --> 11:06.230
F.

11:06.230 --> 11:08.900
E aqui temos 5. 61.

11:08.900 --> 11:15.110
Portanto, este vai ficar ao ar livre até se tornar o menor, se é que alguma vez se tornou.

11:15.230 --> 11:16.790
Muito bem, então vamos novamente.

11:17.330 --> 11:17.660
Certo.

11:17.660 --> 11:22.940
Portanto, agora este gerou outro ponto de volta para lá, que é basicamente ignorado.

11:23.090 --> 11:27.920
E seu outro vizinho, que está aqui, tem seu G, que é dois.

11:27.920 --> 11:33.770
Certo, porque é como um, dois e depois é o valor H que é 4. 12.

11:33.770 --> 11:37.850
Mais uma vez, esta distância aqui o dá 6. 12.

11:37.850 --> 11:44.180
Este valor aqui foi recalculado ou reutilizado porque ainda estava aberto, lembra-se?

11:44.240 --> 11:47.930
E assim é menor, por isso é escolhida.

11:47.930 --> 11:50.390
Portanto, agora os vizinhos para isso serão gerados.

11:50.900 --> 11:52.730
Então isso significa que este é gerado.

11:52.730 --> 11:55.280
Lembre-se, essa já está na lista fechada, portanto não vai acontecer.

11:55.280 --> 11:55.760
Certo.

11:55.760 --> 12:02.360
Agora, se olharmos para estes dois valores, podemos ver que este será, obviamente, o mais próximo.

12:02.360 --> 12:04.700
Então, vamos novamente e chegamos aqui.

12:04.700 --> 12:05.870
Agora, olhe para isto.

12:05.870 --> 12:10.160
Esta é agora 6. 24.

12:10.760 --> 12:15.980
Apesar de estar mais perto, podemos ver fisicamente que está mais perto.

12:15.980 --> 12:20.720
Este ponto aqui em cima é 6. 12.

12:20.720 --> 12:26.000
Agora, isto ainda estava aberto até recentemente, apenas ficou vermelho, o que significa que está na lista fechada.

12:26.000 --> 12:28.820
É o que vai calcular o próximo vizinho.

12:28.820 --> 12:33.110
Portanto, se formos por isso, não gerou um ponto aqui.

12:33.530 --> 12:38.270
Agora, acabou com um F de sete, o que colocou este de volta na disputa.

12:38.270 --> 12:39.770
Por isso, voltamos aqui.

12:39.950 --> 12:41.330
Certo, temos mais alguns vizinhos.

12:41.330 --> 12:47.240
Assim, estes dois, este acabou se aproximando, depois geramos outro vizinho ali.

12:47.270 --> 12:47.630
Certo.

12:47.630 --> 12:55.850
Agora, se olharmos para estes que estão abertos, você pode ver que eles são, de fato, todos os valores de.

12:55.970 --> 12:56.630
Sete.

12:56.630 --> 13:04.190
Então é só escolher um desses ao acaso porque vai ordená-los pelos menores, mas eles são todos iguais, então estamos

13:04.190 --> 13:06.020
apenas escolhendo um.

13:06.200 --> 13:08.210
Por isso, acabamos de voltar para lá.

13:08.210 --> 13:12.170
Ele vai gerar este, que é o 8. 12.

13:12.200 --> 13:17.630
Agora, você viu que este ficou vermelho, então decidiu escolher este,

13:17.630 --> 13:23.090
que gera este, que depois desce e gera este, que é o nosso valor final.

13:23.300 --> 13:23.600
Certo.

13:23.630 --> 13:28.010
Assim, você pode ver que a estrela não se limita a ir dum dum dum dum dum dum dum dum dum até aqui.

13:28.010 --> 13:32.810
Na verdade, ele irá saltar um pouco para trás e para frente enquanto explora mais coisas ao seu redor.

13:32.900 --> 13:39.030
A beleza disso é que nunca está realmente olhando muito à frente, está bem?

13:39.110 --> 13:44.600
É só calcular esses valores de distância, a distância que você já percorreu e a distância que

13:44.600 --> 13:47.260
ainda tem que percorrer, basicamente.

13:47.360 --> 13:54.860
Certo, então agora se eu apenas acertar minha chave de mapeamento que programei, ela nos mostrará nosso caminho que foi

13:54.860 --> 13:55.670
calculado.

13:55.670 --> 14:01.850
Agora, para conseguir o caminho no final, você termina com todos esses vizinhos ou nós.

14:01.850 --> 14:06.080
Poderíamos chamá-los na lista fechada até aqui.

14:06.080 --> 14:13.040
Portanto, o que fazemos é começar com este e segui-lo até os pontos de onde viemos.

14:13.040 --> 14:18.380
Assim, enquanto viajamos, toda vez que vamos a um novo vizinho, o vizinho tem que se lembrar

14:18.380 --> 14:19.660
de seus pais.

14:19.670 --> 14:25.850
Assim, no final, podemos viajar de volta através daquela árvore-mãe e pegar nosso caminho.

14:26.720 --> 14:30.620
Ok, então este é o algoritmo estelar e como ele funciona.

14:30.620 --> 14:34.220
Portanto, é um algoritmo bastante simples.

14:34.220 --> 14:36.410
As idéias são muito simples.

14:36.410 --> 14:41.210
Não está fazendo nada de estranho, como eu disse, olhando para o futuro ou algo parecido.

14:41.840 --> 14:48.620
E por isso agora espero que você tenha uma melhor compreensão conceitual de como isso vai junto, porque quando

14:48.620 --> 14:54.530
voltarmos na próxima palestra, você vai realmente construir isso em seu sistema de labirinto.
