円形障害物を回避するA*経路探索の実装

Circular Obstacle Pathfinding (2017)

A*アルゴリズムはグリッドだけでなく、任意のグラフ上で動作します。この記事では、円形の障害物が点在する世界でA*を使うために、障害物間の接線（サーフィンエッジ）と円周に沿った弧（ハグエッジ）からなる接線可視グラフを構築する方法を解説します。内部・外部ビタンジェントの計算、障害物によるエッジの遮蔽判定、円が接触・重なる場合の拡張、Minkowski和による可変半径の扱いまで、具体的な数式と図で詳しく説明します。