El algoritmo A* encuentra el camino óptimo entre obstáculos circulares

Circular Obstacle Pathfinding (2017)

El algoritmo A* es conocido por su uso en mapas de cuadrícula, pero funciona en cualquier grafo. Este artículo demuestra cómo aplicarlo a un bosque de obstáculos circulares. El proceso implica convertir el mundo en un grafo de visibilidad tangente, generando aristas de 'surfing' (segmentos bitangentes) y de 'hugging' (arcos alrededor de los círculos). Se detallan los cálculos geométricos para construir estas aristas, incluyendo la detección de bloqueos por otros círculos, y se exploran mejoras como el manejo de círculos que se tocan o se superponen y la expansión de Minkowski para agentes con radio variable.