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

ようやく最終回。最終回なんだけど、うっかり前回回数を決めてしまったので、本当は2回分の内容を一つに強引にまとめているためちょっと長くなってしまった。

このシリーズの関連記事

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

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

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

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

今回の予定

今回の予定は、実はマス内容を生成するってだけなんだけど、それだけじゃ面白くないよなぁと悪い癖が。
ということで、マス内容を生成するのに、そのマス内容を生成するための情報としてルートも計算して、ついでに不思議のすごろく側の実装での片道通行とかも考えたりしようと。

ルート検索について

ルート検索についてはいろんなアルゴリズムがあるんだけど、有名どころはこの辺らしい。

• ダイクストラ法
• A*

いずれも下記のページで大変わかりやすくまとまっている。
http://tech.nitoyon.com/ja/blog/2010/01/26/dijkstra-aster-visualize/

・・が。
今回求めたいルートは実はちょっと違う。
おさらいがてら不思議のすごろくで想定される移動方法とかも合わせて、パワポ書いた。
http://www.slideshare.net/tsugehara/ss-16651447
スライドシェアで見るとレイアウトが崩れてたので、ダウンロードしての閲覧推奨だけど。

この内容を基に、もろもろ検討して作ってみた。

A*

さて、最短ルートだけでは足らないとはいえ、「この道がゴールまでたどりつける道かどうか」を調べるためには、既存のアルゴリズム使った方が速そう。
ということで一応A*も使おうと。
作ろうと思うんだけど、この手のものって絶対誰か作ってんだよね。

javascript astarで一番上にヒットするこれを基にする。
https://github.com/bgrins/javascript-astar

微調整が必要なのと、不思議のすごろく側がTypeScriptなのでそれに合わせてTypeScript用のは自作した。
https://github.com/tsugehara/typescript-astar
まずこのastar.jsを手元に用意する。

最短経路探索と全ルート情報の生成

次は最短経路の探索なんだけど、デモベースで。
http://tsuge.sub.jp/sugoroku/blog/cell.html
左上にある「calc point」ってボタンを押すと勝手に計算し出す。
多少枝道がある方が面白い。こんな感じのがいい。

さらにマス生成の際に参考できるよう、そのマスまでのルート情報ってのが必要なんだけど、デモではそれも作ってある。
calc pointをクリックし、計算が終わった後、画面のゴールのところ（赤い四角）をクリックすると、画面下にこういう情報が表示される。

上記の情報は、このすごろくでゴールにたどり着くまでの経路が、上から行くパターン、上から行って上の枝道を利用するパターン、下の枝道を利用するパターンの合計3つであることを示している。
また、それぞれの経路情報から計算した結果、ゴールまでの最短距離は39であるとかの情報もとれている。

制限事項として、画面上部にあるlimitって入力欄以内の経路までしか計算しない。
複雑なすごろくだと25x25程度でも余裕で30万以上経路があるみたいなので、試しに夜通し計算させてみたけど終わってなかったから必ず全経路計算、は諦めた。
ちなみに[calc point]と[calc point one]ボタンの違いは、calc pointがブラウザをロックしないで（非同期で）計算、calc point oneがブラウザをロックして（同期で）計算。

解説は省略して、それぞれcalcPoint、calcPointOneっていうjavascriptのソース見てもらうのがいいかな。
同期計算するなら、これ呼べばいいだけなんだけどね。

var pp = maze.getPointedMaze();

上の例だとpp[x][y].distanceで最短距離、pp[x][y].pathにそのマスの全ルート情報が入ってる。

アルゴリズム的には、全ルート計算はastarと独自の合わせ技。独自側はただの総当りなので、えらい人が作ったものに比べるとちょっと遅いだろうなぁ。
最初に全ルート計算してから、その全ルート情報を基に最小ポイントを計算っていう順番。

マス生成

経路情報をわざわざ計算したのはマス生成をする情報として利用するためなので、マス生成もしよう。
さっきのデモのgenerate with custom cell factoryってボタンを押すと、マスも作った状態ですごろくが生成されるようになる。

まあ色もアルゴリズムも適当なんだけど、ただランダムなのもなんなので、必ず水色のマスが一つ含まれるようにした。
マス生成については、まずmazeオブジェクトのcell_factoryフィールドにコールバック関数を指定する。上記htmlの757行目にあるこの記述。

maze.cell_factory = factory;

今回はこういう内容のセル生成関数。

function cell_factory(e) {
	if (! maze.ext) {
		maze.ext = {};
		maze.ext.sp = Math.floor(Math.random() * e.activeCount);
	}
	if (e.isWall)
		return null;
	if (e.x == maze.end.x && e.y == maze.end.y)
		return null;
	if (e.x == maze.start.x && e.y == maze.start.y)
		return null;

	if (e.activeSeq == maze.ext.sp) {
		return 9;
	}
	return Math.floor(Math.random() * 6)+3;
}

最初maze.ext云々をやっているのは、まだ水色マスの情報が無い場合に、水色マスの情報を生成しているコード。
次の諸々if文は、壁、ゴール、スタートの場合マス情報を更新しないという処理。return nullで更新しないという形。
下記は事前に決めた水色マスの場所なら水色マスを返すって事。

if (e.activeSeq == maze.ext.sp)
		return 9;

最後はランダムで3〜8を返しているだけ。

なおこのコールバック関数の引数eで渡ってくる内容は下表の通り。

フィールド名	解説	備考
x	x座標
y	y座標
distanceFromStart	スタートからのマス数	最小ルートによる計算
distanceToEnd	ゴールまでのマス数	ここまでの最小ルート = beginRoutes[0]が、ゴールまで後何マスかを返す。必ずしもゴールまでの最小ルートではない点に注意
beginRoutes	事前のルート。x,yの二次元配列で、一次元目は距離の短い順、二次元目はそのマスから近い順に格納されている	beginRoutes[0][0].xだと、そこに到達するルートの内一番近いルートの、このマスから見て直前1マスのx座標が格納されている
isWall	壁かどうか
seq	壁、スタート、ゴールも含めてすべてのマスの何番目の処理か
activeSeq	スタート、ゴールを除いたすべての道の何番目の処理か
activeCount	スタート、ゴールを除いたすべての通行可能マスの合計数
wallCount	壁の合計数
roadCount	スタート、ゴールも含めたすべての通行可能マスの合計数

不思議のすごろくとの結合

せっかくなので、不思議のすごろくのすごろくシーンデモも更新してみた。
http://tsuge.sub.jp/sugoroku/demo/sugoroku20130225/index.html

ま、まあ画像は相変わらず残念だけど、マス内容がそれっぽく作られるようになっている。
不思議のすごろくは○マス戻るとかが重要なすごろくじゃないから、ルート情報結局使わないと思うけど。このデモでも使ってない。

また今までみたいに壁を貫通できるとか、一度行った道を戻れるとかもなくなっている。この辺は今回のルート検索系を応用しておまけで作った。おかげでゴールまでつくと何も出来ることがなくなっちゃうけどね。

github

すごろく自動生成については、この連載で使ったJavaScriptのコードをTypeScriptに変換したものをgithubに登録済み。
https://github.com/tsugehara/AutoSugoroku
すごろく自動生成に興味のある人は不思議のすごろくと合わせてチェックしてもらえれば。

課題

残課題無し、綺麗におしまい、と言いたいところなんだけど、実は稀にすごろく自動生成時にバグる事がわかってる。
原因まで調べてないので、現行バージョン使おうという酔狂な人がいたら、生成時にtry〜catchで囲ってエラーが起きたらリトライしてもらえれば。
エラーが起き続ける、って事はないので、リトライ何回かすりゃなんとかなります。

このシリーズはバグ残したまま終了とするので、後日の完成版は不思議のすごろくの進捗と合わせてぼちぼち。
この記事から見て、半年後くらいにgithubを見ればほぼ確実に完成版があるはずなので、使おうという人は2013年7月頃にでもまた覗いていただければということで。