Cargando aplicación...
Preparando tu experiencia meskeIA
Cómo los enemigos de un videojuego encuentran el camino: A*, Dijkstra y BFS paso a paso sobre una rejilla
A*, Dijkstra y BFS — cómo deciden los videojuegos por dónde ir
| Algoritmo | ¿Tiene en cuenta el coste del terreno? | ¿Camino óptimo? | Casillas que explora | Cuándo usarlo |
|---|---|---|---|---|
| BFS | No, solo cuenta casillas | Sí en nº de pasos, no en coste | Muchas (en oleadas) | Casillas alcanzables en N pasos (juegos por turnos) |
| Dijkstra | Sí | Sí, la ruta más barata | Muchas (en todas direcciones) | Sin meta fija o sin heurística clara |
| A* | Sí | Sí, si la heurística es admisible | Pocas (dirigidas a la meta) | Pathfinding con destino conocido: el estándar en videojuegos |
En un RPG o un shooter, cada enemigo calcula con A* la ruta hasta tu posición esquivando muros. Cuando te mueves, recalcula. Es el uso más común del pathfinding.
💡 Recalcular cada frame es caro: muchos juegos lo hacen cada pocos frames o solo si el objetivo se ha movido bastante.
Al ordenar a una unidad ir a un punto, el motor traza la ruta con A* sobre la rejilla del mapa, prefiriendo caminos y evitando bosques o agua (terreno costoso).
💡 Con muchas unidades se combina A* con «flow fields» para no calcular una ruta por unidad.
En un táctico por casillas, BFS resalta hasta dónde puede llegar un personaje con sus puntos de movimiento, y A* traza la ruta concreta al confirmar el destino.
💡 BFS es ideal aquí porque «N pasos» es exactamente lo que limita el movimiento.
Los juegos 3D no usan una rejilla cuadrada, sino polígonos transitables (navmesh). El algoritmo es el mismo A*, pero los nodos son zonas en lugar de casillas.
💡 Unity y Unreal traen sistemas de navmesh + A* listos para usar.
Dijkstra no sabe dónde está la meta: expande en todas direcciones según el coste acumulado. A* suma una heurística que estima lo que falta hasta la meta, así que da prioridad a las casillas que van «hacia allí». Encuentra la misma ruta óptima, pero descartando antes las zonas que se alejan del destino.
💡 Si pones la heurística a cero, A* se convierte exactamente en Dijkstra. Pruébalo mentalmente: sin pista de dónde está la meta, toca explorar a ciegas.
Cuando hay terreno con distinto coste. BFS solo cuenta casillas, así que cruzará una zona de barro si tiene menos casillas, aunque sea lentísima. Dijkstra y A* sí suman el coste y prefieren rodear el barro si eso sale más barato. Carga el preset «Barro central» y compara las rutas.
💡 En un mapa sin terrenos costosos y sin diagonales, BFS, Dijkstra y A* dan caminos de la misma longitud; solo cambia cuánto exploran.
En una rejilla con movimiento en 4 direcciones se usa la distancia Manhattan (|dx| + |dy|). Si permites diagonales, se usa la distancia octil, que tiene en cuenta que el paso diagonal cuesta 1,41. La clave es que la heurística sea admisible: que nunca estime de más. Si lo hace, A* garantiza el camino óptimo.
💡 Si la heurística sobreestima, A* va más rápido pero puede devolver una ruta que no es la más corta. A veces se acepta ese cambio a propósito.
Cuando activas las diagonales, el simulador impide moverse en diagonal si las dos casillas ortogonales de esa esquina son muros: físicamente el personaje no «cabría» por el hueco. Es lo que esperan los jugadores y evita que los enemigos parezcan atravesar paredes.
💡 Algunos juegos sí permiten cortar esquinas para rutas más fluidas; es una decisión de diseño.
Para ir de un punto a otro con una meta conocida, normalmente sí. Pero si necesitas las distancias desde un origen a todos los puntos, Dijkstra es más adecuado. Y con miles de agentes moviéndose a la vez se usan técnicas como flow fields o jump point search (una optimización de A* para rejillas uniformes).
💡 No existe «el mejor algoritmo» absoluto: depende de si hay meta fija, pesos, cuántos agentes y cómo es el mapa.
El algoritmo es independiente del lenguaje: se implementa igual en Python, C#, C++ o JavaScript. Motores como Unity (C#), Unreal (C++/Blueprints) o Godot (GDScript) ya incluyen pathfinding integrado, pero entender A* por dentro te permite ajustarlo y depurarlo cuando el comportamiento no es el esperado.
💡 Implementar A* a mano una vez es un ejercicio clásico y muy recomendable antes de usar el del motor.
La «frontera» (conjunto abierto) guarda las casillas pendientes de explorar. Empieza solo con la casilla de partida, con coste acumulado g = 0.
De la frontera, elige la de menor f = g + h, donde g es el coste real recorrido y h la estimación hasta la meta. La marcas como visitada (conjunto cerrado).
Si la casilla que sacas es la meta, has terminado: reconstruye el camino siguiendo los predecesores hacia atrás. Si no, continúa.
Para cada casilla vecina transitable, calcula el coste de llegar por aquí. Si es mejor que el que tenía, actualiza su g, guarda de qué casilla viene y métela en la frontera.
Vuelve al paso 2 hasta llegar a la meta o vaciar la frontera. Si se vacía sin llegar, no existe camino posible.
Para sacar siempre la casilla de menor f sin recorrer toda la frontera, usa un heap (montículo). Marca la diferencia en mapas grandes.
Para garantizar el camino óptimo, h nunca debe sobreestimar el coste real. Manhattan u octil son seguras en rejillas.
No almacenes la ruta completa en cada casilla. Guarda solo «de quién vengo» y reconstruye al final siguiendo la cadena hacia atrás.
Recalcular la ruta de cada enemigo en cada fotograma hunde el rendimiento. Hazlo cada cierto tiempo o cuando el objetivo se mueva lo suficiente.
Si permites diagonales, impide cortar esquinas entre dos muros para que los personajes no parezcan atravesar paredes.
Si muchos agentes van al mismo destino, calcula un mapa de costes una sola vez (flow field) en lugar de un A* por agente.