Laboratorio de caminos A*

Muévete en horizontal o vertical por una rejilla fija 16 × 16. Cada movimiento cuesta uno; no hay movimientos diagonales ni celdas ponderadas. El coste del camino cuenta aristas, así que un inicio y un objetivo compartidos tienen coste cero.

A* elige una celda abierta con el menor f = g + h. Aquí g es el coste desde el inicio; h es la distancia de Manhattan, la distancia euclídea o cero (Dijkstra). Los empates usan un h menor, luego el orden de inserción; mejorar una celda abierta conserva su orden original. Las tres heurísticas son consistentes en esta rejilla, así que las celdas cerradas no necesitan reabrirse. La búsqueda se detiene cuando el objetivo se retira de la frontera. Visitadas cuenta estos retiros, incluido el objetivo; un paso retira como máximo una celda.

Comparar usa el mismo tablero y la misma política de empate para las tres ejecuciones. La rejilla mostrada pertenece a la heurística seleccionada. Las tres devuelven un camino más corto cuando es alcanzable; los recuentos de visitadas dependen del tablero y de la política de empate. Esta implementación didáctica pequeña recorre la frontera y tiene una cota peor O(V²).

Elige un modo de edición y luego pulsa o arrastra. El inicio y el objetivo no se pueden pintar como muros; colocar un marcador borra ese muro. Con la rejilla enfocada, usa las flechas para mover el cursor marcado y Espacio o Intro para editar. Las coordenadas van de 0 a 15, con (0, 0) arriba a la izquierda.

Ejecutar reanuda una búsqueda en pausa y reinicia una terminada. Un paso pausa primero. Restablecer búsqueda conserva el tablero; elige Vacío para borrarlo y restaurar los marcadores. Editar o cambiar la heurística descarta la búsqueda y la comparación. La velocidad solo afecta a la animación. Salir de la herramienta u ocultar la página la detiene; el tablero, la heurística, la velocidad, el modo de edición y el cursor del teclado se guardan localmente en este navegador, pero no el progreso de la búsqueda. Perder el foco u ocultar la página termina el trazo activo. Los tableros guardados antiguos siguen siendo compatibles.

Fuentes: Hart, Nilsson y Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths (1968), pp. 101–102; 1972 correction sobre consistencia y nodos cerrados.