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:
package Graph
{
import flash.display.Sprite;
import flash.geom.Vector3D;
public class Node extends Sprite
{
private var pos:Vector3D;
private var index:int;
public function Node(idx:int,n_Pos:Vector3D)
{
index=idx;
pos=n_Pos;
this.x=n_Pos.x;
this.y=n_Pos.y;
idx_txt.text=String(idx)
}
public function getIndex():int
{
return index;
}
public function setPos(n_Pos:Vector3D):void
{
pos=n_Pos;
}
public function getPos():Vector3D
{
return pos;
}
}
}
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:
package Graph
{
import flash.display.Sprite;
import flash.geom.Vector3D;
public class Edge extends Sprite
{
private var from:int; //The index of the node from which this edge departs
private var to:int; //The index of the node from which this edge arrives
private var cost:Number; //The cost of crossing through this node (i.e. the distance)
public function Edge(n_From:int,n_To:int,n_Cost:Number=1.0)
{
from=n_From;
to=n_To;
cost=n_Cost;
this.z=1;
}
public function getFrom():int
{
return from;
}
public function setFrom(n_From:int):void
{
from=n_From;
}
public function getTo():int
{
return to;
}
public function setTo(n_To:int):void
{
to=n_To;
}
public function setCost(n_Cost:Number):void
{
cost=n_Cost;
}
public function getCost():Number
{
return cost;
}
/*
Since the edge is just a line that connects the nodes,
we will use this method to draw the edge, the style refers to how we will
want the edge to be
*/
public function drawEdge(fromPos:Vector3D,toPos:Vector3D,style:String="normal")
{
switch(style)
{
case "normal":
//If it is normal, create a gray line
this.graphics.clear();
this.graphics.lineStyle(1, 0x999999, .3);
this.graphics.moveTo(fromPos.x,fromPos.y);
this.graphics.lineTo(toPos.x,toPos.y);
break;
case "path":
//If it is a line from the path, create a black line
this.graphics.clear();
this.graphics.lineStyle(2, 0x000000,1);
this.graphics.moveTo(fromPos.x,fromPos.y);
this.graphics.lineTo(toPos.x,toPos.y);
break;
case "visited":
//If it is a line used by the algorithm, create a red line
this.graphics.clear();
this.graphics.lineStyle(1, 0xFF0000,1);
this.graphics.moveTo(fromPos.x,fromPos.y);
this.graphics.lineTo(toPos.x,toPos.y);
break;
}
}
}
}
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:
package Graph
{
public class Graph
{
private static var nextIndex:int=0;
private var nodes:Vector.<Node>;
private var edges:Vector.<Array>;
public function Graph()
{
nodes=new Vector.<Node>();
edges=new Vector.<Array>();
}
}
}
El gráfico también necesita métodos para añadir y obtener nodos y aristas:
package Graph
{
public class Graph
{
private static var nextIndex:int=0;
private var nodes:Vector.<Node>;
private var edges:Vector.<Array>;
public function Graph()
{
nodes=new Vector.<Node>();
edges=new Vector.<Array>();
}
//In order to get the node, we just ask for the index of it, and access the nodes vector with that key
public function getNode(idx:int):Node
{
return nodes[idx];
}
//To get an edge, we ask for the two nodes that it connects,
//then we retrieve all the edges of the from node and search if one of them
//goes to the same node as the edge we are looking for, if it does, that's our edge.
public function getEdge(from:int,to:int):Edge
{
var from_Edges:Array = edges[from] as Array;
for(var a:int=0;a<from_Edges.length;a++)
{
if(from_Edges[a].getTo()==to)
{
return from_Edges[a];
}
}
return null;
}
//To add a node to the graph, we first look if it already exist on it,
//if it doesn't, then we add it to the nodes vector, and add an array to the
//edges vector where we will store the edges of that node, finally we increase
//the next valid index int in order to give the next available index in the graph
public function addNode(node:Node):int
{
if(validIndex(node.getIndex()))
{
nodes.push(node);
edges.push(new Array());
nextIndex++;
}
return 0;
}
//To add an edge we must first look if both nodes it connects actually exist,
//then we must see if this edge already exist on the graph, finally we add it
//to the array of edges of the node from where it comes
public function addEdge(edge:Edge):void
{
if(validIndex(edge.getTo())&&validIndex(edge.getFrom()))
{
if(getEdge(edge.getFrom(),edge.getTo())==null)
{
(edges[edge.getFrom()]as Array).push(edge);
}
}
}
//To get the edges of a node, just return the array given by the edges vector
//at node's index position
public function getEdges(node:int):Array
{
return edges[node];
}
//This function checks if the node index is between the range of already added nodes
//which is form 0 to the next valid index of the graph
public function validIndex(idx:int):Boolean
{
return (idx>=0&&idx<=nextIndex)
}
//Just returns the amount of nodes already added to the graph
public function numNodes():int
{
return nodes.length;
}
//This is to redraw all the edges on the graph to get them to the normal style
public function redraw():void
{
for each(var a_edges:Array in edges)
{
for each(var edge:Edge in a_edges)
{
edge.drawEdge(getNode(edge.getFrom()).getPos(),getNode(edge.getTo()).getPos());
}
}
}
//This function return the next valid node index to be added
public static function getNextIndex():int
{
return nextIndex;
}
}
}
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:
package{
import flash.display.Sprite;
public class Main extends Sprite
{
public function Main()
{
}
}
}
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:
package{
import flash.display.Sprite;
import Graph.*;
import flash.geom.Vector3D;
public class Main extends Sprite
{
var graph:Graph = new Graph();
//This array contains the position of the different nodes in the graph (x,y)
var nodes:Array =new Array(
[110,20],
[80,50],
[300,200],
[180,250],
[380,380],
[500,200]
);
//This array contains the edges that connects the different nodes (from,to)
var edges:Array = new Array(
[0,1],[0,5],[0,3],
[1,2],[1,0],[1,4],
[2,1],[2,5],
[3,1],[3,5],
[4,0],[4,5],
[5,2],[5,3]
);
public function Main()
{
//A loop in order to create all the nodes
for(var a:int=0;a<nodes.length;a++)
{
var node:Node = new Node(Graph.Graph.getNextIndex(), new Vector3D(nodes[a][0],nodes[a][1]));
graph.addNode(node);
addChild(node);
}
//Another loop to create all the edges between nodes
for(var b:int=0;b<edges.length;b++)
{
var from:int = edges[b][0];
var to:int = edges[b][1];
var edge:Edge = new Edge(from,to,Vector3D.distance(graph.getNode(from).getPos(),graph.getNode(to).getPos()));
graph.addEdge(edge);
//Since the drawEdge method requires the position vectors, we get the nodes
//from the graph with their index and then get their position with getPos()
edge.drawEdge(graph.getNode(from).getPos(),graph.getNode(to).getPos());
addChild(edge);
}
}
}
}
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:
- Toma el nodo más cercano aún no analizado.
- Añade su mejor arista al árbol del camino más corto.
- Si es el nodo de destino, termina la búsqueda.
- Recupera todas las aristas de este nodo.
- Para cada arista calcula el coste de desplazamiento desde el nodo de origen hasta el nodo de llegada.
- 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.
- Toma el siguiente nodo más cercano aún no analizado.
- 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":
package Algorithms {
public class Dijkstra {
public function 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:
package Algorithms {
import Graph.Edge;
import Graph.Graph;
import utils.IndexedPriorityQ;
public class Dijkstra {
private var graph:Graph //The graph where the search will be made
private var SPT:Vector.<Edge>; //The Shortest path tree containing edges
private var cost2Node:Vector.<Number>; //The Cost vector containing numbers
private var SF:Vector.<Edge>; //The Search Frontier containing edges
private var source:int; //Where will the search start
private var target:int; //Where will the search end
public function Dijkstra(g:Graph) {
}
}
}
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:
private function search():void
{
//This will be the indexed priority Queue that will sort the nodes
var pq:IndexedPriorityQ = new IndexedPriorityQ(cost2Node)
//To start the algorithm we first add the source to the pq
pq.insert(source);
//With this we make sure that we will continue the search until there are no more nodes on the pq
while(!pq.isEmpty())
{
/* 1.- Take the closest node not yet analyzed */
//We get the Next Closest Node (NCN) which is the first element of the pq
var NCN:int = pq.pop();
/* 2.-Add its best edge to the Shortest Path Tree (Its best edge is stored on the SF) */
SPT[NCN]=SF[NCN];
//This will color the actual edge red in order to see which edges the algorithm has analyzed
if(SPT[NCN])
{
SPT[NCN].drawEdge(
graph.getNode(SPT[NCN].getFrom()).getPos(),
graph.getNode(SPT[NCN].getTo()).getPos(),
"visited"
);
}
/* 3.- If it is the target node, finish the search */
if(NCN==target)return;
/* 4.- Retrieve all the edges of this node */
var edges:Array=graph.getEdges(NCN);
//With this loop we will analyze each of the edges of the array
for each(var edge:Edge in edges)
{
/* 5.- For each edge calculate the cost of moving from the source node to the arrival Node */
//The total cost is calculated by: Cost of the node + Cost of the edge
var nCost:Number = cost2Node[NCN]+edge.getCost();
//If the arrival node has no edge on the SF, then add its cost to the
//Cost vector, the arrival node to the pq, and add the edge to the SF
if(SF[edge.getTo()]==null)
{
cost2Node[edge.getTo()]=nCost;
pq.insert(edge.getTo());
SF[edge.getTo()]=edge;
}
/* 6.- If the cost of this edge is less than the cost of the arrival node until now, then update the node cost with the new one */
else if((nCost<cost2Node[edge.getTo()])&&(SPT[edge.getTo()]==null))
{
cost2Node[edge.getTo()]= nCost;
//Since the cost of the node has changed, we need to reorder again the pq to reflect the changes
pq.reorderUp();
//Because this edge is better, we update the SF with this edge
SF[edge.getTo()]=edge;
}
}
}
}
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":
public function getPath():Array
{
var path:Array = new Array();
if(target<0) return path;
var nd:int = target;
path.push(nd);
while((nd!=source)&&(SPT[nd]!=null))
{
SPT[nd].drawEdge(
graph.getNode(SPT[nd].getFrom()).getPos(),
graph.getNode(SPT[nd].getTo()).getPos(),
"path"
);
nd = SPT[nd].getFrom();
path.push(nd);
}
path=path.reverse();
return path;
}
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:
package Algorithms{
import Graph.Edge;
import Graph.Graph;
import utils.IndexedPriorityQ;
public class Dijkstra {
private var graph:Graph
private var SPT:Vector.<Edge>
private var cost2Node:Vector.<Number>
private var SF:Vector.<Edge>
private var source:int;
private var target:int;
public function Dijkstra(n_graph:Graph,src:int,tar=int) {
graph=n_graph;
source=src;
target=tar;
SPT= new Vector.<Edge>(graph.numNodes());
cost2Node = new Vector.<Number>(graph.numNodes());
SF = new Vector.<Edge>(graph.numNodes());
search();
}
private function search():void
{
var pq:IndexedPriorityQ = new IndexedPriorityQ(cost2Node)
pq.insert(source);
while(!pq.isEmpty())
{
var NCN:int = pq.pop();
SPT[NCN]=SF[NCN];
if(SPT[NCN])
{
SPT[NCN].drawEdge(
graph.getNode(SPT[NCN].getFrom()).getPos(),
graph.getNode(SPT[NCN].getTo()).getPos(),
"visited"
);
}
if(NCN==target)return;
var edges:Array=graph.getEdges(NCN);
for each(var edge:Edge in edges)
{
var nCost:Number = cost2Node[NCN]+edge.getCost();
if(SF[edge.getTo()]==null)
{
cost2Node[edge.getTo()]=nCost;
pq.insert(edge.getTo());
SF[edge.getTo()]=edge;
}
else if((nCost<cost2Node[edge.getTo()])&&(SPT[edge.getTo()]==null))
{
cost2Node[edge.getTo()]= nCost;
pq.reorderUp();
SF[edge.getTo()]=edge;
}
}
}
}
public function getPath():Array
{
var path:Array = new Array();
if((target<0)||(SPT[target]==null)) return path;
var nd:int=target;
path.push(nd);
while((nd!=source)&&(SPT[nd]!=null))
{
SPT[nd].drawEdge(
graph.getNode(SPT[nd].getFrom()).getPos(),
graph.getNode(SPT[nd].getTo()).getPos(),
"path"
);
nd = SPT[nd].getFrom()
path.push(nd);
}
path = path.reverse();
return path;
}
}
}
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:
package{
import flash.display.Sprite;
import Graph.*;
import utils.Grapher;
public class Main extends Sprite
{
var graph:Graph = new Graph();
public function Main()
{
//The parameters of the Grapher class are the width and height of the stage
//the number of columns and rows, and then the graph for storing the data
//After this we just add the grapher to the stage and we are done.
//This will create a grid of nodes of 7*7
var grapher:Grapher = new Grapher(550,400,7,7,graph);
addChild(grapher);
}
}
}
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:
package{
import flash.display.Sprite;
import Graph.*;
import utils.Grapher;
import Algorithms.Dijkstra;
public class Main extends Sprite
{
var graph:Graph = new Graph();
public function Main()
{
var grapher:Grapher = new Grapher(550,400,7,7,graph);
addChild(grapher);
//We create a new Dijkstra search that will look a path from node 24 to node 35
var dijkstra:Dijkstra = new Dijkstra(graph,24,35);
dijkstra.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:
package Algorithms{
import Graph.Edge;
import Graph.Graph;
import flash.geom.Vector3D;
import utils.IndexedPriorityQ;
public class Astar {
private var graph:Graph
private var SPT:Vector.<Edge>
private var G_Cost:Vector.<Number> //This vector will store the G cost of each node
private var F_Cost:Vector.<Number> //This vector will store the F cost of each node
private var SF:Vector.<Edge>
private var source:int;
private var target:int;
public function Astar(n_graph:Graph,src:int,tar:int)
{
graph=n_graph;
source=src;
target=tar;
SPT= new Vector.<Edge>(graph.numNodes());
G_Cost = new Vector.<Number>(graph.numNodes());
F_Cost = new Vector.<Number>(graph.numNodes());
SF = new Vector.<Edge>(graph.numNodes());
search();
}
}
}
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:
private function search():void
{
//The pq is now sorted depending on the F cost vector
var pq:IndexedPriorityQ = new IndexedPriorityQ(F_Cost)
pq.insert(source);
while(!pq.isEmpty())
{
var NCN:int = pq.pop();
SPT[NCN]=SF[NCN];
if(SPT[NCN])
{
SPT[NCN].drawEdge(
graph.getNode(SPT[NCN].getFrom()).getPos(),
graph.getNode(SPT[NCN].getTo()).getPos(),
"visited"
);
}
if(NCN==target)return;
var edges:Array=graph.getEdges(NCN);
for each(var edge:Edge in edges)
{
//The H cost is obtained by the distance between the target node, and the arrival node of the edge being analyzed
var Hcost:Number = Vector3D.distance(
graph.getNode(edge.getTo()).getPos(),
graph.getNode(target).getPos())
var Gcost:Number = G_Cost[NCN] + edge.getCost();
var to:int=edge.getTo();
if(SF[edge.getTo()]==null)
{
F_Cost[edge.getTo()]=Gcost+Hcost;
G_Cost[edge.getTo()]=Gcost;
pq.insert(edge.getTo());
SF[edge.getTo()]=edge;
}
else if((Gcost<G_Cost[edge.getTo()])&&(SPT[edge.getTo()]==null))
{
F_Cost[edge.getTo()]=Gcost+Hcost;
G_Cost[edge.getTo()]=Gcost;
pq.reorderUp();
SF[edge.getTo()]=edge;
}
}
}
}
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:
package Algorithms {
import Graph.Edge;
import Graph.Graph;
import flash.geom.Vector3D;
import utils.IndexedPriorityQ;
public class Astar {
private var graph:Graph
private var SPT:Vector.<Edge>
private var G_Cost:Vector.<Number> //This vector will store the G cost of each node
private var F_Cost:Vector.<Number> //This vector will store the F cost of each node
private var SF:Vector.<Edge>
private var source:int;
private var target:int;
public function Astar(n_graph:Graph,src:int,tar:int)
{
graph=n_graph;
source=src;
target=tar;
SPT= new Vector.<Edge>(graph.numNodes());
G_Cost = new Vector.<Number>(graph.numNodes());
F_Cost = new Vector.<Number>(graph.numNodes());
SF = new Vector.<Edge>(graph.numNodes());
search();
}
private function search():void
{
//The pq is now sorted depending on the F cost vector
var pq:IndexedPriorityQ = new IndexedPriorityQ(F_Cost)
pq.insert(source);
while(!pq.isEmpty())
{
var NCN:int = pq.pop();
SPT[NCN]=SF[NCN];
if(SPT[NCN])
{
SPT[NCN].drawEdge(
graph.getNode(SPT[NCN].getFrom()).getPos(),
graph.getNode(SPT[NCN].getTo()).getPos(),
"visited"
);
}
if(NCN==target)return;
var edges:Array=graph.getEdges(NCN);
for each(var edge:Edge in edges)
{
//The H cost is obtained by the distance between the target node, and the arrival node of the edge being analyzed
var Hcost:Number = Vector3D.distance(
graph.getNode(edge.getTo()).getPos(),
graph.getNode(target).getPos())
var Gcost:Number = G_Cost[NCN] + edge.getCost();
var to:int=edge.getTo();
if(SF[edge.getTo()]==null)
{
F_Cost[edge.getTo()]=Gcost+Hcost;
G_Cost[edge.getTo()]=Gcost;
pq.insert(edge.getTo());
SF[edge.getTo()]=edge;
}
else if((Gcost<G_Cost[edge.getTo()])&&(SPT[edge.getTo()]==null))
{
F_Cost[edge.getTo()]=Gcost+Hcost;
G_Cost[edge.getTo()]=Gcost;
pq.reorderUp();
SF[edge.getTo()]=edge;
}
}
}
}
public function getPath():Array
{
var path:Array = new Array();
if(target<0) return path;
var nd:int = target;
path.push(nd);
while((nd!=source)&&(SPT[nd]!=null))
{
SPT[nd].drawEdge(
graph.getNode(SPT[nd].getFrom()).getPos(),
graph.getNode(SPT[nd].getTo()).getPos(),
"path"
);
nd = SPT[nd].getFrom();
path.push(nd);
}
path=path.reverse();
return path;
}
}
}
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*:
package{
import flash.display.Sprite;
import Graph.*;
import utils.Grapher;
import Algorithms.Dijkstra;
import Algorithms.Astar;
public class Main extends Sprite
{
var graph:Graph = new Graph();
public function Main()
{
var grapher:Grapher = new Grapher(550,400,7,7,graph);
addChild(grapher);
//We create a new Astar search that will look a path from node 24 to node 35
var astar:Astar = new Astar(graph,24,35);
astar.getPath();
}
}
}
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
