forked from: match 3 puzzle remove block algorithm
すごく普通の解法っぽい気はしますが、
正確な判定は出来てると思います。
/**
* Copyright o8que ( http://wonderfl.net/user/o8que )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/kPDc
*/
// forked from bkzen's match 3 puzzle remove block algorithm
package
{
import com.bit101.components.Label;
import com.bit101.components.PushButton;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Sprite;
import flash.events.Event;
import flash.utils.getTimer;
/**
* マッチ3パズルのアルゴリズムを考える。
* scan メソッドを完成させる。
* なるべく高速で正確な方法を考える。
* grid を Array で保持することが気に入らない等の場合は
* それらを変更しても良いものとする。
*
* @author jc at bk-zen.com
*/
[SWF (backgroundColor = "0xFFFFFF", frameRate = "30", width = "465", height = "465")]
public class Test3 extends Sprite
{
private const colors: Array = [0xCC0000, 0x00CC00, 0x0000CC, 0x660000, 0x006600, 0x000066];
private const numColors: int = 3;
private const w: int = 8;
private const h: int = 8;
private const gridLength: int = w * h;
private var grid: Array;
private var view: BitmapData;
private var bmp: Bitmap;
private var label: Label;
private var btn: PushButton;
private var resetBtn: PushButton;
public function Test3()
{
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}
private function init(e: Event = null): void
{
removeEventListener(Event.ADDED_TO_STAGE, init);
//
grid = [];
for (var raw:int = 0; raw < h; raw++) {
grid[raw] = [];
for (var col:int = 0; col < w; col++) {
grid[raw][col] = new Cell(Math.random() * numColors, col, raw);
}
}
view = new BitmapData(w, h, false, 0);
addChild(bmp = new Bitmap(view));
bmp.scaleX = bmp.scaleY = 20;
btn = new PushButton(this, 0, bmp.height + 5, "scan", onClickScan);
label = new Label(this, btn.width + 5, btn.y, "result: ");
resetBtn = new PushButton(this, 0, btn.y + btn.height + 5, "reset", onClickReset);
draw();
}
private function reset():void
{
var i: int, c: Cell;
for (i = 0; i < gridLength; i ++)
{
c = grid[int(i / w)][i % w];
c.type = Math.random() * numColors | 0, c.removed = false;
}
draw();
}
/**
* 1. 縦・横で同じ色が3つ以上連なっていた場合にそれらの Cell removed を true にする。
* 2. 連なったCellの塊がいくつあるかを数える。
* @return 連なったCellの塊がいくつあるか
*/
private function scan(): int
{
var raw:int, col:int;
var matches:Array; // マッチしたCellを保持するリスト
var value:int = 0; // return value
// スキャン済みCellチェック用のリストを作成する
var scannedCells:Array = [];
for (raw = 0; raw < h; raw++) {
scannedCells[raw] = [];
for (col = 0; col < w; col++) {
scannedCells[raw][col] = { h:false, v:false };
}
}
// 左上から右下へと順に走査する
for (raw = 0; raw < h; raw++) {
for (col = 0; col < w; col++) {
matches = [];
if (!scannedCells[raw][col].h) { scanHorizontal(grid[raw][col]); }
if (!scannedCells[raw][col].v) { scanVertical(grid[raw][col]); }
// マッチしているCellがあったら、
// 全てのCellを削除し、見つけた塊の数を一つ増やす
if (matches.length > 0) {
for (var i:int = 0; i < matches.length; i++) {
matches[i].removed = true;
}
value++;
}
}
}
return value;
// 横方向の走査
function scanHorizontal(cell:Cell):void {
var candidates:Array = [cell];
scannedCells[cell.y][cell.x].h = true;
var i:int;
// 左側に走査
for (i = cell.x - 1; i >= 0; i--) {
// 既にスキャン済みか、タイプが違うなら走査終了
if (scannedCells[cell.y][i].h || (grid[cell.y][i].type != cell.type)) { break; }
// 候補に追加して、スキャン済みのチェックを入れる
candidates.push(grid[cell.y][i]);
scannedCells[cell.y][i].h = true;
}
// 右側に走査
for (i = cell.x + 1; i < w; i++) {
if (scannedCells[cell.y][i].h || (grid[cell.y][i].type != cell.type)) { break; }
candidates.push(grid[cell.y][i]);
scannedCells[cell.y][i].h = true;
}
// 横に３つ以上連なっていたら、
// それぞれを、マッチに追加し縦方向の走査を行う
if (candidates.length >= 3) {
for (i = 0; i < candidates.length; i++) {
matches.push(candidates[i]);
scanVertical(candidates[i]);
}
}
}
// 縦方向の走査
function scanVertical(cell:Cell):void {
var candidates:Array = [cell];
scannedCells[cell.y][cell.x].v = true;
var i:int;
// 上側に走査
for (i = cell.y - 1; i >= 0; i--) {
if (scannedCells[i][cell.x].v || (grid[i][cell.x].type != cell.type)) { break; }
candidates.push(grid[i][cell.x]);
scannedCells[i][cell.x].v = true;
}
// 下側に走査
for (i = cell.y + 1; i < h; i++) {
if (scannedCells[i][cell.x].v || (grid[i][cell.x].type != cell.type)) { break; }
candidates.push(grid[i][cell.x]);
scannedCells[i][cell.x].v = true;
}
// 縦に３つ以上連なっていたら、
// それぞれを、マッチに追加し横方向の走査を行う
if (candidates.length >= 3) {
for (i = 0; i < candidates.length; i++) {
matches.push(candidates[i]);
scanHorizontal(candidates[i]);
}
}
}
}
/**
* grid を view に反映します。
*/
private function draw():void
{
var i: int, c: Cell, t: int;
view.lock();
for (i = 0; i < gridLength; i ++)
{
c = grid[int(i / w)][i % w];
t = c.type + (c.removed ? 3 : 0);
view.setPixel(i % w, i / w, colors[t]);
}
view.unlock();
}
private function onClickScan(e: Event):void
{
var t: int = getTimer(), c: int;
c = scan();
label.text = "result : " + (getTimer() - t) + " [ms] remove cnt : " + c;
// 最後に view に反映する。
draw();
}
private function onClickReset(e: Event):void
{
reset();
}
}
}
class Cell
{
public var type: int;
public var x: int, y: int;
public var removed: Boolean;
function Cell(t: int, x: int, y: int)
{
type = t;
this.x = x;
this.y = y;
}
}