Pathfinding a fondo
Este tutorial fue escrito en febrero de 2026, para la v2 del motor.
El tutorial de clic para mover construyó un sistema de navegación con BFS de 4 direcciones. Funciona, pero BFS es solo una herramienta del cajón. No puede hacer diagonales, trata todos los tiles igual y no tiene sentido de dirección — se expande hacia afuera hasta toparse con el destino. Según lo que tu juego necesite, hay mejores opciones.
Vamos a comparar cuatro algoritmos de pathfinding en la misma cuadrícula: BFS de 4 direcciones, BFS de 8 direcciones, el algoritmo de Dijkstra con terreno ponderado, y búsqueda A* con heurística. Mismos sprites, mismas paredes, mismo sistema de clic para mover. Lo único que cambia es cómo se encuentra el camino.
Configuración
Esta es la misma cuadrícula, sprites y sistema de movimiento libre del tutorial de clic para mover. Si algo te resulta desconocido, ve a leer ese primero — retomamos justo donde lo dejamos:
const sprites = {
floor: [[
3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 11, 3,
3, 3, 3, 3, 3, 3, 3, 3,
3, 11, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 11, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3,
], null],
wall: [[
5, 5, 5, 5, 5, 5, 5, 5,
5, 6, 5, 5, 5, 6, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 6, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 6, 5, 5, 5, 5, 6,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 6, 5, 5,
], null],
player: [[
-1, -1, 12, 12, 12, 12, -1, -1,
-1, 12, 12, 12, 12, 12, 12, -1,
-1, 12, 7, 12, 12, 7, 12, -1,
-1, 12, 12, 12, 12, 12, 12, -1,
-1, -1, 12, 12, 12, 12, -1, -1,
-1, -1, 12, 12, 12, 12, -1, -1,
-1, -1, 12, -1, -1, 12, -1, -1,
-1, -1, 12, -1, -1, 12, -1, -1,
], null],
};
// prettier-ignore
const grid = [
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,1,0,0,1,1,1,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1],
[1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1],
[1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,1,1,1,0,0,0,0,0,0,1,1,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
];
let playerPx = 12, playerPy = 12;
let targetX = -1, targetY = -1;
let path = [];
const speed = 1.5;
function findPath(sx, sy, gx, gy) {
if (mget(gx, gy, 0) === 'wall') return null;
const key = (x, y) => x + ',' + y;
const queue = [{ x: sx, y: sy }];
const visited = new Set([key(sx, sy)]);
const parent = {};
while (queue.length > 0) {
const { x, y } = queue.shift();
if (x === gx && y === gy) {
const result = [];
let cx = gx, cy = gy;
while (cx !== sx || cy !== sy) {
result.push({ x: cx, y: cy });
const p = parent[key(cx, cy)];
cx = p.x; cy = p.y;
}
return result.reverse();
}
for (const [dx, dy] of [[0, -1], [1, 0], [0, 1], [-1, 0]]) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue;
if (visited.has(key(nx, ny))) continue;
if (mget(nx, ny, 0) === 'wall') continue;
visited.add(key(nx, ny));
parent[key(nx, ny)] = { x, y };
queue.push({ x: nx, y: ny });
}
}
return null;
}
function init() {
cursor('crosshair');
for (let y = 0; y < 16; y++)
for (let x = 0; x < 16; x++)
mset(x, y, grid[y][x] === 1 ? 'wall' : 'floor');
}
function update() {
if (click()) {
const pos = mouse();
const gx = Math.max(0, Math.min(15, Math.floor(pos.x / 8)));
const gy = Math.max(0, Math.min(15, Math.floor(pos.y / 8)));
const sx = Math.floor(playerPx / 8);
const sy = Math.floor(playerPy / 8);
const result = findPath(sx, sy, gx, gy);
if (result) {
path = result;
targetX = gx;
targetY = gy;
}
}
if (path.length > 0) {
const tx = path[0].x * 8 + 4;
const ty = path[0].y * 8 + 4;
const dx = tx - playerPx;
const dy = ty - playerPy;
const dist = Math.sqrt(dx * dx + dy * dy);
if (dist < 1) {
playerPx = tx;
playerPy = ty;
path.shift();
} else {
playerPx += (dx / dist) * speed;
playerPy += (dy / dist) * speed;
}
}
}
function draw(time, frame) {
cls(0);
map(0);
for (const step of path)
circfill(step.x * 8 + 4, step.y * 8 + 4, 1, 9);
if (targetX >= 0) {
if (frame % 30 < 15)
rectfill(targetX * 8 + 2, targetY * 8 + 2, targetX * 8 + 5, targetY * 8 + 5, 10);
else
rect(targetX * 8, targetY * 8, targetX * 8 + 8, targetY * 8 + 8, 10);
}
spr('player', Math.floor(playerPx) - 4, Math.floor(playerPy) - 4);
}El jugador comienza en (1, 1) y se desliza hacia cada punto intermedio a 1.5 píxeles por frame. findPath() devuelve un array de pasos {x, y} — al código de movimiento no le importa cómo se encontró el camino. Esa es la idea clave: cada algoritmo que construyamos devuelve la misma forma, así que el sistema de movimiento nunca cambia. Solo cambia el pathfinding.
BFS de 4 direcciones
Aquí está la función findPath() de la configuración, extraída por separado. Esta es nuestra base — cada mejora parte de ella:
function findPath(sx, sy, gx, gy) {
if (mget(gx, gy, 0) === 'wall') return null;
const key = (x, y) => x + ',' + y;
const queue = [{ x: sx, y: sy }];
const visited = new Set([key(sx, sy)]);
const parent = {};
while (queue.length > 0) {
const { x, y } = queue.shift();
if (x === gx && y === gy) {
const result = [];
let cx = gx, cy = gy;
while (cx !== sx || cy !== sy) {
result.push({ x: cx, y: cy });
const p = parent[key(cx, cy)];
cx = p.x; cy = p.y;
}
return result.reverse();
}
for (const [dx, dy] of [[0, -1], [1, 0], [0, 1], [-1, 0]]) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue;
if (visited.has(key(nx, ny))) continue;
if (mget(nx, ny, 0) === 'wall') continue;
visited.add(key(nx, ny));
parent[key(nx, ny)] = { x, y };
queue.push({ x: nx, y: ny });
}
}
return null;
}BFS explora hacia afuera desde el inicio, un anillo a la vez. Cada celda recuerda de cuál celda vino. Al llegar al destino, rastreamos esos padres hacia atrás para construir el camino más corto. El array [[0,-1],[1,0],[0,1],[-1,0]] define cuatro direcciones cardinales — arriba, derecha, abajo, izquierda. Los caminos siempre van por los ejes de la cuadrícula, así que cada ruta termina siendo una escalera de segmentos horizontales y verticales.
La limitación es bastante obvia una vez que la ves: el jugador no puede cortar esquinas. Un destino a un tile al noreste toma dos pasos (uno a la derecha, uno arriba) en vez de una diagonal. Arreglemos eso.
BFS de 8 direcciones
Expandir a ocho direcciones significa agregar las cuatro diagonales — NE, SE, SO, NO — a la lista de vecinos. Pero hay un detalle. Sin una verificación de seguridad, el jugador puede colarse por huecos diagonales entre dos paredes que comparten una esquina. La solución: antes de permitir un movimiento diagonal, verificamos que ambas celdas cardinales adyacentes estén abiertas:
function findPath(sx, sy, gx, gy) {
if (mget(gx, gy, 0) === 'wall') return null;
const key = (x, y) => x + ',' + y;
const queue = [{ x: sx, y: sy }];
const visited = new Set([key(sx, sy)]);
const parent = {};
const dirs = [[0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1]];
while (queue.length > 0) {
const { x, y } = queue.shift();
if (x === gx && y === gy) {
const result = [];
let cx = gx, cy = gy;
while (cx !== sx || cy !== sy) {
result.push({ x: cx, y: cy });
const p = parent[key(cx, cy)];
cx = p.x; cy = p.y;
}
return result.reverse();
}
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue;
if (visited.has(key(nx, ny))) continue;
if (mget(nx, ny, 0) === 'wall') continue;
if (dx !== 0 && dy !== 0) {
if (mget(x + dx, y, 0) === 'wall') continue;
if (mget(x, y + dy, 0) === 'wall') continue;
}
visited.add(key(nx, ny));
parent[key(nx, ny)] = { x, y };
queue.push({ x: nx, y: ny });
}
}
return null;
}La verificación de corte de esquinas es el bloque if (dx !== 0 && dy !== 0). Si intentamos movernos al noreste, tanto la celda norte como la celda este deben estar abiertas. De lo contrario atravesaríamos una esquina de pared — imagina una pared en forma de L donde el jugador se desliza por la curva.
BFS trata todos los pasos como costo igual. Un paso diagonal en realidad cubre más terreno (unos 1.41 tiles) que un paso cardinal (1 tile), pero BFS los cuenta igual. Para cuadrículas sin peso esto produce caminos correctos en cantidad de pasos, pero no en distancia real. Las siguientes dos secciones abordan esto.
Algoritmo de Dijkstra
BFS trata cada paso igual. El algoritmo de Dijkstra no — rastrea el costo total para llegar a cada celda y siempre expande la más barata primero. Eso significa que podemos dar diferentes costos a distintos tipos de terreno. El barro es caro, el suelo es barato, y el camino rodea el barro cuando ir por el camino largo es realmente más rápido.
Añadimos un sprite marrón de barro y dispersamos algunas manchas de barro por la cuadrícula. El suelo cuesta 1, el barro cuesta 3. Los pasos diagonales multiplican el costo del terreno por 1.41 (la raíz cuadrada de 2) para compensar la distancia extra. La cola es un array ordenado — insertamos cada nueva entrada en la posición correcta por costo. En una cuadrícula de 16x16 esto es suficientemente rápido. Para mapas más grandes querrías un montículo binario:
function findPath(sx, sy, gx, gy) {
const tile = mget(gx, gy, 0);
if (tile === 'wall') return null;
const key = (x, y) => x + ',' + y;
const dirs = [[0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1]];
const cost = { floor: 1, mud: 3 };
const dist = {};
dist[key(sx, sy)] = 0;
const parent = {};
const queue = [{ x: sx, y: sy, d: 0 }];
while (queue.length > 0) {
const { x, y, d } = queue.shift();
if (x === gx && y === gy) {
const result = [];
let cx = gx, cy = gy;
while (cx !== sx || cy !== sy) {
result.push({ x: cx, y: cy });
const p = parent[key(cx, cy)];
cx = p.x; cy = p.y;
}
return result.reverse();
}
if (d > (dist[key(x, y)] ?? Infinity)) continue;
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue;
const nt = mget(nx, ny, 0);
if (nt === 'wall') continue;
if (dx !== 0 && dy !== 0) {
if (mget(x + dx, y, 0) === 'wall') continue;
if (mget(x, y + dy, 0) === 'wall') continue;
}
const moveCost = (dx !== 0 && dy !== 0) ? cost[nt] * 1.41 : cost[nt];
const nd = d + moveCost;
const nk = key(nx, ny);
if (nd < (dist[nk] ?? Infinity)) {
dist[nk] = nd;
parent[nk] = { x, y };
let i = 0;
while (i < queue.length && queue[i].d <= nd) i++;
queue.splice(i, 0, { x: nx, y: ny, d: nd });
}
}
}
return null;
}La cola de prioridad es el gran cambio. BFS usa una cola FIFO simple — primero en entrar, primero en salir. Dijkstra ordena por costo acumulado, así que los caminos baratos se exploran primero. La línea if (d > (dist[key(x, y)] ?? Infinity)) continue omite entradas obsoletas — si ya encontramos una ruta más barata a esta celda, no tiene sentido expandirla de nuevo.
Búsqueda A*
Dijkstra siempre expande la celda más barata, pero no tiene sentido de dirección. Busca hacia afuera como ondas en un estanque. A* añade una heurística — una estimación de qué tan lejos está cada celda del destino. Las celdas que parecen más cercanas se exploran primero. Terminamos con el mismo camino óptimo, pero A* examina muchas menos celdas en el proceso.
Para movimiento en 8 direcciones, la heurística correcta es la distancia octil: max(dx, dy) + (sqrt(2) - 1) * min(dx, dy). Tiene en cuenta que los pasos diagonales cuestan más que los cardinales. La cola de prioridad ordena por f = g + h, donde g es el costo hasta ahora y h es la estimación heurística:
function findPath(sx, sy, gx, gy) {
const tile = mget(gx, gy, 0);
if (tile === 'wall') return null;
const key = (x, y) => x + ',' + y;
const dirs = [[0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1]];
const cost = { floor: 1, mud: 3 };
function heuristic(x, y) {
const dx = Math.abs(x - gx), dy = Math.abs(y - gy);
return Math.max(dx, dy) + (Math.SQRT2 - 1) * Math.min(dx, dy);
}
const g = {};
g[key(sx, sy)] = 0;
const parent = {};
const explored = new Set();
const queue = [{ x: sx, y: sy, f: heuristic(sx, sy) }];
while (queue.length > 0) {
const { x, y } = queue.shift();
const k = key(x, y);
if (explored.has(k)) continue;
explored.add(k);
if (x === gx && y === gy) {
const result = [];
let cx = gx, cy = gy;
while (cx !== sx || cy !== sy) {
result.push({ x: cx, y: cy });
const p = parent[key(cx, cy)];
cx = p.x; cy = p.y;
}
return { path: result.reverse(), explored };
}
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue;
const nt = mget(nx, ny, 0);
if (nt === 'wall') continue;
if (dx !== 0 && dy !== 0) {
if (mget(x + dx, y, 0) === 'wall') continue;
if (mget(x, y + dy, 0) === 'wall') continue;
}
const moveCost = (dx !== 0 && dy !== 0) ? cost[nt] * 1.41 : cost[nt];
const ng = (g[k] ?? Infinity) + moveCost;
const nk = key(nx, ny);
if (ng < (g[nk] ?? Infinity)) {
g[nk] = ng;
parent[nk] = { x, y };
const f = ng + heuristic(nx, ny);
let i = 0;
while (i < queue.length && queue[i].f <= f) i++;
queue.splice(i, 0, { x: nx, y: ny, f });
}
}
}
return null;
}Los puntos rojos son celdas exploradas — cada celda que el algoritmo tuvo que examinar antes de encontrar el camino. Compara esto con Dijkstra en la misma ruta y verás que A* típicamente explora una fracción de las celdas. El ahorro se vuelve más dramático en mapas más grandes.
Esta versión devuelve { path, explored } en vez de solo el camino. El conjunto de explorados es solo para visualización — en un juego real lo quitarías y devolverías el camino directamente.
A* solo encuentra el camino óptimo cuando la heurística es optimista — debe estimar igual o menos que el costo real, nunca más. Si la heurística sobreestima, A* podría saltarse rutas más baratas y devolver un camino subóptimo. La distancia octil funciona aquí porque nuestro terreno más barato (suelo) cuesta 1 por paso, coincidiendo con la suposición de la heurística. Si tu terreno más barato costara menos de 1, necesitarías escalar la heurística hacia abajo para que nunca estime de más.
Juntando todo
Aquí están los cuatro algoritmos en una sola demo. Presiona 1 a 4 para cambiar entre ellos. Cada clic ejecuta los cuatro para que el HUD pueda mostrar estadísticas comparativas — longitud del camino y cantidad de celdas exploradas — pero solo se dibujan el camino y el área de búsqueda del algoritmo activo:
const algorithms = ['BFS 4-dir', 'BFS 8-dir', 'Dijkstra', 'A*'];
let active = 0;
let results = [];
// inside update()
for (let i = 0; i < 4; i++) {
if (btnp(String(i + 1)) && active !== i) {
active = i;
path = results[active]?.path ?? [];
}
}
if (click()) {
// run all four algorithms, display the active one
results = [
findPathBfs4(sx, sy, gx, gy),
findPathBfs8(sx, sy, gx, gy),
findPathDijkstra(sx, sy, gx, gy),
findPathAStar(sx, sy, gx, gy),
];
path = results[active]?.path ?? [];
}
// inside draw()
const r = results[active];
if (r) {
for (const k of r.explored) {
const [ex, ey] = k.split(',').map(Number);
rectfill(ex * 8 + 2, ey * 8 + 2, ex * 8 + 5, ey * 8 + 5, 8);
}
}
text(algorithms[active] + ' [' + (active + 1) + ']', 1, 1, 7);
if (r) text('path:' + r.path.length + ' explored:' + r.explored.size, 1, 8, 7);Intenta hacer clic en el mismo destino con cada algoritmo. BFS 4-dir produce los caminos más largos (sin diagonales). BFS 8-dir toma atajos pero ignora el costo del terreno. Dijkstra encuentra el camino verdaderamente más barato a través del terreno ponderado. A* encuentra el mismo camino que Dijkstra pero explora menos celdas para llegar. La elección correcta depende de lo que le importa a tu juego — simplicidad, precisión o rendimiento. Tómate un tiempo para experimentar con diferentes posiciones de inicio y destino para sentir cómo se comporta cada uno.
Para seguir explorando
- Jump Point Search — una optimización para cuadrículas de costo uniforme que salta grandes extensiones de espacio abierto. Más rápido que A* en mapas con grandes áreas abiertas.
- Campos de flujo — en vez de un camino por unidad, calcula un mapa de direcciones desde cada celda hacia el destino. Eficiente cuando muchas unidades buscan camino al mismo objetivo (juegos de estrategia, tower defense).
- Pathfinding jerárquico — divide el mapa en clusters, busca camino entre clusters primero, luego dentro de cada cluster. Escala a mundos enormes donde A* completo sería demasiado lento.
- Obstáculos dinámicos — recalcula caminos cuando el mapa cambia. Replanificar parcialmente desde la celda bloqueada es más rápido que volver a ejecutar desde cero.
- Theta* — pathfinding de ángulo libre que produce caminos más suaves que A* restringido a la cuadrícula, permitiendo atajos por línea de visión entre celdas no adyacentes.