A*アルゴリズムをJava 6で書くと

A*は、障害のあるマップ上の始点から目標点までのルートを計算するアルゴリズムの最も代表的なひとつ。

普通の説明だと、マトリックスな配列形式のマップを使って、座標で中身を取り出しながら探索パスを増やしていったりするんだけど、そういう方法はとりません。3Dの場合や、そもそも座標系でない場合などにコードが対応できないし、xやy がどうこう、幅や高さがどうこうとか入っていると、アルゴリズムの本質も隠れてしまいがちになります。

ここではA*が解けるのに必要な構造をもった、抽象的に「位置」と「探索対象フィールド」を定義し、それにアクセスするアルゴリズムにしてます。コードはJava6を使っています。

問題の入力と出力

// 位置
interface Point {
  // 同値判定できる必要がある
  boolean equals(Object point);
  int hashCode();
}

// マップ
interface Field {
  // その位置に入れるかどうか
  boolean canWalkIn(Point point);
  // その位置に隣接する位置一覧
  Point[] neighbors(Point point);
  // その位置の目標からのスコア。
  // パスが伸びればその合計スコアは増えるように、正の整数である
  int score(Point goal, Point point);
}

という二つのクラスがある上で、

interface Solver {
  // フィールドと、始点と目標点を与えると、始点から終点までのルートパスを返す
  Point[] calc(Field map, Point start, Point goal);
}

この引数の情報で、結果として始点から目標点までのパスを、位置を移動順に並べたリストとして出すプログラムをかける。

A*

A*アルゴリズムは、ゴールにたどり着くまで総当り探索で調べるアルゴリズム。ただし、ポイントのスコア(単純にはゴールからの距離＋移動コストなど)があって、パス上すべてのポイントのスコアを合計した、パスのスコアの低い順に、パスを広げていくものになっています。

class AStar implements Solver {
  public Point[] calc(Field map, Point start, Point goal) {
    this.map = map;
    this.goal = goal;
    
    // 初期ポイント: (0, [start])
    visitedCache.add(start);
    ArrayList<Point> path = new ArrayList<Point>();
    path.add(start);
    ScoredPath spath = new ScoredPath(0, path);
    pathes.add(spath);
    
    return astar();
  }
  
  Point[] astar() {
    while (pathes.size() > 0) {
      // 一番スコアの低いパスを取り出し進める
      ScoredPath spath = pathes.remove(0);
      Point current = spath.path.get(spath.path.size() - 1);
      // ゴールに着いていたら終了
      if (current.equals(goal)) {
        return spath.path.toArray(new Point[spath.path.size()]);
      }
      // 隣接するポイントごとに...
      for (Point next: map.neighbors(current)) {
        // すでに通ってたらスルー
        if (visitedCache.contains(next)) continue;
        // 通ったしるしをつける
        visitedCache.add(next);
        // 入れなければスルー
        if (!map.canWalkIn(next)) continue;
        // パスに追加し、そのパスのスコアを計算
        ArrayList<Point> path = new ArrayList<Point>(spath.path);
        path.add(next);
        int score = spath.score + map.score(goal, next);
        // スコア順になるよう、この新たなパスを挿入
        insert(score, path);
      }
    }
    // もう行ける場所がなく、到達不能。
    return null;
  }
  
  void insert(int score, ArrayList<Point> path) {
    for (int i = 0; i < pathes.size(); i += 1) {
      ScoredPath spath = pathes.get(i);
      if (spath.score >= score) {
        pathes.add(i, new ScoredPath(score, path));
        return;
      }
    }
    pathes.add(new ScoredPath(score, path));
  }
  
  Field map;
  Point goal;
  ArrayList<ScoredPath> pathes = new ArrayList<ScoredPath>();
  Set<Point> visitedCache = new HashSet<Point>();
  
  class ScoredPath {
    ScoredPath(int score, ArrayList<Point> path) {
      this.score = score;
      this.path = path;
    }
    int score;
    ArrayList<Point> path;
  }
}

ちなみに、Field.neighborsでいける場所だけ返すように設計しておけば、Field.canWalkInは必要ないです。

忘れないようにJavaを使ってみたけど、Javaはやはり冗長なところが多くなったなあと思う。型推論、値型なタプル、もう少し豊富なコレクションのメソッド(lastやコピーを作るappend)があれば、だいぶ簡潔に書けそうなんだけれど。