渋谷ほととぎす通信

完全趣味でやってるUnityメモ。説明できないところを説明できるようにするための個人ブログ。昨日の自分より少しでも大きくなれるように。。。 ※所属団体とは一切関係がありません

経路探索Astarアルゴリズムの勉強がてらUnityで実装してみた話


今日、正確には昨日、ECS完全に理解した勉強会に参加してきました。
個人的には制作モチベーションの刺激を頂いた感ある、実りある勉強会でした。

そして懇親会。お寿司がやたら美味しく感じ、おごってくれた & 場所を提供してくれたmixiさんには感謝です。
※人材募集しているらしいです。

ということで、ECSは全く関係ないですが、最近Astarアルゴリズムを勉強しようと思っていろいろ調べ、Unityで実装したという備忘録を残しておきます。

まあ、もう枯れた技術と言っても過言ではないと思いますが、実際に自分でやってみないと血肉にならない質なので、やってみます。

成果物としてはこのようなものを作りました。
f:id:esakun:20181023013907g:plain
クリックしたタイルにUnityちゃんが走っていくというシンプルなもの。
この経路探索にAstarを使用しています。

Astarアルゴリズムの考え方や、実装方法については、以下の記事などを参考にしました。

その他にもググればたっくさん資料が出てくるので、良い時代です。

  1. ゴールのノードを設定
  2. スタート地点から周囲のノードのコストを調べる
  3. より良いコストを探していく

基本的にはゴール地点にたどり着くまで3を続けるという処理になります。

面白いのが、ヒューリスティックコストと呼ばれる、推定コストの概念です。
今回の実装では、各ノードからゴールまでの直線距離を推定コストとしました(単純なので)。

ここの値を工夫することで、探索結果が大きく変わってくるため面白いです。

f:id:esakun:20181023030417p:plain:w400
使い方としては、Astarインスタンスを初期化した後は、

  • 開始ノード
  • ゴールノード
  • 結果注入用リスト

これらをAstarに渡せば経路の結果が帰ってくるので、それをViewに反映させるといったシンプルなAPIに仕上げています。

結果注入用リストをわざわざ代入させているのは、GC発生的な観点から、new List, ToListToArrayをあまり使いたくないという思いがあったためです。

f:id:esakun:20181023025512g:plain
このように障害物(紫色のタイル)もちゃんと避けてくれます。

ちなみに、Astarだけを使いたい場合は、今回のサンプルリポジトリAstar.csNode.csを引っこ抜くだけです(MITライセンス)。

最後に

今回のサンプル含めた全ソースはコチラにアップしています。
※DOTweenは別途インポートしないとコンパイルが通りません。

Astarは長い距離を操作したり、障害物が多かったりするとCPU負荷が高くなります。
この辺JobSystemでなんとかしたい感あるため、その辺調査してみようかと思っています。

参考

GitHub - seinosuke/AStar: A*(A-star)アルゴリズムの可視化っぽい何か
こちらのコードを大変参考にさせていただきました。感謝です。

環境

  • Unity2018.2.12f1


この寿司をどこで注文したのかを質問し忘れたことが悔いとして残っています。