読者です 読者をやめる 読者になる 読者になる

素人がプログラミングを勉強していたブログ

プログラミング、セキュリティ、英語、Webなどのブログ since 2008

連絡先: すかいぷ:javascripter_  か javascripter あっと tsukkun.net skypeのほうがいいです

棒倒し法による自動生成の迷路

javascript

JavaScriptによる自動生成迷路に置いた。

 function rand(n) {
    return Math.floor(Math.random() * n);
  }
  
  const width = 33, height = 33;
  var wall = (1 << (width - 2)) - 1 << 1;
  var table = [1 << (width - 2)];
  var stripe = 0;
  var i, j;
  for (i = 1; i < width; i += 2) {
    stripe |= 1 << i;
  }
  for (i = 1; i < height - 1; i++) {
    table[i] = i & 1 ? wall : stripe;
  }
  table[height - 1] = 2;
  
  const top = 0, right = 1, bottom = 2, left = 3;
  
  for (i = 2; i < height - 2; i += 2) {
    for (j = 2; j < width - 2; j += 2) {
      var choices = [];
      if (table[i - 1] & 1 << j) {
        choices.push(top);
      }
      if (table[i] & 1 << j >> 1) {
        choices.push(right);
      }
      if (table[i + 1] & 1 << j) {
        choices.push(bottom);
      }
      if (j == width - 3) {
        choices.push(left);
      }
      switch (choices[rand(choices.length)]) {
      case top:
        table[i - 1] ^= 1 << j;
        break;
      case right:
        table[i] ^= 1 << j >> 1;
        break;
      case bottom:
        table[i + 1] ^= 1 << j;
        break;
      case left:
        table[i] ^= 1 << j << 1;
        break;
      }
    }
  }
  
  const scale = 10;
  var canvas = document.getElementById("canvas");
  canvas.width = width * scale;
  canvas.height = height * scale;
  var context = canvas.getContext("2d");
  
  for (i = 0; i < height; i++) {
    for (j = 0; j < width; j++) {
      if (~table[i] & (1 << j)) {
        context.fillRect((width - j - 1) * scale, i * scale, scale, scale);
      }
    }
  }

大きさ制限のないバージョンは

function rand(n) {
  return Math.floor(Math.random() * n);
}

const width = 33, height = 33;

var table = [];
var i, j, k;
for (i = 0; i < width; i++) {
  table[i] = [];
  for (j = 0; j < height; j++) {
    table[i][j] = !(i == 1 && j == 0) && !(i == width-2 && j == height-1) && (i == 0 || j == 0 || i == width - 1 || j == height - 1) || i % 2 == 0 && j % 2 == 0;
  }
}
for (j = 2; j < height-2; j += 2) {
  for (i = 2; i < width-2; i += 2) {
    var choices = [];
    if (j == 2) {
      choices.push([i-1,j]);
    }
    if (!table[i][j-1]) {
      choices.push([i,j-1]);
    }
    if (!table[i+1][j]) {
      choices.push([i+1,j]);
    }
    if (!table[i][j+1]) {
      choices.push([i,j+1]);
    }
    if (choices.length == 0) {
      continue;
    }
    var wall = choices[rand(choices.length)];
    table[wall[0]][wall[1]] = true;
  }
}

var scale = 2;
var canvas = document.createElement("canvas");
canvas.width = width*scale;
canvas.height = height*scale;
var context = canvas.getContext("2d");
table.forEach(function (line, i) {
  line.forEach(function (cell, j) {
    if (cell) {
      context.fillRect(i*scale, j*scale, scale, scale);
    }
  });
});

document.body.appendChild(canvas);

こんな感じ