///
module maze {
// ルール
// 1. マスに沿ってタテヨコに直進すること。
// 2. 黒いマスは通らないこと。
// 3. 曲がるときは、必ず右か左に曲がること。Uターンは禁止する。
// 4. 6マス以上直進すること。(※ 5歩以上直進すること)
var 外 = " ";
var 壁 = "■";
var ポイント = "☆";
var 出入口 = "★";
var MAP = [
//0 1 2 3 4 5 6 7 8 910111213141516171819202122
" ★ ", // 0
" □□□□□□□□■□□■□□□□□□□□□ ", // 1
" □■□□□□□■□□□□□□□□□□□□□ ", // 2
" □□■□□□□□□□□□■□□□■□□□□ ", // 3
" □□□□□□□■□□□□□■□□□□■□□ ", // 4
" □□□□■□□□□□□□□□□□□□□□□ ", // 5
" □□□□□□■□■□□□□□■□□□□□□ ", // 6
" ■□□□□□□□□□□□□□□□■□□□■ ", // 7
" □□□■□□□□□■□□□□□□□□□□□ ", // 8
" □□□□□□■□□□■□■□■□□□□□□ ", // 9
" □■□□■□□□□□□□□□□■□□■□□ ", // 10
" □□■□□□■□□□☆□□□□□□■□□□ ", // 11
" □□□□■□□□□□□□□■□■□□□□□ ", // 12
" □□□□□■□■□□■□□□□□□□■□□ ", // 13
" □□■□□□□□□□□□□■□□■□□□□ ", // 14
" □□□□■□□■□□□■□□□□□□□□□ ", // 15
" □□□□□□□□□□□□□□■□■□□□□ ", // 16
" □□■□□□□□□□■□□□□□□□□■□ ", // 17
" □□□□□□□■□■□□□□■□□□□□□ ", // 18
" □□■□□□□□□□□■□□□■□□□□□ ", // 19
" □□□□□□■□■□■□□□□□□□□■□ ", // 20
" ■□□□□□□□□□□□■□□□□□□□□ ", // 21
" ", // 22
];
/**
* 方向
*/
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;
}
}
/**
* ソルバ
*/
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;
});
}
// 第一段階: スタートから☆を通る直前のノードまでのルートを見つける
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);
}
// 前半のルートと☆を通るエッジと後半のルートをつなげる
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;
}
}
/**
* グラフ
*/
class Graph {
public nodeList: Node[] = [];
public edgeList: Edge[] = [];
// 経路探索
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);
}
}
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;
}
}
/**
* グラフのノード
*/
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 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;
}
}
/**
* ビュー
*/
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 = $("
");
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" });
});
});
}
}
var view: MazeView;
export function init(stage: JQuery) {
view = new MazeView(stage);
}
export function start() {
var solver = new Solver();
console.log("総ノード数:" + solver.graph.nodeList.length);
console.log("総エッジ数:" + solver.graph.edgeList.length);
var pedges = solver.graph.edgeList.filter(edge => edge.type == Edge.TYPE_POINT);
console.log("☆を通るエッジ:\n" + pedges.join("\n"));
var routes1 = solver.solve1(pedges);
console.log("前半のルート:\n" + routes1.join("\n"));
var routes2 = solver.solve2(pedges);
console.log("後半のルート:\n" + routes2.join("\n"));
var routes = solver.concat(routes1, pedges, routes2);
console.log("最終的なルート:\n" + routes.join("\n"));
routes.sort((a, b) => a.cost - b.cost);
console.log("最短ルート:\n" + routes[0]);
// routes.forEach(route => view.trace(route));
view.trace(routes[0]);
}
}
$(document).ready(() => {
maze.init($("#stage"));
});