【Unity】AStarアルゴリズムのサンプル

github.com

A* のアルゴリズムを組んで見たくて wiki を参考に作成してみました

A* - Wikipedia

アルゴリズム

アルゴリズムは wiki にあるとおりの順番で実装してあります

1

開始地点をオープン済みとして登録する

2

オープン済みのノードの中から一番コストが小さいノードを探す
※ コスト = 移動コスト + ゴールまでの推定コスト + 今までの移動コスト

この際にゴールだったら計算終了

current = _openHash.OrderBy(p => _map[p].Score)
    .OrderBy(p => _map[p].MoveCost)
    .First();

3

オープン済みノードから削除し、探索済みに登録

_openHash.Remove(current);
_closeHash.Add(current);

4

周りをオープンする

オープン済みで今のノードよりスコアが大きい場合はオープン済みから削除
探索済みで、今のノードよりスコアが大きければ探索済みから削除する

if (_openHash.Contains(pos))
{
    if (_map[current].Score <= _map[pos].Score + _map[current].MoveTotalCost)
        continue;

    _openHash.Remove(pos);
}

if (_closeHash.Contains(pos))
{
    if (_map[current].Score <= _map[pos].Score + _map[current].MoveTotalCost)
        continue;

    _closeHash.Remove(pos);
}

_openHash.Add(pos);

5

2に戻りゴールにたどり着くまで処理を繰り返す

内部の動き

オープンが緑、クローズが灰色、最後に決定したルートが赤で表示されます