Advertisement
  1. Code
  2. Games

Serie de Inteligencia Artificial - Parte 1: Búsqueda de caminos

Scroll to top
Read Time: 24 min

Spanish (Español) translation by Manuel (you can also view the original English article)

Este tutorial es el primero de tres que tratan sobre cómo dar algo de Inteligencia Artificial (IA) a los juegos y aplicaciones que crees. En este primer tutorial vamos a aprender sobre la búsqueda de rutas.


Avance del resultado final

Veamos el resultado final para el que vamos a trabajar:

Haz clic en un punto, luego en otro y la IA calculará el camino más corto posible para llegar entre ellos. Puedes utilizar la lista desplegable para seleccionar el algoritmo de IA a utilizar.


Paso 1: Visión general de la serie AI

Este tutorial será el primero de tres que tratarán sobre cómo dotar de Inteligencia Artificial (IA) a los juegos y aplicaciones que crees. Puede que pienses que esto suena demasiado difícil, pero en realidad es bastante sencillo. Explicaré dos aspectos clave de la IA en los juegos y, a continuación, crearé un juego interesante utilizando lo que aprendamos. ¡Espero que disfrutes de esta breve serie!


Paso 2: Introducción

En los juegos, uno de los aspectos más importantes es que sean muy eficientes, que hagan lo que tienen que hacer utilizando los mínimos recursos. Hay toda una ciencia sólo para eso.

En este tutorial vamos a cubrir un aspecto clave en el desarrollo de juegos: el pathfinding. Discutiremos los 2 mejores métodos, cómo funcionan, cómo los hacemos funcionar en AS3, y por último, pero no menos importante, cuándo usarlos. Vamos a empezar...


Paso 3: ¿De qué se trata el Pathfinding?

Supón que te encuentras en medio de un bosque con 50 rutas potenciales diferentes frente a ti, no tienes casi energía y necesitas encontrar la mejor salida, ¿Cómo lo harías?

Una opción sería seguir cada una de las 50 rutas; un método de prueba y error. Seguramente saldrá, pero eso llevaría demasiado tiempo. Este problema no es nuevo y muchas personas han aportado ideas para resolverlo. Uno de ellos fue Edsger W. Dijkstra, que desarrolló un algoritmo para obtener el camino más corto dado un gráfico, un origen y un destino.

Antes de empezar a resolver el problema, debemos crear esos elementos, el grafo que contiene toda la información, los nodos que son el punto de paso del grafo, y las aristas que conectan los nodos. Piensa que el gráfico es un mapa: los nodos son las ciudades y las aristas las carreteras que las conectan.


Paso 4: Configuración del proyecto

Antes de empezar a codificar, vamos a configurar nuestro espacio de trabajo. Crea una nueva carpeta y nómbrala "PathFinding". Dentro de ella crea otra carpeta y nómbrala "Graph". Luego, en la carpeta PathFinding crea un nuevo archivo FLA de Flash (AS3) y llámalo "PathFinding".


Paso 5: Creación del símbolo del nodo

En el "PathFinding.fla" ve a Insert > New Symbol y crea un nuevo MovieClip llamado Node. Selecciona "export for actionscript" y como clase escribe "Graph.Node"


Paso 6: Dibujar el nodo

Dentro del Movieclip del Nodo, crea un nuevo Círculo con un radio de 25 y colócalo en el centro. A continuación, añade un nuevo cuadro de texto, hazlo dinámico y dale un nombre de instancia "idx_txt" y colócalo en el centro del escenario.


Paso 7: Creación del nodo

Cada nodo se compone de dos elementos principales: un índice para identificarlo y su posición en el gráfico. Con esto en mente crea una nueva clase dentro de la carpeta/paquete Graph y llámala "Node". Haz que extienda la clase sprite, entonces sólo añade dos variables: una int para el índice, y un Vector3D para la posición. Además, añade sus correspondientes métodos set y get:


Paso 8: Creación del borde

La arista contiene tres elementos: los índices de los dos nodos que conecta y su "coste" (o distancia entre nodos en este caso). De nuevo en el paquete/carpeta Graph crea una nueva clase y llámala "Edge"; haz que extienda la clase Sprite de nuevo.

Ahora agrega dos ints para los nodos, y un Number para el costo, luego agrega los métodos set y get correspondientes:


Paso 9: Creación del gráfico

El gráfico es un elemento más complejo ya que debe almacenar toda la información. En la carpeta Graph, crea una nueva clase y nómbrala "Graph". Como sólo contiene datos, no es necesario extender la clase Sprite.

El gráfico contendrá un Vector con todos los nodos del gráfico, otro Vector con las aristas que tiene cada nodo y un int estático para obtener el siguiente índice disponible para un nodo. De esta manera, será más fácil acceder a todos los elementos del gráfico, ya que el índice del nodo es la clave del vector de aristas, lo que significa que si quieres obtener las aristas de un nodo con índice 3, accedes al vector de aristas en la posición 3 y obtendrás las aristas de ese nodo.

Ahora vamos a crear estas variables:

El gráfico también necesita métodos para añadir y obtener nodos y aristas:


Paso 10: Construir un gráfico

Ahora que tenemos todos los elementos necesarios, vamos a construir un gráfico.

En la carpeta PathFinding, crea una nueva clase y llámala "Main", esta será nuestra clase principal:

Ahora tenemos que importar las clases que acabamos de crear, ya que están en la carpeta Graph. A continuación creamos dos variables: una para el gráfico y otra que es una matriz de la posición de los nodos que queremos añadir. Después sólo hay que añadir esos nodos y sus aristas:


Paso 11: ¿Cómo elegir el camino correcto?

Como te dije antes hay muchos métodos para obtener un camino entre dos nodos, como el DFS(Deep First Search), o el BFS(Broad First Search), pero a veces no sólo quieres obtener un camino que conecte los nodos, también quieres obtener el "mejor" camino, que la mayoría de las veces significará el que tarde menos tiempo o el más cercano, dependiendo de lo que quieras.

Durante este tutorial sólo me referiré a él como el que menos cuesta seguir. (En nuestro caso, recuerda que "coste" significa distancia. En un juego, es posible que quieras encontrar el camino menos peligroso, o el que menos combustible consume, o el menos visible...)

Existen algoritmos que funcionan en función del coste, siendo los más importantes el Algoritmo de Dijkstra y el Algoritmo A* (A-Star). Hablemos primero del algoritmo de Dijkstra


Paso 12: Introducción al algoritmo de Dijkstra

Este algoritmo fue creado por Edsger Dijkstra en 1959. Avanza en función del coste que representa cada arista, siempre se elegirán primero las aristas de menor coste, por lo que cuando se llegue al objetivo, se estará seguro de que el camino es el de menor coste disponible.


Paso 13: Cómo funciona el algoritmo de Dijkstra

Dado que este algoritmo trabaja con costes, debemos tener un lugar en el que almacenaremos el coste de ir a cada nodo desde el origen (el nodo inicial); llamémosle vector de costes.

Por ejemplo, si el origen es el nodo 0, cuando accedamos al vector de costes en la posición 3, éste nos devolverá el coste más bajo hasta el momento de pasar de 0 a 3. También necesitaremos una forma de almacenar el camino más corto: En el siguiente paso explicaré el árbol del camino más corto.

Los pasos básicos del algoritmo son los siguientes:

  1. Toma el nodo más cercano aún no analizado.
  2. Añade su mejor arista al árbol del camino más corto.
  3. Si es el nodo de destino, termina la búsqueda.
  4. Recupera todas las aristas de este nodo.
  5. Para cada arista calcula el coste de desplazamiento desde el nodo de origen hasta el nodo de llegada.
  6. Si el coste total de esta arista es menor que el coste del nodo de llegada hasta ahora, entonces actualiza el coste del nodo con el nuevo.
  7. Toma el siguiente nodo más cercano aún no analizado.
  8. Repite esta operación hasta que se alcance el objetivo o no haya más nodos disponibles.

Una animación tendrá más sentido. Aquí estamos tratando de llegar de 1 a 6:


Paso 14: Elementos principales del algoritmo

Este algoritmo se compone de diferentes vectores que almacenarán toda la información necesaria, por ejemplo los costes de los nodos, o el mejor camino hasta el momento. Lo explicaré mejor:

  • El vector de costes: Aquí almacenaremos el mejor coste hasta el momento de llegar a un determinado nodo desde el origen. Por ejemplo, si el nodo origen es el 3 y accedemos al elemento 6 del vector de costes, obtendremos el mejor coste encontrado hasta el momento de pasar del 3, el nodo origen, al nodo 6.
  • El árbol del camino más corto (SPT): Este vector contiene la arista de menor coste para llegar a un nodo concreto. Esto significa que si accedemos al elemento 7 del SPT, nos devolverá la mejor arista para acceder a ese nodo.
  • La frontera de búsqueda (SF): Este vector almacenará la mejor arista para llegar a un nodo específico, casi igual que el SPT, pero éste tendrá todos los nodos que aún no están en el SPT. Esto significa que el SF funcionará como un área de prueba donde probaremos todas las aristas para un nodo, cuando todas las aristas sean analizadas estaremos seguros de que el SF contiene la mejor, por lo que podremos entonces añadirla al SPT.
  • La cola prioritaria indexada (pq): Una cola de prioridad es una estructura de datos que siempre mantiene sus elementos de forma ordenada. Como el algoritmo necesita obtener primero el nodo de menor coste, esta estructura mantendrá los nodos en orden descendente según su coste, pero como queremos recuperar el índice del nodo y no el coste en sí, utilizamos una cola de prioridad indexada. Por ejemplo, si el primer elemento del pq es el nodo 4, significará que es el de menor coste.

Nota: AS3 no contiene muchas estructuras de datos, incluyendo la cola de prioridad indexada, por lo que codifiqué una para usarla en este tutorial. Para conseguirlo solo tienes que descargar los archivos fuente e importar la carpeta utils a la carpeta PathFinding. La clase es utils.IndexPriorityQ.


Paso 15: Crear una carpeta de algoritmos

Antes de empezar a codificar, en la carpeta PathFinding, crea una nueva carpeta y llámala "Algoritmos".

En esta nueva carpeta, crea una nueva clase AS3 llamada "Dijkstra":


Paso 16: El algoritmo de Dijkstra en AS3

Ahora vamos a codificar el Algoritmo. Necesitarás tres cosas básicas: el propio gráfico, el nodo origen y el nodo destino; pero también debemos crear los vectores de los que acabamos de hablar (Coste,SPT,SF). Recuerda importar las clases de gráficos:


Paso 17: La función de búsqueda

Una vez que hemos configurado la clase, podemos empezar a codificar el algoritmo que estará en la función "Búsqueda". Explicaré el código con comentarios, así que si todavía tienes algunas preguntas vuelve a los pasos 12 y 13 para recordar cómo funciona este algoritmo:


Paso 18: Obtención de la ruta

Cuando la función termine de buscar tendremos la ruta toda desordenada en el SPT, por lo que nos toca recuperarla. Como el SPT tiene la mejor arista para llegar a un nodo, podemos trabajar hacia atrás para obtener el mejor camino. Toma como referencia la siguiente imagen que proviene de la animación anterior:

Si accedemos al SPT en el nodo destino, que en este caso es el 6, nos devolverá la mejor arista para llegar allí. Esa sería la ventaja de 6 - 5. Ahora si repetimos este proceso con el nuevo nodo que viene con la arista, el 5 obtendríamos la mejor arista para llegar a ese nodo, que es la arista 5 - 2. Repitiendo este proceso una vez más con el nodo 2, nos dará la arista 2 - 1, por lo que finalmente llegamos al principio, ahora uniendo todas esas aristas obtenemos el mejor camino: 6 > 5 > 2 >1.

Como ves, tenemos que trabajar hacia atrás empezando por el objetivo y moviéndonos hacia el origen para conseguir el mejor camino.


Paso 19: La función getPath

Crea una nueva función que devolverá una matriz con los nodos de la ruta, llámala "getPath":


Paso 20: La clase Dijkstra completa

Ya hemos terminado casi todo, ahora sólo nos queda rellenar el constructor y llamar a la función de búsqueda, por lo que la clase tendrá este aspecto:


Paso 21: Crear un nuevo gráfico

Para ver un mejor resultado del algoritmo, escribí una clase que ayuda a la creación de gráficos. Se llama Grapher y se puede encontrar dentro de la carpeta de utilidades que viene con los archivos fuente. Esta clase crea una cuadrícula de nodos desde la que podemos observar cómo el algoritmo se mueve por el gráfico.

Con esta clase, abre de nuevo el archivo "Main.as" y modifícalo. Ahora tendremos el siguiente código:

Guarda y ejecuta el archivo y obtendrás este resultado:


Paso 22: Uso del algoritmo de Dijkstra

Ahora vamos a realizar una búsqueda con el nuevo algoritmo que acabamos de hacer. Importa la clase Dijkstra, crea una instancia de la misma y llama a la función getPath:

Guarda y ejecuta el archivo. Verás las aristas que el algoritmo analizó como líneas rojas, y el mejor camino encontrado (del nodo 24 al nodo 35) aparece como línea negra:


Paso 23: ¿No hay algo mejor?

Como podemos ver, el algoritmo de Dijkstra encuentra el camino más corto entre dos nodos, pero como muestra la última imagen, hay muchas líneas rojas. Esto significa que todas esas aristas fueron analizadas, lo cual no es un gran problema porque tenemos un gráfico pequeño, pero imagina un gráfico más grande; serían demasiadas aristas para analizar. Si pudiéramos encontrar una manera de reducir esto y hacer que el algoritmo sea aún más eficiente... pues les presento el algoritmo A* (A-Star).


Paso 24: El algoritmo A*

El algoritmo A* es una versión modificada de Dijkstra. Tiene en cuenta una forma modificada de obtener el coste de cada nodo con un enfoque heurístico. Esto significa que proporcionamos una pequeña "ayuda" al algoritmo y le decimos hacia dónde ir, funcionando como una brújula y moviendo el algoritmo directamente hacia el objetivo.

En lugar de calcular el coste de un nodo sumando el coste de la arista al coste del nodo almacenado, ahora se calcula sumando el coste del nodo almacenado y un coste heurístico, que es una estimación de lo cerca que está del objetivo el nodo que estamos analizando. Este nuevo coste se denomina coste F


Paso 25: El coste F

El coste F se calcula mediante la siguiente fórmula F = G + H, donde G es el coste del nodo y H es el coste heurístico de ese nodo para el objetivo. En este tutorial el coste H se calculará utilizando la distancia euclidiana entre el nodo y el objetivo, que es la distancia en línea recta entre los dos nodos.

Lo que hace esto es que al final, los nodos con un coste F más bajo serán los primeros en ser probados y como el coste F dependerá sobre todo del coste H, al final el algoritmo siempre priorizará los nodos más cercanos al objetivo.


Paso 26: El algoritmo A* en AS3

En la carpeta Algoritmos, crea una nueva clase llamada "Astar". Las variables dentro de la clase serán casi las mismas que las de la clase Dijkstra, pero aquí tendremos otro vector para almacenar el coste F de cada nodo:

Paso 27: La nueva clase de búsqueda

La única diferencia entre la función de búsqueda del algoritmo de Dijkstra y ésta será que los nodos se ordenarán (en la cola de prioridad indexada) en función del vector de costes F y que el vector de costes F vendrá dado por el coste H calculado y el coste G almacenado:


Paso 28: La clase A* completa

Estos son los únicos cambios necesarios, ya que la función getPath es la misma para ambas clases. Al final la clase será esta:


Paso 29: Uso del algoritmo A*

Una vez más abre el "Main.as" e importamos la clase Astar, luego borramos la búsqueda Dijkstra que creamos, sustituyéndola por una búsqueda A*:

Guarda y ejecuta el archivo. Como puedes ver, el resultado es muy impresionante, no hay líneas rojas, lo que significa que la búsqueda fue directamente del origen al destino sin analizar aristas adicionales:


Paso 30: ¿Cuál es mejor?

Pues bien, aunque el algoritmo A* es más rápido y mejor a la hora de obtener un camino directo desde el origen hasta el destino, habrá algunos casos en los que Dijkstra será la mejor opción.

Por ejemplo, imagina un juego de estrategia en tiempo real, en el que has dado instrucciones a tu aldeano para que vaya a buscar algunos recursos; con el algoritmo A* tendrías que hacer una búsqueda de cada recurso en el mapa y luego analizar cuál está más cerca. Con una búsqueda de Dijkstra, como se expande la misma cantidad hacia todas las direcciones, el primer recurso que encuentre será el mejor para recoger y habrás realizado una sola búsqueda frente a las muchas búsquedas de la A*.

Básicamente, querrás utilizar el algoritmo de Dijkstra cuando realices una búsqueda general y el algoritmo A* cuando buscas un elemento específico.


Conclusión:

Esto es todo por este tutorial, espero que les haya gustado y lo utilicen para sus proyectos. No pierdas de vista el próximo tutorial de esta serie de IA y hazme saber tu opinión al respecto.

¡Gracias por leer! -Eduardo

Advertisement
Did you find this post useful?
Want a weekly email summary?
Subscribe below and we’ll send you a weekly email summary of all new Code tutorials. Never miss out on learning about the next big thing.
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.