match 3 puzzle remove block algorithm
マッチ3パズルのアルゴリズムを考える。
scan メソッドを完成させる。
なるべく高速で正確な方法を考える。
grid を Array で保持することが気に入らない等の場合は
それらを変更しても良いものとする。
[追記]
連なったCellのカタマリの数え方として
同じtypeのブロックの消える対象が縦横で交差した場合はそれらをまとめて１つとする。
これらL字、十字のような場合ははそれぞれ1個とする
■□□
■□□
■■■
---
□■□
■■■
□■□
---
以下のような場合は 2個とする。
■■■
■■■
□□□
/**
* Copyright bkzen ( http://wonderfl.net/user/bkzen )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/1BEX
*/
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 = [];
var i: int;
for (i = 0; i < gridLength; i ++) { grid[i] = new Cell(Math.random() * numColors, i % w, i / w); }
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[i];
c.type = Math.random() * numColors | 0, c.removed = false;
}
draw();
}
/**
* 1. 縦・横で同じ色が3つ以上連なっていた場合にそれらの Cell removed を true にする。
* 2. 連なったCellの塊がいくつあるかを数える。
* @return 連なったCellの塊がいくつあるか
*/
private function scan(): int
{
var res: int, i: int, j: int, k: int, c: Cell, t: int, cnt: int;
// 例) 縦と横を走査してゴリゴリ調べる。
// 例の課題としては、どれが１カタマリなのかがわからない。
// さらに固まった形でマッチしていた場合にバグがある。
// 例えば、3*3 の正方形状など
// 横の走査
for (i = 0; i < h; i ++)
{
t = grid[k = i * w].type, cnt = 1;
for (j = 1; j < w; j ++)
{
c = grid[k + j];
if (t == c.type)
{
cnt++;
}
else
{
t = c.type;
if (cnt > 2)
{
while (cnt--)
{
c = grid[k + j - cnt - 1];
c.removed = true;
}
res ++;
}
cnt = 1;
}
}
if (cnt > 2)
{
while (cnt--)
{
c = grid[k + j - cnt - 1];
c.removed = true;
}
res ++;
}
}
// 縦の走査
for (i = 0; i < w; i ++)
{
t = grid[i].type, cnt = 1;
for (j = 1; j < h; j ++)
{
c = grid[i + j * w];
if (t == c.type)
{
cnt++;
}
else
{
t = c.type;
if (cnt > 2)
{
k = 0;
while (cnt--)
{
c = grid[i + (j - cnt - 1) * w];
if (c.removed) k++;
c.removed = true;
}
res += 1 - k;
}
cnt = 1;
}
}
if (cnt > 2)
{
k = 0;
while (cnt--)
{
c = grid[i + (j - cnt - 1) * w];
if (c.removed) k++;
c.removed = true;
}
res += 1 - k;
}
}
return res;
}
/**
* grid を view に反映します。
*/
private function draw():void
{
var i: int, c: Cell, t: int;
view.lock();
for (i = 0; i < gridLength; i ++)
{
c = grid[i];
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;
}
}