迷路作成アルゴリズム

<canvas id="canvas1" width=310 height=310></canvas>
<script type="text/javascript">
var canvas = document.getElementById("canvas1");
var context = canvas.getContext("2d");

var addLoad = new Array();

var mWidth = 31;
var cells = new Array(mWidth);
for(var i = 0; i < mWidth; i++) {
	cells[i] = new Array(mWidth);
	for(var j = 0; j < mWidth; j++) {
		cells[i][j] = false;
	}
}

for(var i = 0; i < mWidth; i++) {
	cells[0][i] = true;
	cells[mWidth-1][i] = true;
	cells[i][0] = true;
	cells[i][mWidth-1] = true;
}

function hitWall(p, d) {
	var x = p.x + 2*d.x;
	var y = p.y + 2*d.y;
	if(x > mWidth-2 || y > mWidth-2 || x < 0 || y < 0) {
		return true;
	}
	return cells[x][y];
}

function whichDirection(p) {
	var d = [];
	if(!cells[p.x+1][p.y]) {
		d.push({x:1, y:0});
	}
	if(!cells[p.x-1][p.y]) {
		d.push({x:-1, y:0});
	}
	if(!cells[p.x][p.y+1]) {
		d.push({x:0, y:1});
	}
	if(!cells[p.x][p.y-1]) {
		d.push({x:0, y:-1});
	}
	len = d.length;
	if(len == 0) {
		return {x:0, y:0};
	}
	var n = Math.floor(len*Math.random());
	return d[n];
}

function drawCells(p, d) {
	var x = p.x + d.x;
	var y = p.y + d.y;
	cells[x][y] = true;
	x += d.x;
	y += d.y;
	cells[x][y] = true;
	load.push({x:x, y:y});
}

function initPoint() {
	var p = {x:0, y:0};
	p.x = Math.floor(14*Math.random()) + 1;
	p.y = Math.floor(14*Math.random()) + 1;
	p.x *= 2;
	p.y *= 2;
	return p;
}
 
function getRandom() {
	if(Math.random() < 0.2) {
		return true;
	}
	return false;
}

function stopLoad(p) {
	var d1 = {x:1, y:0};
	var d2 = {x:-1, y:0};
	var d3 = {x:0, y:1};
	var d4 = {x:0, y:-1};
	return hitWall(p, d1) && hitWall(p, d2) && hitWall(p, d3) && hitWall(p, d4);
}

function nextPoint() {
	var len = addLoad.length-1;
	if(len < 2) {
		return addLoad[0];
	}
	var n = Math.floor(len*Math.random());
	return addLoad[n];
}

function isLoadExist() {
	var exist = false;
	if(addLoad.length != 0) {
		addLoad = []; // clear()がundefined
	}
	for(var i = 0; i < load.length; i++) {
		if(!stopLoad(load[i])) {
			addLoad.push(load[i]);
			exist = true;
		}
	}
	return exist;
}

var load = Array();
var p = initPoint();
load.push({x:p.x, y:p.y});
var d = whichDirection(p);
var n = 0;
function makeMeiro() {
	if(!isLoadExist()) {
		return;
	}
	n++;
	if(n > 2000) return;
	if(stopLoad(p)) {
		p = nextPoint();
		d = whichDirection(p);
	}
	if(hitWall(p, d) || getRandom()) {
		d = whichDirection(p);
		return;
	}
	else {
		drawCells(p, d);
		p.x += 2*d.x;
		p.y += 2*d.y;
	}
}

function drawMeiro() {
	makeMeiro();
	context.fillStyle = "rgb(0, 0, 0)";
	for(var i = 0; i < mWidth; i++) {
		for(var j = 0; j < mWidth; j++) {
			if(cells[i][j]) {
				x = i * 10;
				y = j * 10;
				context.fillRect(x, y, 10, 10);
			}
		}
	}
}
setInterval(drawMeiro, 10);
</script>