TypeScriptで経路探索
パッケージ製品開発担当の大です。こんにちは。
最近、某２ちゃんねるまとめブログを見てたらこんな記事を見つけました。
MAZE （クリックで拡大）
この迷路を脱出する最短経路を導き出せとのこと。
元ネタは、裏サンデー 連載投稿トーナメントにエントリーされていた、「MAZE」という漫画なんだそうです（残念ながらもう消えちゃってるみたいですが: まとめWiki）。
まぁ、単純にプログラミングのお題として面白そうだったので、前回にひきつづきTypeScriptの練習がてら解いてみました。
※ TypeScriptは0.8.3.1で評価しています。近日中にリリースされる予定の0.9では、boolがbooleanに変更されたり、ジェネリクスが導入されていたりと、大きな変更が行われます。ここに載っているコードそのままでは動作しなくなると思いますので、ご注意ください。
グラフの作成
経路探索ということで、まずはルールにしたがってグラフを作成します。グラフはノードの集合とエッジの集合で構成されます。
/**
* グラフ
*/
class Graph {
public nodeList: Node[] = [];
public edgeList: Edge[] = [];
newNode(x: number, y: number, direciton: Direction): Node {
var node = new Node(x, y, direciton);
this.nodeList.push(node);
return node;
}
findNode(x: number, y: number, direction: Direction): Node {
for (var i = 0; i < this.nodeList.length; i++) {
var node = this.nodeList[i];
if (node.x == x && node.y == y && node.direction == direction) {
return node;
}
}
return null;
}
newEdge(from: Node, to: Node, cost: number): Edge {
var edge = new Edge(from, to, cost);
this.edgeList.push(edge);
return edge;
}
}
ノードは、進んできた方向（上下左右）と座標の情報（xとy）を保持します。あと経路探索用にいくつかのプロパティを持っています。
/**
* ノード
*/
class Node {
static INITIAL_COST = Number.POSITIVE_INFINITY; // ノードのコストの初期値は無限大
// この3つは経路探索用
public cost: number;
public done: bool;
public route: Edge;
constructor(public x: number, public y: number, public direction: Direction) {
}
init():void {
this.cost = Node.INITIAL_COST;
this.done = false;
this.route = null;
}
toString(): string {
return "(" + this.x + "," + this.y + ")";
}
}
各エッジはノード間の距離をコストとして保持します。
/**
* エッジ
*/
class Edge {
static TYPE_NORMAL = 0; // 普通のエッジ
static TYPE_POINT = 1; // ☆を通るエッジ
public type = Edge.TYPE_NORMAL;
constructor(public from: Node, public to: Node, public cost: number) {
}
toString(): string {
return this.from + "->" + this.to;
}
}
スタートから順に全てのエッジとノードを作成していきます。
/**
* ソルバ
*/
class Solver {
public graph: Graph;
private start: Node;
private goal: Node;
constructor() {
// グラフの作成
this.graph = new Graph();
this.start = this.graph.newNode(11, 1, Direction.U2D);
this.goal = this.graph.newNode(11, 0, Direction.D2U);
this.createEdges(this.start, Direction.U2D);
}
private createEdges(from: Node, direction: Direction):void {
var point = false;
for (var i = 1; ; i++) {
var cell = this.getCell(from, i, direction);
if (cell == 壁 || cell == 外) {
break;
}
if (cell == ポイント) {
point = true;
}
if (cell == 出入口 || i >= 5) {
// 出入口に到達したか、5歩以上歩いた
var to = this.getNode(from, i, direction);
var edge = this.graph.newEdge(from, to, i);
if (point) {
// ポイントを通過したエッジ
edge.type = Edge.TYPE_POINT;
}
}
}
}
private getCell(from: Node, distance: number, direction: Direction): string {
return direction.move(from.x, from.y, distance, (x, y) => {
try {
return MAP[y][x];
} catch (e) {
return 外;
}
});
}
private getNode(from: Node, distance: number, direction: Direction): Node {
return direction.move(from.x, from.y, distance, (x, y) => {
var node = this.graph.findNode(x, y, direction);
if (node == null) {
// 見つからなければ新規に作成
node = this.graph.newNode(x, y, direction);
if (direction.isHorizontal()) {
// 水平方向に向かっているときは垂直方向に曲がれる
this.createEdges(node, Direction.U2D);
this.createEdges(node, Direction.D2U);
} else {
// 垂直方向に向かっているときは水平方向に曲がれる
this.createEdges(node, Direction.L2R);
this.createEdges(node, Direction.R2L);
}
}
return node;
});
}
}
/**
* 方向
*/
class Direction {
static L2R = new Direction("→");
static U2D = new Direction("↓");
static R2L = new Direction("←");
static D2U = new Direction("↑");
constructor(public value: string) {
}
// (x, y)からこの方向へdistance分移動し、callbackを適用します。
move(x: number, y: number, distance: number, callback: (x: number, y: number) => any): any {
switch (this) {
case Direction.L2R:
return callback(x + distance, y);
case Direction.U2D:
return callback(x, y + distance);
case Direction.R2L:
return callback(x - distance, y);
case Direction.D2U:
return callback(x, y - distance);
}
}
isHorizontal(): bool {
return this == Direction.L2R || this == Direction.R2L;
}
toString(): string {
return this.value;
}
}
Direction#moveがanyを返すのが残念な感じですが、ここらへんはジェネリクスが導入されたら改善できるかもしれませんね。
そんなこんなで、総ノード数383、総エッジ数785の有向グラフになりました。
（ほんとはGoogle ChartのWEB APIを使用したかったのですが、エッジ数が160までしか使用できない制限があるようなので、ローカルでGraphVizを動かして出力したものです。）
右上のほうにある赤いノードがスタート、右下のほうの青いノードがゴールです。
左のまんなからへんに、何本か青いエッジがあります。これらは、課題である「☆を通過する」エッジですが、見ての通り複数存在します。
☆を通るエッジ: (14,11)->(9,11) (14,11)->(8,11) (13,11)->(8,11) (8,11)->(13,11) (8,11)->(14,11) (8,11)->(15,11) (8,11)->(16,11) (8,11)->(17,11) (9,11)->(14,11) (9,11)->(15,11) (9,11)->(16,11) (9,11)->(17,11) (10,11)->(15,11) (10,11)->(16,11) (10,11)->(17,11)
スタートから出発して、青いエッジのどれかを通り、ゴールにたどり着く最短のルートを求めるのがこの問題ということになります。
前半のルートと後半のルート
一気に解くやりかたが思いつかなかったので、ルートを前半と後半にわけて考えました。
- 前半は、「☆を通過する」エッジの手前のノード（from）をゴールとして考え、それぞれの最短ルートを求めます。
- 後半は、「☆を通過する」エッジの直後のノード（to）からゴールまでのそれぞれの最短ルートを求めます。
これならダイクストラ法でいけますね。
/**
* ソルバ
*/
class Solver {
// 第一段階: スタートから☆を通る直前のノードまでのルートを見つける
solve1(edges: Edge[]): Route[] {
return this.solve(this.start, edges.map(edge => edge.from), false);
}
// 第二段階: ☆を通った直後のノードからゴールへのルートを見つける
solve2(edges: Edge[]): Route[] {
return this.solve(this.goal, edges.map(edge => edge.to), true);
}
// fromからtoへのルートをすべて見つける
private solve(from: Node, to: Node[], reverse: bool): Route[] {
// ノードを初期化
this.graph.nodeList.forEach(node => node.init());
from.cost = 0;
this.graph.findRoute(from, reverse);
// 目的地のうち、fromからのルートが存在したものについてルートを作成
return to.sort().filter((node, i, a) => a.indexOf(node) == i) // unique
.filter(node => node.done)
.map(node => this.createRoute(from, node, reverse));
}
private createRoute(from: Node, to: Node, reverse: bool): Route {
var path: Edge[] = [];
var node = to;
while (node != from) {
if (reverse) {
path.push(node.route);
node = node.route.to;
} else {
path.unshift(node.route);
node = node.route.from;
}
}
return new Route(path, to.cost);
}
}
/**
* グラフ
*/
class Graph {
// 経路探索
findRoute(node: Node, reverse: bool): void {
var edges = this.edgeList.filter(edge => (reverse ? edge.to : edge.from) == node);
edges.forEach(edge => {
var n = reverse ? edge.from : edge.to;
// 設定されているコストよりも小さかったら上書き
if (n.cost >= edge.cost + node.cost) {
n.cost = edge.cost + node.cost;
n.route = edge;
}
});
// このノードは探索済
node.done = true;
// 未探索のノード
var undone = this.nodeList.filter(node => !node.done)
.sort((a, b) => a.cost - b.cost);
if (undone.length > 0 && undone[0].cost != Node.INITIAL_COST) {
// コストが最小のものについて再帰的に経路探索
this.findRoute(undone[0], reverse);
}
}
}
/**
* ルート
*/
class Route {
constructor(public path: Edge[], public cost: number) {
}
lastNode():Node {
return this.path[this.path.length - 1].to;
}
startNode():Node {
return this.path[0].from;
}
toString(): string {
var s = this.path.map(edge => edge.from)
.concat(this.lastNode())
.map(node => node.toString())
.join("->");
return "cost: " + this.cost + ", path: " + s;
}
}
結果がこちらになります。
前半のルート:
cost: 69, path: (11,1)->(11,7)->(6,7)->(6,12)->(12,12)->(12,3)->(6,3)->(6,9)->(1,9)->(1,16)->(10,16)->(10,11) cost: 64, path: (11,1)->(11,8)->(18,8)->(18,2)->(12,2)->(12,13)->(18,13)->(18,20)->(13,20)->(13,11) cost: 57, path: (11,1)->(11,8)->(20,8)->(20,15)->(13,15)->(13,10)->(8,10)->(8,5)->(14,5)->(14,11) cost: 65, path: (11,1)->(11,7)->(6,7)->(6,12)->(12,12)->(12,5)->(6,5)->(6,10)->(14,10)->(14,5)->(8,5)->(8,11) cost: 52, path: (11,1)->(11,8)->(21,8)->(21,21)->(14,21)->(14,16)->(9,16)->(9,11)
赤いエッジがスタートからの最短ルートです。
後半のルート:
cost: 43, path: (13,11)->(13,16)->(1,16)->(1,9)->(6,9)->(6,3)->(11,3)->(11,0) cost: 56, path: (14,11)->(14,5)->(20,5)->(20,15)->(15,15)->(15,10)->(6,10)->(6,5)->(11,5)->(11,0) cost: 40, path: (8,11)->(8,5)->(14,5)->(14,10)->(6,10)->(6,5)->(11,5)->(11,0) cost: 39, path: (9,11)->(9,16)->(1,16)->(1,9)->(6,9)->(6,3)->(11,3)->(11,0)
赤いエッジがゴールへの最短ルートです。
ルートをつなげる
最後に、前半のルートと「☆を通過する」エッジと後半のルートをつなげて、コストが最小のものをみつければミッション完了です。
/**
* ソルバ
*/
class Solver {
// 前半のルートと☆を通るエッジと後半のルートをつなげる
concat(routes1: Route[], edges: Edge[], routes2: Route[]): Route[] {
var routes: Route[] = [];
for (var i = 0; i < routes1.length; i++) {
for (var j = 0; j < edges.length; j++) {
if (routes1[i].lastNode() != edges[j].from) {
continue;
}
for (var k = 0; k < routes2.length; k++) {
if (edges[j].to != routes2[k].startNode()) {
continue;
}
var path = routes1[i].path.concat(edges[j]).concat(routes2[k].path);
var cost = routes1[i].cost + edges[j].cost + routes2[k].cost;
routes.push(new Route(path, cost));
}
}
}
return routes;
}
}
最短ルート:
cost: 101, path: (11,1)->(11,8)->(20,8)->(20,15)->(13,15)->(13,10)->(8,10)->(8,5)->(14,5)->(14,11)->(9,11)->(9,16)->(1,16)->(1,9)->(6,9)->(6,3)->(11,3)->(11,0)
結果、最短ルートは101マスになりました。100マスを切るのは無理な気がします。。。
可視化する
console.logに結果出力して終わりではちょっとさみしいので、もうちょっと可視化してみます。
TypeScriptは、既存のJavaScriptの資産を活用できるのも大きな魅力です。
既存のJavaScriptライブラリをTypeScriptから使用するには、型を定義する必要があります。有名どころのライブラリについては、誰かが型を定義したファイルがDefinitelyTypedなどに集められています。ここから直接ダウンロードも出来ますし、tsdなどのツールを使用して取得することもできます。便利ですね。
ここでは、jQueryを使用するため、jquery.d.tsをダウンロードします。
自分のTypeScriptのソースの先頭で、
/// <reference path="jquery.d.ts" />
と書けば、ソース中でjQueryを使用できるようになります（別途jquery本体は実行時に必要です）。
/**
* ビュー
*/
class MazeView {
private player: JQuery;
constructor(private stage: JQuery) {
for (var i = 1; i < MAP.length - 1; i++) {
for (var j = 1; j < MAP[i].length - 1; j++) {
stage.append(this.createCell(j, i));
}
}
// 出入口にプレイヤーを配置
this.player = this.createCell(11, 0);
stage.append(this.player);
}
private createCell(x: number, y: number): JQuery {
var cell = MAP[y][x];
var elem = $("<div class='cell' />");
if (cell == 壁) {
elem.addClass("wall");
} else if (cell == ポイント) {
elem.addClass("point");
} else if (cell == 出入口) {
elem.addClass("player");
}
elem.css("left", this.position(x));
elem.css("top", this.position(y));
return elem;
}
private position(n: number): string {
return (n * 20) + "px";
}
trace(route: Route): void {
var clone = this.player.clone();
this.stage.append(clone);
var start = route.startNode();
clone.css("left", this.position(start.x));
clone.css("top", this.position(start.y));
route.path.forEach(edge => {
edge.to.direction.move(edge.from.x, edge.from.y, edge.cost, (x, y) => {
clone.animate({ left: this.position(x), top: this.position(y) },
{ duration: "slow" });
});
});
}
}
実行ボタンを押すと、最短ルートを表示します。（Chrome23、Firefox21、IE9で動作確認済。IE9でうまく動かない場合は、開発者ツールでドキュメントモードをIE9標準にするか、他のブラウザでお試しください。 IE8以前では動作しませんが、そこまで古くないブラウザならだいたい動作すると思います）
ソース
最終的なコードは以下のようになりました。
