Na palestra anterior, começamos a trabalhar em nossa API gráfica.
Agora estamos no ponto em que estamos prontos para colocar a funcionalidade de um algoritmo de busca de caminhos
A estrela.
Portanto, provavelmente faz sentido apenas revisar o algoritmo aStar que examinamos na seção anterior.
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
de um labirinto.
Assim, no labirinto, cada quadrado era basicamente um nó, e se você pudesse ir de um quadrado para outro, então
isso era uma borda ou um caminho entre eles.
Portanto, temos que começar a posição.
Temos uma posição de objetivo.
Temos que calcular como passar por isso.
Agora, há três valores sobre os quais vamos avaliar cada posição, e esse é o valor de
PH, que é o custo de chegar à meta daquele nó, o valor G, que é o custo de chegar àquele
nó.
Portanto, quanto já custa chegar a esse nó desde o início.
E então temos um valor H, que é a adição de ambas as coisas que dão ao nó geral seu tipo
de custo holístico, eu acho que sobre como ele é adequado, como é o melhor a ser feito.
Portanto, vamos escrever alguns destes algoritmos em nossa classe gráfica.
Certo.
Portanto, antes de tudo, vamos criar nossa heurística, que é basicamente nosso método que determinará
o quão adequado é cada nó.
E neste caso, vamos usar a distância do nó até o local final, que vai ser mais ou
menos como o vôo dos corvos.
Então é por isso que é chamado de holístico, acho que é o melhor palpite que se pode fazer porque não
sabemos.
Na verdade, não podemos voar diretamente para a posição final.
Podemos ser capazes, mas de cada nó, essa será nossa melhor maneira de medi-lo.
Então vamos apenas criar algo que devolva um carro alegórico.
Vamos chamar isso de distância e para dentro dela.
Vamos passar o nó A e o nó B.
Agora, é claro, este é um cálculo tão simples que você provavelmente não precisa escrever um método para isso, mas de qualquer
forma, só para que você possa vê-lo.
Portanto, o que vamos voltar aqui é a magnitude quadrática.
Portanto, queremos um vetor de três dimensões ao quadrado.
Agora a magnitude quadrada é mais rápida de calcular do que a magnitude real entre dois pontos,
que é um vetor.
E não importa se usamos uma magnitude quadrada, desde que estejamos avaliando cada nó com base no mesmo
tipo de algoritmo de avaliação, que é este aqui.
Assim, nossa magnitude quadrada será um ponto de identificação ou eu transformaria a posição do ponto menos e isso tem que estar
em um suporte ao redor menos nosso outro nó, que é o nó B.
Assim, B dot obter ponto de identificação, transformar posição do ponto assim.
Certo.
Portanto, isso será nosso heurístico.
Agora, está faltando um colchete ali mesmo.
Certo.
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
precisaremos de outro algoritmo para encontrá-lo.
Agora, na versão anterior de uma estrela que criamos, na última seção, usamos uma consulta de link para fazer
isso.
Não vamos fazer isso agora.
Na verdade, vamos fazer isso manualmente.
Portanto, este é o mesmo algoritmo, mas apenas um pouco, acho eu, mais mão na massa, mais maneira manual de datilografar
tudo.
Portanto, vamos chamar isto de F mais baixo e isto basicamente vai fazer nossa consulta LINQ de qualquer forma.
Assim, o nó de lista passará por todos os nossos nós e então aqui vamos calcular e retornar a posição
do nó mais baixo.
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.
Agora vamos inicializar nosso valor f mais baixo para ser f mais baixo vai ser igual ao primeiro valor da nossa lista.
Portanto, L zero ponto f e iterar conta é zero para isso.
Portanto, temos que garantir que esta conta iterativa se alinhe com o que está neste L aqui, o que faremos
no ciclo seguinte.
Por isso, agora vamos percorrer todos eles e verificá-los para encontrar os mais baixos.
Portanto, para int i igual a um I é menos do que l contagem de pontos i mais i mais.
E depois aqui dentro.
Aqui.
Nós iremos se.
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 é
igual a nossa contagem.
Certo.
Assim, nós.
Então, aqui embaixo vá contar mais, mais.
E depois disso retornamos nossa contagem de iteradores, que será nosso nó com o valor F mais baixo k.
Agora, junto com essas duas coisas, precisamos agora implementar nossa estrela.
Por isso, vamos subir acima de nossa distância e colocar essas coisas aqui dentro.
K Então este é um algoritmo bastante longo que você teria notado quando passamos por ele antes,
mas este será o mesmo, mas ligeiramente diferente, porque não estamos usando esse código de link aqui.
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.
Assim, estamos permitindo que objetos de jogo
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
de verificação de erro.
Se não conseguirmos encontrar esses nós, voltaremos falsos e diremos, bem, aqui não há caminho.
Muito bem, então agora vamos entrar na verdadeira estrela.
Portanto, precisamos de uma lista de nós que será nossa lista aberta.
Portanto, o nó aberto é igual ao novo nó de lista.
E então precisamos novamente da mesma coisa para o nosso fechamento.
Portanto, vou apenas copiar e colar isso.
Esta é nossa lista fechada.
Certo.
Então eu posso criar um flutuador para uma pontuação g tentativa e igual a zero.
Agora o que era G?
Bem, G é a nossa distância, que já fomos tão longe.
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
selecioná-lo como nossa próxima posição no gráfico.
Portanto, precisamos calculá-lo primeiro.
Basicamente, então vamos ter um bool.
Tentativa é melhor.
Portanto, se calcularmos a pontuação G provisória para ser realmente melhor do que a que já está no nó,
então podemos usar a melhor.
Portanto, vamos com ponto inicial g igual a zero.
Agora, isto é antes de começarmos realmente a fazer looping em qualquer coisa, então estamos apenas estabelecendo
estes dois valores.
Começa em h igual à distância de partida e k.
Portanto, H é nossa distância até o fim.
G é o quão longe chegamos de todos os custos até agora, que vai ser zero porque ainda não fomos a lugar
algum.
E então o ponto inicial f é igual ao ponto inicial h porque não há nada para realmente somar neste ponto.
Agora o anúncio aberto vai igualar nosso nó inicial dessa forma.
Ok, então agora para nosso grande loop de parede, enquanto a contagem de pontos abertos é maior que zero,
vamos fazer com que um t int i seja igual ao mais baixo f na lista aberta, porque queremos selecionar
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
significa que encontramos um caminho.
Portanto, aqui dentro reconstruiremos o caminho que vou digitar em um momento.
Portanto, reconstrua o caminho que será o nome de nosso método do início ao fim.
Vamos fazer disso um capital e retornaremos.
É verdade.
Portanto, voltaremos e faremos as reconstruções mais tarde, entre parênteses, porque esse é um método.
Então, vamos descer.
E aqui ainda não encontramos o fim.
Vamos continuar comparando as coisas tão abertas.
Remover ponto em.
Vamos remover o nó com o qual estamos trabalhando.
I.
Anúncio fechado.
Este nó porque agora dissemos que o estamos explorando.
Então, vizinho do nó.
Assim, a partir desse nó em particular, vamos agora explorar todos os vizinhos.
Então, vizinho do nó.
Portanto, para cada borda E nesta lista de pontos de borda de nó.
Portanto, estes são todos os caminhos que saem daquele nó em particular que acabamos de fechar.
Vamos explorar todos esses vizinhos.
Portanto, o vizinho vai igualar o nó final E.
Agora se.
Índice fechado de pontos do vizinho.
Portanto, se o vizinho está meio fora dos limites porque já estivemos lá, continuaremos apenas olhando
para os outros limites porque não adianta olhar para algo que já está sendo fechado.
Certo.
Portanto, agora também a pontuação tentativa g é igual a este nó ponto g mais distância deste nó para o vizinho.
Então, se índice aberto de vizinho é igual a menos um, então não está na lista aberta.
Queremos adicioná-la à lista aberta.
Assim, abre-se o vizinho para que possamos realmente explorá-lo novamente
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
tentativo é melhor.
Igual a verdade.
Caso contrário, tentar é melhor.
Igual a falso.
Certo.
Assim, uma vez que passamos por esse processo, se tentarmos é melhor, se o valor g que acabamos de calcular for
melhor do que apenas queremos dar a esse nó esse novo valor g.
Portanto, se a tentativa for melhor do que aqui, iremos.
O ponto vizinho veio de igual a este nó vizinho ponto g é igual ao ponto g provisório g pontuação vizinho ponto h
é igual à distância deste nó até o nó final e então o ponto vizinho f é igual ao ponto vizinho g mais o ponto
vizinho h.
Muito bem, então isso está feito.
Agora, se chegamos até aqui e não retornamos mais longe em nenhum lugar, então nós realmente queremos, que seria aqui onde
construímos o caminho é sair daqui com um retorno falso, dizendo
que ainda não há caminho.
Não há nenhum caminho entre esses dois nós em qualquer lugar que possa ser encontrado.
Muito bem.
Portanto, este é nosso algoritmo A Star.
Temos agora dentro de sua estrutura atual os nós todos ligados entre si com base neste valor aqui.
Assim, quando passamos por isso, na verdade temos uma longa lista de nós como uma lista vinculada ou basicamente
é uma lista vinculada de nós.
Estamos no nó final, temos acesso ao nó final.
Agora temos que fazer nosso caminho de volta para o início, para que realmente o caminho esteja na sua direção
para frente, não na sua direção inversa.
Assim, quando voltarmos na próxima palestra, continuaremos trabalhando nisto e escreveremos este método de reconstrução
do caminho para que possamos realmente ter o caminho que estamos procurando.