ダイクストラ法による最短ルートの求めかた

ダイクストラ法と呼ばれるアルゴリズムを使って最短経路問題を解いてみます。

ダイクストラ法アルゴリズムで最短ルートを求める

サンプルプログラムとソースコード

ダイクストラ法と呼ばれているアルゴリズムを使って最短経路問題を解くプログラムです。
スタート、ゴール地点を指定するとリアルタイムで答えが分かります。
ノード（点）の追加、削除もできます。

プログラムをダウンロード
プログラムとソースコードをダウンロード

使用ツール:VC++2008 ExpressEdition
C(C++)言語とWin32APIでプログラミングしてます

解説

CPUキャラクターを目的地へ誘導したい

これから「キャラクターを目的地へ誘導する」ことについて考えてみます。
ゲームプログラミングには避けて通れないアルゴリズムですね。

スタートからゴールの間には壁があるのでまっすぐ進めませんが、
線でつながる各ポイントを通過すれば壁に当たらず進めることが分かっています。
この線から最短経路を探して目的地へたどり着けるでしょうか。

ダイクストラ法アルゴリズムの解説

ダイクストラ法が何かを解説すると余計に難しくなるので省略しますが、
ダイクストラ法アルゴリズムを使う最大のメリットは、
「不要な経路が分かった時点で以降の計算を省略できる」
これに尽きます。
ではさっそく。一つ例を説明していきましょう。

さきほどの図です。スタート点をA、ゴール点をFとします。
青い数字は、それぞれの点間の移動に要する距離です。

■Aの一つ隣の点を調べます

Aの隣はBとCです。
BとCの各点にAからの検索がきたこと、そしてスタート地点から移動に要した距離をセットします。
両方とも「Aの10」になりますね。

さて次はAの隣、BとCについて調べていきましょう。

■Bの一つ隣の点を調べます

Bの隣はA,C,Dです。
Dにはこれまでと同じ方法で「Bの18」をセットできます。

ここからが大事なところです。

BからCへ向かうルートをたどるとき、Cはすでに一度探索が行われています。
Cが未探索であれば、Cには「Bの20」をセットするはずですが、
セットしたい距離よりも小さな距離が既に入っている時はセットできません。

この時にA→B→Cを通るルートが最短距離になり得ないことが判明します。
A→B→Cを通るルート検索は以降省略できます。

B→Aについても同様ですね。
Aはスタート地点です。ここには距離「0」が入っています。
小さな値の入った点には進めないので戻るルートをたどることもありませんね。

■もしも検索済みの点よりも小さい値がセットできたならどうでしょうか

図は点CからBを検索した場合です。さらにこのとき「AB間の距離を５」、そして「BC間の距離が２」としました。A→B→Cは距離７になります
Bはすでに検索済みですがより小さな距離が入る場合は距離を再セットして計算を続けます。

なのでBの隣のD,C,Aが再び検索の対象になります。

■同じように処理を続けていくと

未処理の点あるいは最小値を更新しながら次の点をたどっていくと、たどれる点が無くなります。

これで計算完了です。

計算はゴール地点から

さて、ひとつ上の図を見てみて下さい。ダイクストラ法の計算が終わると各点にはスタート地点へ向かう隣の点が記憶されています。
なのでゴール地点からそれぞれ記憶されている次の点をたどっていけばスタート地点への最短経路が分かりますが・・・

あれ?

もしかしてゴール点から計算したほうが良かったのでは？

そうなのです。ゴール点から計算すればスタートから順に点をたどれました。
そしてどの点からもゴールへ向かう経路が分かります。
ということは、たった一回の計算で
複数のキャラを一斉に同じゴールに向かわせることもできるのです。

ゴール側から計算したほうがいいですね。

プログラミング

「ノード」と「コスト」

プログラミングする場合各点をクラスなどで定義することになりますが、この点を「ノード」と呼ぶことにします。
ノード間の移動に必要な距離を「コスト」と呼ぶにします。

ダイクストラ法は最短「距離」以外の計算にも使えます。
「ノード」と「コスト」で繋がった関係であれば時間やお金の計算などいろいろな物に置き換えて計算できるのです。
ただし、
マイナス値のコストがある場合このアルゴリズムは使えないので注意してください。

(他のノードの値を補正してマイナスにならないようにノードを作るとかすれば、工夫次第でダイクストラ法も使うことができると思う)

ノードが持つ情報

各ノードにには少なくとも次のような情報が必要になるはずです。

・自分のノードに接続しているノード
・接続されたノードへ行くためのコスト

　これらはノードのおかれている立場ですね。
接続されるノードは一つとは限りません。配列やリスト構造になると思います。
ノードの環境の作り方はサンプルプログラムをダウンロードして参考にしてみて下さい。

・探索済みのノードであるか
・自分のノードへたどるのに要した始点からのコスト

　ダイクストラ法の計算結果を各ノードに書き込むために必要になります。
コストが負の値だと計算できないことに注目して「負の値の時は未探索」とすると、フラグ分のメモリを稼ぐことができますね。

・探索されたときの探索元となるノード

　おっと。これがないと経路が分かりませんね。
探索はゴールから行います。計算後、各ノードから探索元をたどっていくといづれゴール地点に到達できます。


//他のノードへの接続情報
struct NodeConnect {
    Node*  node;//移動先ノード
    int    cost;//移動にかかるコスト
};

//ノード
struct Node {
    std::list m_connectNode;  //接続しているノード
    int	  cost;   //探索に要したコスト。-1の時はそのノードを未探索としています。
    Node* toGoal; //ゴールへの最短ルートにつながるノード
};

ダイクストラ法アルゴリズムの記述例

公開しているソースコードから抜粋しました。計算の核心部です。
もうちょっといい方法があるかもしれませんが・・・


Node* start;
Node* goal;
std::list nodelist;

void SearchRoot(){

    //全ノードの計算結果をリセット
    std::list::iterator it = m_node.begin();
    for ( ; it != m_node.end(); it++ ) {
        (*it)->cost = -1;
        (*it)->toGoal = NULL;
    }

    std::list work1;
    std::list work2;

    std::list* currLevel = &work1;
    std::list* nextLevel = &work2;
    std::list* for_swap;//currLevelとnextLevel入れ替えに使う

    //ゴールから計算します。
    goal->cost = 0;//ゴールにコスト0をセットして計算済みとする
    currLevel->push_back(goal);//検索第一階層のノードセット(ゴールノードをセットする)

    std::list::iterator it;
    int nodeCost;
    while ( currLevel->size() ) {

        for( it = currLevel->begin(); it != currLevel->end(); it++ ) {

            //次のノード階層へ進めるなら、nextレベルに格納
            std::list::iterator it_cnct = (*it)->m_connectNode.begin();
            for( ; it_cnct != (*it)->m_connectNode.end(); it_cnct++ ) {

                nodeCost = (*it)->cost + it_cnct->cost;

                if ( ( it_cnct->node->cost == -1 ) || ( nodeCost < it_cnct->node->cost ) ) {
                    //未探索ノードあるいは最短ルートを更新できる場合

                    //経路コストとゴールへ向かうためのノードをセット
                    it_cnct->node->cost = nodeCost;
                    it_cnct->node->toGoal = (*it);
                } else {
                    continue;
                }
                //次に検索する階層のリストに登録
                nextLevel->push_back( it_cnct->node );
            }

        }

        //リストを入れ替えて次の階層を検索する
        for_swap = currLevel;
        currLevel = nextLevel;
        nextLevel = for_swap;
        nextLevel->clear();//クリアする
    }
}