概要

　経路探索の手法として代表的なものにA-star法がありますが，単純にマップをグリッド状に区切ってノードを設定した場合，目的地までの距離が長くなるにしたがって計算時間が長くなる問題があります．そこで，今回は目的地までの距離に大きく依存しないような経路探索方法をご紹介します．なお，調べてみたらほかにもこの方法を紹介しているものがありましたが，本記事では手法の詳細まで踏み込んで解説します．また，基本的な部分はA-star法と同じですので，A-star法について知っておくと理解しやすくなると思います．
　なお，後述しますが開始点から目的地までを直線で結んだ際に通過するオブジェクトが多い場合，A-star法のほうが処理がはやいときがあります．今回ご紹介する方法は「マップが広大」「オブジェクトの数が多くない」「階層がない」ときに有用だと考えています．

探索方法（概要）

　詳細な説明に入る前に，さらっと雰囲気だけ説明しておきます．まず，ユニット（移動させたい対象）の位置から目的地までRaycastします．オブジェクトにぶつからなかったら処理を終了します．オブジェクトにぶつかったら，そのオブジェクトからRaycastの起点に応じた「コーナー」位置を取得します．そして，今度はコーナー位置に向けて再びRaycastします．ここでオブジェクトにぶつからなかったら，次のRaycastの起点の候補として保存します．オブジェクトにぶつかったら，再度そのオブジェクトからRaycastの起点に応じたコーナー位置を取得して，その位置に向けてRaycastをします．Raycastの起点の候補をすべて取得したら，予想コストが最も小さいノードを次のRaycastの起点として，ゴールへ向けてRaycastします．これを繰り返していき，オブジェクトに阻まれることなくゴールへRaycastできたら処理を終了します．

【図1】処理の流れ
（（左上）StartからGoalに向けてRayを照射する．（上）左下のオブジェクトからコーナー位置を取得する．オブジェクトに対して左下がRaycastの起点となっているので，左上と右下のコーナー位置を返している．（右上）予想コストが最も小さい右下のノードを起点として，Goalに向けてRaycastする．（左下）真ん中下のオブジェクトからコーナー位置を取得する．真下がRaycastの起点となっているので，左下と右下のコーナー位置を返している．（下）右下のノードを起点として，Goalに向けてRaycastする．ここで，Goalへオブジェクトに阻まれることなく到達したので処理を終了する．（右下）最終的に，緑色の線が得られる経路となる）

コーナーの設定

　回避したいオブジェクトに対しては，図2のようにあらかじめ「コーナー」を設定しておきます．また，Raycastの起点となる位置に対して返すコーナーの位置を決めておきます．例えば起点が右上のときは左上と右下のコーナーを返すように設定しておきます．また，真上に対しては右上と左上を返すようにします．なお，実際はコーナー位置への参照を返すようにして実装します．これは，そのコーナーをチェックしたかを確認するためです．
　さらに，各コーナーに対して2つの情報を持たせます．ひとつは「そのコーナーがノードとして使用されたかどうか（フラグA）」，もうひとつは「そのコーナーがRaycastの対象となったかどうか（フラグB）」です．

【図2】 Raycastの起点と，返すコーナーの位置の関係
（黄色と緑色の点がRaycastの起点，青色の点がコーナーの位置である．四角いオブジェクトに対しては，Raycastの起点を右上，右下，左上，左下，上下左右の8方向にわける）

探索方法（詳細）

　それでは，実際に処理の流れを示しながらより詳細な処理方法を説明します．また，右側だけに着目して説明するために，左側に壁（黒く塗られた領域）を設定しています．
　なお，チェックした地点の情報を記録するためにノードクラスを作成して使用しますが，ノードに持たせる情報としては以下の項目を使用します．

親ノード
ノードの位置
実コスト（スタートからそのノードまでの経路をたどったときの距離）
予想コスト（実コストと，ゴールまでの距離の和）

【図3】ユニット，ゴール，オブジェクトの位置関係（ユニットは緑色，ゴールのはオレンジ色で示している．また，オブジェクトを識別するために0から3の番号を割り振っている）

【図4】処理の経過

【処理開始】

すべてのオブジェクトの，すべてのコーナーのフラグAをfalseにします．
ユニットの位置を，ノードリストに追加します．このとき，親ノードはnullにしておきます（ノードは親ノードと位置，実コストと予想コストの値を持ちます）．

【ループAの1周目】

すべてのオブジェクトの，すべてのコーナーのフラグBをfalseにします．
ノードリストのうち，最も予想コストが小さいノードを基準ノードとして取得し，基準ノードの位置からゴールに向けてRaycastします（図4左上）．さらに，基準ノードをノードリストから削除します．最初なので，当然ユニットの位置がRaycastの起点となります．
オブジェクト0に真下からぶつかったので，右下の位置を次のステップのRaycastのターゲットとしてリスト（ターゲットリスト）に追加します．

【ループBの1周目】

オブジェクト0の右下のコーナーに向けてRaycastします（図4上）．また，オブジェクト0の右下のフラグBをtrueにし，ターゲットリストから削除します．結果としてオブジェクト2に左からぶつかったので，オブジェクト2の左上と左下の位置をターゲットリストに追加します．

【ループBの2周目】

オブジェクト2の左上に向けてRaycastします（図4右上）．オブジェクト2の左上のフラグBをtrueにし，ターゲットリストから削除します．結果，オブジェクト0に下から当たりましたが，オブジェクト0の右下のフラグBはtrueなので，ターゲットリストにその位置を追加しません．

【ループBの3周目】

オブジェクト2の左下に向けてRaycastします（図4右上）．オブジェクト2の左下のフラグBをtrueにし，ターゲットリストから削除します．結果，オブジェクトに当たることなくその地点へRaycastできたので，親ノードを基準ノード，位置をオブジェクト2の左下としてノードを作成し，ノードリストに追加します．さらに，オブジェクト2の左下のフラグAをtrueとします．
また，ここでターゲットリストが空になったのでループBを抜けます．

【ループAの2週目開始】

すべてのオブジェクトの，すべてのコーナーのフラグBをfalseにします．
ノードリストから，最も予想コストが小さいノードを基準ノードとして取得し，基準ノードの位置からゴールに向けてRaycastします（図4左下）．さらに，基準ノードをノードリストから削除します．今回はオブジェクト2の左下の位置が基準ノードの位置となります．
オブジェクト0に真下からぶつかったので，右下の位置を次のステップのRaycastのターゲットとしてリスト（ターゲットリスト）に追加します．

【ループBの1週目開始】

オブジェクト0の右下に向けてRaycastします（図4下）．オブジェクト0の右下のフラグBをtrueにし，ターゲットリストから削除します．結果，オブジェクト3に左から当たったので，オブジェクト3の左上と左下の位置をターゲットリストに追加します．

......以降は割愛しますが，結果として図のような経路が得られます．

【図5】得られる経路

長くなりましたが，大切なのは

処理のはじめにすべてのフラグAをfalseにする．
基準ノードを選択してゴールに向けてRaycastする前にすべてのフラグBをfalseにする．
ターゲットリストに追加する前に，そのオブジェクトの該当のコーナーのフラグBがfalseであること確認し，ターゲットリストに追加するときにtrueとする．
ノードリストかに追加する前に，そのオブジェクトの該当のコーナーのフラグAがfalseであることを確認し，ノードリストに追加するときにtrueとする．

といったところです．

計測

　それでは，実際に使用・計測してみます．まずは図6左のようなマップで左上，右下を対角に移動したときの時間を計測します．なお，マップのサイズは101x101です．青色の物体が避けるべきオブジェクトです．

【図6】オブジェクトが少ないマップと，経路探索の様子
（赤い線が，ゴールへ向けたRaycastで，青い線がターゲット地点に向けたRaycastで発射したRayを表す．Raycastの回数が少ないことがわかる）

結果としては

Raycastによる経路探索：2 ms程度
A-starによる経路探索：38 ms程度

となりました．しかし，図7左のように，オブジェクトを増やすと

Raycastによる経路探索：48 ms程度
A-starによる経路探索：33 ms程度

となり，避けるべきオブジェクトが増加すると処理が遅くなる弱点が響いてきます．

【図7】オブジェクトが多いマップと，経路探索の様子
（Raycastの回数が多く，処理の負担が増していることがわかる）

　また，図8のような迷路のマップでは，そもそもゴールまで到達できませんでした．確認してみると，深いところまで進んだ挙句行き止まりだったとき，戻り切れていないことがうかがえます．さらに調べてみると，図8右のような囲まれ方をされた場合ゴールまで到達できないことがわかりました．とにかく，迷路を解く方法としては適していないと言えるでしょう．

【図8】迷路で実行したときの様子と，経路探索に失敗する場合の例
（赤い球体がユニットを表す．ユニットの両脇に壁がある場合は，ゴールから遠ざかる方向にも経路探索を行うが，ユニットの両脇に壁がない場合はノードがゴールから遠ざかる方向に設定されないため，経路探索に失敗してしまう）

　ただし，マップをグリッド状に区切る必要がないので，図9のようにオブジェクトがZ軸，X軸に沿って配置されていないときにも無駄なく経路探索できるのはひとつメリットとして挙げられると思います．

【図9】ランダムにオブジェクトが配置されたマップでの経路探索の様子

参考

同様の方法が別の場所で紹介されていたので，掲載しておきます．

A-star法について．

NavMeshについて．経路探索にはこれを使えばいいと思います（使ったことはないですが，とても便利そうです）．

実験用のプロジェクト．