Si pones h(n) = 0 para todo n, ¿qué obtienes?

Dijkstra. A* con heurística cero degenera en Dijkstra: la PQ se ordena solo por gScore, sin sesgo hacia el goal. Es exactamente la relación. Dijkstra es A* con h=0. Esa observación deja claro qué aporta la heurística: dirección hacia el goal.

Tu grid permite movimiento en 4 direcciones a costo 1. ¿Qué heurística da el menor número de nodos explorados sin perder optimalidad?

Manhattan. Es la distancia exacta para grid 4-conexo, así que es admisible y maximamente informada simultáneamente. Manhattan = |dx|+|dy| coincide con el costo real cuando no hay obstáculos. Más informada, menos exploración. Euclidiana es admisible pero subestima (siempre <= Manhattan), así que explora más.

Multiplicas la heurística por 2 (weighted A*). ¿Qué pasa?

La búsqueda es más rápida porque A* prioriza más fuertemente nodos cerca del goal, pero el path encontrado puede ser subóptimo (a lo sumo 2x peor que el óptimo). Es el trade-off clásico de weighted A*. Garantía de optimalidad se pierde, pero ganás velocidad. Para action games donde el path se recalcula constantemente, vale la pena.

Un mapa de 200x200 con 80% de espacio libre. ¿Qué algoritmo es típicamente más rápido?

A* con heurística admisible bien elegida. Explora una 'gota' dirigida al goal en vez del círculo completo de Dijkstra. Para one-to-one search en mapa grande, A* gana ampliamente. La diferencia se nota mucho con goal específico y mapa con espacio abierto. JPS lo bate sobre grids uniformes pero A* es la opción default.

Tu mapa tiene 50% de muros distribuidos aleatoriamente. ¿Cómo cambia el comportamiento de A*?

La heurística sigue siendo admisible, pero pierde precisión: subestima mucho porque no sabe de los muros. A* explora más nodos que en mapa abierto, pero sigue siendo correcto. La heurística asume distancia 'libre'. Cuando hay obstáculos, el costo real es mayor que h. Sigue siendo admisible (h <= real) y A* sigue siendo óptimo, pero la ventaja sobre Dijkstra se reduce.

A*: el estándar del pathfinding en juegos

Q: Multiplicas la heurística por 2 (weighted A*). ¿Qué pasa?

La búsqueda es más rápida porque A* prioriza más fuertemente nodos cerca del goal, pero el path encontrado puede ser subóptimo (a lo sumo 2x peor que el óptimo). Es el trade-off clásico de weighted A*. Garantía de optimalidad se pierde, pero ganás velocidad. Para action games donde el path se recalcula constantemente, vale la pena.

Q: Un mapa de 200x200 con 80% de espacio libre. ¿Qué algoritmo es típicamente más rápido?

A* con heurística admisible bien elegida. Explora una 'gota' dirigida al goal en vez del círculo completo de Dijkstra. Para one-to-one search en mapa grande, A* gana ampliamente. La diferencia se nota mucho con goal específico y mapa con espacio abierto. JPS lo bate sobre grids uniformes pero A* es la opción default.

Q: Tu mapa tiene 50% de muros distribuidos aleatoriamente. ¿Cómo cambia el comportamiento de A*?

La heurística sigue siendo admisible, pero pierde precisión: subestima mucho porque no sabe de los muros. A* explora más nodos que en mapa abierto, pero sigue siendo correcto. La heurística asume distancia 'libre'. Cuando hay obstáculos, el costo real es mayor que h. Sigue siendo admisible (h <= real) y A* sigue siendo óptimo, pero la ventaja sobre Dijkstra se reduce.

0. Introducción

A* (1968, Hart-Nilsson-Raphael) es el algoritmo de pathfinding por defecto en videojuegos. Age of Empires, Baldur’s Gate, prácticamente todo RTS, todo tactical, todo grid-based moderno. Es Dijkstra con un agregado: una heurística que estima cuán cerca está cada nodo del goal.

Esa heurística sesga la búsqueda hacia el destino. En vez de explorar en círculo (Dijkstra), A* prioriza nodos que parecen prometedores. En mapas grandes, eso significa explorar 5–20× menos celdas para llegar al mismo camino óptimo.

La fórmula que lo define

A* prioriza por:

f(n) = g(n) + h(n)

g(n) — costo real desde el origen hasta n. Es el mismo gScore de Dijkstra.
h(n) — estimación heurística del costo desde n hasta el goal. No lo conoces realmente; es una conjetura informada.
f(n) — suma. La PQ de A* extrae el nodo con menor f, que combina “cuánto te costó llegar” con “cuánto te falta”.

La elección de h es la decisión de diseño más importante de A*. Ahí entra el concepto de admisibilidad.

¿Cuándo usar A*?

Tienes un goal específico conocido (one-to-one search). Si necesitas multi-target, Dijkstra puede ser más simple.
El mapa es grande y la velocidad importa.
Puedes calcular una heurística razonable (en un grid, es trivial).

¿Cuándo NO?

Multi-target o flow fields → Dijkstra o flow field directo.
Mapas chiquitos (< 30×30): A* y Dijkstra terminan tan rápido que no se nota la diferencia. Usa lo que ya tengas.
Heurística difícil de calcular o impredecible (ej: navegación por grafos abstractos donde la distancia “real” no se puede estimar): A* sin heurística buena = Dijkstra disfrazado.

1. A* en acción

Click para alternar muros, Shift+click mueve el origen, Alt+click mueve el destino. La frontera de A* se colorea por f-cost (g+h); el verde es el camino reconstruido. Compara con la cantidad explorada vs Dijkstra: A* explora mucho menos.

velocidad200

Figura 1 — Click para muros, Shift+click mueve el origen, Alt+click mueve el destino. La frontera se colorea por f-cost: azul es f bajo (prometedor), rojo es f alto (alejándose).

Notarás que A* “apunta” al goal: la mancha de exploración tiene forma de gota orientada hacia el destino, no de círculo como Dijkstra.

1.1 El bucle, casi idéntico a Dijkstra

function astar(grid, start, goal, h)
    gScore = Map.fillWith(Infinity)
    fScore = Map.fillWith(Infinity)
    gScore[start] = 0
    fScore[start] = h(start, goal)
    parent = Map()
    pq = MinPriorityQueue()                # ordenada por fScore
    pq.push(start, fScore[start])

    while pq not empty
        current = pq.popMin()
        if current == goal:
            return reconstructPath(parent, goal)

        for each neighbor of walkableNeighbors(current)
            tentative_g = gScore[current] + cost(neighbor)
            if tentative_g < gScore[neighbor]
                gScore[neighbor] = tentative_g
                fScore[neighbor] = tentative_g + h(neighbor, goal)
                parent[neighbor] = current
                pq.push(neighbor, fScore[neighbor])

Diferencias mínimas con Dijkstra:

La PQ se ordena por fScore, no por gScore.
Al actualizar un vecino, calculas f = g + h y eso es lo que va a la PQ.

Si h(n) = 0 para todo n, A* es Dijkstra. La heurística es lo que añade el sesgo.

2. La elección de heurística

Las cuatro heurísticas más comunes sobre el mismo mapa: Manhattan suma diferencias en x e y (4-conexo), Euclidiana usa distancia recta, Chebyshev y Octile permiten diagonales (8-conexo). El número junto al nombre cuenta cuántos nodos exploró cada una; con mejor heurística, A* explora menos.

Figura 2 — Cuatro paneles A sobre el mismo mapa. Cada uno usa una heurística distinta y reporta cuántos nodos exploró. Heurística más informada = menos exploración, siempre que sea admisible.*

2.1 Las cuatro heurísticas comunes

Heurística	Fórmula	Cuándo
Manhattan	`\|dx\| + \|dy\|`	Grid 4-conexo (sin diagonales). Es la exacta distancia mínima si no permites diagonales.
Euclidiana	`√(dx² + dy²)`	Movimiento libre en ángulos arbitrarios. Subestima en grid 4-conexo (sigue siendo admisible).
Chebyshev	`max(\|dx\|, \|dy\|)`	Grid 8-conexo donde diagonal cuesta lo mismo que ortogonal. Distancia exacta de rey en ajedrez.
Octile	`max(dx,dy) + (√2 − 1)·min(dx,dy)`	Grid 8-conexo donde diagonal cuesta √2 (más realista). Distancia exacta.

Regla rápida: usa la heurística que sea exacta para el costo de movimiento de tu grid. Si tu agente puede moverse en 4 direcciones a costo 1, Manhattan. Si puede hacer diagonales a costo √2, Octile. Si en cualquier diagonal cuesta 1, Chebyshev.

2.2 Admisibilidad — la regla de oro

Una heurística es admisible si nunca sobreestima el costo real al goal:

Para todo nodo n: h(n) ≤ costo_real(n, goal)

Si h es admisible, A* garantiza el camino óptimo. Si h sobreestima, A* puede encontrar un camino más rápido pero no necesariamente óptimo.

El slider multiplica la heurística por un factor. Con factor = 1 A* es óptimo (el camino es verde). Subir el factor (heurística inadmisible / "weighted A\*") hace la búsqueda más rápida pero el camino encontrado puede ser subóptimo (camino rojo). Hay un trade-off: velocidad por calidad.

peso heurístico1.00

Figura 3 — El slider multiplica la heurística por un factor. Con factor = 1, A* es admisible y el path es verde (óptimo). Subir el factor (weighted A*) hace la búsqueda más rápida pero puede dar un path subóptimo (rojo).

2.3 Weighted A* — comprar velocidad con calidad

A veces te conformas con un camino “casi óptimo” si A* corre 3× más rápido. La técnica clásica es multiplicar la heurística por un peso w > 1:

fScore[n] = gScore[n] + w * h(n, goal)

w = 1 → A* clásico, camino óptimo.
w = 1.5 → camino a lo sumo 50% peor que el óptimo, búsqueda mucho más rápida.
w = ∞ → puro greedy best-first, ignora g por completo. Muy rápido, pero el camino puede ser horrible.

Es trade-off de calidad vs velocidad. Para juegos action donde el agente recalcula path 10 veces por segundo, w = 1.5–2 suele ser ideal: nadie nota un path 30% más largo en una persecución.

3. A* vs Dijkstra — la prueba dura

Mismo mapa, mismo destino. Dijkstra explora en círculo (sin saber hacia dónde va); A* sesga la búsqueda hacia el goal y explora mucho menos. La proporción aparece abajo.

A* explora 0% de lo que explora Dijkstra.

velocidad180

Figura 4 — Mismo mapa, mismo goal. Dijkstra explora “en círculo” porque no sabe a dónde va. A* “apunta” al goal y explora una gota dirigida. La proporción de nodos explorados aparece debajo.

En mapas abiertos sin obstáculos, A* explora típicamente 10–20% de lo que explora Dijkstra. En mapas con muchos obstáculos esa ventaja se reduce porque la heurística engaña — A* sigue siendo correcto, pero la heurística “miente” sobre el costo real porque no sabe de obstáculos.

3.1 Optimizaciones obvias

Tie-breaking — cuando dos nodos tienen igual fScore, prefieres el de menor h (más cerca del goal). Reduce ramificaciones simétricas.
closed set — marca nodos ya extraídos. No los procesas de nuevo aunque aparezcan en la PQ con f menor (puede pasar si la PQ no soporta decrease-key).
Buckets en lugar de PQ — si los costos son enteros pequeños, una pq de buckets (Bucket[fScore]) es O(1) por operación. Factorio lo hace así.

3.2 Cuándo A* deja de ser ideal

JPS sobre grids uniformes 8-conexos: 10× más rápido que A*. Lo verás en Pathfinding avanzado.
Theta* cuando los paths con esquinas duras se ven feos: añade line-of-sight checks y produce paths suavizados.
HPA* para mapas enormes (10000×10000): jerarquía de clusters.
NavMesh poligonal en vez de grid: A* sobre triángulos. Lo verás en A* sobre NavMesh.

4. Pseudocódigo completo

function astar(grid, start, goal, heuristic)
    closedSet = Set()
    gScore = Map.fillWith(Infinity)
    fScore = Map.fillWith(Infinity)
    parent = Map()

    gScore[start] = 0
    fScore[start] = heuristic(start, goal)
    pq = MinPriorityQueue()
    pq.push(start, fScore[start])

    while pq not empty
        current = pq.popMin()
        if current == goal:
            return reconstructPath(parent, goal)
        if current in closedSet: continue
        closedSet.add(current)

        for each neighbor of walkableNeighbors(current)
            if neighbor in closedSet: continue
            tentative_g = gScore[current] + stepCost(current, neighbor)
            if tentative_g < gScore[neighbor]
                parent[neighbor] = current
                gScore[neighbor] = tentative_g
                fScore[neighbor] = tentative_g + heuristic(neighbor, goal)
                pq.push(neighbor, fScore[neighbor])

    return null    // unreachable

5. Implementación en Unity / C#

using System;
using System.Collections.Generic;
using UnityEngine;

public static class AStar {
    public delegate float Heuristic(Vector2Int a, Vector2Int b);

    public static readonly Heuristic Manhattan = (a, b) => Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
    public static readonly Heuristic Euclidean = (a, b) => Vector2Int.Distance(a, b);
    public static readonly Heuristic Octile = (a, b) => {
        int dx = Mathf.Abs(a.x - b.x), dy = Mathf.Abs(a.y - b.y);
        const float F = 0.41421356f; // sqrt(2) - 1
        return Mathf.Max(dx, dy) + F * Mathf.Min(dx, dy);
    };

    static readonly Vector2Int[] Dirs = {
        new(1, 0), new(-1, 0), new(0, 1), new(0, -1),
    };

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

        int Idx(Vector2Int c) => c.y * W + c.x;
        int sIdx = Idx(start);
        gScore[sIdx] = 0;
        fScore[sIdx] = h(start, goal);

        // .NET 6+: PriorityQueue<int, float>
        var pq = new PriorityQueue<int, float>();
        pq.Enqueue(sIdx, fScore[sIdx]);
        var closed = new bool[N];

        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;

            foreach (var d in Dirs) {
                int nx = cx + d.x, ny = cy + d.y;
                if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
                if (!walkable[nx, ny]) continue;
                int ni = ny * W + nx;
                if (closed[ni]) continue;

                float tentative = gScore[cur] + 1f;
                if (tentative < gScore[ni]) {
                    parent[ni] = cur;
                    gScore[ni] = tentative;
                    fScore[ni] = tentative + h(new Vector2Int(nx, ny), goal);
                    pq.Enqueue(ni, fScore[ni]);
                }
            }
        }
        return null;
    }

    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));
            cur = parent[cur];
        }
        path.Reverse();
        return path;
    }
}

6. En otros engines

Godot: AStarGrid2D y AStar2D traen A* completo, con heurísticas configurables por callback. Cuesta cero usarlos en gameplay grid-based.
Unreal: FNavigationSystem usa A* sobre NavMesh internamente. Para grid manual, TArray + min-heap manual o usar plugins como NavGrid.
JavaScript / TypeScript: la lib del sitio implementa A* con heurística pluggable como generador para que las visualizaciones puedan animar paso a paso.

7. Quiz

Pon a prueba lo que entendiste

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

Si pones h(n) = 0 para todo n, ¿qué obtienes?
Tu grid permite movimiento en 4 direcciones a costo 1. ¿Qué heurística da el menor número de nodos explorados sin perder optimalidad?
Multiplicas la heurística por 2 (weighted A*). ¿Qué pasa?
Un mapa de 200x200 con 80% de espacio libre. ¿Qué algoritmo es típicamente más rápido?
Tu mapa tiene 50% de muros distribuidos aleatoriamente. ¿Cómo cambia el comportamiento de A*?