こんにちは、Unityエンジニアのオオバです。
ある地点からある地点までの経路を探索してキャラクタを動かすゲームを作りたくなった場合、経路探索アルゴリズムが必要になります。
経路探索アルゴリズムはいくつもあるのですが、比較的シンプルなA*（エースター）をUnityで一から時前実装してみようと思います。
具体的に作ったものはこちらです。
クリックしたタイルにUnityちゃんが走っていくというシンプルなものですが、しっかり障害物（紫のタイル）を避けた経路を探索して移動しています。
本記事では上記のサンプルを作成していきます。
👉DOTweenの教科書を読んでUnityアニメーションをプログラミングしてみよう！
A*って何？
A*（Aスター）とは、最短ルートを見つけるための計算方法 です。
ゲームのキャラクターが障害物を避けながらゴールに向かうときや、地図アプリで最短ルートを探すときに使われています。
A*の仕組み
A* はゴールまでのルートを探すときに、「すでに進んだ距離」 + 「あとどれくらい進むか」 を考えて、できるだけ早くゴールにたどり着けるようにします。
これによって、適当に進むのではなく、無駄なく効率的に最短ルートを探せるのが特徴です。
- 今までに進んだ距離（移動コスト）
- ゴールまでどれくらい近そうか（予想）
この2つを足し算して、できるだけ小さい値の道を優先して進む 仕組みになっています。
- スタート地点を確認する
- 今いる場所から行ける道を調べる
- できるだけ短いルートになりそうな道を選ぶ
- ゴールに着いたら終了
- どの道を通ったのかを記録し、最短ルートを作る
この流れを何度も繰り返して、最も早くゴールにたどり着けるルートを見つけます。
- ゴールのノードを設定
- スタート地点から周囲のノードのコストを調べる
- より良いコストを探していく
基本的にはゴール地点にたどり着くまで3を続けるという処理になります。
A*のヒューリスティックコスト
A*で面白いのはヒューリスティックコストと呼ばれる推定コストの概念です。ヒューリスティックコストをどのように計算するかで経路探索挙動が大きく変わってきます。
今回の実装では各ノードからゴールまでの直線距離を推定コストとしました(単純なので)。
ここの値を工夫することで、探索結果が大きく変わってくるため自分で実装する際にはいろいろと試してみてください。
オオバ製A*の使い方
今回オオバが開発したA*の使い方を解説します。
まずはA*インスタンスを初期化します。その後以下の処理を実装します。
- 開始ノード
- ゴールノード
- 結果注入用リスト
これらをA*インスタンスに渡すと経路の結果が帰ってきます。
そして経路結果をViewに反映させれば、先のサンプルのようなものが作成できます。
障害物を避けるA*
経路探索で重要なのは障害物を避けることです。
このように障害物(紫色のタイル)もちゃんと避けて経路探索してくれます。
_astar.SetLock(lockNodeId, isLock);
上記ソースコードにようにA*インスタンスに SetLock メソッドでロックをセットすることで障害物にすることができます。
記事の最後でA*とサンプルをセットにしたUnityプロジェクトを公開しているので参考にしてみてください。
まとめ
本記事ではUnityでA*アルゴリズムを実装してみるということをテーマに解説してきました。
A*を使うことで経路を探索するゲームが作れるようになり、アイデアの幅が広がります。キャラを障害物を避けて動かしたり、ゴール地点に自動で移動させたい方は参考にしてみてください。
注意点としてはA*は長い距離を操作したり、障害物が多かったりするとCPU負荷が高くなります。この辺はC#JobSystemを使って処理を逃がすなど工夫ができそうです。
今回作成したA*およびサンプル含めた全ソースはこちらにアップしています。興味ある方はさんこうにしてみてください。
筆者のXをフォローしよう
- Unity6000.0.32f1