迷路プログラム
きっかけ
会社にあった雑誌（日経ソフトウェアだったかな？）にJavaScriptを使用した迷路作成のプログラムがあったので、それをいろいろ改造してプログラムを作ってみました。
雑誌に乗っていたプログラムは、決められた迷路を幅優先探索（BFS:Breadth first search)というアルゴリズムでスタートからゴールまでの道のりを見つけるというプログラムでした。
幅優先探索とは、出発点から近い点から順に探索する方法です。迷路でいうと、分岐点が出た場合に、分岐点の片方だけを探索するのでなく、分岐点から一歩ずつ平行に進んでいくという感じです。
文章での説明が難しいので図で説明すると、下図のように横から順に探索するイメージです。（図の番号順通りに探索します）
これとよく比較されるのが深さ優先探索(DFS:Depth first search)といって、ゴールが見つかるまで分岐があっても一方の道を進み続ける方法です。
プログラム拡張
雑誌のプログラムを改造して、まず迷路を大きくしました。 その後、迷路を穴掘り法と呼ばれるアルゴリズムでランダム生成するように変更しました。 穴掘り法とはマップを壁で埋め尽くし、ランダム方向に掘り進め、マップ外に当たったら、またランダムな位置から壁を掘るという方法です。
ランダムに生成される迷路を見ていると、トルネコや風来のシレンといった不思議なダンジョンシリーズを思い出して、 RPGで主人公たちが進むマップみたいなものを思いつきました。
そこで、作ったのが下記のプログラムです。 これは、スタート地点（左上）から最も遠い地点までへ最短で行く道を見つけてくれるというプログラムです。 左下の探索ボタンを押すと（何回か？）、ゴールとそこまでの最短ルートに線を描いてくれます。 目視で一番遠い地点と思っていたのが、実は他に遠いゴールがあったということが分かるので、意外と面白いです。 よかったら、遊んでみてください。 迷路探索プログラム
一応下にソースコードの全文を貼っています。自分の環境で作ってみたいと思いましたら、是非下からコピーして作ってみてください。 （探索ボタンを複数回押さないといけないバグなどがありますので、解決方法や改善方法があればご教授ください～T_T）
※クリックで開きます
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>迷路の最短経路での最長ゴールを求める</title>
</head>
<body>
<canvas id="canvas" width="900" height="900"></canvas>
<div>
<input type="button" onclick="walk()" value="探索">
</div>
<script>
var canvas = document.getElementById("canvas");
var context = canvas.getContext("2d");
var xMax = 449;
var yMax = 449
var x1 = [1, 0, -1, 0],
y1 = [0, 1, 0, -1]; //移動方向のテーブル
var xa = 1,
ya = 1,
dir = 0; //掘り進む座標と向き
var x, y, blk;
var maze = new Array(yMax);
for (y = 0; y < yMax; y++) {
maze[y] = new Array(xMax);
for (x = 0; x < xMax; x++) {
maze[y][x] = 1; //壁で埋め尽くす
}
}
maze[ya][xa] = 0; //スタート地点に穴を掘る
blk = (Math.floor(xMax) * Math.floor(yMax) * 2);
while (blk > 0) {
while (1) {
dir = (dir + Math.floor(Math.random() * 4) - 1) & 3; //方向転換
x = xa + x1[dir] * 2;
y = ya + y1[dir] * 2;
if ((x < 1) | (x >= xMax) | (y < 1) | (y >= yMax)) {
break;
}
//if(maze[y][x]==0){ break; } //掘り進めない場合、ループ脱出
for (var i = 0; i < Math.floor(Math.random() * 2); i++) { //2マス分掘り進む
xa += x1[dir];
ya += y1[dir];
maze[ya][xa] = 0;
}
blk--;
}
do { //新しいスタート地点を探す
xa = Math.floor(Math.random() * Math.floor(xMax));
ya = Math.floor(Math.random() * Math.floor(yMax));
} while (maze[ya][xa] == 1)
dir = Math.floor(Math.random() * 4);
}
var v = [0, 0, -1, 1, -1, 1, 0, 0];
var queue = new Array();
var route = new Array(yMax);
var routeLength = 0;
var calRoute = new Array();
for (var i = 0; i < yMax; i++) {
route[i] = new Array(xMax);
}
var WALKED = 99;
var isGoal = false;
var startPos = {
x: 1,
y: 1
}, goalPos = {
x: xMax - 20,
y: yMax - 20
};
var size = 2; //一マスの大きさ
queue.push({
x: startPos.x,
y: startPos.y
});
//改善点①スタート地点の再計算を回避
maze[startPos.y][startPos.x] = 88;
var mazeDraw = function() {
for (var y = 0; y < yMax; y++) {
for (var x = 0; x < xMax; x++) {
if (maze[y][x] == 1) {
context.fillStyle = "rgb(50, 90, 150)";
context.fillRect(x * size, y * size, size, size);
}
if (maze[y][x] == 99) {
context.fillStyle = "rgb(84, 109, 142)";
context.fillRect(x * size, y * size, size, size);
}
}
}
context.fillStyle = "rgb(0,0,255)";
context.fillRect(startPos.x * size, startPos.y * size, size, size);
//context.fillStyle = "rgb(255, 0, 0)";
//context.fillRect(goalPos.x*size, goalPos.y*size, size, size);
}
var BFS = function() {
var pos = queue.shift();
var x = pos.x;
var y = pos.y;
for (var i = 0; i < 4; i++) {
if (maze[y + v[i + 4]][x + v[i]] == 0) {
queue.push({
x: x + v[i],
y: y + v[i + 4]
});
route[y + v[i + 4]][x + v[i]] = {
px: x,
py: y
};
maze[y + v[i + 4]][x + v[i]] = WALKED;
}
}
if (queue[0] == null) {
context.fillStyle = "rgb(255, 0, 0)";
context.fillRect(x * size, y * size, 5, 5);
for (;;) {
isGoal = true;
pos = route[y][x];
if (pos.px == startPos.x && pos.py == startPos.y) {
alert("最短ルートでの最長ゴールを見つけました。移動距離:" + routeLength);
break;
}
calRoute.push(pos);
routeLength++;
x = pos.px;
y = pos.py;
}
setTimeout(function drawShortcut() {
pos = calRoute.pop();
context.fillStyle = "rgb(250, 140, 20)";
context.fillRect(pos.px * size, pos.py * size, size, size);
x = pos.px;
y = pos.py;
setTimeout(drawShortcut, 10);
})
}
return;
}
window.onload = mazeDraw;
var walk = function() {
if (!isGoal) {
//mazeDraw();
BFS();
//改善点②returnをつけて再帰処理を回避(ずっとsetTimeout処理を続けていそう・・・)
} else {
return;
}
//setTimeout(walk, 0);
walk();
}
</script>
<div>
</body>
</html>
