最短経路を探す

C#

ゲームを作ろうとすると、高確率で必要になるのが経路探索です。
メジャーなやり方は以下です。

  • ダイクストラ法
  • A*探索

2種書いてますがどっちもほぼ同じです。

簡単に説明すると、ダイクストラ法はあるノードから隣接ノードをたどり、その隣接ノードに辿り着くのに掛かったコストを記録していく方法です。
例を見た方が分かりやすいので、簡単な例を提示します。

例 ダイクストラ法

AからEに辿り着くルートを計算します。

ⒶーーⒷーーⒸ
│  │  │
└ーーⒹーーⒺ

探索1回目

Aが出発点なので隣接ノードを探します。
BとDですね。

Bへの到達コストはー2本なのでコスト2です。
Dへの到達コストはー4本なのでコスト4です。

この時点でBノードにはコスト2、Dノードにはコスト4と記録します。
またB,Dそれぞれに直前ノードはAであると記録します。
Aノードは探索が終わったので探索済みにします。

A:コスト0 直前ノードなし 探索済み
B:コスト2 直前ノードA 未探索
D:コスト4  直前ノードA 未探索

探索2回目

続いてBとDの内、コストの低い方から探索を開始します。
今回はコスト2のBです。

Bからの接続ノードはCとDです。
Aも接続していますが、これは探索済みのノードのため無視します。

BからCへの到達コストは2です。AからBの到達コストは2なので合計コスト4です。
BからDへの到達コストは1です。AからBの到達コストは2なので合計コスト3です。

ところがDは1回目の探索で既にコスト情報やノード情報を持っています。
なのでどちらの探索が有利か検討します。

A-B-Dはコスト3です。
A-Dはコスト4です。

ということはA-B-Dの方が有利ですね。
なのでDの情報をコスト3 直前ノードBで上書きします。

A:コスト0 直前ノードなし 探索済み
B:コスト2 直前ノードA 探索済み
C:コスト4 直前ノードB 未探索
D:コスト3  直前ノードB 未探索

探索3回目

また未探索のノードの中からコストの低いノードを選びます。
つまりコスト3のDです。

Dからの接続ノードはA, B, Eです。
ABは探索済みのため、Eのみ計算します。

DからEの到達コストは2です。AからDの到達コストは3なので合計コスト5です。
ここでEに到達したため探索は打ち切ります。

今回はCからのノード探索を行っていません。
厳密には全てのノードを探索すべきですが、全ノード検索は時間もかかるし計算量も肥大化するので通常は発見時点で打ち切ります。
もしCからEのコストが0.5だった場合、A-B-D-EよりA-B-C-Eのルートの方がトータルコストは安くなるわけですが、その辺はどこまで厳密さを求めるかですね。

例 A*探索(えーすたー)

A*探索はダイクストラ法の改良版です。
少しだけ例を改変します。

ーⓏーーⒶーーⒷーーⒸ
    │  │  │
    └ーーⒹーーⒺー

このような例の場合、AからEへのルートを探索する際に、Z方向の探索って必要だと思いますか?
もしかしたらC, DからEへのルートが繋がっていない可能性もあるので、実はZルートが最短だった、というケースもあるかもしれません。でも確率的には低そうですよね?

ダイクストラ法でやる場合、BとZのコストは2で等価となるため2回目の探索がZから始まるかもしれません。もしそうなったら不要な計算を挟むことになり、時間をロスしますよね。

そこでA*探索の出番になります。
ダイクストラ法で等価となってしまう問題に対して、適切な重み付けを行うことでより可能性が高い方を優先させます。

今回のケースでいうと、BとZならBの方から探索した方が最短の可能性が高そうです。
なぜ直感的にそう思うかというと、B-E間とZ-E間の物理的な距離を比べるとB-E間の方が短いからです。人間はこういった予測を立てますので、似たような方法で重み付けを行います。

つまりBとZは共にコスト2だけど、BE間の距離は3、ZE間の距離は5というように別の指標を与えます。これでBはコスト合計5, Zは合計コスト7と差が生まれます。
これにより優先順位を変えて、より計算時間が短くなるようにします。

とはいえ完璧ではないため、却って計算量が増える場合もありますので良し悪しです。
またもう1つ重要な点は、別の指標を与えるときに、その数字が実コストより大きくならないようにすることです。

極端な例だと、A-Eの実コストが5なのに、別指標のコストを10とかで計算すると、重み付けが破綻してしまうので注意です。

ソース

Dictionary<Hex, float> dist = new Dictionary<Hex, float>();
Dictionary<Hex, Hex> prev = new Dictionary<Hex, Hex>();
List<Hex> unvisitedHexes = new List<Hex>();

Hex source = selectedUnit.Hex;
Hex target = hex.GetComponent<Hex>();

foreach (var h in map.Hexes)
{
    if (h != source)
    {
        dist.Add(h, Mathf.Infinity);
        prev.Add(h, null);
    }
    else
    {
        dist.Add(h, 0);
        prev.Add(h, null);
    }

    unvisitedHexes.Add(h);
}

while (unvisitedHexes.Count > 0)
{
    Hex closestHex = null;

    foreach (var possibleHex in unvisitedHexes)
    {
        if (closestHex == null || dist[possibleHex] < dist[closestHex])
        {
            closestHex = possibleHex;
        }
    }


    if (closestHex == target)
    {
        break;
    }

    unvisitedHexes.Remove(closestHex);

    foreach (var neighbour in closestHex.Neighbours)
    {
        float alt = dist[closestHex] + map.CostToEnterTile(neighbour);

        if (alt < dist[neighbour])
        {
            dist[neighbour] = alt;
            prev[neighbour] = closestHex;
        }
    }
}

if (prev[target] == null)
{
    return;
}

var path = new List<Hex>();
Hex pathHex = target;

while (pathHex != null)
{
    path.Add(pathHex);
    pathHex = prev[pathHex];
}

path.Reverse();

this.selectedUnit.CurrentPath.Clear();
this.selectedUnit.CurrentPath.AddRange(path);

簡単な解説。

Dictionary dist = new Dictionary();
Dictionary prev = new Dictionary();
List unvisitedHexes = new List();

まずはコストを計算する変数dist(Distance)のリストを作ります。
次に直前のノードの情報を格納するprevのリストを作ります。
そして調べるノートの一覧を作成します。

最初のforeach文で値を初期化します。
コストが小さいかどうかを判定するので、Infinityとか10000とかとにかく大きな値を入れましょう。

あとはWhile文で調べるノードが無くなるまで繰り返します。
コストが最小なノードを選んで、その隣接ノードをすべて評価します。
調べ終わったら探索済みのノードをリストから削除して、また次の探索を行います。

探索が目的地点に到達した時点でWhile文はbreakして抜けます。
あとは到達ノードから順に直前ノードをたどれば経路の完成です。
実際にユニットを動かす場合にはSource→Targetに向かって動かすので、最後にReverseしています。

コメント