Flash AS3版连连看游戏核心算法

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) );