[IA] Búsquedas en grafos en C#
La teoría de grafos es un campo muy ámplio, que daría contenido para escribir no un post, sinó varios libros! Pero aquí os enseño algunos expermientos que he hecho para su aplicación en programación de videojuegos. En un juego estilo Command & Conquer se podría usar un grafo para saber si el jugador tiene permitido contruir la unidad "soldado". Como recordaréis, este juego permite construir unidades si antes cumples determinados requisitos, como haber construido el edificio "barracones", como muestra el siguiente diagrama:
Podríamos implementar esto a base de numerosas sentencias "If" anidadas, pero el código sería muy difícil de mantener y propenso a bugs: malo. Así pues, se podrían usar técnicas de búsqueda de grafos para ver qué unidades o edificios podemos construir. Otra opción es para la planificación de rutas (con su culminación en el algoritmo A* Pathfinding), es decir, determinar si un objeto puede moverse de una zona a otra del juego.
Existen varios algoritmos de búsqueda dentro de un grafo... aquí os muestro una implementación muy sencilla. Pero antes veamos de forma muy resumida los componentes de un grafo. En este algoritmo, el grafo consta de Nodos y de Lados. Los Nodos son las circunferéncias de la imágen, y son los puntos por los cuales nos queremos mover. Los lados son conexiones entre dos puntos. Así pues entre el Nodo 1 y el Nodo 6 existiría un Lado que va a contener la información de los nodos que une (1-6).
Estos objetos pueden ser definidos conecptualmente mediante clases del siguiente modo:
Estas clases sólo definen el grafo y sus nodos, de la búsqueda podrían encargarse clases específicas, con sus algoritmos determinados. En este caso he utilado la siguiente, basada en el algoritmo "Deep First Search". Este algoitmo va a encontrar la ruta que busquemos, pero sin tener en cuenta si es o no la más eficiente. El concepto eficiente podría variar dependiendo de los requerimientos, podría ser el número de nodos intermedios, o el número de nodos intermedios teniendo en cuenta el "peso" de cada lado (un lado puede cruzar una montaña, y el movimiento en esa zona sería más lento y costoso). En este caso la implementación es la siguiente:
La implementación del algoritmo es la siguiente:
public void BuscarRuta()
{
// Limpiamos
nodosVisitados.Clear();
ruta.Clear();
// stack de referencias a los lados (cola LIFO)
Stack<GrafoLado> cola = new Stack<GrafoLado>();
// Se crea un lado tonto y se pone en el stack
GrafoLado ladoDummy = new GrafoLado(this.origen, this.origen, 0f);
cola.Push(ladoDummy);
// Mientras haya lados en el stack, seguimos buscando
while
(cola.Count > 0)
{
GrafoLado ladoSiguiente = cola.Pop();
// Guardamos en la ruta
ruta.Add(ladoSiguiente.To);
// Guardamos registro de nodos visitados
nodosVisitados.Add(ladoSiguiente.From);
// Si el siguiente lado es el de destino,
// hemos encontrado la ruta
if(ladoSiguiente.To == destino)
{
this.rutaEncontrada = true;
return;
}
foreach (GrafoLado lado in grafo.Lados)
{
// Si el nodo no existe en la lista de visiados, y adems es accesible desde el nodo actual,
// lo aadimos al stack
uint visitado = nodosVisitados.Find(b => b == lado.To );
if(visitado == 0 && lado.From == ruta[ruta.Count-1])
{
cola.Push(lado);
break;
}
}
}
// No se ha encontrado ruta...
this.rutaEncontrada = false;
El código como siempre lo encontraréis adjunto en el interior del artículo.