成果物
www.youtube.com
ようやくConstrained DelaunayをA Starアルゴリズムで解くことが出来ました。これは、かなり重要なアルゴリズムで、ゲームのAIもこれと似た仕組みを使って障害物を避けながら移動しています。
仕組み
前回Constrained Delaunayのアルゴリズムを実装して、三角形を生成するところまでできました。今回は、その三角形をもとに点と点の接続情報を表すグラフを作成し、A Starアルゴリズムで解いています。
nekodigi.hatenablog.com
A Starに関してはこちらをご覧ください。
nekodigi.hatenablog.com
コード
Constrained Delaunay A Starという名前で追加しています。
github.com