En la conferencia anterior, empezamos a trabajar en nuestra Graph API.
Ahora estamos en el punto en el que estamos listos para poner en la funcionalidad para una búsqueda de ruta del algoritmo de
la estrella A.
Así que probablemente tenga sentido revisar el algoritmo de aStar que vimos en la sección anterior.
Así que tenemos un laberinto o tenemos una serie de puntos de ruta que están conectados con bordes que no son diferentes
a un laberinto.
Así que en el laberinto, cada cuadrado era básicamente un nodo, y si podías ir de un cuadrado a otro, entonces
eso era un borde o un camino entre ellos.
Así que tenemos que empezar a posicionarnos.
Tenemos una posición de gol.
Tenemos que calcular cómo superar esto.
Ahora, hay tres valores que vamos a evaluar cada posición, y es el valor PH, que es el
costo de llegar a la meta desde ese nodo, el valor G, que es el costo de llegar a ese nodo.
Entonces, cuánto ha costado llegar a ese nodo desde el principio.
Y luego tenemos un valor H, que es la adición de ambas cosas que le da al nodo en general
su tipo de costo holístico, supongo, sobre cómo es el ajuste, cómo es el mejor para ir.
Así que vamos a escribir algunos de estos algoritmos en nuestra clase de grafos.
De acuerdo.
Así que, en primer lugar, vamos a crear nuestra heurística, que es básicamente nuestro método que determinará
lo adecuado que es cada nodo.
Y en este caso, vamos a utilizar la distancia desde el nodo a la ubicación final, que va a ser
más o menos como el cuervo vuela.
Por eso se llama holístico, supongo que es como la mejor suposición que se puede hacer porque no lo
sabemos.
En realidad no podemos volar directamente a la posición final.
Podríamos ser capaces, pero desde cada nodo, esa va a ser nuestra mejor manera de medirlo.
Así que vamos a crear algo que devuelva un flotador.
Llamémosle distancia y entremos en ella.
Pasaremos el nodo A y el nodo B.
Ahora, por supuesto, este es un cálculo tan simple que probablemente no necesitas escribir un método para ello, pero de
todos modos ah, sólo para que lo veas.
Así que lo que vamos a devolver aquí es la magnitud al cuadrado.
Así que queremos la magnitud del vector tres al cuadrado.
Ahora la magnitud al cuadrado es más rápida de calcular que la magnitud real entre dos puntos,
que es un vector.
Y no importa si usamos una magnitud cuadrada mientras estemos evaluando cada nodo basado en el mismo tipo
de algoritmo de evaluación, que es este de aquí.
Así que nuestra magnitud cuadrado será un punto de identificación o conseguir I'd punto de transformación de la posición menos y que tiene que estar en un paréntesis
alrededor de allí menos nuestro otro nodo, que es el nodo B.
Así que el punto B obtiene el punto ID, transforma la posición del punto así.
De acuerdo.
Así que esa va a ser nuestra heurística.
Ahora, me falta un soporte justo ahí.
De acuerdo.
En este momento, una vez que tenemos eso asociado a cada nodo, necesitamos encontrar el que tiene la distancia más corta, eso significa
que necesitaremos otro algoritmo para encontrarlo.
Ahora, en la versión anterior de una estrella que creamos, en la última sección, usamos una consulta de enlace para
hacerlo.
No vamos a hacer eso ahora.
En realidad vamos a hacerlo manualmente.
Así que este es el mismo algoritmo, pero un poco, supongo, más práctico, más manual de escribir
todo.
Así que vamos a llamar a esto el más bajo F y esto es básicamente va a hacer nuestra consulta LINQ de todos modos.
Así que el nodo de la lista pasará a través de todos nuestros nodos y luego aquí vamos a calcular y devolver la posición
del nodo más bajo.
Así que queremos que float lowest f sea igual a cero, int count sea igual a cero int iterator count sea igual a cero.
Ahora vamos a inicializar nuestro valor f más bajo para que sea f más bajo va a ser igual al primer valor de nuestra lista.
Así que L cero punto f y la cuenta de iteración es cero para eso.
Así que tenemos que asegurarnos de que esta cuenta de iteración se alinea con lo que hay en esta L aquí, lo que haremos en
el siguiente bucle.
Así que ahora haremos un bucle con todos ellos y los comprobaremos para encontrar el más bajo.
Así que para int i es igual a uno I es menor que l punto cuenta i más más.
Y luego aquí.
Aquí.
Iremos si.
L en la posición I punto f es menor o igual que la f más baja entonces la f más baja es igual a l i punto f y la cuenta del iterador
es igual a nuestra cuenta.
De acuerdo.
Así que entonces.
Entonces, aquí abajo, cuenta más, más.
Y después de eso devolvemos el recuento de nuestro iterador, que será nuestro nodo con el valor F más bajo k.
Ahora, junto con esas dos cosas, tenemos que implementar nuestra estrella.
Así que subiremos por encima de nuestra distancia y pondremos esas cosas aquí.
K Así que este es un algoritmo bastante largo que habrás notado cuando lo repasamos antes, pero
esto será lo mismo pero ligeramente diferente porque no estamos usando ese código de enlace aquí.
Así que public bool a star game object start id game object y i d y entonces node start es igual a nuestro find node start
ID.
Así que estamos permitiendo que los objetos del juego
sean pasados y estamos usando nuestro nodo de búsqueda que creamos antes para obtener los nodos correctos de la lista, el nodo de búsqueda y el id k y luego si el inicio es igual a null o el final es igual a null, sólo un poco
de comprobación de errores.
Si no podemos encontrar esos nodos, devolveremos false y diremos, bueno, no hay camino aquí.
Bien, ahora vamos a entrar en la verdadera estrella.
Así que necesitamos una lista de nodos que será nuestra lista abierta.
Así que el nodo abierto es igual al nuevo nodo de la lista.
Y luego necesitamos lo mismo para nuestro cerrado.
Así que voy a copiar y pegar eso.
Esta es nuestra lista cerrada.
De acuerdo.
Entonces puedo crear un flotador para la puntuación g tentativa e igualarlo a cero.
¿Ahora qué era G?
Bueno, G es la distancia que hemos recorrido hasta ahora.
Bien, la puntuación G tentativa es la que daríamos al nodo si estuviéramos a punto de ponerlo en una lista y seleccionarlo
realmente como nuestra próxima posición en el gráfico.
Así que primero tenemos que calcularlo.
Básicamente, entonces vamos a tener un bool.
Es mejor que sea provisional.
Así que si calculamos que la puntuación G tentativa es realmente mejor que la que ya está en el nodo, entonces
podemos usar la mejor.
Así que vamos a ir con el punto de partida g es igual a cero.
Ahora bien, esto es antes de que hayamos comenzado a hacer un bucle a través de cualquier cosa, por lo que sólo estamos estableciendo
estos dos valores.
El inicio en h es igual a la distancia del inicio y k.
Así que H es nuestra distancia al final.
G es hasta dónde hemos llegado todos los costes hasta ahora, que va a ser cero porque no hemos ido a ninguna parte todavía.
Y entonces el punto inicial f es igual al punto inicial h porque no hay nada que sumar en este punto.
Ahora el anuncio abierto va a ser igual a nuestro nodo de inicio así.
Bien, así que ahora para nuestro gran bucle de pared, mientras que el recuento de puntos abiertos es mayor que cero,
vamos a hacer que un t int i es igual a la f más baja en la lista abierta porque queremos seleccionar que nuestro
siguiente vamos a ir a lo que el nodo este nodo es igual a la lista abierta en la posición I entonces si este punto este nodo punto ID es igual a la ID final, entonces eso significa
que hemos encontrado un camino.
Así que aquí vamos a reconstruir el camino que voy a escribir en un momento.
Así que reconstruir el camino que va a ser el nombre de nuestro método de principio a fin.
Hagamos de eso una capital y volveremos.
Es cierto.
Así que volveremos a hacer las reconstrucciones más tarde en los soportes que van allí porque eso es un método.
Así que vamos a bajar.
Y aquí no hemos encontrado el final.
Sigamos comparando cosas tan abiertas.
Quita el punto en.
Vamos a eliminar el nodo con el que estamos trabajando.
I.
Anuncio cerrado.
Este nodo porque ahora hemos dicho que lo estamos explorando.
Así que nodo vecino.
Así que desde ese nodo en particular, ahora vamos a explorar todos los vecinos.
Así que nodo vecino.
Así que para cada arista E en esta lista de aristas de nodo punto.
Así que estos son todos los caminos que salen de ese nodo en particular que acabamos de cerrar.
Vamos a explorar a todos estos vecinos.
Así que el vecino va a ser igual al nodo final E.
Ahora si.
Índice de puntos cerrados del vecino.
Así que si el vecino está fuera de los límites porque ya hemos estado allí, seguiremos mirando
los otros bordes porque no tiene sentido mirar algo que ya está cerrado.
De acuerdo.
Así que ahora también la puntuación g tentativa es igual a este nodo punto g más la distancia de este nodo al vecino.
Entonces, si el índice abierto del vecino es igual a menos uno, entonces no está en la lista abierta.
Queremos añadirlo a la lista abierta.
Así que abrir añadir vecino para que podamos explorar de nuevo la próxima
vez y luego vamos a establecer tentativa es mejor para igualar a la verdad, si diez a2g puntuación es menor que el punto g vecino, entonces también vamos a decir que
tentativa es mejor.
Es igual a verdadero.
Si no es así, es mejor que sea provisional.
Es igual a falso.
De acuerdo.
Así que una vez que hemos pasado por ese proceso, si el tentativo es mejor, si el valor a g que acabamos de calcular
es mejor, entonces queremos darle a ese nodo ese nuevo valor g.
Así que si tentativa es mejor que aquí, vamos.
El punto vecino de es igual a este nodo el punto vecino g es igual a la puntuación tentativa g el punto vecino h es igual
a la distancia de este nodo al nodo final y entonces el punto vecino f es igual al punto vecino g más el punto
vecino h.
Bien, ya está hecho.
Ahora bien, si hemos llegado hasta aquí y no hemos devuelto un true más arriba en ningún sitio, entonces lo que queremos, que sería aquí arriba
donde construimos el camino es salir de aquí con un return false, diciendo
que todavía no hay camino.
No hay ningún camino entre esos dos nodos que se pueda encontrar.
Muy bien.
Así que este es nuestro algoritmo de la estrella A.
Ahora tenemos dentro de su estructura real los nodos todos unidos en base a este valor aquí.
Así que para cuando hayamos recorrido esto, en realidad tenemos una larga lista de nodos como una lista enlazada o básicamente
es una lista enlazada de nodos.
Estamos en el nodo final, nos hemos hecho con el nodo final.
Ahora tenemos que volver a subir hasta el inicio para que realmente el camino sea en su dirección hacia
adelante, no en su dirección inversa.
Así que cuando volvamos en la próxima clase, seguiremos trabajando en esto y escribiremos este método de reconstrucción
de la ruta para que podamos obtener realmente la ruta que estamos buscando.