■ HTML5のCanvasに自動生成した迷路を描画してみた

2010年5月6日 5:57 PM | カテゴリ: Featured, HTML5 | コメント(1)

HTML5のCanvasに自動生成した迷路を描画してみた

GW中にPCに触れなかった反動でついカッとなって。


ゲームではありません。
自動生成した迷路をHTML5のCanvas + JavaScriptで実現してみたくなったので。
今回の迷路生成アルゴリズムは、壁延ばし法を採用してみました。
詳しくは、こちら↓
自動生成迷路

以下、HTMLファイルです。

以下、JavaScriptファイルです。
必要以上にコメントを入れてますんで、
鬱陶しいかもしれませんｗ

/**
 * 定数宣言
 */
const MAZE_WIDTH = 51;          // 迷宮の縦サイズ
const MAZE_HEIGHT = 51;         // 迷宮の横サイズ

/**
 * 変数宣言
 */
var ctx;                        // 2Dコンテキストオブジェクト
var mazeArray;                  // 迷宮の配列
var directionX = [-1, 0, 1, 0]; // 方向配列(X軸)
var directionY = [0, -1, 0, 1]; // 方向配列(Y軸)

/**
 * Pointクラス
 */
function Point(x, y) {
  this.x = x;
  this.y = y;
}

/**
 * イニシャライズ
 */
window.onload = function() {
  // Canvas要素の取得
  var canvas = document.getElementById('canvas');

  // Canvasサイズの変更
  canvas.width = MAZE_WIDTH * 8;
  canvas.height = MAZE_HEIGHT * 8;

  // Canvas要素から2Dコンテキストオブジェクトを取得する
  ctx = canvas.getContext('2d');

  // 迷宮配列の作成（周辺壁のみ）
  mazeArray = new Array(MAZE_HEIGHT);
  for (var i = 0; i < MAZE_HEIGHT; i++) {
    var lineArray = new Array(MAZE_WIDTH);
    for (var j = 0; j < MAZE_WIDTH; j ++) {
      if (j == 0 || j == MAZE_WIDTH - 1 ||
          i == 0 || i == MAZE_HEIGHT - 1) {
        lineArray[j] = 1;
      } else {
        lineArray[j] = 0;
      }
    }
    mazeArray[i] = lineArray;
  }

  // 壁延ばし開始位置のスタックを作成
  var stack = [];
  for (i = 2; i < MAZE_WIDTH - 2; i += 2) {
    stack.push(new Point(i, 0));
    stack.push(new Point(i, MAZE_HEIGHT - 1));
  }
  for (i = 2; i < MAZE_HEIGHT - 2; i += 2) {
    stack.push(new Point(0, i));
    stack.push(new Point(MAZE_WIDTH - 1, i));
  }
  var count = 0;
  while (stack.length > 0) {
    var r = Math.floor(Math.random() * stack.length);
    var point = stack[r];
    stretch(mazeArray, stack, point);
  }
  draw();
}

/**
 * 壁を伸ばす
 */
function stretch(array, stack, origin) {
  // 壁延ばし開始位置をスタックから消去
  var index = stack.indexOf(origin);
  if (index > -1)
    stack.splice(index, 1);

  var point = origin;  // 現在位置
  var deadEnd = false; // 行き止まりフラグ

  // これ以上伸ばせなくなるまで壁を伸ばす
  while (!deadEnd) {
    // 延伸可能位置を４方向から探索
    var directions = [];
    for (var direction = 0; direction < 4; direction++) {
      var po = new Point(point.x + directionX[direction] * 2,
                         point.y + directionY[direction] * 2);
      if (po.x >= 0 && po.x < MAZE_WIDTH &&
          po.y >= 0 && po.y < MAZE_HEIGHT &&
          array[po.y][po.x] == 0) {
        directions.push(direction);
      }
    }

    if (directions.length == 0) {
      // これ以上伸ばせなくなったら行き止まりフラグを立てる
      deadEnd = true;
    } else {
      // 方向を確定
      var r = Math.floor(Math.random() * directions.length);
      direction = directions[r];
      // 2つ先の位置を指定
      longPosition = new Point(point.x + directionX[direction] * 2,
                               point.y + directionY[direction] * 2);
      // 1つ先の位置を指定
      shortPosition = new Point(point.x + directionX[direction],
                                point.y + directionY[direction]);
      // 伸ばした位置を壁延ばし開始位置スタックに入れる
      stack.push(longPosition);
      // 迷宮配列の壁を伸ばす
      array[longPosition.y][longPosition.x] = 1;
      array[shortPosition.y][shortPosition.x] = 1;
      point = longPosition;
    }
  }
}

/**
 * 迷路の描画
 */
function draw() {
  ctx.fillStyle = "#999999";
  for (var i = 0; i < MAZE_HEIGHT; i ++) {
    for (var j = 0; j < MAZE_WIDTH; j ++) {
      if (mazeArray[i][j] == 1)
        ctx.fillRect(j * 8, i * 8, 8, 8);
    }
  }
}

実際の動作は、こちらをご覧ください。

迷路自動生成

わかりづらい！とか、もっといい方法がある！という意見がありましたら
コメントいただけると喜びます＾＾