合計 昨日 今日

アバター
MNS
 
記事: 35
登録日時: 2010年10月16日(土) 22:10
日記: 日記を見る (37)
日記
- 5月 2011
HPA* ... 経路探索の最適化 (2)
   2011年5月30日(月) 21:37
せっかく作ったんでコミュニティの紹介 (3)
   2011年5月05日(木) 21:15

+ 4月 2011
+ 3月 2011
+ 2月 2011
+ 1月 2011
+ 12月 2010
+ 11月 2010
+ 10月 2010
カテゴリー
フィード
次へ

HPA* ... 経路探索の最適化

パーマリンクby MNS on 2011年5月30日(月) 21:37

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

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

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

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


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


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

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

●探索アルゴリズム

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

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

まあだらだら書いてもしょうが無いので、百聞は一見にしかず、画像で見てみましょう。
graph.png
graph.png (4.46 KB) 表示数: 305 回

これが元のグラフです。
Sと書いてあるのがスタートノード、Gがゴールノードです。
赤いグリッドは、A*で計算して得られた経路のノードで、
淡赤は、A*で展開されたノードを表しています

これを、クラスターに分割し、抽象ノードを配置したものが下です
absgraph.png
absgraph.png (6.48 KB) 表示数: 305 回

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

これにエッジで繋ぐと次のように成ります。
absgraphwithedges.png
absgraphwithedges.png (15.4 KB) 表示数: 289 回

同じクラスター同士のモノがつながれていることが分かると思います。

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

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

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


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

おまけ
画像
画像
添付ファイル
最後に編集したユーザー MNS [ 2011年5月30日(月) 23:13 ], 累計 2 回

コメント数: 2 閲覧数: 29493

せっかく作ったんでコミュニティの紹介

パーマリンクby MNS on 2011年5月05日(木) 21:15

ゲームというものをやっていると、たくさんのゲームキャラクタたちに出会います
私たちゲームプログラマーというものは、それらゲームキャラクタの作り手からして、
ゲームキャラクタたちにとっての母であると言えましょう

さて、いざゲームをやればどうでしょう。同じ動きしかしない敵機、
ただ同じ方向に歩き続け、踏まれることを期待し続けるカメ、
壁にぶつかっては遠回りをし続けるお馬鹿なヒーロー。

彼等がこんなにも無惨な知能を持っているのは、全て私たちの責任です。
彼等は命の危機で合ってさえ、避けることすら許されないのでしょうか!?
否、彼等は頭上に迫るヒゲおやじを避けて床に叩きつけ、帽子を奪い去ることが許されてもいいはずです

そう、私たちには愛が足りないのです。ゲームキャラクタに対する愛が。

さあ、悔い改めましょう



画像
 AIの可能性は無限大

コメント数: 3 閲覧数: 29742

依存名の問題 (チャットでのまとめ)

パーマリンクby MNS on 2011年4月04日(月) 19:30

具体的にはこういうコードでエラーがでる問題
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
template <class T>
class   XClass
{
    std::vector<T> m_vec;
 
public:
 
    //m_vecの最初の要素を指すイテレータを取得
    std::vector<T>::iterator GetBeginItr(){ return m_vec; } //エラー!!
};


もっと分かりやすくすると、こう
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
template <class T>
class   Nantoka
{
    //クラスTに定義された型typeの変数
    T::type     m_value;  //エラー!!
 
public:
 
    Nantoka(){}
 
};
上のコードでもエラーがでます。

これは、依存名というものの問題で、
上のNantokaクラスでいえば、typeが依存名で、
これがテンプレートクラスTに依存している、ということです。

これらのエラーは、この依存名のあいまいさから起こります。
上の例では、typeは「型」ですが、依存名は型だけでなく、変数、関数、何でもあります。

さきの例では、typeは型以外ありえませんから、コンパイラだって分かるだろうと思われるでしょうが、
次のような使い方の時、問題がおきます。
コード[C++]: 全て選択
1
2
3
4
5
6
template <class T>
void    func()
{
    //クラスTに定義された型typeのポインタ
    T::type* local_ptr;  //エラー!!
}

これが何がまずいか、というと、
仮に、typeがstatic変数であるとすると、
T::type* loval_ptr → (T::type) × (local_ptr)
という積の式に解釈できてしまうことです。

コンパイラはどちらか判別できないので、
エラーになってしまうということでした。

これを回避するには、T::typeが型であると明示する必要があります。
それを行う演算子が"typename"演算子です。
よって、次のようになります。
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
template <class T>
class   Nantoka
{
    //クラスTに定義された型typeの変数
    typename    T::type m_value;
 
public:
 
    Nantoka(){}
 
};

これで、コンパイラは自信をもって、
T::typeが型であると判別することができます。

よって、最初の例に戻ると、
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
template <class T>
class   XClass
{
    std::vector<T> m_vec;
 
public:
 
    //m_vecの最初の要素を指すイテレータを取得
    typename std::vector<T>::iterator GetBeginItr(){ return m_vec.begin(); }
};

というコードになります。


チャットで解決に尽力した方々 → バグさん、Chocolaさん、kerotanさん、nissyさん

参考:http://www.fides.dti.ne.jp/~oka-t/cpplab-template-4.html
最後に編集したユーザー MNS [ 2011年4月04日(月) 19:34 ], 累計 1 回

コメント数: 0 閲覧数: 29134

RTS製作日記。その20

パーマリンクby MNS on 2011年3月27日(日) 08:44

特に進展してないんですが、とりあえず敵の簡単なAIを作ってみたので、
それを載せる目的で日記をかきます。

導入しようと言っていたGOAP(Goal-Oriented Action Planning)
どういうシロモノか結局よく分かりませんでした。
というか、うまい使い方があまり思いつきませんでした。
まあ、それでも何となくこうかな…って感じで埋め込んだんですが、
RTSとの相性は微妙そうだなと思ったりしなかったり。

正直現状では作れるのが兵舎、そして歩兵1種のみなので、
敵は完全に単一の戦略しか使ってきません。
しかも動きがなかなか素早いのでこちらもぱっぱとやんなきゃ多分全滅させられます。
あと、相変わらずゲームに終わりがないので、
敵の資源の供給を止めて、兵を全員倒したら終わりってことにしてください。

※いまさらファイルが古かったことに気づいて差し替えました(5/19)
RTS.zip
(1.03 MB) ダウンロード数: 409 回
添付ファイル
最後に編集したユーザー MNS [ 2011年5月19日(木) 19:45 ], 累計 1 回

コメント数: 0 閲覧数: 29096

RTS製作日記。その19

パーマリンクby MNS on 2011年3月20日(日) 23:05

#実装したもの
 ◎内政の概念 → 住民
             資源(とその生産)
             建物(とその建築)
             ユニット生産

*ゲーム画面+その説明:
myrts.png
myrts.png (202.06 KB) 表示数: 423 回


*ゲーム本体
RTS.zip
(984.83 KB) ダウンロード数: 342 回



本当は、AIを内政に対応させた上で記事を書こうと思ったんですが、
この内政の枠組みをつくるだけでも一苦労で、結構期日が開いてしまったので、
とりあえず途中経過という形で載せることにしました。
敵と戦えない以上、もはやゲームですらないですが、
とりあえず、RTSがどういったものか何となく伝わればいいなあ、と思ったり。
添付ファイル

コメント数: 3 閲覧数: 29697

オンラインデータ

登録ユーザー: なし