[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.

7 comentarios en “[IA] Búsquedas en grafos en C#”

  1. Muy interesante Jesús y también los links que ha dejado Vicente, la verdad que cuando te pones a profundizar en algún tema en concreto salen cosas muy interesantes 🙂

  2. Hombre….pero porque cuando trato de ejecutar el proyecto…me dice q el gamehelper.csproj….no está en el proyecto…son dos errores…el primero es volver a introducir el dll en el proyecto…bien está en el bin….pero el gamehelper.csproj…no está en ninguna parte…me podrias…ayudar..para poderle yo tambien trabajar a ese proyecto…en la teoria de grafos…gracias y excelente trabajo

    nota: hasta ahora solo se ejecuta una pantalla azul…el mouse desaparece cuando entra en el form1

    jdnichollsc@hot…

  3. entonces….si yo tengo por ejemplo un proyecto…con los nodos como botones q creo en tiempo de ejecucion..y de este poseo un evento…q es el click del boton…yo aqui la primera vez q se ejecuta el evento llevo las coordenadas(primer boton)…y la segunda pido las otras coordenadas(segundo boton) y hago una flecha de vertice padre a vertice hijo….yo puedo controlar el lado segun si el vertice hijo está a la derecha o a la izquierda….como puedo implementar esas clases??

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *