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

引き続き、BULLETに飽きた時の気分転換用のすごろく自動生成を考えよう。
前回は簡単なアルゴリズムで、通路の作成まで出来た。

このシリーズの関連記事

すごろくの自動生成について考える 1/5
http://d.hatena.ne.jp/tsugehara/20130103/1357227114

すごろくの自動生成について考える 2/5
http://d.hatena.ne.jp/tsugehara/20130104/1357270438

すごろくの自動生成について考える 4/5
http://d.hatena.ne.jp/tsugehara/20130220/1361334869

すごろくの自動生成について考える 5/5
http://d.hatena.ne.jp/tsugehara/20130225/1361791529

現在進んでいる方向の定義と方向転換

前回の問題の一つに、「くねくねしすぎ」ってのがあった。
それもそのはず、完全ランダムで適当に進んでいるだけなので、必然的にうねる。
この対処をするためにも、現在進んでいる方向を保持し、方向転換を一定確率で行うようにすればいい。

解説前に実行結果とデモ。

http://tsuge.sub.jp/sugoroku/blog/add_current_course.html

Perっていう入力値が新しく追加されているので、その数値をいじらながら適当に生成すると、値が少なければ少ないほど直線的なすごろくが出来るようになる。

少しリファクタリングをしているので、その辺の説明をはしょって、肝心のgenRouteメソッドだけ解説。

	genRoute: function() {
		var p, course, maze;
		var try_count = 0;
		do {
			p = new Pos(this.start.x, this.start.y);
			maze = this.cloneMaze();
			if (++try_count > 3000) {
				alert("can not create route");
				return;
			}
			var current_course = this.getNewCourse(p, maze);
			if (! current_course) {
				alert("can not create route");
				return;
			}
			while (! p.is(this.end)) {
				var add = p.addNew(current_course);
				if (! this.canCreateRoute(add, maze, current_course) || this.isChangeCourse()) {
					var courses = this.getCourses(p, maze);
					if (courses.length == 0)
						break;
					current_course = courses[rand(0, courses.length-1)];
					p.add(current_course);
				} else {
					p.add(current_course);
				}
				if (! p.is(this.end))
					maze[p.x][p.y] = 3;
			}
		} while (! p.is(this.end));
		this.maze = maze;
	},

進行方向を保存するため、以前までは毎回「どこ進もうかな」と考えていたのを、current_course変数に今進んでいる方向を記憶して基本的にはその方向に進みつつ、進めなくなった場合か一定確率で進路を変更するようにした。

迷路や洞窟ではないためperは結構少なくてよくて、18くらいで適正値だと思われる。
1や2でもそれなりに面白いけど、0は詰む。
※0を詰まないようにすることも出来るけど、省略

分かれ道

per18だと100x100でもまず詰まない。ゴール方向に誘導してあげる必要があるかと思ったけど、そんなことなかった。試した限り200x200では十分詰むから、もう少し大きいすごろくを作るなら、進行方向をさりげなくゴールの方に寄せてあげる必要があるかもしれないけど、今回の用途では100x100が最大値であるため不要。

ということで、基本的な通路はほとんど出来ちゃった気がするので、次は分かれ道を考えよう。

分かれ道については、これまでのアルゴリズムを変更する必要は特に無くて、最初にスタートとゴールを設定する、スタートとゴールまでの道を作る、までやった後、「今ある通路から任意の確率で分かれ道を発生させる」処理を動かせばいい。

いいんだけど、少し複雑な問題があって、既存の通路と分かれ道の通路が並行して走ってしまうと、2マスの通路が出来てしまうという問題が出てくる。
このため、分かれ道は既存の通路に合流可能なものの、合流すると際には2マス先から一気に合流してくれないと困ることになる。

わかりづらいので図説すると、こういう既存の通路があって、

□■□□□
□■□□□
□■□□□
□■□□□
□■□□□

こういう分かれ道はOK。

□■□□□
□■■■□
□■□■□
□■■■□
□■□□□

これは、駄目。

□■■□□
□■■■□
□■□■□
□■■■□
□■□□□

ということで、既存の道と合流できるようにしつつ、並行出来ないようにしないといけない、ということ。
また、分かれ道が別の分かれ道と合流するのはいいけど、分かれ道が自分自身と合流は出来ないようにした方がいいかな。

続く

分かれ道の生成が必要なので、次はそのコーディング作業ですな。