— Amit Patel, Red Blob Games, blog de referencia de la industria.
En cualquier juego con enemigos que persiguen al jugador hay un problema común: dado un mapa (típicamente un tilemap), encuentra la ruta más corta de A a B. La solución estándar desde 1968 es A\* (A-estrella, pronunciado "A-star"), un algoritmo de búsqueda en grafo que combina coste real (lo que llevas recorrido) con heurística (lo que te queda por recorrer). La fórmula canónica:
f(n) = g(n) + h(n)donde:
g(n) = coste real desde el origen hasta el nodo n.h(n) = estimación heurística desde n hasta el destino.f(n) = prioridad total del nodo en la cola.La gracia de A es que si h es admisible (nunca sobreestima el coste real), A devuelve la ruta óptima. Si h es consistente (cumple la desigualdad triangular), A* además encuentra la primera vez que visita cada nodo y no necesita re-expandir.
Una analogía culinaria: A* es como cocinar siguiendo una receta con dos cronómetros, uno para "lo que llevo" y otro para "lo que falta". Si los dos están bien calibrados, llegas al plato perfecto en el mínimo tiempo.
función A_estrella(grafo, inicio, destino, heurística):
abiertos = cola_prioridad()
cerrados = conjunto()
g_score = mapa() // g(n): coste real.
f_score = mapa() // f(n) = g(n) + h(n).
padres = mapa() // para reconstruir el camino.
g_score[inicio] = 0
f_score[inicio] = heurística(inicio, destino)
abiertos.push(inicio, f_score[inicio])
mientras abiertos no esté vacío:
actual = abiertos.pop_mínimo()
si actual == destino:
return reconstruir(padres, actual)
cerrados.insertar(actual)
para cada vecino de actual:
si vecino en cerrados: continue
tentative_g = g_score[actual] + coste(actual, vecino)
si tentative_g < g_score.get(vecino, infinito):
padres[vecino] = actual
g_score[vecino] = tentative_g
f_score[vecino] = tentative_g + heurística(vecino, destino)
abiertos.push(vecino, f_score[vecino])
return failureLos dos detalles clave:
decrease_key (actualizar la prioridad de un nodo ya insertado). En Rust, un BinaryHeap estándar no lo soporta, así que se simula insertando duplicados y descartándolos al pop.HashSet<(i32, i32)> o un HashMap<(i32, i32), NodeId> cumple el rol.Aviso: implementación didáctica simplificada. El código siguiente omite el
closed_set(conjunto de nodos ya expandidos) y se apoya sólo en el chequeotentative_g < g.get(next)para descartar re-procesado. Eso la hace asintóticamente subóptima: en grafos grandes o con heurística poco ajustada, un mismo nodo puede entrar varias veces en la open list y volver a expandirse. Para un prototipo o un mapa pequeño (< 1 000 nodos) no se nota; para producción, añade unHashSet<GridPos>de cerrados y salta (continue) cualquier nodo que ya esté dentro al hacerpop. Esa es la forma "de libro de texto" que garaniza O((V+E) log V). Mantenemos la versión simplificada porque ilustra mejor la idea central (g + h + parent map) sin la ceremonia del set extra.
// cap-22 — sección 22.3: A* sobre grid.
use std::collections::{BinaryHeap, HashMap, HashSet};
use bevy::prelude::*;
#[derive(Eq, PartialEq, Hash, Clone, Copy, Debug)]
pub struct GridPos(pub i32, pub i32);
#[derive(Eq, PartialEq)]
struct OpenEntry {
f: i32,
pos: GridPos,
}
impl Ord for OpenEntry {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other.f.cmp(&self.f) // min-heap.
}
}
impl PartialOrd for OpenEntry {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { Some(self.cmp(other)) }
}
pub fn a_star<F>(
start: GridPos,
goal: GridPos,
mut neighbours: F,
mut heuristic: impl FnMut(GridPos) -> i32,
) -> Option<Vec<GridPos>>
where
F: FnMut(GridPos) -> Vec<(GridPos, i32)>,
{
let mut open: BinaryHeap<OpenEntry> = BinaryHeap::new();
let mut g: HashMap<GridPos, i32> = HashMap::new();
let mut came_from: HashMap<GridPos, GridPos> = HashMap::new();
g.insert(start, 0);
open.push(OpenEntry { f: heuristic(start), pos: start });
while let Some(OpenEntry { pos: current, .. }) = open.pop() {
if current == goal {
let mut path = vec![current];
while let Some(prev) = came_from.get(&path.last().copied().unwrap()) {
path.push(*prev);
}
path.reverse();
return Some(path);
}
for (next, cost) in neighbours(current) {
let tentative_g = g[¤t] + cost;
if tentative_g < *g.get(&next).unwrap_or(&i32::MAX) {
g.insert(next, tentative_g);
came_from.insert(next, current);
open.push(OpenEntry { f: tentative_g + heuristic(next), pos: next });
}
}
}
None
}El closure neighbours te permite customizar la topología: en un grid ortogonal son las 4 u 8 casillas vecinas con coste 10 (ortogonal) o 14 (diagonal, √2 × 10); en un navmesh son los polígonos conectados.
La heurística es lo que diferencia un A* "tonto" (que explora todo el mapa) de uno eficiente.
h = |dx| + |dy|. Admisible si no hay costes distintos de 1.h = (|dx| + |dy|) + (√2 - 2) × min(|dx|, |dy|). Más ajustada, expande menos nodos.h = √(dx² + dy²). Admisible siempre; útil en mapas abiertos.h = max(|dx|, |dy|). Admisible sólo si las diagonales cuestan lo mismo que las ortogonales.// cap-22 — sección 22.4: heurísticas.
pub fn manhattan(a: GridPos, b: GridPos) -> i32 {
(a.0 - b.0).abs() + (a.1 - b.1).abs()
}
pub fn octile(a: GridPos, b: GridPos) -> i32 {
let dx = (a.0 - b.0).abs();
let dy = (a.1 - b.1).abs();
let (min, max) = if dx < dy { (dx, dy) } else { (dy, dx) };
min * 14 + (max - min) * 10 // 10 para ortogonal, 14 para diagonal (10 * √2 ≈ 14).
}Usa Manhattan en juegos 2D de plataforma donde no hay diagonales; usa Octile en juegos top-down donde sí las hay.
La pregunta interesante: ¿cómo modelamos el grafo en ECS? Tres opciones:
Res<Grid> con el mapa de tiles sólidos/libres. A* lee el resource, devuelve una lista de GridPos. Sistema posterior mueve la entidad por la lista.Tile y Cost. Más caro, pero permite efectos visuales (niebla de guerra, tile en llamas que sube el coste) sin tocar el algoritmo.TilemapPos y consulta vecinos con un Query. Útil en mapas pequeños.// cap-22 — sección 22.5: opción 1 — grid en resource.
#[derive(Resource)]
pub struct Grid {
pub width: i32,
pub height: i32,
pub walls: HashSet<GridPos>,
}
impl Grid {
pub fn neighbours(&self, p: GridPos) -> Vec<(GridPos, i32)> {
let dirs = [(0,1),(1,0),(0,-1),(-1,0)];
dirs.iter()
.map(|(dx, dy)| GridPos(p.0 + dx, p.1 + dy))
.filter(|np| !self.walls.contains(np) && np.0 >= 0 && np.1 >= 0 && np.0 < self.width && np.1 < self.height)
.map(|np| (np, 10))
.collect()
}
}Bevy 0.18 introduce relationships (#[derive(Relationship)] y RelationshipTarget) que se ajustan perfectamente a modelar un path:
// cap-22 — sección 22.6: path como relación entre waypoints.
#[derive(Component, Relationship)]
#[relationship(linked_walk_target)]
pub struct WalkTargetOf { #[relationship] pub entity: Entity }
#[derive(Component, RelationshipTarget)]
#[relationship_target(linked_walk_target)]
pub struct WalkPath(Vec<Entity>);
#[derive(Component)]
pub struct WalkTarget;Una entidad enemy puede tener un WalkPath que apunta a una secuencia de entidades walk_target. Cada entidad walk_target es un nodo del grafo, y la entidad "dueña" del path sabe a qué nodo ir. Esto es elegante para visualizar el path en el editor y para representar paths que pueden compartirse entre varias entidades.
Cuando el mapa no es un grid (un metroidvania con plataformas y slopes, un top-down con cuevas irregulares), A* sobre grid funciona pero produce paths feos: el enemigo camina en diagonal a través de una pared estrecha que no debería cruzar. La solución estándar es un navmesh (navigation mesh): una malla de polígonos convexos que cubre el área transitable.
El flujo:
recast o navmesh (crate) hacen esto.// cap-22 — sección 22.7: esqueleto de uso de navmesh.
let navmesh = navmesh::NavMesh::from_poly_mesh(polygons);
let path = navmesh::a_star(&navmesh, start_poly, goal_poly)?;
let smoothed = funnel::smooth(&path, &vertices); // línea recta con recortes.En Rust, el crate navmesh (de uncommoncast) es el más maduro para 2D; para 3D, recast-rs es el port de Recast.
A* devuelve "centroide del polígono 1 → centroide del polígono 2 → centroide del polígono 3", lo que produce paths con zigzag. El funnel algorithm genera la línea recta real: dentro de cada polígono va recto, en cada arista compartida se ajusta para no atravesar paredes.
El pseudocódigo simplificado:
función funnel(polys, start, goal):
apex = polys[0].centro
left = left_corner_of_first_edge(apex)
right = right_corner_of_first_edge(apex)
path = [apex]
para cada polígono en polys[1..]:
left_corner, right_corner = corners_of_shared_edge(anterior, polígono)
si left_corner está más adentro que left:
// cruzamos el lado izquierdo.
path.push(left)
apex = left
left = left_corner
right = apex
si right_corner está más adentro que right:
// cruzamos el lado derecho.
path.push(right)
apex = right
right = right_corner
left = apex
path.push(goal)
return pathEl detalle geométrico es cuidadoso (ángulos y productos cruzales), pero el resultado es siempre un path recto que respeta las paredes.
Si tienes 100 zombies persiguiendo al mismo jugador, no quieres 100 A*s. Quieres un flow field: una rejilla donde cada celda tiene un vector que apunta "hacia el destino". Calculas el field una vez (con Dijkstra desde el destino), y cada entidad lee el vector de su celda para moverse.
// cap-22 — sección 22.9: flow field en resource.
#[derive(Resource)]
pub struct FlowField {
pub width: i32,
pub height: i32,
pub directions: Vec<Vec2>,
}
impl FlowField {
pub fn compute(grid: &Grid, goal: GridPos) -> Self {
// Dijkstra desde goal, asignando a cada celda el coste de llegar a goal.
// Después, para cada celda, mirar los 8 vecinos y elegir el de menor coste.
// El vector hacia ese vecino es la dirección.
unimplemented!()
}
}Ventaja: O(N) por actualización de field, O(1) por entidad. Para RTS o juegos con hordas, es la diferencia entre 30 FPS y 5 FPS.
A* no recalcula el mundo cada frame; usa un cache de paths. La pregunta es cuándo invalidar el cache. Tres reglas:
// cap-22 — sección 22.10: política de re-path.
#[derive(Component)]
pub struct PathCache {
pub path: Vec<GridPos>,
pub last_calculated: f32,
pub goal_at_calc: GridPos,
}
fn maybe_repath(
mut q: Query<(&mut PathCache, &GridPos)>,
time: Res<Time>,
player: Query<&GridPos, With<Player>>,
) {
let player_pos = *player.single();
let now = time.elapsed_secs();
for (mut cache, current) in &mut q {
let stale = now - cache.last_calculated > 0.5;
let goal_moved = cache.goal_at_calc != player_pos;
let blocked = cache.path.first().map_or(false, |p| is_blocked(*p));
if stale || goal_moved || blocked {
cache.path = a_star(*current, player_pos, neighbours, manhattan).unwrap_or_default();
cache.last_calculated = now;
cache.goal_at_calc = player_pos;
}
}
}Si usas una heurística que sobreestima (por ejemplo, euclídea sobre un mapa con ríos que cuestan 10x), A* puede devolver un path subóptimo: el algoritmo "cree" que ir por el río es mejor que rodearlo, sin comprobarlo. En mapas abiertos con coste uniforme, da igual; en mapas con costes muy variables, te puede dejar atascado en un loop donde el enemigo no encuentra la salida.
Otro clásico: no limpiar el BinaryHeap correctamente. Un heap con entradas duplicadas para el mismo nodo (al hacer decrease_key simulado con reinsertar) puede contener miles de entradas inválidas. La solución: al pop, comprobar if g_actual != g_recordado { continue; } antes de procesar.
Nombre: el coste de ir, no el de llegar.
Resumen: A* combina coste real (g) con heurística (h). Maximiza siempre la admisibilidad de h y la consistencia. Usa flow fields para muchos agentes, navmesh para mapas no-grid, y re-paths throttleados para evitar spam.
Aplicar cuando: cualquier IA que se mueva por un mapa con obstáculos.
No aplicar cuando: enemigo estático o que sigue al jugador sin considerar paredes (puede ir en línea recta).
Costo: A* en grid es O(N log N) en el peor caso; para mapas grandes (> 10 000 nodos) considera jerarchical pathfinding o flow fields.
Beneficio: paths correctos y suaves con bajo coste de CPU si se hace bien.
La regla de oro: *A corre una vez por cambio de destino*, no por frame. Las entidades se mueven siguiendo el path cacheado hasta que algo invalide el cache. Esta separación entre "planificación" (A) y "ejecución" (movimiento por waypoints) es lo que mantiene el frame budget bajo control. Una vez la tienes clara, la puedes aplicar tanto a zombies como a comerciantes NPC, a tropas en un RTS, o a una IA de bolos.
A en grid funciona cuando el mapa es una rejilla. Pero muchos juegos 2D tienen mapas orgánicos (cuevas, ríos, pendientes) que no encajan en una rejilla. Para eso existe el navmesh (navigation mesh): una malla de polígonos convexos que cubre las zonas transitables, y un A que opera sobre los polígonos en vez de tiles.
El flujo:
Ventajas del navmesh sobre el grid:
En Bevy, la opción recomendada para 2D es vleue_navigator (de vleue), que implementa el algoritmo Polyanya (pathfinding óptimo simultáneo sobre navmesh, simultáneamente más rápido que A* sobre el grafo de polígonos). Históricamente este crate se llamó bevy_pathmesh; fue renombrado a vleue_navigator a partir de la versión 0.7, así que si ves bevy_pathmesh en tutoriales viejos, es el mismo proyecto. La versión vigente para Bevy 0.18/0.19 es la 0.15.
# cap-22 — sección 22.14: pathfinding sobre navmesh (Bevy 0.18/0.19).
[dependencies]
vleue_navigator = "0.15" # Polyanya; pre-0.7 este crate se llamaba `bevy_pathmesh`.//! cap-22 — sección 22.14: setup navmesh con vleue_navigator.
use bevy::prelude::*;
use vleue_navigator::prelude::*;
fn main() {
App::new()
.add_plugins(DefaultPlugins)
.add_plugins(VleueNavigatorPlugin) // registra `NavMesh` como asset.
.add_systems(Startup, setup)
.add_systems(Update, move_to_destination)
.run();
}
fn setup(mut commands: Commands, asset_server: Res<AssetServer>) {
// Carga un navmesh precalculado (.navmesh.glb o generado con Polyanya).
// El `Handle<NavMesh>` va como componente; el plugin actualiza paths.
let navmesh: Handle<NavMesh> = asset_server.load("navmesh.glb#NavMesh");
commands.spawn(navmesh);
}
fn move_to_destination(
mut commands: Commands,
navmeshes: Query<&Handle<NavMesh>>,
navmesh_assets: Res<Assets<NavMesh>>,
mut query: Query<(Entity, &Transform, &Destination), With<NPC>>,
) {
let Ok(navmesh_handle) = navmeshes.single() else { return };
let Some(navmesh) = navmesh_assets.get(navmesh_handle) else { return };
for (entity, transform, dest) in &mut query {
// `path` devuelve `Option<Vec<Vec2>>>` usando Polyanya.
if let Some(waypoints) = navmesh.path(transform.translation.truncate(), dest.0) {
// Seguir los waypoints (sistema de movimiento aparte).
commands.entity(entity).insert(Pathing(waypoints));
}
}
}
#[derive(Component)]
struct Pathing(Vec<Vec2>);*Cuándo usar navmesh en vez de A grid:**
Cuándo NO usarlo:
Generar el navmesh: en 2D, una opción simple es vleue_navigator, que incluye un generador de navmesh a partir de los contornos del mapa (Polyanya triangula automáticamente el área transitable). Otra opción, para mapas complejos, es Recast (herramienta de la industria, originalmente 3D, pero con bridge a 2D). El proceso típico: diseñar en Tiled/LDTK → exportar la geometría transitables → generar el navmesh → cargarlo en Bevy como asset NavMesh.
El trade-off real: navmesh es más natural y escalable, pero el setup inicial (generar el navmesh cada vez que cambia el mapa) es fricción. A en grid es más simple, funciona "al toque", y para mapas gridded es indistinguible de navmesh en la práctica. Si tu mapa es gridded, quédate con A grid**. Si es orgánico, migra a navmesh.
g(n) con heurística admisible h(n) para encontrar el path óptimo en grafos ponderados. La admisibilidad (nunca sobreestimar) es lo que garantiza optimalidad.BinaryHeap (priority queue) + HashMap<(i,j), Cell> para g/parent. El check if g_actual != g_recordado { continue; } al pop es OBLIGATORIO para evitar procesar entradas inválidas.★ **Pac-Man (Namco, 1980)** — los cuatro fantasmas no usan A*. Cada uno tiene
una "tile objetivo" fija (Blinky: Pac-Man; Pinky: 4 tiles adelante; Inky:
vector desde Blinky; Clyde: Scattery si lejos, Chase si cerca) y se mueven
paso a paso eligiendo el vecino cuya distancia a la tile objetivo es
mínima. Es un caso degenerado de A* con h = distancia a la tile y g = 1
siempre. Con 4 fantasmas y mapas de 28x31 tiles, sale a cuenta reinventar
la rueda cada nivel.
★ **Starcraft (Blizzard, 1998)** — el pathfinding fue una de las grandes
contribuciones técnicas de Blizzard. Usaban una variante de A* con
"influence mapping" (los propios edificios ejercen influencia repulsiva
en el path) y un sistema de "regiones" conectadas para evitar
recalcular A* cada frame cuando una unidad cruza un chunk. Los pathing
glitches de Starcraft son leyenda; el que una Dragoon se atasque entre
dos marines sigue siendo un meme 25 años después.
★ **Civilization (MicroProse, 1991)** — el pathfinding de las unidades
usaba un A* por turnos, no por frame. Cada unidad recalculaba su
path al inicio del turno del jugador, y durante el turno seguía los
waypoints. Esa decisión (pathfinding discreto, no continuo) es lo que
permitía que Civ 1 corriese en máquinas de 1 MB de RAM.En el cap 22B (animación 2D) dejamos a las entidades QUIETAS un momento y nos dedicamos a que se MUEVAN bonito: animaciones por frames, animation graphs (mezclar animaciones tipo "Idle + Walk" sin transicionar de golpe), tweens y procedurales. Verás por qué un atlas de sprites con un AnimationTimer es el patrón 2D mínimo viable, y por qué bevy_animation 0.18+ te da más control cuando necesitas blending (caminar + disparar a la vez). También tocaremos el bug clásico: animaciones que se "saltan" al cambiar de estado porque nadie reseteó el timer. Si el cap 22 era "calculo cómo llegar", el cap 22B es "llegar con estilo". A por ello.