forked from: match 3 puzzle remove block algorithm
横方向の走査のときにリンクリストを作っていき、
縦方向の走査のときにリンクリストの頭としっぽをつないで、
最後にリストの数を数えてます。
めっちゃ速く計算できます。
by shohei909
マッチ3パズルのアルゴリズムを考える。
scan メソッドを完成させる。
なるべく高速で正確な方法を考える。
grid を Array で保持することが気に入らない等の場合は
それらを変更しても良いものとする。
@author jc at bk-zen.com
/**
* Copyright shohei909 ( http://wonderfl.net/user/shohei909 )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/sui0
*/
// forked from bkzen's match 3 puzzle remove block algorithm
/*
横方向の走査のときにリンクリストを作っていき、
縦方向の走査のときにリンクリストの頭としっぽをつないで、
最後にリストの数を数えてます。
めっちゃ速く計算できます。
by shohei909
*/
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, 0x220000, 0x002200, 0x000022];
private const numColors: int = 3;
private const w: int = 460;
private const h: int = 410;
private const gridLength: int = w * h;
private var grid: Vector.<Vector.<Cell>>;
private var view: BitmapData;
private var bmp: Bitmap;
private var label: Label;
private var btn: PushButton;
private var resetBtn: PushButton;
private var scaned:Boolean = false;
private var t:Boolean = true;
private var f:Boolean = false;
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 = new Vector.<Vector.<Cell>>;
for (var i:uint = 0; i < w; i ++) {
grid[i] = new Vector.<Cell>;
for (var j:uint = 0; j < h; j ++) {
grid[i][j] = new Cell( Math.random() * numColors, i, j );
}
}
view = new BitmapData(w, h, false, 0);
addChild(bmp = new Bitmap(view));
bmp.scaleX = bmp.scaleY = 1;
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
{
scaned = false;
for (var i:uint = 0; i < w; i ++) {
for (var j:uint = 0; j < h; j ++) {
grid[i][j] = new Cell( Math.random() * numColors, i, j );
}
}
draw();
}
/**
* 1. 縦・横で同じ色が3つ以上連なっていた場合にそれらの Cell removed を true にする。
* 2. 連なったCellの塊がいくつあるかを数える。
* @return 連なったCellの塊がいくつあるか
*/
private function scan(): int
{
if(! scaned ){
scaned = true;
scanH();
scanV();
}
return count();
}
private function scanH():void {
var h:uint = this.h, w:uint = this.w, cnt:uint;
var ii:uint = 0;
var jj:uint = 0;
var grid:Vector.<Vector.<Cell>> = grid;
for (var i:uint = 0; i < h; i++ )
{
var t:int = -1;
for (var j:uint = 0; j < w; j++ )
{
var c:Cell = grid[j][i];
if (t == c.type)
{
cnt++;
} else {
if (cnt > 2){ connectH( ii, jj, cnt ) }
cnt = 1;
t = c.type;
ii = i; jj = j;
}
}
}
if (cnt > 2){connectH( ii, jj, cnt )}
}
private function scanV():void {
var h:uint = this.h, w:uint = this.w, cnt:uint;
var ii:uint = 0;
var jj:uint = 0;
for (var i:uint = 0; i < w; i ++)
{
var t:int = -1;
for (var j:uint = 0; j < h; j++ )
{
var c:Cell = grid[i][j];
if ( t == c.type )
{
cnt++;
} else {
if (cnt > 2){ connectV( ii, jj, cnt) }
cnt = 1;
t = c.type;
ii = i; jj = j;
}
}
}
if (cnt > 2){ connectV( ii, jj, cnt ) }
}
private function connectH( i:int, j:int, cnt:uint ):void{
var grid:Vector.<Vector.<Cell>> = grid;
var first:Cell = grid[j][i];
var prev:Cell = first;
for( var n:uint = 0; n < cnt; n++ ){
prev.removed = true;
var c:Cell = grid[j+n][i];
c.first = first;
prev.next = c;
prev = c;
}
prev.removed = true;
}
private function connectV( i:int, j:int, cnt:int ):void{
var grid:Vector.<Vector.<Cell>> = grid;
var c:Cell = grid[i][j];
var prev:Cell = null;
var first:Cell = c.first;
for( var n:uint = 0; n < cnt; n++ ){
c = grid[i][j+n];
var cFirst:Cell = c.first;
var cc:Cell = cFirst;
if( cFirst != first ){
if( !prev ){ prev = first.last(); }
prev.next = cFirst;
do{
cc.first = first;
prev = cc;
cc = cc.next;
}while( cc )
}
c.removed = true;
}
}
private function count():int {
var h:uint = this.h, w:uint = this.w, cnt:uint;
var grid:Vector.<Vector.<Cell>> = grid;
for (var i:uint = 0; i < w; i ++)
{
for (var j:uint = 0; j < h; j++ )
{
var c:Cell = grid[i][j];
if( c.removed && !c.next ){
cnt++;
}
}
}
return cnt;
}
/**
* grid を view に反映します。
*/
private function draw():void
{
var c: Cell, t: int;
view.lock();
for (var i:uint = 0; i < w; i ++) {
for (var j:uint = 0; j < h; j ++) {
c = grid[i][j];
t = c.type + (c.removed ? 3 : 0);
view.setPixel(i, j, 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 next: Cell;
public var first:Cell;
public var removed: Boolean;
function Cell(t: int, x: int, y: int)
{
type = t;
first = this;
}
public function last():Cell{
var p:Cell = this;
var n:Cell = next;
while( n ){
p = n;
n = n.next;
}
return p;
}
}