渋谷ほととぎす通信

「Unityをわかりやすく」初心者のためのゲーム作りブログ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最後に

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

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

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

この寿司をどこで注文したのかを質問し忘れたことが悔いとして残っています。
オススメ記事
検証環境
  • Unity2018.2.12f1
参考サイト