すごろくの自動生成について考える 2/5

引き続き、すごろくの自動生成について考えよう。
前回はすごろくの定義と大体のフェーズ分けまで出来た。

このシリーズの関連記事

フェーズ分け部分を作る

とりあえず通路が難しいのはわかっているので、通路以外をささっと書こう。
こんなんでいいだろう。

<html>
<head>
<title>Sugoroku generator</title>
<script type="text/javascript">
function Maze(width, height) {
	this.width = parseInt(width);
	this.height = parseInt(height);
	this.maze = [];
	for (var x=0; x<this.width; x++) {
		this.maze[x] = [];
		for (var y=0; y<this.height; y++) {
			this.maze[x][y] = 0;
		}
	}
	this.start = null;
	this.end = null;
}
Maze.prototype = {
	fillStyle: {
		0: "#000",
		1: "#ff0",
		2: "#f00",
		3: "#fff"
	},
	genFixedPoints: function() {
		do {
			this.start = new Pos(rand(0, this.width-1), rand(0,this.height-1));
			this.end = new Pos(rand(0, this.width-1), rand(0,this.height-1));
		} while(Math.max(Math.abs(this.start.x-this.end.x), Math.abs(this.start.y-this.end.y)) < 1);
		this.maze[this.start.x][this.start.y] = 1;
		this.maze[this.end.x][this.end.y] = 2;
	},
	genRoute: function() {
	},
	genCell: function() {
	},
	draw: function(canvas) {
		var ctx = canvas.getContext("2d");
		ctx.save();
		var w = Math.floor(canvas.width / this.width);
		var h = Math.floor(canvas.height / this.height);
		ctx.clearRect(0, 0, canvas.width, canvas.height);
		for (var x=0; x<this.width; x++) {
			for (var y=0; y<this.height; y++) {
				ctx.fillStyle = this.fillStyle[this.maze[x][y]];
				ctx.fillRect(x*w, y*h, w, h);
			}
		}
		ctx.restore();
	}
}
function generate() {
	document.getElementById("h").value
	Math.random()
	var maze = new Maze(
		document.getElementById("w").value ? document.getElementById("w").value : rand(20, 100),
		document.getElementById("h").value ? document.getElementById("h").value : rand(20, 100)
	);
	document.getElementById("w").value = maze.width;
	document.getElementById("h").value = maze.height;
	maze.genFixedPoints();
	maze.genRoute();
	maze.genCell();
	maze.draw(document.getElementById("c"));

}
function rand(s, e) {
	return Math.floor(Math.random() * (e - s + 1) + s);
}
function Pos(x, y) {
	this.x = x;
	this.y = y;
}
</script>
</head>
<body>
<h1>Sugoroku genrator</h1>
<div>
	W <input type="text" id="w" value="" size="3" />
	H <input type="text" id="h" value="" size="3" />
	<input type="button" onclick="generate()" value="generate" />
</div>
<div>
	<canvas id="c" width="400" height="400"></canvas>
</div>
</body>
</html>

細かい解説は省略するけど、Mazeクラスにまとめてある。
Mazeクラスには重要な関数が五つあって、それぞれ以下の通り。

関数	役割	備考
コンストラクタ	フロアサイズ決定	縦横共に20〜100
genFixedPoints	スタート地点とゴール地点決定	ランダム。ただしスタートとゴールは2マス以上離す
genRoute	通路決定	まだ作ってない
genCell	マス決定	まだ作ってない

実行すると、スタートとゴールだけ描かれたすごろくが出来る。
黒が壁、黄色がスタート、赤がゴール、白が通路。
白はまだ無い。

部品作り

今後どんなアルゴリズムを使うにせよ、「現在位置からどう動くか」なので、東西南北のどこに動くかとか、現在からどこに動けるかとか、そういうのを計算してくれる部品を先に作りましょうかね。
まずこの三つをMaze.prototypeに追加。

	getCourses: function(base, maze) {
		var ret = [];
		var ewsn = ["east","west","south","north"];
		for (var i=0; i<ewsn.length; i++) {
			var add = this.getEWSNPos(ewsn[i]);
			var p = base.addNew(add);
			if (p.x < 0 || p.x >= this.width || p.y < 0 || p.y >= this.height)
				continue;
			if (maze[p.x][p.y] == 1 || maze[p.x][p.y] == 3)
				continue;
			ret.push(add);
		}
		return ret;
	},
	getEWSNPos: function(ewsn) {
		switch (ewsn) {
		case "east":
			return new Pos(1, 0);
		case "west":
			return new Pos(-1, 0);
		case "south":
			return new Pos(0, 1);
		case "north":
			return new Pos(0, -1);
		}
		throw "hen dayo.";
	},
	cloneMaze: function() {
		var maze = [];
		for (var x=0; x<this.width; x++) {
			maze[x] = [];
			for (var y=0 ;y<this.height; y++) {
				maze[x][y] = this.maze[x][y];
			}
		}
		return maze;
	},

上から、東西南北に動けるルートを計算、東西南北それぞれの加算値を計算、迷路のクローンを生成。
迷路のクローンについては、動けなくなったら作り直さないといけないので一応。なくてもいいけど。

んで、場所クラスPosにもちょっとだけメソッド追加。
こんなんすね。

Pos.prototype = {
	is: function(pos) {
		return this.x == pos.x && this.y == pos.y;
	},
	addNew: function(pos) {
		return new Pos(this.x + pos.x, this.y + pos.y);
	},
	add: function(pos) {
		this.x += pos.x;
		this.y += pos.y;
	}
}

上から、同じ場所かどうか、加算した上で新しいインスタンスを返すメソッド、自分自身に加算するメソッド。
部品はこんなもんでまあ十分でしょう。

一番簡単な通路生成

とりあえず通路を生成しよう。
一番簡単なのっていうと、「完全ランダム」。
東西南北いずれかに進めて、ゴールにたどりついたら道完成、たどりつけなかったら最初からやり直し。
なお、この段階では一本道で、まだ分かれ道とかは考えないものとする。

genRouteを書いてみる。

	genRoute: function() {
		var p, course, maze;
		do {
			p = new Pos(this.start.x, this.start.y);
			maze = this.cloneMaze();
			while (! p.is(this.end)) {
				var courses = this.getCourses(p, maze);
				if (courses.length == 0)
					break;
				p.add(courses[rand(0, courses.length-1)]);
				if (! p.is(this.end))
					maze[p.x][p.y] = 3;
			}
		} while (! p.is(this.end));
		this.maze = maze;
	},

実行結果がこちら。

東西南北自由に動くので、通路が連結しまくって肥大化している。
洞窟っぽいけど、明らかにすごろくではない。

ちなみにこれは、結構ハマる。
特に100x100サイズのような大きいフロアの場合、そんなランダムだけでゴールにたどりつけるわけないでしょうってJavaScriptが悲鳴をあげて、事実上の無限ループになって処理が終わらないことが多々ある。

通路を一マスにする

ゴールに導いてあげる方法は後で考えるとして、とりあえず通路が二マス以上あるすごろくって無い気がする、ということで、通路は1マスになるようにしよう。
getCoursesを修正しよう。

	getCourses: function(base, maze) {
		var ret = [];
		var ewsn = ["east","west","south","north"];
		for (var i=0; i<ewsn.length; i++) {
			var add = this.getEWSNPos(ewsn[i]);
			var p = base.addNew(add);
			if (p.x < 0 || p.x >= this.width || p.y < 0 || p.y >= this.height)
				continue;
			if (maze[p.x][p.y] == 1 || maze[p.x][p.y] == 3)
				continue;

			var plus_ones = this.getEWSNPlusOne(ewsn[i]);
			var ng = false;
			for (var j=0; j<plus_ones.length; j++) {
				var p2 = p.addNew(plus_ones[j]);
				if (p2.x < 0 || p2.x >= this.width || p2.y < 0 || p2.y >= this.height)
					continue;
				if (maze[p2.x][p2.y] == 1 || maze[p2.x][p2.y] == 3) {
					ng = true;
					break;
				}
			}
			if (ng)
				continue;
			ret.push(add);
		}
		return ret;
	},
	getEWSNPlusOne: function(ewsn) {
		var ret = [];
		switch (ewsn) {
		case "east":
			ret.push(this.getEWSNPos("east"));
			ret.push(this.getEWSNPos("south"));
			ret.push(this.getEWSNPos("north"));
			return ret;
		case "west":
			ret.push(this.getEWSNPos("west"));
			ret.push(this.getEWSNPos("south"));
			ret.push(this.getEWSNPos("north"));
			return ret;
		case "south":
			ret.push(this.getEWSNPos("east"));
			ret.push(this.getEWSNPos("west"));
			ret.push(this.getEWSNPos("south"));
			return ret;
		case "north":
			ret.push(this.getEWSNPos("east"));
			ret.push(this.getEWSNPos("west"));
			ret.push(this.getEWSNPos("north"));
			return ret;
		}
		throw "hen dayo.";
	},

まあメソッド名の命名センスが無いのはともかく、getEWSNPlusOneで一歩先の判定対象をとってきて、getCoursesで一歩先に通路かスタート地点があれば進行方向候補から外すっていう修正をする。
すると、こうなる。

大分それっぽくなった。
ただ、相変わらず無限ループになる問題はあるし、分かれ道も無いし、そもそもくねくねしすぎな気がする。

次回の課題とデモサイト

一応、無限ループ防止というか、3000回やっても駄目なら諦めて下さい的な処理を入れて、それぞれのデモを下記においた。
http://tsuge.sub.jp/sugoroku/blog/full_random.html
http://tsuge.sub.jp/sugoroku/blog/full_random2.html

ちょっとくねくねしすぎなので、次回はある程度直線通路を作る処理を加えて、無限ループをなるべく減らしたバージョンまで進展させたところまでは書こうかなと思う。