Pathfinding en videojuegos: A* (A estrella), Dijkstra y NavMesh con ejemplos paso a paso

Has construido tu primer prototipo. Tus enemigos se mueven, persiguen al jugador y hasta patrullan. Pero hay un problema: atraviesan paredes, se quedan atascados en las esquinas y toman rutas absurdas que gritan "esto no está bien". Has buscado tutoriales, has copiado código, incluso has pedido ayuda a una IA generativa. El problema sigue ahí. No es que tu juego sea malo: es que tus NPCs no saben navegar por el mundo que has creado.

Bienvenido al pathfinding. La diferencia entre un enemigo que parece tonto y uno que da miedo. Entre un NPC que rompe la inmersión y uno que refuerza la experiencia. Entre un prototipo vergonzoso y un sistema del que puedes sentirte orgulloso.

Este artículo no es una clase de informática teórica ni una historia de algoritmos. Es una guía práctica para que entiendas qué hace que tus personajes se muevan inteligentemente por un escenario, cuándo usar A*, Dijkstra o NavMesh, y cómo aplicarlo sin ahogarte en matemáticas incomprensibles.

Si alguna vez has pensado "quiero que mi IA deje de dar vergüenza", sigue leyendo.

Qué es pathfinding (y qué NO es)

Pathfinding es el proceso de calcular una ruta desde un punto A hasta un punto B dentro de un espacio navegable. Nada más, nada menos. No es "inteligencia artificial" en el sentido amplio. No hace que tu enemigo decida si atacar o huir. No evita colisiones en tiempo real. No anima a tu personaje ni le da personalidad.

Es una pieza específica del sistema de navegación: encontrar el camino.

Piénsalo así. Tienes tres capas separadas en el movimiento de un NPC:

Decisión (¿qué objetivo persigo?): aquí entran behavior trees, máquinas de estado finitas o sistemas de utilidad. Tu enemigo decide "voy a perseguir al jugador" o "vuelvo a mi patrulla".

Pathfinding (¿cómo llego hasta ese objetivo?): esta es la capa que estamos tratando. Calcula la ruta óptima o viable entre dos puntos considerando obstáculos, pesos de terreno y geometría del mundo.

Movimiento y evasión (¿cómo me muevo físicamente sin chocar?): steering behaviors, avoidance, locomotion. Tu personaje sigue la ruta pero esquiva a otros agentes, suaviza giros y traduce el path en movimiento fluido.

Si mezclas estas capas, te volverás loco depurando. Un NPC que se queda atascado puede tener un path perfecto pero un problema de colisiones. Un enemigo que toma rutas raras puede tener bien el algoritmo pero mal definido el espacio navegable.

Pathfinding resuelve una pregunta concreta: dado un mapa y dos puntos, ¿cuál es la mejor ruta?

El mapa y el método: representación vs algoritmo

Aquí está la confusión más común que paraliza a quienes empiezan: mezclar la representación del mundo con el algoritmo de búsqueda.

La representación es cómo traduces tu escenario (con paredes, puertas, escaleras, terrenos caros de atravesar) en algo que un algoritmo pueda procesar: un grafo. Puede ser un grid de tiles, una malla de polígonos navegables (NavMesh), un grafo de puntos estratégicos o cualquier estructura donde existan nodos conectados por aristas.

El algoritmo es el método que usas para buscar la ruta óptima dentro de esa representación: Dijkstra, A*, Greedy Best-First, o cualquier variante.

Aquí la clave: NavMesh no es un algoritmo alternativo a A*. NavMesh es una representación del mundo. Luego, sobre esa representación, aplicas un algoritmo como A* para calcular rutas. Entender esta separación es fundamental.

Un grid 2D también es una representación. Un grafo de waypoints conectados manualmente también lo es. Cada una tiene ventajas y limitaciones:

• Grid (cuadrícula): perfecto para juegos tile-based, roguelikes, estrategia por turnos. Fácil de implementar, pero puede ser costoso en memoria si el mundo es enorme, y produce rutas en ángulos de 90 grados (o diagonales si permites ese movimiento).
• NavMesh (Navigation Mesh): ideal para entornos 3D con geometría compleja. Pre-calcula áreas navegables y las representa como polígonos convexos. Eficiente en runtime porque reduces drásticamente el número de nodos. El problema: requiere un proceso de "baking" (horneado) y puede ser difícil de ajustar dinámicamente.
• Grafos de waypoints: nodos colocados manualmente conectados entre sí. Útil en juegos con movimiento libre pero zonas tácticas definidas (coberturas, puertas, puntos de emboscada). Control total, pero laborioso de mantener.

Ahora que hemos separado el mapa del método, vamos a lo que viniste a buscar: los algoritmos.

Dijkstra paso a paso: la búsqueda sin brújula

Dijkstra es el algoritmo fundacional. Es óptimo, exhaustivo y no necesita saber nada sobre tu objetivo. Simplemente expande en todas direcciones buscando el camino de menor coste acumulado.

Imagina este grid de 5×5. Queremos ir desde el nodo S (Start) hasta el nodo G (Goal). Los números son el coste de atravesar cada casilla. Las X son obstáculos infranqueables.

[ 1][ 1][ 1][ 1][ 1]
[ 1][ X][ X][ 2][ 1]
[ S][ 1][ 2][ 2][ 1]
[ 1][ X][ 2][ 1][ G]
[ 1][ 1][ 1][ 1][ 1]

Dijkstra funciona con dos listas:

• Open list (nodos por explorar): comienza con el nodo inicial.
• Closed list (nodos ya procesados): comienza vacía.

Para cada nodo guardamos el coste acumulado desde el inicio (g) y el nodo previo en el camino (para reconstruir la ruta al final).

Iteración 1: exploramos S (coste 0). Sus vecinos son el nodo de arriba (coste 1) y el de abajo (coste 1). Ambos pasan a Open con g=1. S pasa a Closed.

Iteración 2: tomamos el nodo con menor g de Open (empate, elegimos uno). Digamos que es el de arriba de S. Sus vecinos no visitados son añadidos/actualizados en Open. Ese nodo pasa a Closed.

Iteración 3, 4, 5...: repetimos. Siempre tomamos el nodo con menor coste acumulado en Open, exploramos sus vecinos, actualizamos costes si encontramos un camino más barato.

El algoritmo termina cuando G pasa de Open a Closed. Entonces reconstruyes el camino siguiendo los punteros de "nodo previo" desde G hasta S.

El resultado: el camino óptimo (el de menor coste total). El problema: Dijkstra ha explorado en todas direcciones, incluso las que se alejan del objetivo. Es como buscar las llaves del coche revisando toda la casa habitación por habitación sin saber si están en la cocina o en el baño.

Funciona. Es óptimo. Pero no es eficiente si sabes aproximadamente hacia dónde quieres ir.

A* paso a paso: Dijkstra con brújula

A* es Dijkstra mejorado. La diferencia: añade una heurística, una estimación de cuánto falta para llegar al objetivo desde cada nodo. Esa estimación "guía" la búsqueda hacia la meta en lugar de expandir a ciegas.

Usamos el mismo grid del ejemplo anterior. Ahora, además del coste acumulado g(n) desde el inicio, calculamos una heurística h(n) hacia el objetivo. La suma de ambos es f(n) = g(n) + h(n).

La heurística más común en grids: la distancia Manhattan (suma de diferencias en X e Y) si solo permites movimiento ortogonal, o distancia Euclidiana si permites diagonales.

Tomemos Manhattan. Desde un nodo en posición (x, y) hasta G en (4, 4):

h(n) = |x - 4| + |y - 4|

Ahora repetimos el proceso de Dijkstra, pero esta vez ordenamos Open por f(n) en lugar de solo por g(n).

Iteración 1: S está en (0, 2). h(S) = |0-4| + |2-4| = 6. f(S) = 0 + 6 = 6. Exploramos S, añadimos sus vecinos con f calculado.

Iteración 2: tomamos el nodo de Open con menor f. Esa pequeña diferencia cambia todo: en lugar de explorar uniformemente en círculos, A* prefiere nodos que estén más cerca del objetivo. Los nodos que se alejan tienen f más alta, así que quedan al fondo de la cola.

El resultado: llegas al objetivo explorando muchos menos nodos que Dijkstra. En grids grandes la diferencia es brutal.

Condición crítica: la heurística debe ser admisible (nunca sobrestimar el coste real). Si h(n) sobrestima, A* puede devolver rutas subóptimas. Manhattan y Euclidiana son admisibles si tus costes de movimiento son coherentes con ellas.

En resumen: A* = Dijkstra + dirección. Más rápido, igual de óptimo si usas una heurística admisible, y el estándar de facto en videojuegos.

NavMesh: del mundo 3D a un grafo navegable

NavMesh no compite con A*. Es una representación del espacio, no un algoritmo. Pero merece una sección propia porque es la solución estándar para navegación en entornos 3D.

El problema que resuelve: en un juego 3D con geometría compleja (edificios, rampas, escaleras, muebles), convertir cada triángulo del mesh en un nodo de grafo sería inviable. Necesitas millones de nodos para representar un nivel mediano. Inmanejable.

NavMesh reduce el problema. En lugar de trabajar con toda la geometría, genera una malla simplificada de polígonos convexos que representan las superficies donde un agente puede caminar. Luego, esos polígonos se conectan entre sí formando un grafo mucho más pequeño.

El proceso tiene tres fases:

Fase 1: Baking (horneado)

El motor analiza tu geometría de nivel, detecta superficies planas transitables (suelo, rampas, plataformas) y genera polígonos navegables. Aquí defines parámetros como:

• Agent radius (radio del agente): cuánto espacio necesita tu personaje. Esto hace que el NavMesh se "encoja" alrededor de obstáculos para que un agente grande no intente pasar por huecos estrechos.
• Agent height: para detectar techos bajos y túneles donde el agente no cabe.
• Max slope: pendientes demasiado empinadas se marcan como no navegables.
• Step height: escalones pequeños que el agente puede subir sin necesidad de rampas.

El resultado: una malla de polígonos que cubre las zonas caminables del nivel, con conexiones entre polígonos adyacentes y, si es necesario, links especiales (saltos, teletransportes, puertas).

Fase 2: Pathfinding sobre el NavMesh

Una vez horneado, el NavMesh es un grafo. Cada polígono es un nodo, cada borde compartido es una arista. Cuando pides una ruta de A a B, el motor:

1. Identifica en qué polígono está A y en qué polígono está B.
2. Ejecuta A* (u otra variante) sobre el grafo de polígonos.
3. Devuelve una secuencia de polígonos que conectan ambos puntos.

Como los polígonos son áreas grandes, el grafo tiene muchos menos nodos que un grid. La búsqueda es rápida.

Fase 3: Path smoothing (suavizado de ruta)

El path que obtienes es una secuencia de polígonos. Pero si mueves al agente de centro a centro de cada polígono, la ruta será robótica y con giros bruscos. Aquí entra el smoothing: técnicas como el funnel algorithm (algoritmo del embudo) calculan la ruta más directa dentro del corredor de polígonos, generando un camino suave y natural.

El resultado final: rutas que parecen pensadas por un humano, no por una máquina.

Limitaciones y trade-offs

NavMesh pre-calculado es estático. Si tu nivel cambia dinámicamente (destruyes un muro, abres una puerta, colocas una barricada), necesitas actualizar el NavMesh. Algunos motores permiten "partial rebaking" o tiles dinámicos, pero añade complejidad.

Además, el NavMesh no resuelve evasión entre agentes. Si dos enemigos siguen rutas que convergen, pueden chocar. Ahí necesitas steering behaviors o local avoidance (otra capa, como dijimos al inicio).

Cuándo usar qué: reglas de decisión

Aquí está la tabla que deberías tener en la cabeza cuando elijas tu enfoque.

Dijkstra: úsalo si necesitas calcular distancias óptimas desde un punto hacia TODOS los demás nodos del grafo (por ejemplo, para implementar influence maps o análisis de territorio en un RTS). En pathfinding puro rara vez lo usas, porque A* es estrictamente mejor si tienes un único objetivo.

A*: el caballo de batalla. Úsalo en:

• Juegos 2D con grid (roguelikes, tower defense, tácticos por turnos).
• Pathfinding sobre grafos de waypoints.
• Navegación sobre NavMesh (sí, internamente los motores suelen usar A* sobre el grafo de polígonos).

Es rápido, óptimo, bien estudiado y tiene mil variantes si necesitas optimizaciones avanzadas más adelante.

NavMesh: úsalo en entornos 3D con geometría compleja donde un grid sería inviable:

• Shooters (enemigos que te rodean en edificios).
• Acción/aventura 3D (NPCs en ciudades, dungeons).
• Survival o sigilo (patrullas realistas que respetan el layout del nivel).

NavMesh no es un algoritmo, es el pipeline de representación. Por dentro seguirás usando A*.

Casos híbridos:

• Mundo abierto enorme: NavMesh local + grafo de regiones para tránsito entre zonas.
• RTS con unidades que destruyen obstáculos: grid dinámico o NavMesh con tiles actualizables.
• Top-down con niveles generados proceduralmente: grid simple y A* sin complicarte.

Regla final: empieza con lo más simple que funcione. Un grid de 50×50 con A* básico ya te lleva muy lejos. NavMesh es un upgrade cuando la complejidad del nivel lo justifica, no el punto de partida.

Errores típicos y cómo depurar sin perder la cordura

Implementar pathfinding no termina cuando "funciona una vez". Aquí están los problemas que te vas a encontrar (y cómo atacarlos).

Error 1: Heurística no admisible

Síntoma: A* devuelve rutas subóptimas o raras.

Causa: tu h(n) sobrestima el coste real. Ejemplo: usas distancia Euclidiana pero tu coste de movimiento diagonal es más alto que sqrt(2).

Solución: asegúrate de que h(n) nunca sobrestime. Si dudas, usa una heurística más conservadora o directamente h(n) = 0 (convierte A* en Dijkstra, lento pero seguro).

Error 2: Nodos mal conectados

Síntoma: el algoritmo no encuentra camino aunque visualmente debería existir.

Causa: el grafo tiene un gap. Dos nodos que parecen adyacentes no están conectados. O permitiste diagonales pero no verificaste que las casillas ortogonales también estén libres (el NPC "atraviesa" esquinas).

Solución: dibuja tu grafo. Literalmente. Visualiza las conexiones. Si usas diagonales, chequea que no permitas atravesar obstáculos en diagonal.

Error 3: Agente más grande que el pasillo

Síntoma: el path es correcto, pero el NPC se atasca en puertas o pasillos.

Causa: el NavMesh fue bakeado con un agent radius menor que el tamaño real de tu personaje. O tu grid no considera el tamaño del agente.

Solución: ajusta el agent radius en el NavMesh. Si usas grid, "infla" los obstáculos según el tamaño del agente antes de calcular rutas.

Error 4: Performance horrible con muchos agentes

Síntoma: 20 enemigos calculando paths cada frame y tus FPS se desploman.

Causa: recalculas rutas innecesariamente. Pathfinding es costoso; hacerlo cada frame para cada agente es suicidio.

Solución:

• Calcula rutas solo cuando cambia el objetivo o el entorno (event-driven).
• Usa intervalos: cada agente recalcula su path cada N frames, no todos a la vez.
• Cachea rutas si varios agentes van al mismo sitio.
• Limita la profundidad de búsqueda o el área explorada.
• Considera "lazy paths": calcula solo los primeros pasos de la ruta y recalcula cuando te acerques.

Error 5: Rutas correctas pero movimiento feo

Síntoma: el NPC llega al objetivo, pero gira en ángulos rectos, se pega a las paredes o hace zigzag.

Causa: esto NO es un problema de pathfinding. Es un problema de steering y avoidance.

Solución: añade smoothing al path (string pulling, Catmull-Rom splines). Implementa steering behaviors para suavizar la trayectoria. Separa el problema: pathfinding te da waypoints, steering traduce eso en movimiento fluido.

Error 6: El NPC ignora cambios en el entorno

Síntoma: abres una puerta, colocas un obstáculo nuevo, y el enemigo sigue usando la ruta vieja.

Causa: calculaste el path una vez y nunca lo actualizaste.

Solución: invalida rutas cuando el entorno cambia. Si usas NavMesh dinámico, rebakea la zona afectada. Si usas grid, marca las casillas modificadas y fuerza recálculo en los agentes cercanos.

Checklist de diagnóstico rápido

Cuando tu pathfinding falle, revisa en orden:

1. ¿El grafo está bien definido? (nodos, conexiones, pesos coherentes)
2. ¿El agente cabe en el espacio navegable? (radio, altura)
3. ¿La heurística es admisible?
4. ¿El path calculado es correcto en teoría? (dibújalo)
5. Si el path es correcto pero el movimiento es malo: es steering, no pathfinding.
6. Si el path no se encuentra: visualiza Open/Closed durante la búsqueda para ver dónde se atasca el algoritmo.

Depurar pathfinding sin visualización es masoquismo. Dibuja el grafo. Dibuja el path. Dibuja los nodos explorados. La mayoría de bugs se evaporan cuando ves lo que realmente está pasando.

Más allá de "funciona": pathfinding como diseño

Un error común de quien empieza: creer que pathfinding es un problema puramente técnico. Lo implementas bien y listo. Pero la verdad es que pathfinding también es diseño.

A veces no quieres la ruta óptima. Quieres la ruta interesante.

Ejemplos:

• En un juego de sigilo, prefieres que los guardias patrullen rutas predecibles (incluso subóptimas) para que el jugador pueda planificar. Rutas demasiado "inteligentes" rompen el diseño del nivel.
• En un shooter, puedes asignar costes artificiales a ciertas zonas para que los enemigos prefieran flanquearte en lugar de atacar frontalmente, aunque la ruta frontal sea más corta.
• En un RPG táctico, puedes hacer que ciertos tipos de unidades eviten terreno difícil aunque técnicamente puedan atravesarlo, para reforzar la diferencia de roles (infantería pesada vs exploradores ligeros).

Pathfinding te da herramientas: costes de terreno, áreas prohibidas, modificadores de zona. Úsalas para guiar el comportamiento, no solo para "llegar de A a B lo más rápido posible".

El pathfinding bien diseñado es invisible. El jugador no piensa "vaya, qué buen algoritmo". Piensa "estos enemigos se mueven como deberían". Esa es la meta.

El siguiente paso: de prototipo a sistema

Si has llegado hasta aquí, ya no estás en el nivel "mi NPC atraviesa paredes". Entiendes la diferencia entre representación y algoritmo. Sabes cuándo usar A*, cuándo NavMesh, y por qué Dijkstra existe. Puedes seguir un ejemplo paso a paso y replicarlo en tu motor.

Ese es el salto de quien copia tutoriales sin entender a quien tiene criterio.

Pero hay una diferencia más grande: pasar de implementar una técnica aislada a construir sistemas completos. Pathfinding no vive solo. Convive con IA de decisión, con animación, con diseño de niveles, con optimización, con gameplay. Los proyectos reales integran todo eso y funcionan bajo presión: deadlines, feedback, iteración.

Ahí es donde entra la metodología.

Si esta parte te engancha (navegación, IA aplicada, diseño de sistemas, programación de gameplay, motores gráficos), y quieres profesionalizarlo con proyectos reales, feedback constante y un entorno donde construir portfolio en lugar de acumular tutoriales sueltos, el Grado en Diseño y Desarrollo de Videojuegos y Entornos Virtuales es el itinerario diseñado para eso.

No es la única forma de aprender. Pero es la forma estructurada: con profesores en activo, proyectos que simulan producción real, y una comunidad donde "hacer videojuegos" deja de ser una aspiración y se convierte en oficio.

Ahora vuelve a tu prototipo. Implementa un grid simple, prueba A* con lápiz y papel antes de escribir código, visualiza la búsqueda. Y cuando funcione, cuando tu NPC rodee ese obstáculo por primera vez sin atravesarlo, vas a sentir algo que ningún tutorial te puede dar: la certeza de que lo entiendes.

Ese es el primer paso. Los siguientes dependen de ti.