2007/06/06
■ [Java] A* アルゴリズム完全版 
ただし、PointやFieldの具体型を作ると、キャストで警告が出るのがいやだったので、全部genericsに書き換えました。generic typeの配列はnew T[]すると警告が出るので、そのへんも全部List<T>に書き換えることになりました。余計なところで複雑になっている。計算機科学の教育でJavaを避けるようになったのもわかる気がします。
Point.java
// 位置 public interface Point { // 同値判定できる必要がある boolean equals(Object point); int hashCode(); }
これだけは変わってません。
Field.java
import java.util.*; // マップ public interface Field<TPoint extends Point> { // その位置に入れるかどうか boolean canWalkIn(TPoint point); // その位置に隣接する位置一覧 List<TPoint> neighbors(TPoint point); // その位置の目標からのスコア。 // パスが伸びればその合計スコアは増えるように、正の整数である int score(TPoint goal, TPoint point); }
Listが入り、ジェネリクス化しました。でもまだまだ単純です。
Solver.java
import java.util.*; public interface Solver<TPoint extends Point, TField extends Field<TPoint>> { List<TPoint> calc(TField map, TPoint start, TPoint goal); }
GenericsをGenericsで使うとクラスの型宣言は長くなります。<TField extends Field<TPoint extends Point>> って書きたいところだけど無理っぽい。
AStar.java
import java.util.*; class AStar<TPoint extends Point, TField extends Field<TPoint>> implements Solver<TPoint, TField> { public List<TPoint> calc(TField map, TPoint start, TPoint goal) { // 再入、並行実行可能にするためインスタンス生成し、実行 return new AStar<TPoint, TField>().solve(map, start, goal); } private List<TPoint> solve(TField map, TPoint start, TPoint goal) { this.map = map; this.goal = goal; visitedCache = new HashSet<TPoint>(); pathes = new ArrayList<ScoredPath>(); // 初期ポイント: (0, [start]) visitedCache.add(start); ArrayList<TPoint> path = new ArrayList<TPoint>(); path.add(start); ScoredPath spath = new ScoredPath(0, path); pathes.add(spath); return astar(); } private List<TPoint> astar() { while (pathes.size() > 0) { // 一番スコアの低いパスを取り出し進める ScoredPath spath = pathes.remove(0); TPoint current = spath.path.get(spath.path.size() - 1); // ゴールに着いていたら終了 if (current.equals(goal)) { return spath.path; } for (TPoint next: map.neighbors(current)) { // すでに通ってたらスルー if (visitedCache.contains(next)) continue; // 通ったことにする visitedCache.add(next); // 入れなければスルー if (!map.canWalkIn(next)) continue; // パスに追加し、そのパスのスコアを計算 ArrayList<TPoint> path = new ArrayList<TPoint>(spath.path); path.add(next); int score = spath.score + map.score(goal, next); // スコア順になるよう、この新たなパスを挿入 insert(score, path); } } // もう行ける場所がなく、到達不能。 return null; } private void insert(int score, ArrayList<TPoint> 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)); } private TField map; private TPoint goal; private ArrayList<ScoredPath> pathes; private Set<TPoint> visitedCache; private class ScoredPath { ScoredPath(int score, ArrayList<TPoint> path) { this.score = score; this.path = path; } int score; ArrayList<TPoint> path; } }
手続きメインなので、ほとんど変わらないけど、privateとか入れたので、地味にめんどくさくなってます。結局、警告の出ないtoArrayの使い方がわからなかったのでList化したのです。
Point2D.java
座標としてxとyを持った単純なポイントです。
public class Point2D implements Point { public Point2D(int x, int y) { this.x = x; this.y = y; } public boolean equals(Object o) { if (o instanceof Point2D) { Point2D p = (Point2D) o; return p.x == x && p.y == y; } return false; } public int hashCode() { return x + y; } public int x() { return x;} public int y() { return y;} private int x; private int y; }
情報隠蔽はきちっとしておきました。
equalsのなかでキャストを使ってますが、この場合は警告は出ないようです。
Field2D.java
有限マップです。A*自体はスコアリングがしっかりしてれば無限境界のマップでもいけるはずですが、今回は表示の簡略化(回り込まれると面倒なので)と、壁を省略するため、境界壁の構造にしてます。
import java.util.*; public class Field2D implements Field<Point2D> { public Field2D(String[] data, int width) { this.data = data.clone(); this.width = width; this.height = data.length / width; } public boolean canWalkIn(Point2D point) { if (0 <= point.x() && point.x() < width && 0 <= point.y() && point.y() < height && " ".equals(get(data, point))) return true; return false; } public List<Point2D> neighbors(Point2D point) { List<Point2D> result = new ArrayList<Point2D>(4); result.add(new Point2D(point.x() - 1, point.y())); result.add(new Point2D(point.x() + 1, point.y())); result.add(new Point2D(point.x(), point.y() - 1)); result.add(new Point2D(point.x(), point.y() + 1)); return result; } public int score(Point2D goal, Point2D point) { return Math.abs(point.x() - goal.x()) + Math.abs(point.y() - goal.y()); } public Field2D walk(List<Point2D> path) { String[] newData = data.clone(); for (Point2D point: path) { set(newData, point, "*"); } return new Field2D(newData, width); } public void print() { printWall(); for (int y = 0; y < height; y += 1) { System.out.print("#"); for (int x = 0; x < width; x += 1) { Point2D point = new Point2D(x, y); System.out.print(get(data, point)); } System.out.println("#"); } printWall(); } private void printWall() { for (int x = 0; x < width + 2; x += 1) { System.out.print("#"); } System.out.println(); } private void set(String[] data, Point2D point, String value) { data[point.y() * width + point.x()] = value; } private String get(String[] data, Point2D point) { return data[point.y() * width + point.x()]; } private String[] data; private int width; private int height; }
スコアはgoalからの絶対距離です。壁は無視します。
それ以降はユーティリティです。walkはパスをたどって、マークをつけたマップを返します。printはマップを壁付きで標準出力に出します。
cloneで代入してもキャストが不要なのはちょっとだけいいかもしれません。
Main.java
例題実行します。
import java.util.*; class Main { public static void main(String[] args) { String[] mapData = new String[] { " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#", "#", "#", "#", " ", " ", " ", " ", " ", " ", "#", "#", " ", "#", "#", " ", "#", " ", " ", " ", " ", "#", "#", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", }; int width = 5; Field2D map = new Field2D(mapData, width); System.out.println("[source map]"); map.print(); Point2D start = new Point2D(1, 1); Point2D goal = new Point2D(0, 5); AStar<Point2D, Field2D> astar = new AStar<Point2D, Field2D>(); List<Point2D> path = astar.calc(map, start, goal); Field2D walked = map.walk(path); System.out.println("[result map]"); walked.print(); } }
実行結果
$ java Main [source map] ####### # # # # ##### # # # ### ### # # # # ## # # # # # ####### [result map] ####### # # # ****# #####*# # ***# ###*### #*#** # #*##* # #**** # # # #######
コメント