javascriptで不思議のダンジョン自動生成

Roguelike(Rogue, NetHack,トルネコ,etc)のダンジョンを自動生成するプログラムです。
javascriptにもだいぶ慣れてきたので、やってみました。
http://eva-lu-ator.net/~gemma/geocities/jscont/dungeon.html

昔に書いた解説はこちら。 http://racanhack.sourceforge.jp/rhdoc/index.html
Gauche で書いた例はこちら。 id:Gemma:20070617


以下、解説。
まずは、[40][80]の２次元配列を用意して、初期化して、表示してみましょう。
実例: http://eva-lu-ator.net/~gemma/geocities/jscont/dungeon_a.html

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
  <title>Dungeon</title>
  <meta http-equiv="content-type" content="text/html; charset=utf-8" />
  <script src="./lib/prototype.js" type="text/javascript"></script>
  <script type="text/javascript" language="javascript">
  // <![CDATA[

var dungeon_width = 80;
var dungeon_height = 40;

dungeon = new Array(dungeon_height);
for (j=0; j < dungeon_height; j++) {
   dungeon[j] = new Array(dungeon_width)
   for (i=0; i < dungeon_width; i++) {
     dungeon[j][i] = '.';
   }
}

function main() {
  dungeon.each(function(x) {
    var elt = document.createElement('code');
    elt.appendChild(document.createTextNode(x.join('')));
    $('main').appendChild(elt);
    $('main').appendChild(document.createElement('br'));
  });
}

window.onload = main;
  // ]]>
  </script>
</head>
<body>
<div id="main"></div>
</body>
</html>

では次に区画分け。

実例: http://eva-lu-ator.net/~gemma/geocities/jscont/dungeon_b.html
肝はsplit関数で、

function split(rect) {
  if ((rect.x1 - rect.x0 < margin * 2) ||
      (rect.y1 - rect.y0 < margin * 2) ||
      (random_range(0,5) === 0)) {
　　//以上が終了条件
    return [rect];
  } else {
    if (random_range(0,2) === 0) {
      //縦に分割
      var a = random_range(rect.y0 + margin, rect.y1 - margin);
      return [new rectangle(rect.x0, rect.y0, rect.x1, a),
	      new rectangle(rect.x0, a, rect.x1, rect.y1)].map(split).flatten();
    } else {
      //横に分割
      var a = random_range(rect.x0 + margin, rect.x1 - margin);
      return [new rectangle(rect.x0, rect.y0, a, rect.y1),
	      new rectangle(a, rect.y0, rect.x1, rect.y1)].map(split).flatten();
    }
  }
}

となっています。
map(split).flatten(); で、どんどん区画を再帰で細かくしていって最後のflattenで１次元の配列にしています。

最終的には、それをこんなふうに、つないでやるわけです。

これで、「どの部屋も必ず繋がっている」ことが保証されます。
この保証さえあれば後は自由に、通路を足したり、隠し部屋を作ったり、できます。

つなぐ処理がmake_corriderです。

function make_corrider(partitions, rooms) {
  var connect_list = new Array();
  
  for (var i = 0; i < partitions.length - 1; i++)
    connect_list.push([i, i + 1]);
    
  var connect = function(p0,p1,r0,r1) {
    if (p0.y1 == p1.y0) {
      var a = random_range(r0.x0, r0.x1);
      var b = random_range(r1.x0, r1.x1);
      fill(new rectangle(a, half(p0.y0 + p0.y1), a, p0.y1));
      fill(new rectangle(b, half(p1.y0 + p1.y1), b, p1.y0));
      fill(new rectangle(a, p0.y1, b, p1.y0));
    } else if (p0.x1 == p1.x0) {
      var a = random_range(r0.y0, r0.y1);
      var b = random_range(r1.y0, r1.y1);
      fill(new rectangle(half(r0.x0 + r0.x1), a, p0.x1, a));
      fill(new rectangle(half(r1.x0 + r1.x1), b, p1.x0, b));
      fill(new rectangle(p0.x1, a, p1.x0, b));
    }
  };
  
  connect_list.each(function(x){
                         connect(partitions[x[0]],partitions[x[1]],rooms[x[0]],rooms[x[1]])});
}

分割の方向が縦か横かを判断してから、それに応じた通路を書いてやります。通路の形は、２回曲がり角があるような、Z字、N字です。
実例: http://eva-lu-ator.net/~gemma/geocities/jscont/dungeon_c.html

これで、「どの部屋も必ず繋がっている」ことが保証されています。
しかし、ただの一本道になって迷路としてつまらないので、通路を足してやります。
そこでmake_corriderのconnect_listに、座標が隣り合っている区画のペアを、ランダムに追加してやります。

  for (var i = 0; i < partitions.length; i++)
    for (var j = i + 1; j < partitions.length; j++)
      if (random_range(0,5) == 0)
	if (partitions[i].x0 == partitions[j].x1 ||
	    partitions[i].x1 == partitions[j].x0 ||
	    partitions[i].y0 == partitions[j].y1 ||
	    partitions[i].y1 == partitions[j].y0)
	  connect_list.push([i,j]);

これで完成です。
実例: http://eva-lu-ator.net/~gemma/geocities/jscont/dungeon.html