Question 1

¿Qué es el algoritmo A* (A estrella) y por qué se usa en videojuegos?

Accepted Answer

A* es un algoritmo de búsqueda de caminos que encuentra la ruta más corta entre dos puntos sobre una rejilla o grafo. Combina el coste real recorrido (g) con una estimación de lo que falta hasta la meta (heurística h), priorizando las casillas con menor f = g + h. Gracias a esa estimación explora muchas menos casillas que Dijkstra, por lo que es el estándar para mover enemigos y NPCs en videojuegos: es rápido y, si la heurística es admisible, garantiza el camino óptimo.

Question 2

¿Cuál es la diferencia entre A*, Dijkstra y BFS?

Accepted Answer

BFS (búsqueda en anchura) explora en oleadas y encuentra el camino con menos casillas, pero ignora que unos terrenos cuesten más que otros. Dijkstra sí tiene en cuenta el coste del terreno y halla siempre la ruta más barata, aunque explora en todas direcciones por igual. A* es Dijkstra más una heurística que orienta la búsqueda hacia la meta: encuentra la misma ruta óptima que Dijkstra pero visitando muchas menos casillas. En este simulador puedes ver las tres sobre el mismo mapa.

Question 3

¿Qué es una heurística admisible en pathfinding?

Accepted Answer

Una heurística es una estimación del coste que falta desde una casilla hasta la meta. Se dice que es admisible cuando nunca sobreestima ese coste real. En rejillas se usan la distancia Manhattan (movimiento en 4 direcciones) o la distancia octil/Chebyshov (con diagonales). Que la heurística sea admisible es la condición que garantiza que A* devuelva siempre el camino óptimo; si sobreestima, A* es más rápido pero puede dar una ruta no óptima.

Question 4

¿Cómo persiguen los enemigos al jugador en un videojuego?

Accepted Answer

La mayoría de juegos dividen el escenario en una rejilla de casillas o en una malla de navegación (navmesh) y aplican A* para calcular la ruta desde el enemigo hasta el jugador, esquivando muros y prefiriendo el terreno más barato. El camino se recalcula cuando el jugador se mueve o cambia el escenario. En juegos por turnos también se usa BFS para resaltar las casillas alcanzables en un número dado de pasos.

Question 5

¿Para qué sirve poner terreno costoso o diagonales en el mapa?

Accepted Answer

El terreno costoso (por ejemplo barro o agua) simula zonas por las que es más lento moverse: entrar en ellas suma más coste, así que un buen algoritmo intentará rodearlas. Es justo donde se nota la diferencia entre BFS (que las atraviesa porque solo cuenta casillas) y Dijkstra o A* (que las evitan si compensa). Activar las diagonales permite moverse en 8 direcciones con coste 1,41 (raíz de 2) por paso diagonal, lo que produce rutas más naturales y obliga a usar una heurística distinta.

Simulador de Pathfinding A*

1. Elige el algoritmo

2. Carga un mapa de ejemplo

3. Dibuja el mapa

4. Ejecuta y observa la búsqueda

📚Guía de Búsqueda de Caminos (Pathfinding)

🔗Apps relacionadas