Pathfinding avanzado: JPS, Theta* y HPA*

0. Introducción

A* es la solución por defecto. Pero hay tres dolores típicos donde A* clásico no es lo mejor:

1. Grids enormes uniformes: A* explora celda por celda. En un grid 500×500 abierto, expande miles de nodos para hacer una línea recta. JPS (Jump Point Search) lo arregla saltando.
2. Paths con esquinas duras feas: A* sobre grid produce zigzags antinaturales. Theta* añade line-of-sight para producir paths suavizados.
3. Mapas gigantes: para un mapa de 10000×10000, A* es prohibitivo aunque uses JPS. HPA* divide el mapa en clusters y busca jerárquicamente.

Cada uno paga un precio (más complejidad, más memoria, más preprocesamiento). En este tutorial ves cuándo cada precio vale la pena.

1. JPS — Jump Point Search

JPS (Harabor & Grastien, 2011) es un refinamiento de A* específico para grids uniformes 8-conexos. La observación clave: en un grid sin obstáculos cercanos, expandir cada celda intermedia es trabajo desperdiciado. Si vas en línea recta, sigue recta hasta que algo cambie.

En grids uniformes, A\* visita cada celda de la frontera. JPS (Jump Point Search) "salta" tramos rectos en una sola expansión y solo gasta una entrada de PQ en los puntos donde la dirección puede cambiar (jump points). Mismo path final, fracción del trabajo.

Figura 1 — A* clásico arriba, JPS abajo. Mismo path final, pero JPS solo mete en la PQ los puntos donde la dirección puede cambiar. Los círculos naranjas son los jump points: nodos clave en el camino.

1.1 La idea

A* expande cada celda que toca. JPS reemplaza la expansión “dame todos mis vecinos” por “dame los próximos jump points en cada dirección”. Un jump point es:

• El goal.
• Una celda con un vecino forzado — un vecino que A* clásico tendría que considerar pero JPS pudo evitar (típicamente porque hay una pared al lado).
• En diagonal: una celda que tiene un jump point horizontal o vertical alcanzable desde ahí.

El algoritmo recorre filas, columnas y diagonales en línea recta, “saltando” celdas hasta encontrar un jump point. Las celdas intermedias nunca entran a la PQ.

1.2 Cuánto gana

En grids 8-conexos uniformes con espacio relativamente abierto, JPS expande 5–10× menos nodos que A*. En grids 100×100 con muchas paredes, la ganancia se reduce — pero sigue siendo mejor.

1.3 Cuándo NO usar JPS

• Grids no uniformes (costos heterogéneos): el algoritmo asume costo uniforme. Hay variantes (JPS+ con costos), pero pierden simplicidad.
• NavMesh poligonal: JPS es exclusivo de grids uniformes 8-conexos.
• Grids con paredes muy densas: la ventaja se diluye. Si más del 50% son paredes, A* puede ser comparable.

2. Theta* — paths sin esquinas duras

A* sobre grid produce paths que parecen escalones: solo se mueve por celdas adyacentes, así que cualquier cambio de dirección es 90° o 45°. Para una unidad humana o un vehículo, eso se ve mecánico y feo.

A* sobre grid produce paths con esquinas duras (verde): siempre se mueve celda a celda. Theta\* añade un test de línea-de-visión: si hay LOS desde el abuelo al vecino, conecta directo. El resultado es un path geodésico (naranja), más corto y más natural. Click para añadir/quitar muros.

mostrar Theta*

Figura 2 — Verde es A* clásico (esquinas en cada celda), naranja es Theta* (suavizado por LOS). Click para añadir/quitar muros y ver cómo Theta* recorta donde puede.

2.1 La idea

Theta* (Daniel et al., 2010) cambia una sola línea del bucle de A*: cuando relajas un vecino, en vez de conectarlo al current, intentas conectarlo al padre del current si hay línea de visión entre ellos.

function relax(current, neighbor)
    parentOfCur = parent[current]

    if hasLineOfSight(parentOfCur, neighbor):
        # camino directo del abuelo al vecino
        tentative_g = gScore[parentOfCur] + dist(parentOfCur, neighbor)
        newParent = parentOfCur
    else:
        # camino normal de A*: padre = current
        tentative_g = gScore[current] + dist(current, neighbor)
        newParent = current

    if tentative_g < gScore[neighbor]:
        gScore[neighbor] = tentative_g
        parent[neighbor] = newParent

hasLineOfSight es típicamente Bresenham sobre el grid: si todas las celdas en la línea son walkable, hay LOS. El path resultante puede saltarse celdas intermedias enteras.

2.2 La trampa

Theta* es más lento por iteración que A* (cada relajación hace un raycast). En grids con muchas paredes, ese costo se nota. Pero:

• El path resultante es mucho más corto en distancia real (no en celdas: el A* y el Theta* recorren la misma cantidad de celdas, pero Theta* las recorre con líneas oblicuas que el agente puede seguir directo).
• Visualmente es muchísimo más natural.
• No requiere post-process de smoothing como sí necesita A* “puro”.

2.3 Cuándo usar Theta*

• Movimiento continuo del agente (no por celdas), sobre un grid lógico. Personajes humanos, drones, vehículos.
• Cuando la dirección importa visualmente: una unidad que zigzaguea cuando podría ir recto se siente mal.

2.4 Variantes

• Lazy Theta* — el LOS solo se verifica al cerrar el nodo, no en cada relajación. Ahorra raycast cuando no se va a cerrar.
• Any-Angle path planning es la familia entera. Theta* es la implementación más conocida.

3. HPA* — A* jerárquico para mapas grandes

A* (incluso con JPS) tiene un techo: cuando el mapa es 5000×5000, ningún algoritmo de búsqueda exhaustiva escala. La solución: dividir el mapa en clusters y buscar jerárquicamente.

El mapa se divide en clusters de 4×4. Cada par de celdas adyacentes en el borde de dos clusters es un portal (puntos violetas). El path naranja es el "alto nivel" — solo de portal a portal. Dentro de cada cluster, A* corre sobre cuadrículas chiquitas, mucho más rápido. En mapas de 1000×1000 esto baja el tiempo de búsqueda en 1–2 órdenes de magnitud.

Figura 3 — Los clusters (4×4 en este ejemplo) se ven con tono alternado. Los puntos violeta son portales — celdas en bordes que conectan dos clusters. El path naranja es el “alto nivel”: va de portal a portal sin entrar al detalle de cada celda. El path verde es el A* completo de referencia.

3.1 Las dos fases de HPA*

Preprocesamiento (una vez por mapa):

1. Divide el mapa en clusters de tamaño fijo (típicamente 8×8 o 16×16).
2. Para cada par de clusters adyacentes, encuentra los portales — pares de celdas walkable en el borde.
3. Construye un grafo abstracto donde cada nodo es un portal y cada arista es el costo de moverse entre portales (vía A* dentro de cada cluster).

Query (por path):

1. Encuentra los portales más cercanos al start y al goal en sus respectivos clusters.
2. Corre A* sobre el grafo abstracto (mucho más pequeño): obtienes una secuencia de portales.
3. Para cada par de portales consecutivos, corre A* dentro del cluster correspondiente: obtienes el path concreto.

3.2 Cuánto gana

• Mapa 512×512 = 262144 nodos. HPA* con clusters 16×16 = 1024 clusters, ~4096 portales. La búsqueda abstracta es 60× más pequeña.
• En tiempo de query: 5–20× más rápido que A* directo, dependiendo del mapa.
• En memoria: paga preprocesamiento y guarda el grafo abstracto.

3.3 Cuándo NO

• Mapas dinámicos que cambian todo el tiempo (destrucción de muros, construcción): el preprocesamiento se invalida en cada cambio. Hay variantes incrementales pero son complejas.
• Mapas chiquitos (< 100×100): A* directo es más simple y rápido en absoluto.

3.4 Trade-off de calidad

El path de HPA* puede ser ligeramente subóptimo (típicamente 0–5% peor que el óptimo). Para juegos, eso casi nunca se nota.

4. Tabla comparativa

Algoritmo	Mejora	Cuándo	Dolor
A*	Baseline	Cualquier mapa con goal específico.	Lento en mapas enormes.
JPS	Velocidad 5–10×	Grids uniformes 8-conexos abiertos.	Solo grids uniformes.
Theta*	Paths suaves	Movimiento continuo del agente.	Más lento por iteración.
HPA*	Velocidad 10–20×	Mapas enormes (≥ 500×500).	Mapas estáticos, preprocesamiento.

Combinables: HPA* dentro de cada cluster puede usar JPS. JPS y Theta* no combinan directamente (Theta* necesita que cada celda esté en la frontera para hacer LOS).

5. Implementación en Unity / C#

Snippet de Theta* (la más simple de las tres optimizaciones). El asset trae las tres con sus tests.

using System.Collections.Generic;
using UnityEngine;

public static class ThetaStar {
    public static List<Vector2Int> Find(bool[,] walkable, Vector2Int start, Vector2Int goal) {
        int W = walkable.GetLength(0), H = walkable.GetLength(1), N = W * H;
        var gScore = new float[N];
        var parent = new int[N];
        for (int i = 0; i < N; i++) { gScore[i] = float.PositiveInfinity; parent[i] = -1; }
        int Idx(int x, int y) => y * W + x;
        int sIdx = Idx(start.x, start.y);
        gScore[sIdx] = 0;
        parent[sIdx] = sIdx;

        var pq = new PriorityQueue<int, float>();
        pq.Enqueue(sIdx, Heuristic(start, goal));
        var closed = new bool[N];

        var dirs = new (int dx, int dy)[] { (1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1) };

        while (pq.Count > 0) {
            int cur = pq.Dequeue();
            int cx = cur % W, cy = cur / W;
            if (cx == goal.x && cy == goal.y) return Reconstruct(parent, W, goal);
            if (closed[cur]) continue;
            closed[cur] = true;

            int parentOfCur = parent[cur];
            int px = parentOfCur % W, py = parentOfCur / W;

            foreach (var d in dirs) {
                int nx = cx + d.dx, ny = cy + d.dy;
                if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
                if (!walkable[nx, ny]) continue;
                int ni = Idx(nx, ny);
                if (closed[ni]) continue;

                float newG; int newP;
                if (parentOfCur != cur && HasLOS(walkable, new Vector2Int(px, py), new Vector2Int(nx, ny))) {
                    newG = gScore[parentOfCur] + Vector2.Distance(new Vector2(px, py), new Vector2(nx, ny));
                    newP = parentOfCur;
                } else {
                    float step = (d.dx != 0 && d.dy != 0) ? Mathf.Sqrt(2f) : 1f;
                    newG = gScore[cur] + step;
                    newP = cur;
                }
                if (newG < gScore[ni]) {
                    gScore[ni] = newG;
                    parent[ni] = newP;
                    pq.Enqueue(ni, newG + Heuristic(new Vector2Int(nx, ny), goal));
                }
            }
        }
        return null;
    }

    static float Heuristic(Vector2Int a, Vector2Int b) => Vector2.Distance(a, b);

    static bool HasLOS(bool[,] walkable, Vector2Int a, Vector2Int b) {
        int W = walkable.GetLength(0), H = walkable.GetLength(1);
        int x = a.x, y = a.y;
        int dx = Mathf.Abs(b.x - x), dy = Mathf.Abs(b.y - y);
        int sx = x < b.x ? 1 : -1, sy = y < b.y ? 1 : -1;
        int err = dx - dy;
        while (true) {
            if (x < 0 || y < 0 || x >= W || y >= H || !walkable[x, y]) return false;
            if (x == b.x && y == b.y) return true;
            int e2 = 2 * err;
            if (e2 > -dy) { err -= dy; x += sx; }
            if (e2 < dx) { err += dx; y += sy; }
        }
    }

    static List<Vector2Int> Reconstruct(int[] parent, int cols, Vector2Int goal) {
        var path = new List<Vector2Int>();
        int cur = goal.y * cols + goal.x;
        while (cur != -1) {
            path.Add(new Vector2Int(cur % cols, cur / cols));
            int p = parent[cur];
            if (p == cur) break;
            cur = p;
        }
        path.Reverse();
        return path;
    }
}

6. En otros engines

• Godot: AStarGrid2D no incluye JPS ni Theta* nativos. Para grandes mapas, lo más práctico es escribir tu propio JPS o usar plugins.
• Unreal: el FNavigationSystem usa NavMesh (no grid) por defecto, y aplica funnel para suavizar (equivalente conceptual a Theta* sobre mesh). Para gameplay con grids uniformes grandes, JPS lo escribes a mano.
• JavaScript / TypeScript: librerías como pathfinding-js traen JPS; Theta* y HPA* casi siempre los implementas a mano.

7. Quiz

Pon a prueba lo que entendiste

Responde una por una. La explicación aparece al elegir, correcta o no.

1. Tu juego es un RTS con mapas de 256x256, grid uniforme, 4-8 jugadores con cientos de unidades. ¿Qué optimización aplicas primero?

   • AJPS o JPS+. Grids uniformes y muchas búsquedas simultáneas son justo el caso ideal.
   • BTheta*. Producirá paths más naturales para las unidades.
   • CHPA*. Divide el mapa en clusters.

2. Tu unidad humana sobre grid 4-conexo se mueve y los players reportan que 'el path se ve raro'. ¿Qué cambias?

   • AA* + funnel post-process, o directamente Theta*. El path con esquinas duras se ve mecánico; suavizar lo arregla.
   • BSubir el peso de la heurística (weighted A*).
   • CCambiar a Dijkstra.

3. Tu mapa abierto de mundo tiene 4096x4096 celdas. A* directo tarda 200ms por path. ¿Qué optimización aplicar?

   • AHPA*. Divides el mapa en clusters (típico 32x32), preprocesas portales una vez al cargar el mapa, y el query corre 10-20x más rápido.
   • BJPS. Más rápido que A* en grids uniformes.
   • CReducir el grid a 256x256 perdiendo precisión.

4. Theta* hace un raycast por relajación. ¿Cuándo deja de valer la pena?

   • AEn mapas con muchísimas paredes y obstáculos densos: el raycast falla la mayoría de las veces, así que pagás el costo sin recibir el beneficio.
   • BEn mapas chiquitos: el overhead del raycast es fijo.
   • CNunca: Theta* siempre es mejor que A*.

5. ¿Qué tienen en común JPS, Theta* y HPA*?

   • ALos tres asumen un goal específico (one-to-one search). Para multi-target o flow fields, ninguno aplica directamente — usarías Dijkstra o flow field directo.
   • BLos tres son variantes de Dijkstra.
   • CLos tres garantizan path óptimo.

8. Siguientes pasos