Pathfinding visual con BFS, Dijkstra y A*

Pathfinding no consiste en encontrar una ruta cualquiera. Consiste en encontrar una ruta que respete el mapa y optimice la medida correcta: pasos, costo, tiempo, riesgo o una combinación de ellos.

BFS, Dijkstra y A* comparten gran parte del mecanismo. Los tres mantienen una frontera de estados pendientes y un registro para reconstruir el camino. Lo que cambia es qué estado sale primero de la frontera.

Antes de elegir el algoritmo, define movimientos, costos y la garantía que convierte una ruta en correcta.

01. Antes del algoritmo: convertir el mapa en un grafo

En una grilla, cada celda transitable es un vértice y cada movimiento permitido es una arista. Con cuatro direcciones, una celda puede conectarse arriba, abajo, a la izquierda y a la derecha. Si agregas diagonales, cambian las aristas, el costo y la heurística válida.

Conversión visual de una grilla en nodos y aristas de un grafo

type Point = { x: number; y: number };

type Cell = {
  walkable: boolean;
  weight: number;
};

const directions = [
  { x: 1, y: 0 },
  { x: -1, y: 0 },
  { x: 0, y: 1 },
  { x: 0, y: -1 },
];

function key({ x, y }: Point) {
  return `${x},${y}`;
}

function neighbors(point: Point, grid: Cell[][]) {
  return directions
    .map(({ x, y }) => ({ x: point.x + x, y: point.y + y }))
    .filter((next) => grid[next.y]?.[next.x]?.walkable);
}

El contrato del mapa debe responder cuatro preguntas:

1. ¿Qué movimientos están permitidos?
2. ¿El costo pertenece a la celda de destino o a la arista?
3. ¿Se puede cortar una esquina bloqueada al mover en diagonal?
4. ¿Todos los pesos son no negativos?

En una grilla de V celdas y cuatro vecinos, hay como máximo un número constante de aristas por celda; por eso E crece como V. Aun así, conviene hablar de O(V + E) porque el mismo razonamiento sirve para grafos que no son grillas.

02. Una frontera, tres criterios de prioridad

Los tres algoritmos descubren vecinos, registran el mejor padre conocido y repiten hasta extraer el objetivo o agotar la frontera.

Comparación de las fronteras de BFS, Dijkstra y A* sobre el mismo mapa

La notación de A* separa lo conocido de lo estimado:

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

g(n): costo real desde el inicio
h(n): estimación restante hasta el objetivo

BFS recorre O(V + E). Dijkstra con un binary min-heap cuesta habitualmente O((V + E) log V). A* conserva ese peor caso general, aunque una buena heurística puede reducir mucho la cantidad de estados expandidos.

Esa última distinción importa en un laboratorio: la complejidad teórica no cambia, pero la frontera visible puede pasar de cubrir casi todo el mapa a formar un corredor hacia el objetivo.

03. BFS: la opción correcta para costo uniforme

BFS explora por capas. Marcar una celda al encolarla evita duplicados, y un índice head permite usar el array como queue sin pagar los desplazamientos de shift().

function bfs(start: Point, goal: Point, grid: Cell[][]) {
  const queue = [start];
  const parent = new Map<string, Point | null>([[key(start), null]]);

  for (let head = 0; head < queue.length; head += 1) {
    const current = queue[head];
    if (key(current) === key(goal)) break;

    for (const next of neighbors(current, grid)) {
      const nextKey = key(next);
      if (parent.has(nextKey)) continue;

      parent.set(nextKey, current);
      queue.push(next);
    }
  }

  return parent;
}

BFS garantiza el camino con menos movimientos cuando cada movimiento tiene el mismo costo. Si hierba, agua y carretera tienen pesos distintos, contar pasos deja de representar el objetivo y necesitas Dijkstra o A*.

Su patrón visual es una ola. Esa expansión amplia no es un defecto: es el precio de no tener información que favorezca una dirección.

04. Dijkstra y A*: el mismo motor, otra prioridad

Dijkstra y A* usan la misma relajación: si una nueva ruta llega a un vecino con menor costo, actualizan su distancia, su padre y su entrada en la frontera. La diferencia está en la prioridad.

type FrontierItem = {
  point: Point;
  cost: number;
  priority: number;
};

function weightedSearch(
  start: Point,
  goal: Point,
  grid: Cell[][],
  heuristic: (point: Point, goal: Point) => number,
) {
  const frontier = new MinPriorityQueue<FrontierItem>(
    (item) => item.priority,
  );
  frontier.push({ point: start, cost: 0, priority: 0 });

  const cost = new Map<string, number>([[key(start), 0]]);
  const parent = new Map<string, Point | null>([[key(start), null]]);

  while (!frontier.isEmpty()) {
    const current = frontier.pop();
    if (current.cost !== cost.get(key(current.point))) continue;
    if (key(current.point) === key(goal)) break;

    for (const next of neighbors(current.point, grid)) {
      const nextCost = current.cost + grid[next.y][next.x].weight;
      const knownCost = cost.get(key(next));

      if (knownCost === undefined || nextCost < knownCost) {
        cost.set(key(next), nextCost);
        parent.set(key(next), current.point);
        frontier.push({
          point: next,
          cost: nextCost,
          priority: nextCost + heuristic(next, goal),
        });
      }
    }
  }

  return { parent, cost };
}

El ejemplo supone una MinPriorityQueue implementada con binary heap. Usar sort() en cada iteración es útil para una demostración mínima, pero oculta el costo real y no representa una implementación de producción.

Con heuristic = () => 0, el motor es Dijkstra. Con una estimación válida hacia el objetivo, es A*. La comprobación de entradas obsoletas evita expandir una prioridad antigua después de encontrar una ruta mejor.

El objetivo debe finalizar la búsqueda cuando sale de la priority queue como mejor estado pendiente, no cuando se descubre por primera vez.

05. Heurísticas honestas y rutas reconstruibles

Una heurística admisible nunca sobrestima el costo restante. En una grilla ponderada debe escalarse por el menor costo de paso posible; de lo contrario, una distancia geométrica puede prometer menos o más de lo que permiten las reglas.

Descomposición visual de la prioridad de A* en costo acumulado y estimación

La heurística afecta el orden de exploración, no el costo real guardado en g(n). Si sobrestima, A* puede ser más agresivo, pero pierde la garantía de optimalidad.

La ruta final se reconstruye siguiendo padres desde el objetivo. Primero hay que comprobar que el objetivo fue alcanzado:

function reconstructPath(
  parent: Map<string, Point | null>,
  start: Point,
  goal: Point,
) {
  if (!parent.has(key(goal))) return [];

  const path: Point[] = [];
  let current: Point | null = goal;

  while (current) {
    path.push(current);
    if (key(current) === key(start)) break;
    current = parent.get(key(current)) ?? null;
  }

  return path.reverse();
}

Separar visualmente visitados, frontera y ruta final evita una confusión frecuente: explorar una celda no significa que esa celda pertenezca al camino elegido.

Estados de búsqueda y reconstrucción de la ruta desde el objetivo al inicio

06. Cómo elegir y qué debe medir el experimento

El laboratorio debe ejecutar los tres algoritmos sobre el mismo mapa y mostrar al menos:

• nodos expandidos;
• tamaño máximo de la frontera;
• costo y longitud de la ruta final;
• tiempo de cálculo separado de la animación;
• estado sin ruta cuando el objetivo es inalcanzable.

También debe bloquear comparaciones injustas. BFS no puede competir por costo si ignora pesos, y A* no debe recibir una heurística incompatible con los movimientos. Para mapas que cambian en pequeñas regiones, algoritmos incrementales como LPA* o D* Lite pueden evitar recalcular desde cero.

La decisión práctica queda así: BFS minimiza pasos uniformes; Dijkstra minimiza costo real; A* busca el mismo óptimo usando información adicional para orientar la frontera. El mapa define el problema, la prioridad define la exploración y el registro de padres convierte esa exploración en una ruta.