El algoritmo A es una técnica de búsqueda en grafos que permite generar rutas óptimas entre un punto de inicio y un punto de meta evitando obstáculos. Aunque suele presentarse sobre mapas de cuadrícula, A funciona sobre cualquier grafo, lo que abre la puerta a problemas más complejos, como el de encontrar un camino en un entorno plagado de obstáculos circulares.
La clave para aplicar A* a este escenario es transformar el bosque de círculos en un grafo navegable. Para ello se construye un grafo de visibilidad tangente compuesto por dos tipos de aristas: las llamadas surfing edges, segmentos rectos que pasan entre dos círculos rozando sus bordes (las bitangentes internas y externas), y las hugging edges, arcos que siguen el contorno de un obstáculo entre dos puntos de tangencia. Los puntos donde unas y otras se conectan forman los nodos del grafo.
El artículo detalla las fórmulas trigonométricas necesarias para localizar las bitangentes entre dos circunferencias —el conocido problema de la correa cruzada y el problema de la polea— y explica cómo descartar, mediante cálculo de distancia punto-segmento, las aristas cuya línea de visión quede bloqueada por un tercer círculo. También aborda los casos degenerados en los que los círculos se tocan, se solapan o uno contiene al otro, donde las funciones trigonométricas dejan de estar definidas y hay que validar el dominio antes de aplicar el arccoseno.
Una vez construido el grafo limpio, A* lo recorre del mismo modo que en una cuadrícula, empleando una cola de prioridad ordenada por la distancia recorrida más una heurística admisible —habitualmente la distancia euclídea en línea recta— que nunca sobreestima el coste restante. El texto propone además varias mejoras para reducir el uso de CPU y memoria, y para gestionar configuraciones de obstáculos más realistas, convirtiendo el método en una solución general y eficiente para la planificación de trayectorias entre formas circulares.