Los grafos organizan espacios navegables, estados, diálogos, misiones y decisiones. Permiten que personajes encuentren rutas, que una historia respete dependencias y que un nivel generado mantenga su conectividad.
Un videojuego contiene muchos sistemas conectados. Habitaciones unidas por puertas, estados de un enemigo, opciones de diálogo y objetivos de una misión pueden representarse como grafos.
Elegir los vértices y aristas correctos transforma comportamientos complejos en problemas conocidos de recorridos, caminos y dependencias.
Una región navegable puede convertirse en un vértice y cada movimiento permitido en una arista.
El modelo debe conservar las restricciones relevantes sin representar más detalle del necesario.
En un mapa de celdas, cada celda transitable se conecta con sus vecinas. Con movimiento ortogonal hay hasta cuatro vecinos; al permitir diagonales aparecen hasta ocho.
Las diagonales suelen tener costo √2 y deben impedir atravesar esquinas bloqueadas cuando eso no sea válido en el juego.
Los waypoints son puntos importantes colocados manual o automáticamente. Una arista indica que el personaje puede desplazarse directamente entre ellos.
Reducen la cantidad de nodos frente a una cuadrícula, pero necesitan conexiones suficientes para no perder rutas válidas.
Una navmesh divide el espacio transitable en polígonos. Los polígonos adyacentes forman un grafo y sus portales compartidos permiten reconstruir un camino geométrico.
Después de buscar una secuencia de polígonos, técnicas como el algoritmo del embudo suavizan el recorrido.
Avanza la búsqueda o ejecútala automáticamente. Haz clic en una celda para agregar o quitar un obstáculo y recalcular la ruta.
Leyenda
Acción actual
A* prioriza el nodo con menor costo estimado total.
g(n) es el costo desde el inicio y h(n) estima el costo restante. Con una heurística admisible, A* encuentra una ruta óptima.
Para movimiento ortogonal de costo unitario se utiliza distancia Manhattan: |x₁−x₂| + |y₁−y₂|. Para movimiento libre puede usarse distancia euclidiana.
Sobreestimar puede acelerar algunas búsquedas, pero pierde la garantía de optimalidad.
while (!abiertos.estaVacia()) {
const actual = abiertos.extraerMinimo();
if (actual === meta) return reconstruir(padre, meta);
for (const vecino of vecinos(actual)) {
const candidato = g[actual] + costo(actual, vecino);
if (candidato < (g[vecino] ?? Infinity)) {
padre[vecino] = actual;
g[vecino] = candidato;
abiertos.insertar(vecino, candidato + heuristica(vecino, meta));
}
}
}Puertas, vehículos y otros personajes pueden invalidar una ruta. Recalcular A* desde cero es sencillo, pero puede ser costoso si el mapa cambia constantemente.
Algoritmos incrementales como D* Lite reutilizan información de búsquedas anteriores. Otra opción es planificar globalmente y evitar obstáculos localmente.
Los mapas grandes pueden dividirse en regiones. Primero se busca una ruta entre regiones y después se refina cada tramo.
La abstracción reduce trabajo a cambio de preparación y posibles rutas ligeramente subóptimas.
Una máquina de estados finitos es un grafo dirigido: patrullar, perseguir, atacar y huir son vértices; las condiciones de transición son aristas.
Conviene separar la condición de transición de las acciones ejecutadas dentro de cada estado.
Los árboles de comportamiento organizan selectores, secuencias y acciones. Aunque suelen dibujarse como árboles, referencias compartidas o subcomportamientos reutilizados pueden formar un grafo.
Son adecuados para decisiones jerárquicas y modulares; las máquinas de estados resultan claras para modos persistentes.
Cada intervención o situación puede ser un nodo y cada respuesta una arista. Condiciones, consecuencias y requisitos se almacenan en transiciones.
El sistema debe manejar ciclos intencionales, opciones inaccesibles y estados que modifican conversaciones futuras.
Una misión compleja puede modelarse como un DAG. Una tarea se habilita cuando se completan sus predecesoras.
El orden topológico ayuda a validar que no existan dependencias circulares imposibles y a determinar qué objetivos están disponibles.
Habitaciones y pasillos forman un grafo de nivel. Un árbol generador garantiza conectividad mínima; agregar aristas crea ciclos y rutas alternativas.
Después de generar, deben validarse accesibilidad, distancia entre puntos importantes y orden de llaves, puertas o habilidades.
Un mapa de influencia propaga valores desde fuentes como enemigos, recursos o zonas seguras. Puede calcularse mediante BFS, Dijkstra o difusión iterativa.
La IA combina varias capas para elegir posiciones con baja amenaza, buena cobertura o cercanía a objetivos.
Varias unidades pueden bloquearse mutuamente aunque cada ruta individual sea válida. Se necesitan reservas temporales, prioridades o algoritmos de planificación multiagente.
Separar navegación global de movimiento local ayuda a evitar colisiones sin recalcular toda la ruta en cada cuadro.
Los grafos proporcionan una base común para espacio, comportamiento y progresión. El mismo conjunto de conceptos —adyacencia, costo, recorrido y dependencia— resuelve problemas muy diferentes dentro de un juego.
En el próximo tema estudiaremos grafos en inteligencia artificial y cómo representan estados, conocimiento y búsqueda de soluciones.