ある地点からある地点まで移動する際のルートを調べたい。
そのルートが最短であってほしい。
ゲームの自動行動や敵AIなどを作るのに使ったりする「経路探索」の考え方と「A*アルゴリズム」について解説する。
経路探索の基本
そもそも経路探索は何をするのか？
ざっくり
スタート地点から移動可能な場所を調べる。
調べた移動可能な場所から、また移動可能な場所を調べることを繰り返す。
ゴールへたどり着いたら探索完了である。
経路を作るには、ゴールへたどり着く一つ前の場所、そこからまた一つ前の場所と、逆を辿る。
こまかく
調べた移動可能な場所は「ノード」と呼ばれる。
このように「調べる」ことを「ノードを展開する」とも言ったりする。
一か所を調べて得られるノードは大抵の場合一つではない。
そのため、展開したノードは何らかのデータ構造によって管理される。
配列(可変長)、キュー・スタック、二分ヒープなどだ。
ノードには以下の情報を持たせる。
- 自ノードから他ノードを展開するための情報(X, Y座標など)
- ゴールから逆を辿り経路を作成するための「自ノードの展開元のノードのポインタ」
他にも移動時の向きや行動内容などを含ませることがある。
一度探索した場所を再度探索することは原則行わない。
同じルートをぐるぐる調べ続けることになるためだ。
最短経路を知るには
最短経路を知るには、展開したノードをスタートから近いものから優先して調べることが重要。
それがダイクストラ法である。
近いというのは移動コストのことであり、このようなグリッド構造では「歩数」ともいえる。
このコストには加算ができる。
- 険しい山道なので移動が遅いので+1
- 毒沼はできれば通りたくないので+100
というのが一例で、状況を考慮に入れた最短経路探索というのも出来る。
移動コストは重みとも呼ばれる。
グリッド構造で各ノード間の移動コストが均一であり、重みを考慮しなくていいという場合、先に見つけたものから優先*1して調べる「幅優先探索」でも同様に最短経路が求められる。
A*アルゴリズム
ダイクストラ法の移動コストに
「自ノードからゴールまでの予想距離」を加えたものが
「A*(エースター)アルゴリズム」である。
評価のよい(値の低い)ノードから優先して探索が進められる。
ゴールとは反対方向も均一に調べるダイクストラ法に比べ、A*は場合によってはゴールに一直線。
評価に使う予想距離の計算式は、移動方法によっても変わる。
- 上下左右 →
*2
この予想距離の計算に用いられる関数は「ヒューリスティック関数」と呼ばれる。
ノードを管理するデータ構造
ダイクストラ法やA*では、評価の良いノードから優先して探索していく。
そのため、複数ある探索予定のノードから最良のノードを探して取り出すことが繰り返される。
ノード管理をごく普通の配列で行えば、最良ノードを知るのには線形探索、取り出しでは大移動と効率が悪い。
そのため、最小値を一手で知れて、要素の追加・削除も高速な「ヒープ」がよく用いられる。
ヒープにはそのままノードを放り込むこともあれば、ヒープ+配列で管理することもある。
各ノードの評価値がばらける場合は前者、良くて数通りなら後者の方が効率が良いだろう。
なお
- A*アルゴリズム
- 上下移動のみ考慮 → 予想距離 =
という組み合わせであれば、評価値は常に2通りとなる。
2つの配列 low・high を入れ替えながら管理すれば効率もいいし実装も簡単。
A*の手順(概略)
- nodes → ノードを管理するデータ構造。
- current_node → 現在のノード。展開を行う基準地点
- goal_node → 基本は空。ゴールにたどり着いたノードを代入
nodesが空になるまでループ↓
- current_node = nodesから最良のノードを取り出し
- current_nodeをもとにノードを展開する。
- 移動可能であること、既に展開されたことのあるノードでないことを確認。
- ゴールに到達したノードであれば、goal_nodeに代入。
- ノードには座標、スタートからの重みの累計(合計歩数)、親ノードなどの情報を持たせる。
- 予想距離を計算。親の重み+親から自ノードへの重みを足したものが評価となる。
- 評価の値を添えてnodesにノードを追加。
- goal_nodeが存在すればループ中断。
goal_nodeが空でなければルートを作成する。
ワンポイント
- 調べるノードが多すぎて処理が重い場合、ノードの作成数をもとにループを打ち切らせる。
最良ノードを記録しながら探索すれば、ある程度の精度での最短経路は見つけてくれる。 - グリッド構造では移動時の向きを考慮すれば、ノードの展開時、調べるマスを一か所減らせる。
