WEBVTT

00:02.860 --> 00:06.940
En la conferencia anterior, empezamos a trabajar en nuestra Graph API.

00:06.970 --> 00:13.510
Ahora estamos en el punto en el que estamos listos para poner en la funcionalidad para una búsqueda de ruta del algoritmo de

00:13.510 --> 00:14.290
la estrella A.

00:14.620 --> 00:20.940
Así que probablemente tenga sentido revisar el algoritmo de aStar que vimos en la sección anterior.

00:20.950 --> 00:28.870
Así que tenemos un laberinto o tenemos una serie de puntos de ruta que están conectados con bordes que no son diferentes

00:28.870 --> 00:30.020
a un laberinto.

00:30.040 --> 00:36.280
Así que en el laberinto, cada cuadrado era básicamente un nodo, y si podías ir de un cuadrado a otro, entonces

00:36.280 --> 00:39.220
eso era un borde o un camino entre ellos.

00:39.340 --> 00:41.500
Así que tenemos que empezar a posicionarnos.

00:41.500 --> 00:43.000
Tenemos una posición de gol.

00:43.000 --> 00:45.690
Tenemos que calcular cómo superar esto.

00:45.700 --> 00:52.600
Ahora, hay tres valores que vamos a evaluar cada posición, y es el valor PH, que es el

00:52.600 --> 00:59.920
costo de llegar a la meta desde ese nodo, el valor G, que es el costo de llegar a ese nodo.

00:59.920 --> 01:02.860
Entonces, cuánto ha costado llegar a ese nodo desde el principio.

01:02.860 --> 01:09.850
Y luego tenemos un valor H, que es la adición de ambas cosas que le da al nodo en general

01:09.850 --> 01:17.380
su tipo de costo holístico, supongo, sobre cómo es el ajuste, cómo es el mejor para ir.

01:17.380 --> 01:22.630
Así que vamos a escribir algunos de estos algoritmos en nuestra clase de grafos.

01:23.680 --> 01:24.160
De acuerdo.

01:24.160 --> 01:31.540
Así que, en primer lugar, vamos a crear nuestra heurística, que es básicamente nuestro método que determinará

01:31.540 --> 01:33.700
lo adecuado que es cada nodo.

01:33.700 --> 01:39.760
Y en este caso, vamos a utilizar la distancia desde el nodo a la ubicación final, que va a ser

01:39.760 --> 01:42.160
más o menos como el cuervo vuela.

01:42.280 --> 01:47.410
Por eso se llama holístico, supongo que es como la mejor suposición que se puede hacer porque no lo

01:47.410 --> 01:47.920
sabemos.

01:47.920 --> 01:51.700
En realidad no podemos volar directamente a la posición final.

01:51.700 --> 01:57.550
Podríamos ser capaces, pero desde cada nodo, esa va a ser nuestra mejor manera de medirlo.

01:57.550 --> 02:00.220
Así que vamos a crear algo que devuelva un flotador.

02:00.220 --> 02:03.160
Llamémosle distancia y entremos en ella.

02:03.190 --> 02:07.740
Pasaremos el nodo A y el nodo B.

02:07.750 --> 02:13.900
Ahora, por supuesto, este es un cálculo tan simple que probablemente no necesitas escribir un método para ello, pero de

02:13.900 --> 02:15.940
todos modos ah, sólo para que lo veas.

02:15.940 --> 02:21.670
Así que lo que vamos a devolver aquí es la magnitud al cuadrado.

02:21.670 --> 02:24.850
Así que queremos la magnitud del vector tres al cuadrado.

02:24.850 --> 02:30.400
Ahora la magnitud al cuadrado es más rápida de calcular que la magnitud real entre dos puntos,

02:30.400 --> 02:31.840
que es un vector.

02:31.840 --> 02:37.930
Y no importa si usamos una magnitud cuadrada mientras estemos evaluando cada nodo basado en el mismo tipo

02:37.930 --> 02:41.020
de algoritmo de evaluación, que es este de aquí.

02:41.020 --> 02:54.400
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

02:54.400 --> 03:00.460
alrededor de allí menos nuestro otro nodo, que es el nodo B.

03:00.460 --> 03:09.160
Así que el punto B obtiene el punto ID, transforma la posición del punto así.

03:09.160 --> 03:09.610
De acuerdo.

03:09.610 --> 03:12.430
Así que esa va a ser nuestra heurística.

03:12.610 --> 03:15.880
Ahora, me falta un soporte justo ahí.

03:15.880 --> 03:16.340
De acuerdo.

03:16.360 --> 03:25.090
En este momento, una vez que tenemos eso asociado a cada nodo, necesitamos encontrar el que tiene la distancia más corta, eso significa

03:25.090 --> 03:28.660
que necesitaremos otro algoritmo para encontrarlo.

03:28.690 --> 03:37.870
Ahora, en la versión anterior de una estrella que creamos, en la última sección, usamos una consulta de enlace para

03:37.870 --> 03:38.920
hacerlo.

03:39.280 --> 03:40.180
No vamos a hacer eso ahora.

03:40.180 --> 03:42.280
En realidad vamos a hacerlo manualmente.

03:42.280 --> 03:48.970
Así que este es el mismo algoritmo, pero un poco, supongo, más práctico, más manual de escribir

03:48.970 --> 03:49.600
todo.

03:49.600 --> 03:55.270
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.

03:55.270 --> 04:05.830
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

04:05.830 --> 04:07.930
del nodo más bajo.

04:07.930 --> 04:21.940
Así que queremos que float lowest f sea igual a cero, int count sea igual a cero int iterator count sea igual a cero.

04:22.720 --> 04:33.460
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.

04:33.460 --> 04:40.270
Así que L cero punto f y la cuenta de iteración es cero para eso.

04:40.270 --> 04:46.300
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

04:46.300 --> 04:47.410
el siguiente bucle.

04:47.410 --> 04:50.560
Así que ahora haremos un bucle con todos ellos y los comprobaremos para encontrar el más bajo.

04:50.560 --> 04:59.230
Así que para int i es igual a uno I es menor que l punto cuenta i más más.

05:00.820 --> 05:01.430
Y luego aquí.

05:01.480 --> 05:01.810
Aquí.

05:01.810 --> 05:03.700
Iremos si.

05:04.000 --> 05:21.790
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

05:21.790 --> 05:25.750
es igual a nuestra cuenta.

05:27.380 --> 05:27.690
De acuerdo.

05:28.120 --> 05:28.840
Así que entonces.

05:28.840 --> 05:33.730
Entonces, aquí abajo, cuenta más, más.

05:34.900 --> 05:48.150
Y después de eso devolvemos el recuento de nuestro iterador, que será nuestro nodo con el valor F más bajo k.

05:48.160 --> 05:54.070
Ahora, junto con esas dos cosas, tenemos que implementar nuestra estrella.

05:54.070 --> 05:59.080
Así que subiremos por encima de nuestra distancia y pondremos esas cosas aquí.

05:59.380 --> 06:05.440
K Así que este es un algoritmo bastante largo que habrás notado cuando lo repasamos antes, pero

06:05.530 --> 06:12.460
esto será lo mismo pero ligeramente diferente porque no estamos usando ese código de enlace aquí.

06:12.460 --> 06:35.890
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

06:36.820 --> 06:38.530
ID.

06:38.560 --> 06:43.090
Así que estamos permitiendo que los objetos del juego

06:43.090 --> 07:02.410
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

07:02.410 --> 07:05.740
de comprobación de errores.

07:05.740 --> 07:10.810
Si no podemos encontrar esos nodos, devolveremos false y diremos, bueno, no hay camino aquí.

07:11.970 --> 07:15.850
Bien, ahora vamos a entrar en la verdadera estrella.

07:15.850 --> 07:20.830
Así que necesitamos una lista de nodos que será nuestra lista abierta.

07:20.830 --> 07:26.770
Así que el nodo abierto es igual al nuevo nodo de la lista.

07:28.970 --> 07:31.850
Y luego necesitamos lo mismo para nuestro cerrado.

07:31.850 --> 07:33.800
Así que voy a copiar y pegar eso.

07:33.890 --> 07:35.810
Esta es nuestra lista cerrada.

07:37.250 --> 07:37.490
De acuerdo.

07:37.550 --> 07:48.080
Entonces puedo crear un flotador para la puntuación g tentativa e igualarlo a cero.

07:48.110 --> 07:49.540
¿Ahora qué era G?

07:49.550 --> 07:55.280
Bueno, G es la distancia que hemos recorrido hasta ahora.

07:55.310 --> 08:04.310
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

08:04.310 --> 08:08.570
realmente como nuestra próxima posición en el gráfico.

08:08.570 --> 08:10.190
Así que primero tenemos que calcularlo.

08:10.190 --> 08:12.980
Básicamente, entonces vamos a tener un bool.

08:13.280 --> 08:16.190
Es mejor que sea provisional.

08:16.190 --> 08:24.590
Así que si calculamos que la puntuación G tentativa es realmente mejor que la que ya está en el nodo, entonces

08:24.590 --> 08:27.050
podemos usar la mejor.

08:27.560 --> 08:31.490
Así que vamos a ir con el punto de partida g es igual a cero.

08:31.490 --> 08:35.300
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

08:35.300 --> 08:36.080
estos dos valores.

08:36.080 --> 08:44.970
El inicio en h es igual a la distancia del inicio y k.

08:45.200 --> 08:48.200
Así que H es nuestra distancia al final.

08:48.200 --> 08:53.300
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.

08:53.300 --> 09:02.930
Y entonces el punto inicial f es igual al punto inicial h porque no hay nada que sumar en este punto.

09:02.930 --> 09:09.650
Ahora el anuncio abierto va a ser igual a nuestro nodo de inicio así.

09:09.650 --> 09:21.770
Bien, así que ahora para nuestro gran bucle de pared, mientras que el recuento de puntos abiertos es mayor que cero,

09:21.770 --> 09:33.350
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

09:33.350 --> 09:51.170
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

09:51.170 --> 09:56.390
que hemos encontrado un camino.

09:57.860 --> 10:02.690
Así que aquí vamos a reconstruir el camino que voy a escribir en un momento.

10:02.690 --> 10:09.830
Así que reconstruir el camino que va a ser el nombre de nuestro método de principio a fin.

10:11.960 --> 10:16.070
Hagamos de eso una capital y volveremos.

10:16.790 --> 10:17.690
Es cierto.

10:17.990 --> 10:24.020
Así que volveremos a hacer las reconstrucciones más tarde en los soportes que van allí porque eso es un método.

10:24.260 --> 10:25.760
Así que vamos a bajar.

10:25.760 --> 10:27.660
Y aquí no hemos encontrado el final.

10:27.680 --> 10:31.060
Sigamos comparando cosas tan abiertas.

10:31.170 --> 10:33.170
Quita el punto en.

10:33.170 --> 10:35.390
Vamos a eliminar el nodo con el que estamos trabajando.

10:36.710 --> 10:37.520
I.

10:39.900 --> 10:41.700
Anuncio cerrado.

10:42.820 --> 10:47.950
Este nodo porque ahora hemos dicho que lo estamos explorando.

10:47.950 --> 10:49.990
Así que nodo vecino.

10:49.990 --> 10:56.500
Así que desde ese nodo en particular, ahora vamos a explorar todos los vecinos.

10:56.500 --> 10:57.910
Así que nodo vecino.

10:58.030 --> 11:04.330
Así que para cada arista E en esta lista de aristas de nodo punto.

11:04.330 --> 11:08.980
Así que estos son todos los caminos que salen de ese nodo en particular que acabamos de cerrar.

11:09.730 --> 11:12.820
Vamos a explorar a todos estos vecinos.

11:12.820 --> 11:19.030
Así que el vecino va a ser igual al nodo final E.

11:20.980 --> 11:22.300
Ahora si.

11:23.020 --> 11:27.580
Índice de puntos cerrados del vecino.

11:28.060 --> 11:35.410
Así que si el vecino está fuera de los límites porque ya hemos estado allí, seguiremos mirando

11:35.440 --> 11:41.620
los otros bordes porque no tiene sentido mirar algo que ya está cerrado.

11:41.770 --> 11:42.340
De acuerdo.

11:42.340 --> 11:53.260
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.

11:54.370 --> 12:04.890
Entonces, si el índice abierto del vecino es igual a menos uno, entonces no está en la lista abierta.

12:04.900 --> 12:06.730
Queremos añadirlo a la lista abierta.

12:06.730 --> 12:15.250
Así que abrir añadir vecino para que podamos explorar de nuevo la próxima

12:16.180 --> 12:35.080
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

12:35.080 --> 12:37.990
tentativa es mejor.

12:38.860 --> 12:40.330
Es igual a verdadero.

12:40.510 --> 12:44.070
Si no es así, es mejor que sea provisional.

12:44.080 --> 12:45.850
Es igual a falso.

12:47.280 --> 12:47.820
De acuerdo.

12:47.820 --> 12:54.630
Así que una vez que hemos pasado por ese proceso, si el tentativo es mejor, si el valor a g que acabamos de calcular

12:54.630 --> 12:58.560
es mejor, entonces queremos darle a ese nodo ese nuevo valor g.

12:58.560 --> 13:03.630
Así que si tentativa es mejor que aquí, vamos.

13:03.630 --> 13:20.970
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

13:21.090 --> 13:37.140
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

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

13:41.370 --> 13:43.110
Bien, ya está hecho.

13:43.110 --> 13:54.840
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

13:54.840 --> 14:00.720
donde construimos el camino es salir de aquí con un return false, diciendo

14:00.720 --> 14:03.900
que todavía no hay camino.

14:03.900 --> 14:08.070
No hay ningún camino entre esos dos nodos que se pueda encontrar.

14:08.370 --> 14:09.060
Muy bien.

14:09.060 --> 14:11.850
Así que este es nuestro algoritmo de la estrella A.

14:11.850 --> 14:22.680
Ahora tenemos dentro de su estructura real los nodos todos unidos en base a este valor aquí.

14:22.680 --> 14:28.710
Así que para cuando hayamos recorrido esto, en realidad tenemos una larga lista de nodos como una lista enlazada o básicamente

14:28.710 --> 14:30.750
es una lista enlazada de nodos.

14:30.750 --> 14:33.870
Estamos en el nodo final, nos hemos hecho con el nodo final.

14:33.900 --> 14:39.960
Ahora tenemos que volver a subir hasta el inicio para que realmente el camino sea en su dirección hacia

14:39.960 --> 14:42.510
adelante, no en su dirección inversa.

14:42.750 --> 14:48.750
Así que cuando volvamos en la próxima clase, seguiremos trabajando en esto y escribiremos este método de reconstrucción

14:48.750 --> 14:53.670
de la ruta para que podamos obtener realmente la ruta que estamos buscando.
