p5.jsで一生遊ぶのに困らないくらいの迷路を自動生成する


2018年06月10日
With
p5.jsで一生遊ぶのに困らないくらいの迷路を自動生成する はコメントを受け付けていません。

p5.jsでスケッチするようになってから、子どものころに遊んだ幾何学っぽいおもちゃをプログラミングで再現するというのをたまにやっています。これまでには「スピログラフ」「模様作り積み木」「万華鏡」なんかにチャレンジしてみたのですが、今回は「迷路」です。

…たぶんほとんどの人には、子どものころに「迷路あそび」に夢中になった時期というのがあるんじゃないですかね。いや、特に根拠はないんですけど。

昔読んでいた子ども雑誌のプレゼント付きクイズコーナーあたりでも、迷路を解くと答えが分かるような企画は定番でしたし、今でも迷路をメインにした知育絵本はたくさん出版されているようです。学園祭でも、特にやることが思いつかなかったクラスの出し物は、机を積んでダンボールで壁を張った教室迷路(あるいはお化け屋敷)と相場が決まっています。

あと、これは生まれた時代が関係していると思うんですが、僕はこれまでの人生の中で、何度か社会的な「プチ迷路ブーム」みたいなものにも遭遇しています。例えば、小学生時分には「コンピューターが作ったスタジオ内の迷路セットを男女のペアが時間内に脱出する」という視聴者参加型テレビ番組(土居まさる司会の「迷路でデート!」)が放送されていたことがありますし、高校生時代には日本各地の空き地になぜか「巨大迷路」が次々と作られて、そこに多くの人が集まるという現象がありました。

…まぁ、それでも人はいつしか「迷路あそび」に飽き、ブームは去ってしまいました。それは宿命なのでしょう。…でもね、でもですよ、どんな人でも、子どものころにワクワクしながら遊んだ「迷路」の思い出は、意識の奥にしっかりと刻み込まれているのです。その記憶が、例えば、年をとって、ふと自分のこれまでの人生を振り返るようなときに、堰を切ったように勢いよくあふれ出すことが、ないとは言い切れないではないですか。

「あぁ、迷路って面白かったよなぁ。また、心ゆくまで迷路で遊んでみたいなぁ」…そんな思いが込み上げてきて、どうにも抑えられなくなった時、手元にすぐに遊べる迷路がなかったら、悲しいじゃありませんか。そんな悲劇を、この世の中から一刻も早く消し去りたい。そう強く願いながらこのスケッチを描きました。ほんとかよ。

●全自動迷路生成器(クリックすると別タブが開きます)

開くと、画面上でいろんな色、サイズの迷路が順次作られていきます。それを眺めるだけのスケッチです。

最後の方に添付したソースコードの30行目に、コメントアウトされている「saveCanvas();」があるのですが、これを復帰させてやると、できあがった迷路が順次PNG形式の画像でダウンロードされるようになります。この状態で丸1日も放っておけば、数年遊ぶのには困らないくらいの量の迷路画像が生成できます。たぶん。

迷路生成のアルゴリズムについては、こちらのページを参考にさせていただきました。

迷路自動生成

コンピュータによる迷路生成は、古典的でポピュラーなテーマなので、ちょっとググればいろいろなアルゴリズムが見つかります。このスケッチでは「穴掘り法(道のばし法)」と呼ばれているものを使いました。

生成のスピードは、迷路のサイズによってかなり差が出ますが、特に大きめな迷路を作っている過程で、道がくねくねと延びていくさまはなんかイイですね。「考えてるぞー」って感じがして。

穴掘り法ではざっくりと、

1.縦横ともに奇数のブロックで構成されるグリッドを用意して、全部壁にしておく
2.縦横共に奇数の座標位置にあるブロックをランダムに選んで道にする。そこを最初の基準位置にする。
3.基準位置から上下左右のいずれかの方向をランダムに選んで、その方向へ2マス分先にあるブロックが「壁」か「道」かを見る。
4.もし「壁」なら、そのブロックと、間にあるブロックを「道」にして、現在の基準位置を記憶。さっき見た2マス先のブロックを次の基準位置にし、3から繰り返す。
5.もし「道」なら、上下左右の方向を選び直す。もし、次に選んだ方角で2マス先が「壁」ならば、4から繰り返す。現在の基準位置から上下左右、いずれを選んでも2マス先に「壁」が見つからなければ、記憶してある過去の基準位置の中からランダムにどれかを選び、3から繰り返す。
6.記憶したすべての過去の基準位置に対して上下左右のチェックを行い「壁」が見つからなくなったら完成

という手順で迷路を作ります。今回はこの手順を自分で一から実装してみました。「記憶しておいたすべての過去の基準位置に対してチェックを完了する」という部分が肝で、乱数の出方によっては、出力上は完成しているように見えても、このチェックが終わるまでしばらく待たされてしまいます。

カンバス下部中央で変化している数字は「すべての方向に対するチェックが終わっていない過去の基準位置」の残数です。スタートからジワジワ増えていき、ある程度迷路ができあがってくると徐々に減りはじめます。この数字が「0」になった時点で完成です。当初は、この数字を表示しない形でスケッチを作っていたのですが、特にサイズが大きい場合には画面に変化のない状態が長時間続いて不安になるので、内部で作業が続いていることが分かるように表示してみました。

コードはこんな感じです。

const margin = 10;
let optMarginX, optMarginY;
let aside;
let xCount, yCount;
let cells = [];
let checkedCells = [];
let cellX, cellY, tmpX, tmpY;
let dirs = [];
let nextDir;
let wallColor, inLoop;

function setup() {
	createCanvas(600, 600);
	colorMode(HSB);
	init();
}

function draw() {
	background(255);
	for (let j = 0; j < yCount; j++) {
		for (let i = 0; i < xCount; i++) {
			cells[i][j].drawRect();
		}
	}
	if (inLoop) {
		digMaze();
		text(checkedCells.length, width / 2 - 5, height - 3);
	} else {
		sleep(2000);
		//saveCanvas(); //←ここを復帰させると画像を自動でダウンロード
		init();
	}
}

function digMaze() {
	if (dirs.length == 0) {
		let pickNextIndex = floor(random(0, checkedCells.length));
		let othercheckedCell = checkedCells[pickNextIndex];
		checkedCells.splice(pickNextIndex, 1);
		if (checkedCells.length == 0) {
			cells[0][1].state = false;
			cells[xCount - 1][yCount - 2].state = false;
			inLoop = false;
		}
		cellX = othercheckedCell.x;
		cellY = othercheckedCell.y;
		dirs = [0, 1, 2, 3];
	}
	let tmpDirIndex = floor(random(0, dirs.length));
	nextDir = dirs[tmpDirIndex];
	dirs.splice(tmpDirIndex, 1);
	switch (nextDir) {
		case 0: tmpX = 0; tmpY = -2; break;
		case 1: tmpX = 2; tmpY = 0; break;
		case 2: tmpX = 0; tmpY = 2; break;
		case 3: tmpX = -2; tmpY = 0; break;
		default: break;
	}
	let nextX = cellX + tmpX, nextY = cellY + tmpY;
	let betNextX = cellX + tmpX / 2, betNextY = cellY + tmpY / 2;
	if (nextX >= 0 && nextX < xCount && nextY >= 0 && nextY < yCount) {
		if (cells[nextX][nextY].state == true) {
			cells[nextX][nextY].state = false;
			cells[betNextX][betNextY].state = false;
			checkedCells.push(new Points(cellX, cellY));
			cellX = nextX; cellY = nextY; dirs = [0, 1, 2, 3];
		}
	}
}

function init() {
	aside = floor(random(5, 40));
	optMarginX = 0, optMarginY = 0;
	dirs = [0, 1, 2, 3];
	mazeColor = random(0, 360);
	inLoop = true;
	xCount = floor((width - margin * 2) / aside);
	if (xCount % 2 == 0) {
		xCount--;
		optMarginX = aside / 2;
	}
	yCount = floor((height - margin * 2) / aside);
	if (yCount % 2 == 0) {
		yCount--;
		optMarginY = aside / 2;
	}
	cells = Array.from(new Array(xCount), () => new Array(yCount).fill(null));
	for (let j = 0; j < yCount; j++) {
		for (let i = 0; i < xCount; i++) {
			cells[i][j] = new Vertex(i, j);
		}
	}
	cellX = floor(random(1, xCount - 2));
	if (cellX % 2 == 0) { cellX++; }
	cellY = floor(random(1, yCount - 2));
	if (cellY % 2 == 0) { cellY++; }
	cells[cellX][cellY].state = false;
	checkedCells.push(new Points(cellX, cellY));
}

class Vertex {
	constructor(i, j) {
		this.state = true;
		this.x = (margin + optMarginX) + i * aside;
		this.y = (margin + optMarginY) + j * aside;
	}

	drawRect() {
		if (this.state) {
			fill(mazeColor, 20, 85, 1);
			noStroke();
			stroke(mazeColor, 20, 85, 1);
			strokeWeight(.5);
			rect(this.x, this.y, aside, aside);
		}
	}
}

class Points {
	constructor(i, j) {
		this.x = i;
		this.y = j;
	}
}

function sleep(waitTime) {
	let startTime = new Date();
	while (new Date() - startTime < waitTime);
}

これでいつ何時迷路で遊びたくなったとしても、すぐさま新しい迷路が手に入れられるわけですが…やっぱり、目の前で迷路ができていくのを眺めていると「あー、これすぐ解きたい。今作られてるこの迷路が完成したら、画像をプリントアウトとかしないですぐ遊びたい」という淫らな欲望がふつふつと沸き上がってきてしまうのが人間というもの。

このスケッチを描いている途中で、己の中に滾り始めたその欲望に抗えなくなり、追加で別のスケッチを作りました。次のエントリでご紹介します