O algoritmo estrela foi inventado pelos cientistas da computação Nils Nilsson, Peter Hart e Bertram Rafael enquanto
trabalhavam no desenvolvimento de um sistema de navegação para o Shakey, o Projeto de Pesquisa de Robôs
em Stanford em 1968.
Eles tinham dois algoritmos que estavam trabalhando na época, tentando encontrar formas otimizadas de determinar caminhos
através dos ambientes.
Eles os chamavam de um e dois.
Aconteceu que um dois era na verdade o mais ideal, e então eles simplesmente o chamaram de estrela.
O algoritmo aStar é bastante sinônimo de A. I. em jogos e usados em todos os lugares, desde ações
de planejamento e personagens até a determinação do melhor caminho através de um ambiente.
O algoritmo estelar tende a ser algo um pouco assustador quando você entra na computação pela primeira
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
funcionar e então você não terá que entender o que está acontecendo por baixo.
Mas é um algoritmo muito intuitivo baseado na maneira como os humanos realmente pensam.
Portanto, antes de mais nada, deixem-me dar-lhes um pouco de desafio.
Dado este labirinto que já criei e, de fato, acho que é uma sala, mas você só pode se mover em movimentos
retos para cima e para baixo ou de um lado para o outro.
E quero que você pense sobre qual seria seu caminho desde esta posição inicial até esta posição final faça uma pausa
no vídeo agora e talvez desenhe um pequeno diagrama para pensar no que você poderia fazer e, em seguida,
o raciocínio sobre o motivo pelo qual o fez.
Certo.
Como você foi?
Bem, há uma série de diferentes caminhos que você pode seguir agora.
Você não pode ir em diagonal, que seria o caminho mais curto do início ao fim, porque temos que ir para cima
e para baixo ou para a esquerda e para a direita, porque é assim que estamos construindo nosso labirinto.
E assim, há uma variedade de padrões diferentes que você poderia ter criado, subindo e atravessando,
nada atravessando até atingir aquele canto superior.
E aqui está apenas um deles.
Agora, você poderia ter atravessado e descido e depois atravessado algumas vezes e depois subido.
Mas eu aposto que você não fez isso.
E a razão é que se você descer a qualquer momento desde o início, você está realmente ficando
mais longe do final.
Portanto, sua escolha de qual passo a seguir deve ser aproximá-lo do final,
e não mais longe.
Certo, e agora se eu lhe dissesse que o labirinto realmente é assim e que há um pequeno problema com o
caminho que você traçou?
Na verdade, há um muro na estrada e, portanto, não se pode ir por ali.
Para que lado você iria em vez disso?
Bem, você desceria para começar e depois voltaria para cima novamente, porque esse é o único caminho que
você pode seguir.
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
adiante.
Você está querendo se aproximar de sua posição de objetivo porque esse parece ser o caminho mais intuitivo a
ser seguido.
E esta é realmente a base do algoritmo das estrelas.
Ele quer continuar tentando quadrados que estejam mais próximos do objetivo final.
Vamos passar por como funciona uma estrela, considerando este mapa.
Começando no canto inferior direito, temos que decidir qual vizinho escolher.
Lembre-se, estamos nos movendo apenas verticalmente e horizontalmente.
Entretanto, se você permitisse um movimento diagonal, então você teria mais um vizinho a mais.
O algoritmo funcionará da mesma forma, mas não estamos fazendo diagonais no momento para que possamos esquecer
esse ponto em particular.
Então, qual vizinho fazer parte do caminho?
Bem, se você olhar de relance, a distância em linha reta de cada um desses vizinhos é praticamente
a mesma.
Bem, é exatamente a mesma coisa, mas um algoritmo de computador não consegue olhar para ele.
Ele pode, entretanto, calcular a distância que o objetivo está longe de cada vizinho.
Portanto, primeiro adicionamos ao nosso algoritmo estrela o valor de H.
Agora H representa idealmente o custo de ir do vizinho para o objetivo.
Neste caso, vamos utilizar a distância como nosso custo.
Embora você pudesse incluir outras coisas no custo, como o caminho mais curto poderia levá-lo através
de um pouco de amor e, portanto, você não consideraria apenas a distância como uma das coisas
incluídas no custo, mas também quanto dano causará ao jogador.
Portanto, neste caso, a distância para cada vizinho e, portanto, o valor h é 5. 8, que eu determinei usando o teorema de
Pitágoras.
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.
Não importa realmente como você mede, desde que seja feito de forma consistente para que todos
os vizinhos entendam o próximo valor utilizado no algoritmo, daremos uma rápida olhada em um exemplo.
Digamos que duas pessoas estão viajando do clube de surf para o clube de golfe.
Em algum momento, uma pessoa está aqui e a outra está aqui só de olhar para onde ela está.
Você pode adivinhar qual deles tomou o caminho mais curto?
Se você apenas levasse a distância deles até o objetivo, você não estaria conseguindo a história completa
de quão longe eles já haviam viajado.
Entretanto, se você combinar a distância dos pontos até o início com a distância restante, você teria uma idéia
melhor da distância total percorrida por cada um, e então você poderia descobrir qual era o caminho
mais curto.
E é isso que o algoritmo de estar faz.
Ela considera não apenas a distância do ponto ao objetivo, mas também a distância que você percorreu para
chegar a esse ponto.
Neste caso, a distância desde o início até cada vizinho é uma só.
Este valor é denotado pela variável g.
Depois combinamos H e G e obtemos um valor F, que é o total destes.
Essencialmente, o F representa a aptidão daquele vizinho em particular para estar no caminho em direção ao
objetivo.
Uma vez calculados todos os valores vizinhos, o vizinho com o valor F mais baixo é escolhido
como o próximo ponto no caminho para acompanhar quais pontos foram visitados.
Há uma lista aberta e fechada, então obviamente START vai para a lista fechada depois que seus vizinhos forem gerados
porque está bem, definitivamente no caminho.
Em seguida, neste caso, temos vizinhos com os mesmos valores F.
Portanto, podemos escolher uma das duas porque nenhuma delas é inferior à outra.
Portanto, vamos subir.
Acrescentamos este ponto à lista fechada e depois abrimos seus vizinhos.
Quaisquer novos vizinhos são adicionados à lista aberta.
Neste caso, seus valores H, G e F são calculados.
Agora temos dois pontos na lista aberta.
Para onde vamos a seguir?
Bem, encontramos o ponto que tem o F mais baixo e voltamos para lá e damos uma olhada em seus vizinhos.
Portanto, neste caso, nós realmente subimos um pouco.
E então, como o valor F do Ponto Verde no fundo é o menor, voltamos para
lá e o colocamos na lista fechada e depois abrimos seus vizinhos.
E continuamos assim até atingirmos o local da meta.
Certo.
Vamos dar uma olhada em um exemplo deste trabalho.
Certo.
Assim, gerei um labirinto usando o método recursivo.
Além disso, fiz um pouco de remoção aleatória da parede e coloquei aqui alguns marcadores para mostrar
onde vai ser o início e o fim do nosso A Star.
Portanto, o laranja é o começo e o amarelo aqui em baixo é a posição final.
Assim, cada marcador vai lhe mostrar um valor G, H e F.
Então G é a distância desde o início que está aqui você pode ver que é uma para aquele e uma para este.
Portanto, estes eram os dois vizinhos para onde se podia ir e o valor h é a distância para o amarelo.
Portanto, estou usando apenas um velho cálculo de distância em linha reta, teorema de Pitágoras.
E assim, deste aqui é 4. 47 e deste aqui em baixo é 4. 24.
Portanto, esta está obviamente mais próxima.
O valor F, que é a adição desses dois, nos dá 5. 24 para este vermelho e 5. 47 para a roxa.
Agora, ambos são colocados na lista aberta e depois aquele que tem o menor valor F neste caso, este é escolhido
como o próximo ponto a ser analisado para gerar vizinhos a partir de agora.
É por isso que ficou vermelho.
Portanto, vai ficar imediatamente vermelho, pois seleciona o próximo a partir da lista aberta.
Portanto, ela é retirada da lista aberta, o que significa que não pode voltar a essa.
Certo, então agora vamos dar uma olhada nos próximos valores que são gerados.
Certo?
Portanto, este aqui gerou alguns vizinhos.
Agora ele voltou e gerou um no início, o que não faz mal, porque neste caso eu não
tenho meu início adicionado à lista aberta no início e, no entanto, não está marcado como fechado.
Eu poderia fazer isso, mas isso ainda funciona de qualquer maneira.
Vamos dar uma olhada nos valores de distância.
Portanto, a distância deste desde o início será a distância de onde veio o pai, que
foi uma mais a distância de lá.
Certo, então agora temos dois, o que nos torna dois a partir daí.
Então acrescentamos esta distância e esta distância, a distância é, então, esta distância até aqui.
Agora isto também foi calculado, mas como está mais longe, basicamente vai ser ignorado.
Este aqui teria então seus valores atualizados novamente.
Portanto, ainda será um desde o início, que ainda está aqui.
Agora, você deve estar se perguntando, por que isto diz 24g aqui em cima?
Porque este era um nó ou um vizinho deste, e realmente foi o caminho de volta a este, foi como aqui
e depois voltou para lá.
Então é por isso que isso é um dois.
E isso o coloca fora de discussão basicamente porque é um valor muito alto.
Certo.
Portanto, vamos dar uma olhada no que será escolhido a seguir.
Este obviamente, porque já ficou vermelho e foi colocado na lista fechada, 5. 47 para o valor
F.
E aqui temos 5. 61.
Portanto, este vai ficar ao ar livre até se tornar o menor, se é que alguma vez se tornou.
Muito bem, então vamos novamente.
Certo.
Portanto, agora este gerou outro ponto de volta para lá, que é basicamente ignorado.
E seu outro vizinho, que está aqui, tem seu G, que é dois.
Certo, porque é como um, dois e depois é o valor H que é 4. 12.
Mais uma vez, esta distância aqui o dá 6. 12.
Este valor aqui foi recalculado ou reutilizado porque ainda estava aberto, lembra-se?
E assim é menor, por isso é escolhida.
Portanto, agora os vizinhos para isso serão gerados.
Então isso significa que este é gerado.
Lembre-se, essa já está na lista fechada, portanto não vai acontecer.
Certo.
Agora, se olharmos para estes dois valores, podemos ver que este será, obviamente, o mais próximo.
Então, vamos novamente e chegamos aqui.
Agora, olhe para isto.
Esta é agora 6. 24.
Apesar de estar mais perto, podemos ver fisicamente que está mais perto.
Este ponto aqui em cima é 6. 12.
Agora, isto ainda estava aberto até recentemente, apenas ficou vermelho, o que significa que está na lista fechada.
É o que vai calcular o próximo vizinho.
Portanto, se formos por isso, não gerou um ponto aqui.
Agora, acabou com um F de sete, o que colocou este de volta na disputa.
Por isso, voltamos aqui.
Certo, temos mais alguns vizinhos.
Assim, estes dois, este acabou se aproximando, depois geramos outro vizinho ali.
Certo.
Agora, se olharmos para estes que estão abertos, você pode ver que eles são, de fato, todos os valores de.
Sete.
Então é só escolher um desses ao acaso porque vai ordená-los pelos menores, mas eles são todos iguais, então estamos
apenas escolhendo um.
Por isso, acabamos de voltar para lá.
Ele vai gerar este, que é o 8. 12.
Agora, você viu que este ficou vermelho, então decidiu escolher este,
que gera este, que depois desce e gera este, que é o nosso valor final.
Certo.
Assim, você pode ver que a estrela não se limita a ir dum dum dum dum dum dum dum dum dum até aqui.
Na verdade, ele irá saltar um pouco para trás e para frente enquanto explora mais coisas ao seu redor.
A beleza disso é que nunca está realmente olhando muito à frente, está bem?
É só calcular esses valores de distância, a distância que você já percorreu e a distância que
ainda tem que percorrer, basicamente.
Certo, então agora se eu apenas acertar minha chave de mapeamento que programei, ela nos mostrará nosso caminho que foi
calculado.
Agora, para conseguir o caminho no final, você termina com todos esses vizinhos ou nós.
Poderíamos chamá-los na lista fechada até aqui.
Portanto, o que fazemos é começar com este e segui-lo até os pontos de onde viemos.
Assim, enquanto viajamos, toda vez que vamos a um novo vizinho, o vizinho tem que se lembrar
de seus pais.
Assim, no final, podemos viajar de volta através daquela árvore-mãe e pegar nosso caminho.
Ok, então este é o algoritmo estelar e como ele funciona.
Portanto, é um algoritmo bastante simples.
As idéias são muito simples.
Não está fazendo nada de estranho, como eu disse, olhando para o futuro ou algo parecido.
E por isso agora espero que você tenha uma melhor compreensão conceitual de como isso vai junto, porque quando
voltarmos na próxima palestra, você vai realmente construir isso em seu sistema de labirinto.