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.
La teoría de grafos es un campo muy ámplio, que daría contenido para escribir no
Si te gustan los grafos, merece la pena mirarse la implementación de la BGL (Boost Graph Library).
http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/index.html
Tienes dos implementaciones en .NET, la de QuickGraph:
http://www.codeplex.com/quickgraph
Y la que hicimos en JadEngine:
http://www.codeplex.com/JADENGINE
Un saludo!
Vicente
Los links son una pasada, muchas gracias Vicente!
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 🙂
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…
hola Juan David, no se pinta nada porqué no hay nada en el draw… es un ejemplo de lógica, y no pinta el resultado.
salu2
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??