Pathfinding en Videojuegos: A* y sus Variantes

Cada vez que un enemigo persigue al jugador por una mazmorra, un escuadrón cruza el mapa en un RTS o un NPC rodea una silla en lugar de atravesarla, hay un algoritmo de pathfinding corriendo debajo. La elección del algoritmo (y cómo está refinado) suele ser la diferencia entre un mundo que se siente vivo y uno que tartamudea cada vez que algo se mueve.

A* es la respuesta que se oye más veces. Se enseña en cualquier curso de IA introductorio, viene de serie en todos los motores y se escriben posts sobre él constantemente. Pero A* por sí solo no escala al tamaño de los juegos modernos. Mundos abiertos enormes, miles de unidades, obstáculos dinámicos... Todo eso exige variantes: NavMesh para 3D, Jump Point Search para rejillas abiertas, enfoques jerárquicos para mapas a escala continental...

Este artículo explora esas soluciones: por qué los algoritmos más simples se quedan cortos, cómo funciona A* de verdad debajo de la heurística, qué variantes resuelven qué problemas y cómo implementar el núcleo en Unity/C#.

1. Por Qué Mover Personajes en un Juego Es Difícil

A primera vista, ir de A a B en una rejilla parece trivial. Breadth-First Search (BFS) encuentra el camino más corto en una rejilla de coste uniforme en O(V + E). Enchúfalo y listo. Salvo que en los juegos casi nunca hay coste uniforme.

Una casilla de pantano cuesta más que una carretera. Una escalera cuesta más que suelo plano. Una casilla bajo fuego enemigo en un juego de tácticas puede costar infinitamente más que rodearla. En cuanto los costes varían, BFS da el camino con menos casillas, no el más barato. Y casi nunca son el mismo.

La escala lo empeora. Un BFS que explora 10.000 casillas en un mapa pequeño explota a millones en un mapa de RTS de 500x500. Al llevarlo a 3D, o a miles de agentes concurrentes, es donde comienzan los problemas de rendimiento.

2. Dijkstra: El Punto de Partida

El algoritmo de Dijkstra resuelve el camino más corto con pesos. Partiendo del origen, expande hacia el nodo conocido más barato en cada iteración, actualizando distancias sobre la marcha. Cuando llega al objetivo, el camino es garantizadamente óptimo.

El problema es la palabra EXPANDE. Dijkstra no sabe en qué dirección está el objetivo. Expande una frontera aproximadamente circular, explorando casillas que se "alejan" del objetivo con el mismo entusiasmo que las que se acercan. En una rejilla de 100x100 con el objetivo en la esquina opuesta, se va a explorar la mayor parte del mapa antes de llegar.

1// Bucle central de Dijkstra — expande el nodo conocido más barato
2while (open.Count > 0)
3{
4    Node current = open.Dequeue(); // menor g
5
6    if (current == target) break;
7
8    foreach (Node neighbor in current.Neighbors)
9    {
10        float tentativeG = current.G + Cost(current, neighbor);
11        if (tentativeG < neighbor.G)
12        {
13            neighbor.G = tentativeG;
14            neighbor.Parent = current;
15            open.Enqueue(neighbor, tentativeG);
16        }
17    }
18}

Dijkstra sigue siendo útil; es exacto, maneja cualquier peso positivo y cuando no se conoce dónde está el objetivo (flow fields, múltiples orígenes, exploración de terreno uniforme) es la herramienta correcta. Pero para consultas de un origen y un objetivo, desperdicia esfuerzo. Esa es la brecha que cierra A*.

3. A*: Dijkstra con Heurística

A* extiende Dijkstra con una idea: estima cuánto queda. Para cada nodo, en lugar de priorizar por g(n) (coste conocido desde el inicio), se prioriza por f(n) = g(n) + h(n), donde h(n) es una estimación heurística del coste restante al objetivo.

El efecto es brutal. Una buena heurística tira de la búsqueda hacia el objetivo en lugar de expandir un círculo. En la misma rejilla de 100x100 donde Dijkstra explora 10.000 casillas, A* con una heurística razonable puede explorar 200. Mismo resultado, órdenes de magnitud menos trabajo.

A* es Dijkstra con sentido de la orientación.

Dos propiedades de h(n) importan. Admisibilidad significa que la heurística nunca sobreestima el coste real restante: si lo hace, A* puede devolver un camino subóptimo. Consistencia (también llamada condición monótona) significa que la heurística respeta la desigualdad triangular: h(n) <= cost(n, m) + h(m) para cualquier vecino m. Las heurísticas consistentes son siempre admisibles y permiten saltarte la reapertura de nodos desde el closed set. Una mejora de rendimiento nada despreciable.

4. Elegir la Heurística

La heurística es donde la mayoría de implementaciones de A* triunfan o fracasan. Para juegos en rejilla, la elección sale directamente de las reglas de movimiento:

• Distancia Manhattan: movimiento en 4 direcciones (sin diagonales). |dx| + |dy|.
• Distancia Chebyshev: 8 direcciones donde las diagonales cuestan igual que los cardinales. max(|dx|, |dy|).
• Distancia Octile: 8 direcciones donde las diagonales cuestan ~1.414 (sqrt 2). max(|dx|, |dy|) + (sqrt(2) - 1) * min(|dx|, |dy|).
• Distancia Euclídea: movimiento en cualquier ángulo. sqrt(dx*dx + dy*dy). Admisible en rejillas también, pero sueltas. Subestimar hace A* más lento.

1public static class Heuristics
2{
3    public static float Manhattan(Vector2Int a, Vector2Int b) =>
4        Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
5
6    public static float Chebyshev(Vector2Int a, Vector2Int b) =>
7        Mathf.Max(Mathf.Abs(a.x - b.x), Mathf.Abs(a.y - b.y));
8
9    public static float Octile(Vector2Int a, Vector2Int b)
10    {
11        int dx = Mathf.Abs(a.x - b.x);
12        int dy = Mathf.Abs(a.y - b.y);
13        return Mathf.Max(dx, dy) + (Mathf.Sqrt(2f) - 1f) * Mathf.Min(dx, dy);
14    }
15
16    public static float Euclidean(Vector2Int a, Vector2Int b) =>
17        Vector2Int.Distance(a, b);
18}

El desempate también importa. Cuando varios nodos comparten el mismo f, A* elige de forma arbitraria, lo que suele producir caminos que zigzaguean por diagonales. Truco: multiplicar la heurística por un factor ligeramente mayor que 1 (tipo 1.001) para desempatar a favor de nodos más cercanos al objetivo. El resultado son caminos más rectos y visualmente más agradables, casi sin coste extra.

Un consejo es multiplicar la heurística por un factor ligeramente mayor que 1 (por ejemplo, 1.001) para desempatar a favor de nodos más cercanos al objetivo. El resultado son caminos más rectos y visualmente más agradables, casi sin coste extra.

5. Implementando A* en Unity/C#

A continuación se muestra una implementación completa de A* para una rejilla 2D. Las tres cosas que importan son la priority queue, el closed set (un hash set, no una lista) y el paso de reconstrucción.

1public class AStarNode
2{
3    public Vector2Int Position;
4    public float G = float.PositiveInfinity;
5    public float H;
6    public float F => G + H;
7    public AStarNode Parent;
8    public bool Walkable;
9}
10
11public class AStarGrid
12{
13    private readonly AStarNode[,] _nodes;
14    private readonly int _width, _height;
15
16    public AStarGrid(bool[,] walkable)
17    {
18        _width = walkable.GetLength(0);
19        _height = walkable.GetLength(1);
20        _nodes = new AStarNode[_width, _height];
21        for (int x = 0; x < _width; x++)
22        for (int y = 0; y < _height; y++)
23            _nodes[x, y] = new AStarNode
24            {
25                Position = new Vector2Int(x, y),
26                Walkable = walkable[x, y],
27            };
28    }
29
30    public List<Vector2Int> FindPath(Vector2Int start, Vector2Int goal)
31    {
32        ResetNodes();
33        var startNode = _nodes[start.x, start.y];
34        var goalNode  = _nodes[goal.x,  goal.y];
35
36        startNode.G = 0;
37        startNode.H = Heuristics.Octile(start, goal);
38
39        var open   = new PriorityQueue<AStarNode, float>();
40        var closed = new HashSet<AStarNode>();
41        open.Enqueue(startNode, startNode.F);
42
43        while (open.Count > 0)
44        {
45            var current = open.Dequeue();
46            if (current == goalNode) return Reconstruct(current);
47
48            closed.Add(current);
49
50            foreach (var neighbor in GetNeighbors(current))
51            {
52                if (!neighbor.Walkable || closed.Contains(neighbor)) continue;
53
54                float stepCost = StepCost(current, neighbor);
55                float tentativeG = current.G + stepCost;
56                if (tentativeG >= neighbor.G) continue;
57
58                neighbor.Parent = current;
59                neighbor.G = tentativeG;
60                neighbor.H = Heuristics.Octile(neighbor.Position, goal);
61                open.Enqueue(neighbor, neighbor.F);
62            }
63        }
64        return null; // inalcanzable
65    }
66
67    private static float StepCost(AStarNode a, AStarNode b)
68    {
69        bool diagonal = a.Position.x != b.Position.x
70                     && a.Position.y != b.Position.y;
71        return diagonal ? 1.41421356f : 1f;
72    }
73
74    private static List<Vector2Int> Reconstruct(AStarNode end)
75    {
76        var path = new List<Vector2Int>();
77        for (var n = end; n != null; n = n.Parent) path.Add(n.Position);
78        path.Reverse();
79        return path;
80    }
81    // GetNeighbors y ResetNodes omitidos por brevedad
82}

6. NavMesh: Cuando las Rejillas No Bastan

Los mundos 3D rara vez se descomponen limpiamente en rejillas. Una rampa inclinada, una cornisa que sobresale, una puerta de media casilla de ancho. Nada de esto encaja bien en la abstracción de rejilla. La solución de la industria es la Navigation Mesh: un conjunto de polígonos convexos que representan la superficie transitable del mundo.

El pathfinding sobre NavMesh sigue usando A*, pero el grafo es distinto. Cada polígono es un nodo, y las aristas conectan polígonos que comparten un borde. El grafo es pequeño (cientos de polígonos en lugar de millones de casillas), la heurística es la distancia euclídea entre centros de polígonos, y el camino es una secuencia de polígonos que luego se convierten en una secuencia concreta de puntos.

Unity lo trae de serie. Hay que marcar la geometría como Navigation Static, "bakear" el NavMesh en el editor (o en runtime con NavMeshSurface), añadir un NavMeshAgent al personaje y llamar a SetDestination. El motor se ocupa de A*, evitar embudos y steering.

1using UnityEngine;
2using UnityEngine.AI;
3
4[RequireComponent(typeof(NavMeshAgent))]
5public class EnemyChaser : MonoBehaviour
6{
7    [SerializeField] private Transform target;
8    private NavMeshAgent _agent;
9
10    void Awake() => _agent = GetComponent<NavMeshAgent>();
11
12    void Update()
13    {
14        if (target == null) return;
15        _agent.SetDestination(target.position);
16    }
17}

El NavMesh integrado está bien para la mayoría de juegos. Sin embargo, hay situaciones en las que no es útil, como plataformas móviles, terreno destructible, mundos procedurales... En esos casos, se recurre a alternativas. El paquete AI Navigation de Unity soporta bake en runtime y NavMeshLinks para saltos off-mesh. Para control total, A* Pathfinding Project (Aron Granberg) es la opción de terceros de referencia y trae sus propios modos grid, NavMesh y jerárquico.

7. Jump Point Search (JPS)

En rejillas de coste uniforme (cada casilla transitable cuesta lo mismo), A* hace mucho trabajo redundante. Expande cada casilla de una región aproximadamente elíptica entre origen y objetivo, y la mayoría de esas expansiones solo confirman que una línea recta sigue siendo una línea recta. Jump Point Search explota esta simetría: se salta casillas que no pueden estar en un camino óptimo.

JPS reemplaza el paso de "expandir todos los vecinos" de A* por un procedimiento de salto recursivo. En lugar de avanzar casilla a casilla, "salta" en líneas rectas y diagonales, parando solo en casillas que son forced-neighbors (casillas que podrían llevar a un camino más corto rodeando un obstáculo) o en el objetivo. El resultado es un A* que puede saltarse cientos de casillas por paso en mapas abiertos, con ganancias de 10x o más frente a A* plano.

1// Salto simplificado de JPS — caso horizontal/vertical
2// Devuelve el siguiente "jump point" en la dirección (dx, dy), o null si no hay
3private Vector2Int? Jump(Vector2Int from, Vector2Int dir, Vector2Int goal)
4{
5    var next = from + dir;
6    if (!InBounds(next) || !IsWalkable(next)) return null;
7    if (next == goal) return next;
8
9    // Movimiento diagonal: primero recurre sobre los componentes cardinales
10    if (dir.x != 0 && dir.y != 0)
11    {
12        if (Jump(next, new Vector2Int(dir.x, 0), goal).HasValue) return next;
13        if (Jump(next, new Vector2Int(0, dir.y), goal).HasValue) return next;
14    }
15
16    // Chequeo de forced-neighbor (obstáculo fuerza un giro)
17    if (HasForcedNeighbor(next, dir)) return next;
18
19    // Sigue saltando en la misma dirección
20    return Jump(next, dir, goal);
21}

La desventaja es que JPS solo funciona en rejillas de coste uniforme. En cuanto se introducen costes variables de terreno (pantano, carretera, etc.), las simetrías que explota se rompen. Hay extensiones (JPS+, JPS(B), Bounded JPS) pero todas atacan el mismo caso de rejilla con coste uniforme. Si se está desarrollando un roguelike o un juego táctico por casillas sin costes variables, JPS es esencialmente rendimiento gratis. Si se trabaja con un juego con terreno con costes, A* plano es la elección correcta.

8. A* Jerárquico (HPA*)

Incluso con JPS, una sola llamada de A* sobre una rejilla de 2048x2048 es lenta. Cuando hay cientos de unidades de RTS pathing simultáneamente por un continente, ninguna optimización por consulta basta. La solución a esto pasa por reducir el tamaño del problema.

HPA* (Hierarchical Pathfinding A*) lo hace descomponiendo el mundo en clusters. Utiliza A* a dos niveles: primero sobre el grafo abstracto de clusters para encontrar qué clusters atravesar, luego sobre la rejilla local de cada cluster para encontrar el camino exacto. El resultado es un camino ligeramente subóptimo pero un orden de magnitud más rápido de calcular, y que permite refinar cada segmento de cluster de forma perezosa, solo cuando la unidad llega ahí.

• Divide la rejilla en clusters NxN (típicamente 10x10 o 16x16).
• Identifica las casillas de borde donde los clusters conectan, pasando a ser nodos del grafo abstracto.
• Precalcula los costes de arista cluster-a-cluster corriendo A* dentro de cada cluster entre sus nodos de borde.
• En tiempo de consulta, A* corre sobre el grafo abstracto para elegir una secuencia de clusters, luego refina cada segmento local bajo demanda.

HPA* brilla en RTS y mundos abiertos. Clásicos como Age of Mythology y más recientemente juegos que usan el grafo Recast de A* Pathfinding Project con metadatos jerárquicos usan variaciones de este patrón. El coste es memoria (se guardan conexiones precalculadas entre clusters) y lógica de invalidación más compleja cuando el terreno cambia.

El pathfinding jerárquico cambia caminos exactos por caminos que existen lo bastante rápido para importar.

9. Entornos Dinámicos y D* Lite

A* planifica una vez y se mueve. Si el mundo cambia (se abre una puerta, se hunde un puente, otra unidad bloquea un pasillo) hay que replanificar desde cero. Para caminos cortos está bien. Para caminos largos sobre mapas grandes con cambios frecuentes, es un desperdicio. Para estos casos, es donde D* y su variante moderna, D* Lite, pueden ayudar.

D* Lite es un algoritmo de búsqueda incremental. Calcula un camino inicial, y cuando el mundo cambia repara el camino localmente en lugar de recalcular todo. Solo se actualiza la parte del árbol de búsqueda afectada por el cambio. Para agentes moviéndose por entornos parcialmente conocidos o dinámicos, D* Lite puede ser más eficiente que llamar a A* repetidamente.

La implementación es más compleja que A*. Ejecuta la búsqueda "al revés", del objetivo al origen, mientras mantiene un valor rhs junto al g, y usa una priority queue con clave en una tupla lexicográfica en lugar de un solo float. La mayoría de juegos no lo necesitan: un A* bien afinado con replanificaciones completas ocasionales es más simple y rápido. Pero cuando se trabaja con pathfinding en un dungeon crawler donde las puertas se abren constantemente o un RTS con modificación constante del terreno, merece la complejidad.

10. Caso de Estudio: Otter's Hell

En Otter's Hell (bullet-hell roguelite en desarrollo en Unity) los enemigos tienen que perseguir a Sparkles (el jugador) por habitaciones creadas proceduralmente. Los niveles no son casillas estáticas: aparecen enemigos, se mueven obstáculos, aparecen y desaparecen coberturas destructibles. Elegir el enfoque correcto de pathfinding importaba porque puede haber docenas de enemigos activos a la vez.

El primer instinto fue usar NavMesh. El agente integrado de Unity maneja steering y avoidance de forma limpia. Pero la naturaleza procedural de las salas obligaba a bakear NavMesh en runtime, y un NavMesh 3D sobre contenido 2D se sentía sobredimensionado. Los re-bakes grandes también picaban los frame times en hardware débil.

La solución final es un A* basado en rejilla sobre una cost grid 2D por habitación. La rejilla de cada nivel es lo bastante pequeña como para que incluso una implementación ingenua termine en bastante menos de un milisegundo por consulta, y es barato reconstruirla cuando el layout muta. Cada enemigo pide un camino al objetivo a una cadencia (no cada frame) y entre replanificaciones el steering local maneja el avoidance a corto plazo.

1public class EnemyPathfinder : MonoBehaviour
2{
3    [SerializeField] private float replanIntervalSeconds = 0.25f;
4
5    private AStarGrid _grid;
6    private List<Vector2Int> _path;
7    private int _waypointIndex;
8    private float _replanTimer;
9
10    public void SetGrid(AStarGrid grid) => _grid = grid;
11
12    void Update()
13    {
14        _replanTimer -= Time.deltaTime;
15        if (_replanTimer <= 0f)
16        {
17            _path = _grid.FindPath(
18                WorldToGrid(transform.position),
19                WorldToGrid(Sparkles.Instance.transform.position));
20            _waypointIndex = 0;
21            _replanTimer = replanIntervalSeconds;
22        }
23
24        FollowPath();
25    }
26}

Replanificar cada 250ms es esencialmente gratis por enemigo, las rejillas son diminutas y el resultado de juego son enemigos que rastrean al jugador de forma inteligente sin la sobrecarga de NavMesh o un sistema jerárquico que el juego no necesita. La lección: el algoritmo correcto depende de la escala. Las variantes de A* existen para mapas enormes y presupuestos ajustados, aunque la mayoría de juegos se apañan con la versión simple.

11. Elegir el Algoritmo Correcto

No hay respuesta universal, pero sí recomendaciones para inclinarse hacia un algoritmo u otro. Esto es, más o menos, lo más adecuado por tipo de juego:

• Rejilla 2D pequeña, costes variables de terreno (juego de tácticas, roguelike con pantanos/carreteras) → A* plano con heurística Octile o Manhattan. Sin complicaciones.
• Rejilla 2D pequeña, coste uniforme (roguelike clásico, movimiento de puzzle) → JPS para ~10x de speedup sobre A* esencialmente gratis.
• Mundo 3D, escala moderada (acción, aventura) → NavMesh. El integrado de Unity aguanta hasta que deja de aguantar.
• Mapa 2D muy grande, muchos agentes (RTS, simulación de multitudes en open-world) → HPA* o flow field para destinos compartidos.
• Entorno muy dinámico, conocimiento parcial (IA de sigilo en mundos destructibles, robótica) → D* Lite.
• Miles de unidades al mismo objetivo (unidades de RTS convergiendo en un punto de reunión, movimiento en formación) → flow fields. Un Dijkstra-desde-el-objetivo, cada agente lee el vector field resultante.

Conclusiones

El pathfinding es uno de esos campos donde el algoritmo de libro (A*) suele ser el correcto, y las variantes de la industria existen para manejar los casos extremos que la versión de libro no puede. Saber qué caso extremo se tiene realmente es la mayor parte de la batalla.

• Dijkstra es exacto pero derrochador para consultas a un objetivo único; A* le gana casi siempre.
• A* es Dijkstra más una heurística: la heurística no puede sobreestimar si se quieren caminos óptimos.
• Empareja la heurística con las reglas de movimiento: Manhattan para 4 direcciones, Octile para 8, Euclídea para cualquier ángulo.
• NavMesh es A* sobre un grafo de polígonos es genial para 3D, dejando que el motor bakee por ti.
• JPS da speedups enormes en rejillas de coste uniforme podando caminos simétricos.
• HPA* escala a mapas de tamaño continental descomponiéndolos en clusters.
• D* Lite es para entornos muy dinámicos; para la mayoría de juegos, A* con reparación local es más simple y suficiente.
• Analiza primero: Los algoritmos elegantes resuelven problemas reales, pero la mayoría de juegos nunca los tocan.

El patrón a través de todos estos algoritmos es el mismo: cambiar un poco de optimalidad por mucha velocidad, o un poco de memoria por mucha escala. Cada variante es la respuesta a una presión específica. Cuando se sienta esa presión como una consulta lenta, un frame perdido, una búsqueda que no termina a tiempo, se sabrá cuál elegir.

El buen pathfinding es invisible. Los jugadores no se fijan en el algoritmo, solo se fijan cuando se rompe.