経路探索といえば、A*(ｴｰｽﾀｰ)アルゴリズムが有名ですよね。
これはまあ、非常に効率的なアルゴリズムとして知られているわけですが、
実際ゲームに組み込むと割と遅いと感じられる場面もしばしば。
とくに、ゲームワールドが巨大だったり、ユニット数が膨大だったりすると、
もはやゲームとして成立しないほど、遅くなることもあります。

もちろん、これを回避する方法というものは幾つも考えられています。
その中でも、有名・簡単・単純なものを紹介しようと思います。

HPA*【hierarchical pathfinding A* algorithm】
ヒエラルキーといえば階層を意味する通り、これは階層的に経路探索を行うアルゴリズムです。
そう言われてもよく分からないと思うかもしれませんが、意外とこれは私たち人間の思考に即しています。

例えば、今、東京駅にいるとします。そして、北海道(例えば千歳?)に行く経路を考えます。
思考の例：
[東京都] → [北海道]
[東京駅] → [羽田空港] → [千歳空港]
[東京駅] → [浜松町駅] → [羽田空港第一ビル駅] …
・・・
このように、まずは大雑把な経路を考えて、
それをどんどん具体化していくような思考を辿ると思います。
北海道へ行くのに、埼玉へ行く経路なんて考えるだけ無駄なんです。


このような、階層的な経路探索を実装したのがHPA*です。
さっきは大雑把な経路といいましたが、カッコイイ言い方をすれば抽象度が高い経路と言えます。
HPA*は次の２つのステップを踏みます
１．構築アルゴリズム
２．探索アルゴリズム


◯構築アルゴリズム
このステップでは、抽象グラフというものを作成します。
抽象グラフは要は元のグラフから重要なノードだけを取り出して、他の除いたものです。
具体的には、次のような手順を踏みます

1. グラフをいくつかのクラスターに分割する
2. 各々のクラスターを繋ぐ玄関口を作成する、
　　すなわち、クラスターの境界付近にあるつながったノードを抽出する
　　それを抽象ノードとし、適当な数を配置する
3. 抽象ノードをエッジで繋ぐ、この時、コストは元のグラフでのコストとする
　　ただし、繋ぐ物は隣接するか、同じクラスターに属するものである

●探索アルゴリズム

1. スタートノード、ゴールノードに最も近い抽象ノードを調べる
2. 抽象グラフにおいて、それらのノードをもとに経路を計算する
3. 得られた経路をもとに、元のグラフでの経路を計算する

クラスターとは、幾つかのノードの集まりです。
要は、ワールド中に配置されているノードを一定の方法でまとめたものです。
ですから、HPA*ではある意味このクラスターをあるノードとして考えたものとも言えます。
クラスター同士は隣接しているので、それらを繋ぐ玄関口が必要です。
ここに、要は重要なノードたる抽象ノードを配置するのです。
HPA*では、この抽象ノード(とエッジ)の経路を計算し、
それを元のグラフに落とす、といった方式を取ります。

まあだらだら書いてもしょうが無いので、百聞は一見にしかず、画像で見てみましょう。 これが元のグラフです。
Sと書いてあるのがスタートノード、Gがゴールノードです。
赤いグリッドは、A*で計算して得られた経路のノードで、
淡赤は、A*で展開されたノードを表しています

これを、クラスターに分割し、抽象ノードを配置したものが下です 今回は、10x10のクラスターに分割しました。
青い枠がクラスターの枠です。
緑のノードが、抽象ノードです。

これにエッジで繋ぐと次のように成ります。 同じクラスター同士のモノがつながれていることが分かると思います。

抽象グラフの作成についてはなんとなく分かったでしょうか？
次にそこでの経路探索について見ていきます。


水色の線が経路です。
最もスタートノードに近い抽象ノードから、
最もゴールノードに近い抽象ノードへ経路が作られていることが分かると思います。

さて、これを元のグラフのレベルに落とすとこうなります

青色のグリッドは得られた経路、
淡青は展開されたノードです。
特に、展開されたノードに注目してください。かなり少なくなってることが分かると思います。
また、”最短経路”でないことも分かると思います。
ただし、経路の平滑化を行うことで、経路はもっとピンとしたものにすることは可能です。


上の例では、もともと展開されているノードは大した数ではないので、
障害物を配置して恣意的に展開ノードが多くなるようにしたものを幾つか掲載しておきます。
比べてみると、HPA*の効果を実感できると思います
（あと、障害物でクラスターが区切られた場合、どう抽象ノードが配置されるかどうかも割と重要かも…)







おまけ

あぁこれってHPA*っていうんですか
カーナビ見ててたぶんこんなアルゴリズムだろうなぁ～とか思ってたんですがやっぱちゃんとした名前があったんですね

そうですね、まあ、カーナビくらいになるともう少し複雑な設計にはなってそうなもんですが。
でもそう考えると、カーナビの導きだす経路は最短経路ではないというのもなんだか残念なきもちになりますね