El algoritmo de la estrella fue inventado por los informáticos Nils Nilsson, Peter Hart y Bertram Rafael mientras
trabajaban en el desarrollo de un sistema de navegación para el Shakey, el Proyecto de Investigación
de Robots de Stanford en 1968.
Tenían dos algoritmos en los que estaban trabajando en ese momento, tratando de encontrar formas optimizadas de determinar las trayectorias
a través de los entornos.
Los llamaron uno y dos.
Resultó que un dos era en realidad lo más óptimo, por lo que lo llamaron simplemente estrella.
El algoritmo aStar es bastante sinónimo de A. I. en los juegos y se utiliza en todas partes, desde la planificación
de acciones y personajes hasta la determinación del mejor camino a través de un entorno.
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
y tienes que desarrollar el tuyo propio y, a menudo, encontrarás tu propia biblioteca y simplemente usarás eso en su lugar porque
va a funcionar y entonces no tendrás que entender lo que está pasando por debajo.
Pero es un algoritmo muy intuitivo basado en la forma en que los humanos piensan realmente.
Así que, en primer lugar, permítanme plantearles un pequeño reto.
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
mover en movimientos rectos hacia arriba y hacia abajo o de lado a lado.
Y quiero que pienses en cuál sería tu camino desde esta posición inicial hasta esta posición final, haz una
pausa en el vídeo ahora y tal vez dibuja un pequeño diagrama para pensar en lo que podrías hacer
y luego el razonamiento de por qué lo hiciste.
De acuerdo.
¿Cómo te fue?
Bueno, hay varias formas de hacerlo.
No puedes ir en diagonal, que sería el camino más corto desde el principio hasta el final, porque tenemos
que movernos de arriba a abajo o de izquierda a derecha, porque así estamos construyendo nuestro laberinto.
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
través, nada a través hasta que realmente golpeó esa esquina superior.
Y aquí está sólo uno de ellos.
Ahora, podrías haber cruzado y bajado y luego cruzar unas cuantas veces y luego subir.
Pero apuesto a que no lo has hecho.
Y la razón es que si bajas en cualquier punto de la salida, en realidad te estás alejando
de la meta.
Por lo tanto, la elección del siguiente paso debe acercarte a la meta,
no alejarla.
Bien, ¿y si te dijera que el laberinto en realidad se parece a esto y que hay un pequeño problema con el
camino que se te ocurrió?
En realidad hay un muro en la carretera, y por lo tanto no se puede ir por ahí.
¿Qué camino tomarías en su lugar?
Pues bien, para empezar te dirigirías hacia abajo y luego volverías a subir, porque ese es el único camino que
puedes seguir.
Pero la cosa es que, cuando no lo sabes, esas paredes están ahí, así que no puedes ver tan
lejos.
Quieres acercarte a la posición de tu objetivo porque parece ser el camino más intuitivo.
Y esta es realmente la base del algoritmo de la estrella.
Quiere seguir probando los cuadrados que más se acerquen al objetivo final.
Veamos cómo funciona una estrella considerando este mapa.
Empezando por la esquina inferior derecha, tenemos que decidir qué vecino escoger.
Recuerda que sólo nos movemos vertical y horizontalmente.
Sin embargo, si permitiera un movimiento en diagonal, tendría un vecino más.
El algoritmo funcionará igual, pero no estamos haciendo diagonales por el momento, así que podemos olvidarnos
de ese punto en particular.
Entonces, ¿qué vecino hacer parte del camino?
Bueno, si lo miras a ojo, la distancia en línea recta de cada uno de estos vecinos es prácticamente
la misma.
Bueno, es exactamente lo mismo, pero un algoritmo informático no puede hacerlo a ojo.
Sin embargo, puede calcular la distancia a la que se encuentra el objetivo de cada vecino.
Así que primero añadimos a nuestro algoritmo estrella el valor de H.
Ahora H representa idealmente el coste de ir del vecino a la meta.
En este caso, vamos a utilizar la distancia como nuestro coste.
Aunque se podrían incluir otras cosas en el coste, como que el camino más corto podría llevarte a
través de un amor de bits y por lo tanto no sólo considerarías la distancia como una de las cosas
incluidas en el coste, sino también cuánto daño causará al jugador.
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
Pitágoras.
También se podría determinar utilizando el número de movimientos X, más el número de movimientos Y entre el vecino
y la meta.
Realmente no importa cómo se mida, siempre y cuando se haga de forma consistente para todos los vecinos
para entender el siguiente valor utilizado en el algoritmo, vamos a echar un vistazo rápido a un ejemplo.
Supongamos que dos personas viajan del club de surf al club de golf.
En un momento dado, una persona está aquí y la otra está aquí simplemente mirando dónde está.
¿Puedes adivinar cuál de ellos tomó el camino más corto?
Si sólo se tomara la distancia a la meta, no se obtendría la historia completa
de lo que ya han recorrido.
Sin embargo, si se combina la distancia de los puntos al inicio con la distancia restante, se tendría una mejor
idea de la distancia total recorrida por cada uno, y entonces se podría averiguar cuál es el camino
más corto.
Y eso es lo que hace el algoritmo de estar.
Tiene en cuenta no sólo la distancia entre el punto y la meta, sino también la distancia que has recorrido para
llegar a ese punto.
En este caso, la distancia del inicio a cada vecino es uno.
Este valor se denota con la variable g.
A continuación, combinamos H y G y obtenemos un valor F, que es el total de estos.
Esencialmente, la F representa la aptitud de ese vecino en particular para estar en el camino hacia
la meta.
Una vez que se han calculado todos los valores de los vecinos, se elige el vecino con el valor F más
bajo como siguiente punto de la ruta para llevar la cuenta de los puntos visitados.
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
porque está bien, definitivamente en el camino.
A continuación, en este caso, tenemos vecinos con los mismos valores F.
Así que podemos elegir cualquiera de las dos porque ninguna es inferior a la otra.
Así que vamos a subir.
Añadimos este punto a la lista cerrada y luego abrimos sus vecinos.
Los nuevos vecinos se añaden a la lista abierta.
En este caso se calculan sus valores H, G y F.
Ahora tenemos dos puntos en la lista abierta.
¿Adónde vamos ahora?
Pues bien, encontramos el punto que tiene la F más baja y volvemos a él y echamos un vistazo a sus vecinos.
Así que en este caso, realmente subimos un poco.
Y como el valor F del Punto Verde de abajo es el más pequeño, volvemos
a él y lo ponemos en la lista cerrada y luego abrimos sus vecinos.
Y seguimos así hasta llegar al lugar de la meta.
De acuerdo.
Veamos un ejemplo de su funcionamiento.
De acuerdo.
Así que he generado un laberinto utilizando el método recursivo.
Además, he eliminado un poco de pared al azar y he puesto aquí algunos marcadores para mostrarte dónde va a estar
el inicio y el final de nuestra Estrella A.
Así que el naranja es el inicio y el amarillo aquí abajo es la posición final.
Así que cada marcador va a mostrar un valor G, H y F.
Así que G es la distancia desde el inicio que está aquí puedes ver que es uno para aquel y otro para este.
Así que estos eran los dos vecinos a los que te podías mover y el valor h es la distancia al amarillo.
Así que sólo estoy usando un viejo cálculo de distancia teorema de Pitágoras.
Y así desde este es 4. 47 y de éste para abajo son 4. 24.
Así que éste es obviamente más cercano.
El valor F, que es la suma de esos dos, nos da 5. 24 para este rojo y 5. 47 para el púrpura.
Ahora, ambos se ponen en la lista abierta y luego el que tiene el menor valor de F en este caso, este se
elige como el siguiente punto para echar un vistazo a generar vecinos de ahora.
Por eso se ha puesto rojo.
Así que se pondrá inmediatamente en rojo al seleccionar el siguiente de la lista abierta.
Así que se saca de la lista abierta, lo que significa que no puede volver a esa.
Bien, ahora vamos a echar un vistazo a los siguientes valores que se generan.
¿Verdad?
Así que este de aquí generó algunos vecinos.
Ahora ha vuelto y ha generado uno al principio, lo cual está bien, porque en este caso no
tengo mi inicio añadido en la lista abierta al principio y entonces no está marcado como cerrado sin embargo.
Podría hacerlo, pero esto sigue funcionando de todos modos.
Veamos los valores de la distancia.
Así que la distancia de este desde el principio va a ser la distancia que su padre es así donde vino,
que era uno más la distancia de allí.
Bien, ahora tenemos dos, lo que nos hace dos de allí.
Así que sumamos esta distancia y esta distancia, la distancia es entonces esta distancia a través de aquí.
Ahora bien, esto también se ha calculado, pero como está más lejos, básicamente se va a ignorar.
En este caso se habrían actualizado de nuevo sus valores.
Así que va a seguir siendo uno desde el inicio real, que todavía está aquí.
Ahora, te preguntarás, ¿por qué dice 24g aquí arriba?
Porque este era un nodo o un vecino de este, y realmente recorrió el camino para volver a este, fue como aquí
y luego volvió a allí.
Por eso es un dos.
Y lo deja fuera de combate básicamente porque es un valor muy alto.
De acuerdo.
Así que echemos un vistazo a lo que se va a elegir a continuación.
Este obviamente, porque ya se ha puesto en rojo y se ha puesto en la lista cerrada, 5. 47 para el valor
F.
Y aquí abajo tenemos 5. 61.
Así que esta va a quedar a la intemperie hasta que se convierta en algo pequeño, si es que llega a serlo.
Bien, vamos de nuevo.
Sí.
Así que ahora este ha generado otro punto de vuelta a allí, que es básicamente ignorado.
Y su otro vecino, que está por aquí, tiene su G, que es dos.
Bien, porque es como uno, dos y luego es el valor H que es 4. 12.
De nuevo, esta distancia aquí le da 6. 12.
Este valor de aquí fue recalculado o reutilizado porque todavía estaba abierto, ¿recuerdas?
Y por eso es más pequeño, por lo que es elegido.
Así que ahora se generarán los vecinos para esto.
Así que eso significa que este se genera.
Recuerda que ese ya está en la lista cerrada, así que no se hará.
De acuerdo.
Ahora, si echamos un vistazo a estos dos valores, podemos ver que este va a ser obviamente el más cercano.
Así que vamos de nuevo y llegamos aquí.
Ahora, mira esto.
Este ya tiene 6 años. 24.
Aunque en realidad está más cerca, podemos ver físicamente que está más cerca.
Este punto de aquí arriba es el 6. 12.
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.
Es la que va a hacer que se calcule el próximo vecino.
Así que si vamos por eso, no generó un punto por aquí.
Ahora, terminó con una F de siete, lo que hizo que este volviera a ser candidato.
Así que hemos vuelto aquí.
Bien, tenemos más vecinos.
Así que estos dos, este terminó más cerca, entonces generamos otro vecino allí.
De acuerdo.
Ahora, si echamos un vistazo a estos que están abiertos, se puede ver que son, de hecho, todos los valores de.
Siete.
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í
que sólo escogemos uno.
Así que hemos vuelto a rebotar hasta allí.
Generará este, que es el 8. 12.
Ahora, usted vio que esto fue rojo, por lo que decidió que elegiría este en su lugar, lo
que genera que uno, que luego viene abajo y genera este, que es nuestro valor final.
De acuerdo.
Así que puedes ver que la estrella a no se limita a hacer dum dum dum dum hasta aquí.
De hecho, rebotará un poco hacia adelante y hacia atrás mientras explora más cosas a su alrededor.
Lo bueno de esto es que nunca se mira demasiado lejos, ¿vale?
Sólo calcula esos valores de distancia, la distancia que ya has recorrido y la que
te queda por recorrer, básicamente.
Bien, ahora si le doy a la tecla de mapeo que he programado, nos mostrará nuestro camino calculado.
Ahora, para obtener el camino al final, se acaba con todos estos vecinos o nodos.
Podríamos llamarlos en la lista cerrada hasta aquí.
Así que lo que hacemos es empezar con éste y seguirlo hasta los puntos de los que venimos.
Así que mientras viajamos, cada vez que vamos a un nuevo vecino, éste tiene que recordar
a su padre.
Así que al final podemos viajar de nuevo a través de ese árbol padre y obtener nuestro camino.
Bien, este es el algoritmo de las estrellas y su funcionamiento.
Así que es un algoritmo bastante sencillo.
Las ideas son muy simples.
No está haciendo nada extraño, como he dicho, mirando hacia adelante o algo así.
Y ahora espero que tengas una mejor comprensión conceptual de cómo va todo junto, porque cuando volvamos
en la próxima conferencia, vas a construir esto en tu sistema de laberinto.