EN 
Українська
Español🎮 Buscador de Rutas para NPC de Videojuegos — Búsqueda A* en Vivo
Observa cómo el algoritmo real de búsqueda A* expande en vivo los nodos de un mapa de videojuego simulado según el coste genuino f=g+h, encontrando rutas de NPC demostrablemente más cortas alrededor de obstáculos, más rápido que el Dijkstra normal.
Acerca de la simulación Búsqueda A* en Vivo
Los motores de videojuegos se hacen constantemente la misma pregunta: ¿cuál es la ruta transitable más corta desde un NPC hasta su objetivo a través de un mapa lleno de muros, terreno y otros obstáculos? La búsqueda A* (Hart, Nilsson y Raphael, 1968) es la respuesta de referencia — una búsqueda de grafos best-first que mantiene una cola de prioridad genuina ordenada por f(n) = g(n) + h(n), donde g(n) es el coste real acumulado desde el inicio y h(n) es una estimación heurística admisible de la distancia restante. Esta simulación ejecuta el algoritmo real — conjunto abierto real, conjunto cerrado real, punteros a los padres reales — sobre un mapa de videojuego en cuadrícula que puedes editar, y ejecuta el algoritmo de Dijkstra normal (A* con h(n) = 0) en el mismo mapa al mismo tiempo, para que puedas observar, nodo a nodo, exactamente cuánto trabajo ahorra la heurística.
🔬 Qué muestra
Dos cuadrículas lado a lado que comparten un mapa de obstáculos: la cuadrícula izquierda ejecuta A* real con una heurística de distancia octile, la cuadrícula derecha ejecuta Dijkstra con la heurística forzada a cero. Las celdas cian están en el conjunto abierto (descubiertas, en cola, aún no expandidas), las celdas ámbar están en el conjunto cerrado (expandidas, finalizadas), y la ruta con el color de acento es la ruta más corta reconstruida mediante punteros a los padres una vez que el nodo objetivo es extraído. Los contadores en vivo totalizan el número real de nodos que cada cola de prioridad realmente extrajo.
🎮 Cómo usarlo
Elige un modo — Muro, Inicio u Objetivo — y luego haz clic en cualquier celda de cualquiera de las cuadrículas para editar el mapa compartido; ambas búsquedas se vuelven a ejecutar al instante. Usa Laberinto aleatorio para generar un nuevo diseño de obstáculos, Borrar muros para empezar desde un campo abierto, y el control deslizante de velocidad de expansión para ralentizar la revelación con fines didácticos o acelerarla para ver la ruta final de inmediato. Repetir reinicia la animación nodo por nodo sin recalcular la búsqueda.
💡 ¿Sabías que...?
Como el algoritmo de Dijkstra es matemáticamente idéntico a A* con h(n)=0, los dos paneles ejecutan exactamente la misma ruta de código con un solo número cambiado — por eso esta es una comparación justa y equivalente, en lugar de dos implementaciones no relacionadas. En mapas abiertos, A* suele expandir menos de la mitad de los nodos que Dijkstra; en mapas donde un muro obliga a ambos algoritmos a un largo rodeo, la diferencia se reduce porque ninguno puede atajar la geometría que la heurística no puede ver a través.
Preguntas frecuentes
¿Qué es la búsqueda A* y en qué se diferencia del algoritmo de Dijkstra?
Ambas son búsquedas de grafos best-first que extraen el nodo de menor coste de una cola de prioridad (el conjunto abierto) en cada paso. El algoritmo de Dijkstra ordena esa cola únicamente por g(n), el coste real acumulado desde el nodo de inicio, por lo que explora hacia fuera en todas las direcciones por igual, como las ondas en un estanque. A* ordena la misma cola por f(n) = g(n) + h(n), añadiendo una estimación heurística admisible h(n) de la distancia restante hasta el objetivo. Ese término adicional sesga la expansión hacia el objetivo, por lo que A* normalmente cierra muchos menos nodos que Dijkstra, garantizando a la vez devolver la misma ruta de menor coste, porque una ejecución de Dijkstra es matemáticamente idéntica a una ejecución de A* con h(n) = 0 para cada nodo — que es exactamente cómo esta simulación implementa la comparación en un mapa compartido.
¿Qué hace que una heurística sea admisible, y por qué eso garantiza que A* encuentre la ruta más corta?
Una heurística h(n) es admisible si nunca sobrestima el coste real restante desde el nodo n hasta el objetivo — puede subestimar o ser exacta, pero nunca demasiado optimista en la dirección equivocada. En una cuadrícula donde los pasos diagonales cuestan √2 y los ortogonales cuestan 1, la distancia en línea recta (octile) hasta el objetivo siempre es menor o igual que el coste real restante de la ruta alrededor de obstáculos, por lo que es admisible. Con una heurística admisible, A* está garantizado a no finalizar nunca un nodo con un valor g subóptimo: cualquier ruta que reporte como la más corta realmente lo es, razón por la cual la simulación puede afirmar que A* y Dijkstra siempre llegan al mismo coste de ruta, no simplemente a uno similar.
¿Qué es la distancia octile y por qué se usa en mapas de cuadrícula que permiten movimiento diagonal?
La distancia octile es la heurística para cuadrículas de 8 direcciones: dados |dx| y |dy| celdas de separación horizontal y vertical, la ruta más corta posible (ignorando obstáculos) se mueve en diagonal min(|dx|,|dy|) veces a un coste de √2 cada una, y luego cubre las |dx|−|dy| celdas restantes ortogonalmente a un coste de 1 cada una. La fórmula (|dx|+|dy|) + (√2−2)·min(|dx|,|dy|) calcula exactamente eso. La distancia euclidiana o Manhattan normal sobrestimaría (rompiendo la admisibilidad en una cuadrícula con movimiento diagonal) o subestimaría demasiado, por lo que la distancia octile es la opción ajustada y admisible que esta simulación usa para la h(n) de A*.
¿Por qué A* suele expandir menos nodos que Dijkstra?
Dijkstra no tiene noción de dónde está el objetivo, por lo que su frontera de expansión crece como un frente de onda aproximadamente circular centrado en el inicio, tocando cada nodo dentro de un radio de coste dado antes de llegar al objetivo. El orden f = g + h de A* mantiene cerca del frente de la cola de prioridad los nodos que apuntan hacia el objetivo, por lo que su frontera se estira en una forma alargada y dirigida al objetivo, saltándose grandes regiones al otro lado del mapa que Dijkstra aún tendría que visitar. Los contadores en vivo de esta simulación totalizan el número real de nodos que cada algoritmo realmente extrajo y cerró de su propia cola de prioridad en el mismo mapa de obstáculos, así que la diferencia que ves es una diferencia genuina y medida, no una supuesta — y en mapas donde la línea recta al objetivo está bloqueada por un obstáculo grande, la diferencia puede reducirse o incluso desaparecer, lo cual la simulación mostrará honestamente.
¿Cuál es la diferencia entre el conjunto abierto y el conjunto cerrado?
El conjunto abierto es la frontera: nodos que han sido descubiertos (alcanzados desde algún vecino) y añadidos a la cola de prioridad, pero aún no expandidos. El conjunto cerrado son los nodos que ya han sido extraídos de la cola y han tenido todos sus vecinos examinados — su coste g más corto desde el inicio está finalizado y no cambiará de nuevo. En la visualización, las celdas cian están en el conjunto abierto (candidatos aún en consideración) y las celdas ámbar están en el conjunto cerrado (totalmente procesadas); una vez que el objetivo es extraído del conjunto cerrado, el algoritmo se detiene y reconstruye la ruta siguiendo los punteros a los padres hacia atrás desde el objetivo hasta el inicio.
¿Puede A* fallar en encontrar la ruta más corta, o fallar en encontrar una ruta en absoluto?
A* está garantizado a encontrar la ruta más corta siempre que exista una y su heurística sea admisible — la heurística de distancia octile de esta simulación satisface esa condición en cada mapa que construyas. Lo que A* no puede hacer es encontrar una ruta que no existe: si bloqueas por completo el objetivo, tanto A* como Dijkstra agotarán sus conjuntos abiertos y reportarán que no se encontró ruta, lo cual el panel de estadísticas mostrará explícitamente en lugar de mostrar silenciosamente una ruta obsoleta.
Una cola de prioridad basada en un montículo binario expande nodos en un orden best-first real según f(n)=g(n)+h(n) en la cuadrícula izquierda y f(n)=g(n) en la derecha; ambas reconstruyen la ruta más corta mediante punteros a los padres genuinos una vez que el objetivo es extraído del conjunto cerrado.
3D · Renderizador Three.js / WebGL · Objetivo de 60 FPS · funciona totalmente en el cliente, sin instalación