Flash AS3版連連看游戲核心算法－IT工程師數位筆記本

文章出處
package model.components
{
import de.polygonal.ds.Array2;
import de.polygonal.ds.DLinkedList;
import de.polygonal.ds.Iterator;
import flash.geom.Point;
import utils.*;

/**
* 連連看算法
* @author Luan (verycss-ok@yahoo.com.cn)
*/
public class Map
{
private var _level:uint; //游戲關卡對應的項目數量
private var _map:Array2; //二維數組
private var _array:Array; //輔助的一維數組
private var _restBlock:uint = 0; //剩余的項目數量
private var _vector:DLinkedList; //保存符合條件線段的地方
private var _countOfPerItem:uint; //每個項目出現的次數(偶數)
private var _result:MatchResult; //暫存符合條件的結果

public function Map(level:uint = 16)
{
//加2是為了加一圈0
_map = new Array2( Setting.COLUMN+2, Setting.ROW+2 );
_array = new Array(_map.size - 2*_map.width - 2*_map.height + 4);
_vector = null;
_result = new MatchResult();

//調用setter
this.level = level;
}

/********************** getter & setter **********************/

public function set level(value:uint):void
{
_level = value;
//取得一個盡量大的偶數值
_countOfPerItem = NumberUtil.getFloorEven(_map.size / _level);
_restBlock = _level * _countOfPerItem;

_initMap();
}

public function get count():uint
{
return _restBlock <= 0?0:_restBlock;
}

public function get map():Array2
{
return _map;
}

public function get result():MatchResult
{
return _result;
}

/********************** 私有方法 **********************/

private function _initMap():void
{
//一維數組初始化和亂序
for (var n:uint = 0; n < _array.length; n++)
_array[n] = 0;

for (var i:uint = 0; i < _level; i++)
{
for (var j:uint = 0; j < _countOfPerItem; j++)
{
_array[i * _countOfPerItem + j] = i + 1;
}
}

_array = ArrayUtil.random(_array);

ArrayUtil.drawWrappedMap(_array, _map);
}

/**
* 橫向檢查
* @param        a
* @param        b
* @return
*/
private function _hTest(a:Point, b:Point):MatchResult
{
if (a.x == b.x || a.y != b.y ) return null;

var x_start:uint = Math.min(a.x, b.x);
var x_end:uint = Math.max(a.x, b.x);

for (var x:uint = x_start + 1; x < x_end; x++)
if ( _map.get(x, a.y) != 0 )
return null;

return _result.fill(a.clone(), b.clone());
}

/**
* 縱向檢查
* @param        a
* @param        b
* @return
*/
private function _vTest(a:Point, b:Point):MatchResult
{
if (a.y == b.y || a.x != b.x) return null;

var y_start:uint = Math.min(a.y, b.y);
var y_end:uint = Math.max(a.y, b.y);

for (var y:uint = y_start + 1; y < y_end; y++)
if ( _map.get(a.x, y) != 0 )
return null;

return _result.fill(a.clone(), b.clone());
}

/**
* A 、B 之間有一個拐點
* @param        a
* @param        b
* @return
*/
private function _oneCorner(a:Point, b:Point):MatchResult
{
var c:Point = new Point(a.x, b.y);
var d:Point = new Point(b.x, a.y);

var isMatch:Boolean = false;

if (_map.get(c.x, c.y) == 0) //C 點上必須沒有障礙
{
isMatch = _vTest(a, c) && _hTest(b, c);
if (isMatch)
{
_result.clear();
return _result.fill(a.clone(), b.clone(), c.clone());
}
}

if (_map.get(d.x, d.y) == 0) //D 點上必須沒有障礙
{
isMatch = _hTest(a, d) && _vTest(b, d);
if (isMatch)
{
_result.clear();
return _result.fill(a.clone(), b.clone(), d.clone());
}
}

return null;
}

/**
* 掃描兩點決定的矩形范圍內有沒有完整的空白線段
* @param        a
* @param        b
* @return
*/
private function _scanLine(a:Point, b:Point):DLinkedList
{
var v:DLinkedList = new DLinkedList();

// 從 a, c 連線向 b 掃描，掃描豎線

// 掃描 A 點左邊的所有線
for (var x1:Number = a.x; x1 >= 0; x1--)
{
var c1:Point = new Point(x1, a.y);
var d1:Point = new Point(x1, b.y);
// 存在完整路線 -- c,d點為零且縱向連通
if ( _map.get(x1, a.y) == 0 && _map.get(x1, b.y) == 0 && _vTest(c1, d1) )
v.
}

// 掃描 A 點右邊的所有線
for (var x2:Number = a.x; x2 < _map.width; x2++)
{
var c2:Point = new Point(x2, a.y);
var d2:Point = new Point(x2, b.y);

if ( _map.get(x2, a.y) == 0 && _map.get(x2, b.y) == 0 && _vTest(c2, d2) )
v.append( new Line(Line.VERTICAL, c2, d2) );
}

// 從 a, d 連線向 b 掃描，掃描橫線

// 掃描 A 點上面的所有線
for (var y1:Number = a.y; y1 >= 0; y1--)
{
var c3:Point = new Point(a.x, y1);
var d3:Point = new Point(b.x, y1);

if ( _map.get(a.x, y1) == 0 && _map.get(b.x, y1) == 0 && _hTest(c3, d3) )
v.append( new Line(Line.HORIZONTAL, c3, d3) );
}

// 掃描 A 點下面的所有線
for (var y2:Number = a.y; y2 < _map.height; y2++)
{
var c4:Point = new Point(a.x, y2);
var d4:Point = new Point(b.x, y2);

if ( _map.get(a.x, y2) == 0 && _map.get(b.x, y2) == 0 && _hTest(c4, d4) )
v.append( new Line(Line.HORIZONTAL, c4, d4) );
}
return v;
}

/**
* 對所有找到的符合線進行判斷，看看 AC 、 DB 是否同樣也可以消除
* @param        a
* @param        b
* @return
*/
private function _twoCorner(a:Point, b:Point):MatchResult
{
_vector = _scanLine(a, b);

if (_vector.isEmpty()) return null; //沒有完整的空白線段，無解 

var itr:Iterator = _vector.getIterator();

while (itr.hasNext())
{
var ln:Line = itr.next() as Line;

switch (ln.direct)
{
case Line.HORIZONTAL:
        if ( _vTest(a, ln.a) && _vTest(b, ln.b) )
        {
                _result.clear();
                return _result.fill(a.clone(), b.clone(), ln.a.clone(), ln.b.clone());
        }
break;

case Line.VERTICAL:
        if ( _hTest(a, ln.a) && _hTest(b, ln.b) )
        {
                _result.clear();
                return _result.fill(a.clone(), b.clone(), ln.a.clone(), ln.b.clone());
        }
break;
}
}

return null;
}

private function _findRestPointA(map:Array2 = null):Point
{
var m:Array2 = map || _map;

if (m.width >= m.height)
{
for (var col:Number = 0; col < m.width; col++)
{
var max_y:Number = Math.min(col + 1, m.height);

for (var y1:Number = 0; y1 < max_y; y1++)
{
        if (m.get(col, y1) != 0)
                return new Point(col, y1);
}

for (var x1:Number = 0; x1 < col; x1++)
{
        if (m.get(x1, max_y-1) != 0)
                return new Point(x1, max_y-1);
}
}
}
else
{
for (var row:Number = 0; row < m.height; row++)
{
var max_x:Number = Math.min(row + 1, m.width);

for (var x2:Number = 0; x2 < max_x; x2++)
{
        if (m.get(x2, row) != 0)
                return new Point(x2, row);
}

for (var y2:Number = 0; y2 < row; y2++)
{
        if (m.get(max_x-1, y2) != 0)
                return new Point(max_x-1, y2);
}
}
}
return null;
}

private function _findRestPointB(a:Point, ignore_b_arr:Array = null):Point
{
if (!a) return null;

var tempMap:Array2 = ArrayUtil.cloneArray2(_map);

tempMap.set(a.x, a.y, 0);

if (ignore_b_arr && ignore_b_arr.length)
{
for each (var bb:Point in ignore_b_arr)
tempMap.set(bb.x, bb.y, 0);
}

var b:Point = _findRestPointA(tempMap);

if (!b) return null;

while ( _map.get(a.x, a.y) != _map.get(b.x, b.y) )
{
tempMap.set(b.x, b.y, 0);

b = _findRestPointA(tempMap);

if (!b) return null;
} 

return b;
}

/********************** 公開方法 **********************/

/**
* 測試兩點是否可以連通
* @param        a
* @param        b
* @usage 判斷 兩點的值相同 并且 滿足連通條件
* @return
*/
public function test(a:Point, b:Point):Boolean
{
_result = new MatchResult();

if (_map.get(a.x, a.y) != _map.get(b.x, b.y))
return false;
if ( _hTest(a, b) || _vTest(a, b) || _oneCorner(a, b) || _twoCorner(a, b) )
return true;
else
return false;
}

/**
* 自動尋找一條可連通的路徑
* @return
*/
public function autoFindLine():MatchResult
{
var a:Point = _findRestPointA(); if (!a) return null;

var b:Point = _findRestPointB(a); if (!b) return null;

var ignoreA:Array = [];
var ignoreB:Array = [];

while ( !this.test(a, b) )
{
ignoreB.push(b);

b = _findRestPointB(a, ignoreB);

//基于A沒有可以連通的點了, 換一個A試試
if (!b)
{
ignoreB = [];
ignoreA.push(a);

var tempMap:Array2 = ArrayUtil.cloneArray2(_map);
tempMap.set(a.x, a.y, 0);

if (ignoreA.length)
        for each (var p:Point in ignoreA)
                tempMap.set(p.x, p.y, 0);

a = _findRestPointA(tempMap);
b = _findRestPointB(a);
}
}

//找不到可以連通的B點
if (!b) return null;

return _result.clone();
}

/**
* 清除兩點
* @param        a
* @param        b
*/
public function earse(a:Point, b:Point):void
{
_map.set(a.x, a.y, 0);
_map.set(b.x, b.y, 0);
_restBlock -= 2;
}

/**
* 刷新
*/
public function refresh():void
{
var num:uint = this.count;
if (num <= 0) return;

_array = ArrayUtil.random( ArrayUtil.getWarppedMapArray(_map) );

ArrayUtil.drawWrappedMap(_array, _map);
}

}

}
append( new Line(Line.VERTICAL, c1, d1) );