WEBVTT

00:02.610 --> 00:09.780
El algoritmo de la estrella fue inventado por los informáticos Nils Nilsson, Peter Hart y Bertram Rafael mientras

00:10.170 --> 00:16.620
trabajaban en el desarrollo de un sistema de navegación para el Shakey, el Proyecto de Investigación

00:16.620 --> 00:18.690
de Robots de Stanford en 1968.

00:19.440 --> 00:26.850
Tenían dos algoritmos en los que estaban trabajando en ese momento, tratando de encontrar formas optimizadas de determinar las trayectorias

00:26.850 --> 00:28.680
a través de los entornos.

00:29.310 --> 00:32.370
Los llamaron uno y dos.

00:32.400 --> 00:38.790
Resultó que un dos era en realidad lo más óptimo, por lo que lo llamaron simplemente estrella.

00:39.330 --> 00:45.690
El algoritmo aStar es bastante sinónimo de A. I. en los juegos y se utiliza en todas partes, desde la planificación

00:45.690 --> 00:49.680
de acciones y personajes hasta la determinación del mejor camino a través de un entorno.

00:49.860 --> 00:55.500
El algoritmo de la estrella tiende a ser algo que da un poco de miedo cuando te metes por primera vez en la informática

00:55.500 --> 01:02.220
y tienes que desarrollar el tuyo propio y, a menudo, encontrarás tu propia biblioteca y simplemente usarás eso en su lugar porque

01:02.220 --> 01:06.750
va a funcionar y entonces no tendrás que entender lo que está pasando por debajo.

01:06.780 --> 01:12.990
Pero es un algoritmo muy intuitivo basado en la forma en que los humanos piensan realmente.

01:13.020 --> 01:17.850
Así que, en primer lugar, permítanme plantearles un pequeño reto.

01:17.940 --> 01:24.180
Teniendo en cuenta este laberinto que ya he creado y de hecho, sólo supongo que es una habitación, pero sólo se puede

01:24.180 --> 01:28.440
mover en movimientos rectos hacia arriba y hacia abajo o de lado a lado.

01:28.440 --> 01:34.680
Y quiero que pienses en cuál sería tu camino desde esta posición inicial hasta esta posición final, haz una

01:34.680 --> 01:40.110
pausa en el vídeo ahora y tal vez dibuja un pequeño diagrama para pensar en lo que podrías hacer

01:40.110 --> 01:43.290
y luego el razonamiento de por qué lo hiciste.

01:51.350 --> 01:51.920
De acuerdo.

01:51.950 --> 01:52.970
¿Cómo te fue?

01:53.000 --> 01:55.490
Bueno, hay varias formas de hacerlo.

01:55.490 --> 02:00.170
No puedes ir en diagonal, que sería el camino más corto desde el principio hasta el final, porque tenemos

02:00.170 --> 02:05.170
que movernos de arriba a abajo o de izquierda a derecha, porque así estamos construyendo nuestro laberinto.

02:05.180 --> 02:10.490
Y así hay una variedad de patrones diferentes que podría haber llegado a ir hacia arriba y a través y hacia arriba y a

02:10.490 --> 02:13.910
través, nada a través hasta que realmente golpeó esa esquina superior.

02:13.910 --> 02:15.830
Y aquí está sólo uno de ellos.

02:16.040 --> 02:22.790
Ahora, podrías haber cruzado y bajado y luego cruzar unas cuantas veces y luego subir.

02:22.790 --> 02:25.130
Pero apuesto a que no lo has hecho.

02:25.130 --> 02:31.100
Y la razón es que si bajas en cualquier punto de la salida, en realidad te estás alejando

02:31.100 --> 02:32.660
de la meta.

02:32.690 --> 02:39.740
Por lo tanto, la elección del siguiente paso debe acercarte a la meta,

02:39.740 --> 02:41.720
no alejarla.

02:42.140 --> 02:48.950
Bien, ¿y si te dijera que el laberinto en realidad se parece a esto y que hay un pequeño problema con el

02:48.950 --> 02:50.720
camino que se te ocurrió?

02:50.720 --> 02:55.250
En realidad hay un muro en la carretera, y por lo tanto no se puede ir por ahí.

02:55.280 --> 02:58.070
¿Qué camino tomarías en su lugar?

02:58.190 --> 03:05.120
Pues bien, para empezar te dirigirías hacia abajo y luego volverías a subir, porque ese es el único camino que

03:05.120 --> 03:06.320
puedes seguir.

03:06.650 --> 03:12.260
Pero la cosa es que, cuando no lo sabes, esas paredes están ahí, así que no puedes ver tan

03:12.260 --> 03:12.980
lejos.

03:12.980 --> 03:21.590
Quieres acercarte a la posición de tu objetivo porque parece ser el camino más intuitivo.

03:21.590 --> 03:26.240
Y esta es realmente la base del algoritmo de la estrella.

03:26.240 --> 03:32.870
Quiere seguir probando los cuadrados que más se acerquen al objetivo final.

03:33.140 --> 03:37.310
Veamos cómo funciona una estrella considerando este mapa.

03:37.400 --> 03:42.500
Empezando por la esquina inferior derecha, tenemos que decidir qué vecino escoger.

03:42.620 --> 03:46.460
Recuerda que sólo nos movemos vertical y horizontalmente.

03:46.460 --> 03:52.070
Sin embargo, si permitiera un movimiento en diagonal, tendría un vecino más.

03:52.220 --> 03:57.980
El algoritmo funcionará igual, pero no estamos haciendo diagonales por el momento, así que podemos olvidarnos

03:57.980 --> 03:59.420
de ese punto en particular.

03:59.870 --> 04:03.320
Entonces, ¿qué vecino hacer parte del camino?

04:03.650 --> 04:09.620
Bueno, si lo miras a ojo, la distancia en línea recta de cada uno de estos vecinos es prácticamente

04:09.620 --> 04:10.550
la misma.

04:10.550 --> 04:15.050
Bueno, es exactamente lo mismo, pero un algoritmo informático no puede hacerlo a ojo.

04:15.080 --> 04:20.660
Sin embargo, puede calcular la distancia a la que se encuentra el objetivo de cada vecino.

04:20.660 --> 04:25.460
Así que primero añadimos a nuestro algoritmo estrella el valor de H.

04:25.670 --> 04:31.160
Ahora H representa idealmente el coste de ir del vecino a la meta.

04:31.160 --> 04:35.060
En este caso, vamos a utilizar la distancia como nuestro coste.

04:35.480 --> 04:41.360
Aunque se podrían incluir otras cosas en el coste, como que el camino más corto podría llevarte a

04:41.360 --> 04:46.880
través de un amor de bits y por lo tanto no sólo considerarías la distancia como una de las cosas

04:46.880 --> 04:51.470
incluidas en el coste, sino también cuánto daño causará al jugador.

04:51.470 --> 04:59.390
Por lo tanto, en este caso, la distancia de cada vecino y, por lo tanto, el valor de h es 5. 8, que determiné usando el teorema de

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

05:00.980 --> 05:09.560
También se podría determinar utilizando el número de movimientos X, más el número de movimientos Y entre el vecino

05:09.560 --> 05:10.280
y la meta.

05:10.280 --> 05:15.980
Realmente no importa cómo se mida, siempre y cuando se haga de forma consistente para todos los vecinos

05:15.980 --> 05:22.220
para entender el siguiente valor utilizado en el algoritmo, vamos a echar un vistazo rápido a un ejemplo.

05:22.220 --> 05:26.090
Supongamos que dos personas viajan del club de surf al club de golf.

05:26.120 --> 05:33.650
En un momento dado, una persona está aquí y la otra está aquí simplemente mirando dónde está.

05:33.680 --> 05:36.620
¿Puedes adivinar cuál de ellos tomó el camino más corto?

05:36.620 --> 05:41.780
Si sólo se tomara la distancia a la meta, no se obtendría la historia completa

05:41.780 --> 05:43.940
de lo que ya han recorrido.

05:44.690 --> 05:51.200
Sin embargo, si se combina la distancia de los puntos al inicio con la distancia restante, se tendría una mejor

05:51.200 --> 05:56.870
idea de la distancia total recorrida por cada uno, y entonces se podría averiguar cuál es el camino

05:56.870 --> 05:58.340
más corto.

05:58.340 --> 06:00.560
Y eso es lo que hace el algoritmo de estar.

06:00.560 --> 06:06.530
Tiene en cuenta no sólo la distancia entre el punto y la meta, sino también la distancia que has recorrido para

06:06.530 --> 06:07.730
llegar a ese punto.

06:07.940 --> 06:12.770
En este caso, la distancia del inicio a cada vecino es uno.

06:12.770 --> 06:15.770
Este valor se denota con la variable g.

06:16.620 --> 06:22.590
A continuación, combinamos H y G y obtenemos un valor F, que es el total de estos.

06:22.800 --> 06:29.580
Esencialmente, la F representa la aptitud de ese vecino en particular para estar en el camino hacia

06:29.580 --> 06:30.290
la meta.

06:30.300 --> 06:35.940
Una vez que se han calculado todos los valores de los vecinos, se elige el vecino con el valor F más

06:35.940 --> 06:41.040
bajo como siguiente punto de la ruta para llevar la cuenta de los puntos visitados.

06:41.070 --> 06:48.540
Hay una lista abierta y otra cerrada, así que obviamente START va a ir a la lista cerrada después de que se generen sus vecinos

06:48.540 --> 06:52.140
porque está bien, definitivamente en el camino.

06:52.170 --> 06:55.980
A continuación, en este caso, tenemos vecinos con los mismos valores F.

06:55.980 --> 07:00.960
Así que podemos elegir cualquiera de las dos porque ninguna es inferior a la otra.

07:01.350 --> 07:03.150
Así que vamos a subir.

07:03.210 --> 07:08.250
Añadimos este punto a la lista cerrada y luego abrimos sus vecinos.

07:08.880 --> 07:12.870
Los nuevos vecinos se añaden a la lista abierta.

07:13.320 --> 07:18.690
En este caso se calculan sus valores H, G y F.

07:18.690 --> 07:22.890
Ahora tenemos dos puntos en la lista abierta.

07:23.040 --> 07:24.360
¿Adónde vamos ahora?

07:24.360 --> 07:33.150
Pues bien, encontramos el punto que tiene la F más baja y volvemos a él y echamos un vistazo a sus vecinos.

07:33.150 --> 07:36.690
Así que en este caso, realmente subimos un poco.

07:36.690 --> 07:43.350
Y como el valor F del Punto Verde de abajo es el más pequeño, volvemos

07:43.350 --> 07:49.890
a él y lo ponemos en la lista cerrada y luego abrimos sus vecinos.

07:50.880 --> 07:55.500
Y seguimos así hasta llegar al lugar de la meta.

07:56.750 --> 07:57.230
De acuerdo.

07:57.230 --> 08:01.040
Veamos un ejemplo de su funcionamiento.

08:01.080 --> 08:01.300
De acuerdo.

08:01.310 --> 08:05.750
Así que he generado un laberinto utilizando el método recursivo.

08:05.750 --> 08:13.010
Además, he eliminado un poco de pared al azar y he puesto aquí algunos marcadores para mostrarte dónde va a estar

08:13.010 --> 08:16.130
el inicio y el final de nuestra Estrella A.

08:16.130 --> 08:21.170
Así que el naranja es el inicio y el amarillo aquí abajo es la posición final.

08:21.320 --> 08:25.880
Así que cada marcador va a mostrar un valor G, H y F.

08:25.880 --> 08:33.410
Así que G es la distancia desde el inicio que está aquí puedes ver que es uno para aquel y otro para este.

08:33.410 --> 08:42.530
Así que estos eran los dos vecinos a los que te podías mover y el valor h es la distancia al amarillo.

08:42.530 --> 08:47.870
Así que sólo estoy usando un viejo cálculo de distancia teorema de Pitágoras.

08:47.870 --> 08:53.120
Y así desde este es 4. 47 y de éste para abajo son 4. 24.

08:53.120 --> 08:54.730
Así que éste es obviamente más cercano.

08:54.800 --> 09:04.310
El valor F, que es la suma de esos dos, nos da 5. 24 para este rojo y 5. 47 para el púrpura.

09:04.310 --> 09:12.410
Ahora, ambos se ponen en la lista abierta y luego el que tiene el menor valor de F en este caso, este se

09:12.410 --> 09:18.980
elige como el siguiente punto para echar un vistazo a generar vecinos de ahora.

09:18.980 --> 09:20.180
Por eso se ha puesto rojo.

09:20.180 --> 09:23.960
Así que se pondrá inmediatamente en rojo al seleccionar el siguiente de la lista abierta.

09:23.960 --> 09:28.790
Así que se saca de la lista abierta, lo que significa que no puede volver a esa.

09:28.910 --> 09:32.720
Bien, ahora vamos a echar un vistazo a los siguientes valores que se generan.

09:32.990 --> 09:33.320
¿Verdad?

09:33.320 --> 09:36.380
Así que este de aquí generó algunos vecinos.

09:36.380 --> 09:41.390
Ahora ha vuelto y ha generado uno al principio, lo cual está bien, porque en este caso no

09:41.390 --> 09:47.780
tengo mi inicio añadido en la lista abierta al principio y entonces no está marcado como cerrado sin embargo.

09:47.780 --> 09:50.570
Podría hacerlo, pero esto sigue funcionando de todos modos.

09:50.570 --> 09:52.640
Veamos los valores de la distancia.

09:52.640 --> 10:02.870
Así que la distancia de este desde el principio va a ser la distancia que su padre es así donde vino,

10:02.870 --> 10:07.160
que era uno más la distancia de allí.

10:07.160 --> 10:10.310
Bien, ahora tenemos dos, lo que nos hace dos de allí.

10:10.310 --> 10:18.200
Así que sumamos esta distancia y esta distancia, la distancia es entonces esta distancia a través de aquí.

10:18.230 --> 10:24.110
Ahora bien, esto también se ha calculado, pero como está más lejos, básicamente se va a ignorar.

10:24.620 --> 10:30.680
En este caso se habrían actualizado de nuevo sus valores.

10:30.680 --> 10:35.960
Así que va a seguir siendo uno desde el inicio real, que todavía está aquí.

10:36.350 --> 10:39.980
Ahora, te preguntarás, ¿por qué dice 24g aquí arriba?

10:39.980 --> 10:47.390
Porque este era un nodo o un vecino de este, y realmente recorrió el camino para volver a este, fue como aquí

10:47.390 --> 10:49.280
y luego volvió a allí.

10:49.280 --> 10:50.810
Por eso es un dos.

10:51.020 --> 10:55.580
Y lo deja fuera de combate básicamente porque es un valor muy alto.

10:55.760 --> 10:56.150
De acuerdo.

10:56.150 --> 10:59.690
Así que echemos un vistazo a lo que se va a elegir a continuación.

10:59.900 --> 11:05.510
Este obviamente, porque ya se ha puesto en rojo y se ha puesto en la lista cerrada, 5. 47 para el valor

11:05.510 --> 11:06.230
F.

11:06.230 --> 11:08.900
Y aquí abajo tenemos 5. 61.

11:08.900 --> 11:15.110
Así que esta va a quedar a la intemperie hasta que se convierta en algo pequeño, si es que llega a serlo.

11:15.230 --> 11:16.790
Bien, vamos de nuevo.

11:17.330 --> 11:17.660
Sí.

11:17.660 --> 11:22.940
Así que ahora este ha generado otro punto de vuelta a allí, que es básicamente ignorado.

11:23.090 --> 11:27.920
Y su otro vecino, que está por aquí, tiene su G, que es dos.

11:27.920 --> 11:33.770
Bien, porque es como uno, dos y luego es el valor H que es 4. 12.

11:33.770 --> 11:37.850
De nuevo, esta distancia aquí le da 6. 12.

11:37.850 --> 11:44.180
Este valor de aquí fue recalculado o reutilizado porque todavía estaba abierto, ¿recuerdas?

11:44.240 --> 11:47.930
Y por eso es más pequeño, por lo que es elegido.

11:47.930 --> 11:50.390
Así que ahora se generarán los vecinos para esto.

11:50.900 --> 11:52.730
Así que eso significa que este se genera.

11:52.730 --> 11:55.280
Recuerda que ese ya está en la lista cerrada, así que no se hará.

11:55.280 --> 11:55.760
De acuerdo.

11:55.760 --> 12:02.360
Ahora, si echamos un vistazo a estos dos valores, podemos ver que este va a ser obviamente el más cercano.

12:02.360 --> 12:04.700
Así que vamos de nuevo y llegamos aquí.

12:04.700 --> 12:05.870
Ahora, mira esto.

12:05.870 --> 12:10.160
Este ya tiene 6 años. 24.

12:10.760 --> 12:15.980
Aunque en realidad está más cerca, podemos ver físicamente que está más cerca.

12:15.980 --> 12:20.720
Este punto de aquí arriba es el 6. 12.

12:20.720 --> 12:26.000
Ahora bien, esto seguía abierto hasta hace poco, sólo se puso en rojo, lo que significa que está en la lista de cerrados.

12:26.000 --> 12:28.820
Es la que va a hacer que se calcule el próximo vecino.

12:28.820 --> 12:33.110
Así que si vamos por eso, no generó un punto por aquí.

12:33.530 --> 12:38.270
Ahora, terminó con una F de siete, lo que hizo que este volviera a ser candidato.

12:38.270 --> 12:39.770
Así que hemos vuelto aquí.

12:39.950 --> 12:41.330
Bien, tenemos más vecinos.

12:41.330 --> 12:47.240
Así que estos dos, este terminó más cerca, entonces generamos otro vecino allí.

12:47.270 --> 12:47.630
De acuerdo.

12:47.630 --> 12:55.850
Ahora, si echamos un vistazo a estos que están abiertos, se puede ver que son, de hecho, todos los valores de.

12:55.970 --> 12:56.630
Siete.

12:56.630 --> 13:04.190
Así que sólo escoge uno de esos al azar porque va a ordenarlos por el más pequeño, pero todos son iguales, así

13:04.190 --> 13:06.020
que sólo escogemos uno.

13:06.200 --> 13:08.210
Así que hemos vuelto a rebotar hasta allí.

13:08.210 --> 13:12.170
Generará este, que es el 8. 12.

13:12.200 --> 13:17.630
Ahora, usted vio que esto fue rojo, por lo que decidió que elegiría este en su lugar, lo

13:17.630 --> 13:23.090
que genera que uno, que luego viene abajo y genera este, que es nuestro valor final.

13:23.300 --> 13:23.600
De acuerdo.

13:23.630 --> 13:28.010
Así que puedes ver que la estrella a no se limita a hacer dum dum dum dum hasta aquí.

13:28.010 --> 13:32.810
De hecho, rebotará un poco hacia adelante y hacia atrás mientras explora más cosas a su alrededor.

13:32.900 --> 13:39.030
Lo bueno de esto es que nunca se mira demasiado lejos, ¿vale?

13:39.110 --> 13:44.600
Sólo calcula esos valores de distancia, la distancia que ya has recorrido y la que

13:44.600 --> 13:47.260
te queda por recorrer, básicamente.

13:47.360 --> 13:55.670
Bien, ahora si le doy a la tecla de mapeo que he programado, nos mostrará nuestro camino calculado.

13:55.670 --> 14:01.850
Ahora, para obtener el camino al final, se acaba con todos estos vecinos o nodos.

14:01.850 --> 14:06.080
Podríamos llamarlos en la lista cerrada hasta aquí.

14:06.080 --> 14:13.040
Así que lo que hacemos es empezar con éste y seguirlo hasta los puntos de los que venimos.

14:13.040 --> 14:18.380
Así que mientras viajamos, cada vez que vamos a un nuevo vecino, éste tiene que recordar

14:18.380 --> 14:19.660
a su padre.

14:19.670 --> 14:25.850
Así que al final podemos viajar de nuevo a través de ese árbol padre y obtener nuestro camino.

14:26.720 --> 14:30.620
Bien, este es el algoritmo de las estrellas y su funcionamiento.

14:30.620 --> 14:34.220
Así que es un algoritmo bastante sencillo.

14:34.220 --> 14:36.410
Las ideas son muy simples.

14:36.410 --> 14:41.210
No está haciendo nada extraño, como he dicho, mirando hacia adelante o algo así.

14:41.840 --> 14:48.620
Y ahora espero que tengas una mejor comprensión conceptual de cómo va todo junto, porque cuando volvamos

14:48.620 --> 14:54.530
en la próxima conferencia, vas a construir esto en tu sistema de laberinto.
