A* um runde Hindernisse: Pfadfindung im Wald

Circular Obstacle Pathfinding (2017)

Der A*-Algorithmus findet optimale Pfade nicht nur auf Gittern, sondern auf beliebigen Graphen. Dieser Artikel zeigt, wie man eine Welt aus kreisförmigen Hindernissen in einen Graphen umwandelt, indem man Tangenten-Sichtbarkeitsgraphen erzeugt: Kanten, die Kreise berühren (Surfing Edges) und Bögen, die ihnen folgen (Hugging Edges). Dazu gehören die Berechnung interner und externer Bitangenten sowie die Überprüfung auf Blockaden durch andere Kreise. Zusätzlich werden Erweiterungen behandelt: Umgang mit sich berührenden oder überlappenden Hindernissen sowie die Minkowski-Erweiterung für variable Akteursradien. Mit diesen Techniken lässt sich A* effizient auf kreisförmige Hinderniswelten anwenden.