繋がっているブロックの数を調べる - ぷよぷよアルゴリズム

ぷよぷよのゲームを実装しようとした場合、4つ以上のブロックが繋がっているか調べる必要があります。今回、「ぷよぷよの作り方」を参考に、JavaScriptで繋がっているブロックの数を調べる方法、繋がっているブロックを消す方法を実装してみました。元のサイトのものに少し手を加えてあります。

今回、関数を再帰的に呼び出すことによって、繋がっているブロックを探索します。ちなみに私はぷよぷよを作るためにこのアルゴリズムについて調べていたのではなく、他のパズルゲームを作っているときにこのアルゴリズムが必要になりました。今回いくつかのサイトを調べてみたところ、「ぷよぷよの作り方」(上で挙げたのと名前は同じですが違うサイトです)も同じように再帰的な探索を利用していました。また少し違った方法として、「「ぷよぷよ」を作ろう」がありました。

最初は本質とは関係ない部分から

まずはブロックの種類を定義しておきます。ブロックの種類を数字で表すという方法は、マジックナンバーと呼ばれ、推奨されていない方法です。そこで今回、ブロックの種類をオブジェクトとして表現しました。

Type = function(mark,color){
	this.mark = mark;
	this.color = color;
};
Type = {
	BLOCK1 : new Type("●","green"),
	BLOCK2 : new Type("■","blue"),
	BLOCK3 : new Type("★","orange"),
	BLOCK4 : new Type("▲","gray"),
	BLOCK5 : new Type("◆","yellow"),
	EMPTY : new Type("□")
};

例えば、黒丸のブロックを指定したい場合、Type.BLOCK1というオブジェクト定数で表現します。また今回空のブロックを示す、Type.EMPTYというオブジェクトも作りました。

セルを作ってブロックを格納

二次元配列にブロックを格納します。今回はテストですので、全てのセルを適当に埋めます(空のブロックも入れます)。初期化のための関数initを作ります。ちなみに上で定義されているcellsが今回定義する二次元配列で、他の関数からもアクセス可能にしておきます。

//10*10のセルを作る
var cells;
var CELL_X = 10;
var CELL_Y = 10;

var init = function(){
	cells = new Array(CELL_X);
	for (var i = 0; i < cells.length; i++) {
		cells[i] = new Array(CELL_Y);
		for (var j = 0; j < cells[i].length; j++) {
			var random = Math.floor(Math.random() * 5 + 1);
			switch (random) {
				case 1:
					cells[i][j] = Type.BLOCK1;
					break;
				case 2:
					cells[i][j] = Type.BLOCK2;
					break;
				case 3:
					cells[i][j] = Type.BLOCK3;
					break;
				case 4:
					cells[i][j] = Type.BLOCK4;
					break;
				case 5:
					cells[i][j] = Type.EMPTY;
					break;
			}
		}
	}
};

描写

initを実行したあとで、以下のようなpaintという関数を呼ぶことで描写を行います。すごい適当な実装です。

var paint = function(){
	document.body.innerHTML = "";
	for(var i= 0; i<cells.length; i++){
		for (var j = 0; j < cells[i].length; j++) {
			document.body.innerHTML += "<font color='"+ cells[i][j].color +"'>"+cells[i][j].mark+"</font>";
		}
		var br = document.createElement("br");
		document.body.innerHTML += "<br>";
	}
};

実行するとこのようになります。

こっから本番

近接する同じ種類のブロックを探して数える関数を定義します。この関数は単に連続するブロックを数えるだけでなく、連続するブロックが4つ以上つながっていれば削除する機能も加えます。ブロックの数を数えるのか、削除を行うのか、引数の値によって機能を分岐します。そこで、関数の定義を

function check(checkType, x, y){}

という形にしました。checkType=1がブロックの数え上げ、checkType=2がブロックの削除になります。この関数は実行すると最後に、このブロックの数を返します。checkType=2の場合は削除できたブロックの個数になります。また、xとyはブロックのチェックを開始する位置です。
これを以下のように実装しました。checkという関数は内部でcheckRecursiveという関数をよび、checkRecursiveという関数は再帰的に探索を行っていきます。ここでのポイントは、checkの中で作成しているcells_checkという二次元配列です。これはcellsと同じ大きさの二次元配列で、ここに探索を行ったかどうかというチェックを入れていきます。未探索のセルには-1、探索済みのセルのうち、チェックの開始点と同じ種類のセルには1。探索済みのうち、チェック開始点と異なる種類のセルには2をつけます。

/**
 * 近接する同じ種類のブロックを探す
 * 返り値は 二次元配列
 * checkTypeの値を1に指定すると、近接するブロックの数を返す
 * checkTypeの値を2に指定すると、近接するブロックが3個以上の場合消去すし、消去できた数を返す.
 * @param {Object}checkType チェックの種類
 * @param {Object} x ブロックを置く位置
 * @param {Object} y
 */
function check(checkType, x, y){
	if(cells[x] == null || cells[x][y] == null || cells[x][y] == Type.EMPTY ) return 0; //範囲外か空のブロック
	/*
	 * 探索用に二次元配列を作る.
	 * 未探索は-1
	 * 探索済み (x,y)にあるブロックと同じ種類のブロックは1
	 *               違う種類のブロック,空のブロックは 2
	 */
	var blockType = cells[x][y];
	var cells_check = new Array(CELL_X);
	for (var i = 0; i < cells_check.length; i++) {
		cells_check[i] = new Array(CELL_Y);
		for (var j = 0; j < cells_check[i].length; j++) {
			cells_check[i][j] = -1; //未チェック
		}
	}
	checkRecursive(x, y, cells_check, blockType);
	//隣接するブロックの数を数える
	var count = 0;
	for (var i = 0; i < cells_check.length; i++) {
		for (var j = 0; j < cells_check[i].length; j++) {
			if (cells_check[i][j] == 1) {
				count++;
			}
		}
	}
	//ブロック消去
	if (checkType == 2) {
		if (count >= 2) {
			for (var i = 0; i < cells_check.length; i++) {
				for (var j = 0; j < cells_check[i].length; j++) {
					if (cells_check[i][j] == 1) {
						cells[i][j] = Type.EMPTY;
					}
				}
			}
		}else{
			return 0;
		}
	}
	return count;
}

/**
 * @param {Object} x
 * @param {Object} y
 * @param {Object} cells_check 二次元配列
 * @param {Object} blockType ブロックの種類
 */
function checkRecursive(x, y, cells_check,blockType){
	if(cells[x] == null || cells[x][y] == null || 0 < cells_check[x][y]) return; //範囲外か探索済み
	if (cells[x][y] != blockType) { //ブロックの種類が違う
		cells_check[x][y] = 2;
		return;
	}
	//一致
	cells_check[x][y] = 1; //チェック
	checkRecursive( x + 1, y, cells_check, blockType); //右探索
	checkRecursive( x - 1, y, cells_check, blockType); //左
	checkRecursive( x, y + 1, cells_check, blockType); //下
	checkRecursive( x, y - 1, cells_check, blockType); //上
	return;
}

ではこれを使ってみます。まずinitで初期化を行い、その直後にpaintを入れます。そして、適当な座標に対してブロックが連続するか調べてみます。なお、このとき4つ以上のブロックが連続していれば削除するようにcheckTypeを2にしておきます。以下のコードようにして実行すると、一旦描写されたあとで、アラートがでます。アラートをクリックすると、checkが呼ばれます。このとき(4,4)を基点に連続するブロックが4つ以上あれば、そこが削除され、新たに変化した様子が画面に描写されます。ブロックの配置はランダムなので、何回かリロードしてやればブロックが消えてくれるはずです。このチェックを全セルに対してやると良いです。

init();
paint();
alert( check(2,4,4) );
paint();

以上です。一応ソース乗せておきます。
puyo_algo.zip