こんにちは、Unityエンジニアのオオバです。

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

ECS完全に理解した勉強会ツイート

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

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

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

成果物としてはこのようなものを作りました。

クリックしたタイルにUnityちゃんが走っていくというシンプルなもの。
この経路探索にAstarを使用しています。

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

• A* - Wikipedia
• よくわかるA*(A-star)アルゴリズム (Unity2Dのサンプルコードつき) - Qiita

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

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

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

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

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

使い方としては、Astarインスタンスを初期化した後は、

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

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

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

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

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

最後に

今回のサンプル含めた全ソースはコチラにアップしています。

GitHub - baobao/UnityAstarSample: Astarの勉強がてらUnityでサンプル作ってみました

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

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

• Unity2018.2.12f1

• GitHub - seinosuke/AStar: A*(A-star)アルゴリズムの可視化っぽい何か