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