成果物
絶対できないと思っていたことを2019年の大晦日の年越し30分前にとうとう成し遂げることができて本当によかったです。
仕組み
ボロノイ図についての詳しい解説はこちらをご覧ください。
A-Starについて
分割した図形からグラフデータを作る
分割した図形から、グラフと呼ばれる点と点のつながりのデータを作ればA*で解くことができるのですが、参考にできるものがなかったので難しかったです。
具体的には、画面内に入っている点の全てを先にノードに追加しておき、三角形や多角形の辺の情報を使ってノードをつないでいきます。
今回は、頂点座標をもとに、ノードを検索するようにしました。見つからなければパスするようにしています。
※追記
なぜか、PVectorの数値の若干の誤差が生じでいたので、ノードの検索時は少々の誤差は見逃すようにしました。これに気付くまでにかなりの時間がかかりました。
コード
Voronoi_A_Starという名前です。dキーでドロネー三角形分割とボロノイ図を切替、sキーで最短経路を計算、fキーで図形全表示と、画面内図形表示を切り替えができます。
ソースコードはこちらです。