A-starアルゴリズム

投稿者: | 2012年5月22日

更新履歴

  • 2014.7.25 : 文章がおかしいので色々修正。Openする条件の説明が分かりにくいので修正
  • 2014.7.25 : 高速化のヒントを追記

(2015/1/21 追記) Qiitaにより詳しい実装方法を書きました。こちらのほうがわかりやすいと思います。

1.はじめに

ここではA*アルゴリズムによる経路探索を解説します。

A*を使うと何が嬉しいのかというと、上のように、開始点と終了点の間に「障害物」が存在する場合でも、最も効率の良い経路が探索できます。

これに対して、例えばブレゼンハムの線分描画アルゴリズムでは、障害物があった場合に、障害物に引っかかって動かなくなってしまいます。

逆に欠点としてA*アルゴリズムは、比較的効率の良い探索を行いますが、やや重い処理となってしまうので、障害物がない場合には、ブレゼンハムの線分描画アルゴリズムを用いた方が、処理が軽くなります。

2.入力と出力

A*は地形に以下の情報を持たせます。

  • ステータス(None→Open→Closed)
  • 移動コスト
  • ヒューリスティック(推定)コスト
  • スコア
  • 親地形のポインタ

そのため、こんな感じの構造体を定義しておくといいかもしれません。

/**
 * A*構造体
 */
struct AStar
{
	enum __STATUS
	{
		NONE,
		OPEN,
		CLOSED,
	};
	__STATUS status; // ステータス
	int cost;        // 移動コスト
	int heuristic;   // ヒューリスティックコスト
	AStar *parent;   // 親A*のポインタ
	Vec2D pos;       // 座標
	// スコア取得
	int GetScore()
	{
		return cost + heuristic;
	}
	
};


3.アルゴリズム

流れは以下のようになります。

最初の地形は全て、ステータスを「None」とします。

そして開始点をOpenします。Open時には「移動コスト」「ヒューリスティックコスト」を算出します。

「移動コスト」とは開始点からの移動量です。(この場合は開始点なので、0になりますけれども)

「ヒューリスティックコスト」とはその地点から終了点までの「推定」の移動量です。これは推定なので、ブレゼンハムなどを用いて終了点までの「障害物を無視した」直線の移動量を算出します。

「親地形のポインタ」にはNULLを入れておきます。

次に開始点をClosedします。Closedの処理としては、その点から8方向をOpenします。(※Openするのはステータスが「None」のもののみです。Open対象の地形が「障害物」もしくはステータスが「Open / Closed」であった場合は無視します

このとき、Openした地形に「親地形」のポインタを入れてやります。(ここでは開始点の地形ポインタですね)

ここまでで準備処理は完了です。

図に描くとこんな感じです。水色が開始点で赤色が終了点です。


そして、ここからがループ処理になります。まず、Openステータスの中に、終了座標に到達しているものを検索します。そして見つかれば、ループ終了です。

見つからなければ、Closedする座標を決めます。判断基準は、「スコア」です。

算出は以下の式になります。

スコア=移動コスト+ヒューリスティックコスト

Openステータスの中から、スコアが最も低いものを検索します。同じ値のスコアが見つかった場合はランダムで選びます。そして8方向をOpenしたら、自身をClosedします。そして、ループの先頭に戻ります。

最後に終了処理です。ここでは「移動経路のスタック」を作成します。

この段階では終了点をOpenできているので、その地形の座標を「移動経路スタック」に積みます。そして、親地形ポインタを辿り座標をスタックに積む…、ということを親地形ポインタがNULLになるまで繰り返します。

これで、「移動経路のスタック」が完成し、移動経路を辿ることができます

高速化のヒント

A*アルゴリズムは重たい処理なので、実際に使用するには処理を軽くするための工夫が必要となります。その例を以下に示します

  • 移動経路をキャッシュする
    • 計算結果をメモリ上に保持しておき、毎フレーム経路を計算しないようにします
  • 計算を数フレームに分けて行う。もしくは処理を別スレッド化する
    • 処理落ちが発生しないように、一定時間(一定範囲)を検索したらいったん処理を打ち切り、次のフレームで続きを計算します
    • そして経路が確定したら移動するようにします
    • 計算フレームを分けることでオブジェクトの配置が変わり、間違った経路となる可能性がありますが、衝突した場合には再計算を行うことで回避します
  • 目標座標が遠い場合は計算しない
    • 広大なマップで、目標座標が遠すぎる場合は何もしないで待機させます
    • 例えば、敵がプレイヤーを追いかけるときにA*を使用する場合、「遠いから気づかなくて当然だよね」という仕様で割り切ることも可能です