forked from: ChineseCheckers
/**
* Copyright zrong ( http://wonderfl.net/user/zrong )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/1Zrm
*/
// forked from lizhi's ChineseCheckers
// forked from lizhi's line fastest a* search path
package
{
import flash.display.Shape;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Point;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
import flash.utils.getTimer;
/**
* ...跳棋
* @author lizhi
*/
public class ChineseCheckers extends Sprite
{
private var w:Number = 20;
private var h:Number = w / 2 / Math.cos(Math.PI / 3);
private var gridLayer:Shape = new Shape();
private var pathLayer:Shape = new Shape();
private var me:Shape = new Shape();
private var p:int = 0;
private var astar:AStar;
private var grid:Grid;
private var tf:TextField = new TextField();
public function ChineseCheckers()
{
grid = new Grid(20, 20);
for (var i:int = 0; i < grid.numCols;i++ ) {
for (var j:int = 0; j < grid.numRows; j++ ) {
if(Math.random()<0.2){
grid.setWalkable(i, j, false);
}
}
}
grid.calculateLinks(2);
astar = new AStar(grid);
astar.heuristic = astar.chineseCheckersEuclidian2;
drawGrid();
addChild(gridLayer);
addChild(pathLayer);
addChild(me);
me.graphics.beginFill(0xff0000);
me.graphics.drawCircle(0, 0, 4);
addChild(tf);
tf.textColor = 0xff0000;
tf.mouseEnabled = false;
tf.autoSize = TextFieldAutoSize.LEFT;
stage.addEventListener(MouseEvent.CLICK, onClick);
}
private function drawGrid():void {
gridLayer.graphics.clear();
gridLayer.graphics.lineStyle(0, 0);
var flagX:Boolean = true;
var flagY:Boolean = true;
var tx:int = 1;
var ty:int = 1;
for (var i:int = 1; i < grid.numCols + grid.numRows - 2; i++ ) {
if (flagX) {
var x:Number = getX(0, tx);
var y:Number = getY(0, tx);
if (tx == grid.numRows - 1) {
flagX = false;
tx = 1;
}else {
tx++;
}
}else {
x = getX(tx, grid.numRows - 1);
y = getY(tx, grid.numRows - 1);
tx++;
}
gridLayer.graphics.moveTo(x, y);
if (flagY) {
x = getX(ty, 0);
y = getY(ty, 0);
if (ty == grid.numCols - 1) {
flagY = false;
ty = 1;
}else {
ty++;
}
}else {
x = getX(grid.numCols-1, ty);
y = getY(0, ty);
ty++;
}
gridLayer.graphics.lineTo(x, y);
}
for (i = 0; i < grid.numCols; i++ ) {
gridLayer.graphics.moveTo(getX(i,0), 0);
gridLayer.graphics.lineTo(getX(i,grid.numRows-1), getY(0,grid.numRows - 1));
for (var j:int = 0; j < grid.numRows;j++ ) {
if (i==0) {
gridLayer.graphics.moveTo(getX(0,j), getY(0,j));
gridLayer.graphics.lineTo(getX(grid.numCols - 1,j), getY(0,j));
}
if(!grid.getNode(i,j).walkable){
gridLayer.graphics.beginFill(0);
}else {
gridLayer.graphics.beginFill(0xffffff);
}
gridLayer.graphics.drawCircle(getX(i, j), getY(0, j), 4);
gridLayer.graphics.endFill();
}
}
}
private function onClick(e:MouseEvent):void
{
var p:Point = getXYByMouseXY(gridLayer.mouseX, gridLayer.mouseY);
var pm:Point = getXYByMouseXY(me.x-gridLayer.x, me.y-gridLayer.y);
grid.setStartNode(pm.x, pm.y);
grid.setEndNode(p.x, p.y);
var time:int = getTimer();
if (astar.findPath()) {
time = getTimer() - time;
tf.text = time + "ms";
pathLayer.graphics.clear();
pathLayer.graphics.lineStyle(3, 0x0000ff);
pathLayer.graphics.moveTo(getX(pm.x, pm.y), getY(pm.x, pm.y));
this.p = 0;
addEventListener(Event.ENTER_FRAME, update);
}
}
private function update(e:Event):void
{
if(astar.path){
var n:Node =astar.path[++p];
if (n) {
var x:Number = getX(n.x, n.y);
var y:Number = getY(n.x, n.y);
pathLayer.graphics.lineTo(x, y );
me.x = x + gridLayer.x;
me.y = y + gridLayer.y;
}else {
removeEventListener(Event.ENTER_FRAME, update);
}
}
}
private function getX(x:int, y:int):Number {
return x * w + y * w / 2;
}
private function getY(x:int, y:int):Number {
return y * h;
}
private function getXYByMouseXY(mx:Number, my:Number):Point {
var y:int = Math.round(my / w);
var x:int = Math.round(mx / w - y / 2);
return new Point(x, y);
}
}
}
import flash.geom.Point;
class AStar {
//private var _open:Array;
private var _open:BinaryHeap;
private var _grid:Grid;
private var _endNode:Node;
private var _startNode:Node;
private var _path:Array;
private var _floydPath:Array;
public var heuristic:Function;
private var _straightCost:Number = 1.0;
private var _diagCost:Number = Math.SQRT2;
private var nowversion:int = 1;
public function AStar(grid:Grid){
this._grid = grid;
heuristic = euclidian2;
}
private function justMin(x:Object, y:Object):Boolean {
return x.f < y.f;
}
public function findPath():Boolean {
_endNode = _grid.endNode;
nowversion++;
_startNode = _grid.startNode;
//_open = [];
_open = new BinaryHeap(justMin);
_startNode.g = 0;
return search();
}
public function floyd():void {
if (path == null)
return;
_floydPath = path.concat();
var len:int = _floydPath.length;
if (len > 2){
var vector:Node = new Node(0, 0);
var tempVector:Node = new Node(0, 0);
floydVector(vector, _floydPath[len - 1], _floydPath[len - 2]);
for (var i:int = _floydPath.length - 3; i >= 0; i--){
floydVector(tempVector, _floydPath[i + 1], _floydPath[i]);
if (vector.x == tempVector.x && vector.y == tempVector.y){
_floydPath.splice(i + 1, 1);
} else {
vector.x = tempVector.x;
vector.y = tempVector.y;
}
}
}
len = _floydPath.length;
for (i = len - 1; i >= 0; i--){
for (var j:int = 0; j <= i - 2; j++){
if (floydCrossAble(_floydPath[i], _floydPath[j])){
for (var k:int = i - 1; k > j; k--){
_floydPath.splice(k, 1);
}
i = j;
len = _floydPath.length;
break;
}
}
}
}
private function floydCrossAble(n1:Node, n2:Node):Boolean {
var ps:Array = bresenhamNodes(new Point(n1.x, n1.y), new Point(n2.x, n2.y));
for (var i:int = ps.length - 2; i > 0; i--){
if (ps[i].x>=0&&ps[i].y>=0&&ps[i].x<_grid.numCols&&ps[i].y<_grid.numRows&&!_grid.getNode(ps[i].x,ps[i].y).walkable) {
return false;
}
}
return true;
}
private function bresenhamNodes(p1:Point, p2:Point):Array {
var steep:Boolean = Math.abs(p2.y - p1.y) > Math.abs(p2.x - p1.x);
if (steep) {
var temp:int = p1.x;
p1.x = p1.y;
p1.y = temp;
temp = p2.x;
p2.x = p2.y;
p2.y = temp;
}
var stepX:int = p2.x > p1.x?1:(p2.x < p1.x? -1:0);
var deltay:Number = (p2.y - p1.y)/Math.abs(p2.x-p1.x);
var ret:Array = [];
var nowX:Number = p1.x + stepX;
var nowY:Number = p1.y + deltay;
if (steep) {
ret.push(new Point(p1.y,p1.x));
}else {
ret.push(new Point(p1.x,p1.y));
}
if (Math.abs(p1.x - p2.x) == Math.abs(p1.y - p2.y)) {
if(p1.x<p2.x&&p1.y<p2.y){
ret.push(new Point(p1.x, p1.y + 1), new Point(p2.x, p2.y - 1));
}else if(p1.x>p2.x&&p1.y>p2.y){
ret.push(new Point(p1.x, p1.y - 1), new Point(p2.x, p2.y + 1));
}else if(p1.x<p2.x&&p1.y>p2.y){
ret.push(new Point(p1.x, p1.y - 1), new Point(p2.x, p2.y + 1));
}else if(p1.x>p2.x&&p1.y<p2.y){
ret.push(new Point(p1.x, p1.y + 1), new Point(p2.x, p2.y - 1));
}
}
while (nowX != p2.x) {
var fy:int=Math.floor(nowY)
var cy:int = Math.ceil(nowY);
if (steep) {
ret.push(new Point(fy, nowX));
}else{
ret.push(new Point(nowX, fy));
}
if (fy != cy) {
if (steep) {
ret.push(new Point(cy,nowX));
}else{
ret.push(new Point(nowX, cy));
}
}else if(deltay!=0){
if (steep) {
ret.push(new Point(cy+1,nowX));
ret.push(new Point(cy-1,nowX));
}else{
ret.push(new Point(nowX, cy+1));
ret.push(new Point(nowX, cy-1));
}
}
nowX += stepX;
nowY += deltay;
}
if (steep) {
ret.push(new Point(p2.y,p2.x));
}else {
ret.push(new Point(p2.x,p2.y));
}
return ret;
}
private function floydVector(target:Node, n1:Node, n2:Node):void {
target.x = n1.x - n2.x;
target.y = n1.y - n2.y;
}
public function search():Boolean {
var node:Node = _startNode;
node.version = nowversion;
while (node != _endNode){
var len:int = node.links.length;
for (var i:int = 0; i < len; i++){
var test:Node = node.links[i].node;
var cost:Number = node.links[i].cost;
var g:Number = node.g + cost;
var h:Number = heuristic(test);
var f:Number = g + h;
if (test.version == nowversion){
if (test.f > f){
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
}
} else {
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
_open.ins(test);
test.version = nowversion;
}
}
if (_open.a.length == 1){
return false;
}
node = _open.pop() as Node;
}
buildPath();
return true;
}
private function buildPath():void {
_path = [];
var node:Node = _endNode;
_path.push(node);
while (node != _startNode){
node = node.parent;
_path.unshift(node);
}
}
public function get path():Array {
return _path;
}
public function get floydPath():Array {
return _floydPath;
}
public function manhattan(node:Node):Number {
return Math.abs(node.x - _endNode.x) + Math.abs(node.y - _endNode.y);
}
public function manhattan2(node:Node):Number {
var dx:Number = Math.abs(node.x - _endNode.x);
var dy:Number = Math.abs(node.y - _endNode.y);
return dx + dy + Math.abs(dx - dy) / 1000;
}
public function euclidian(node:Node):Number {
var dx:Number = node.x - _endNode.x;
var dy:Number = node.y - _endNode.y;
return Math.sqrt(dx * dx + dy * dy);
}
private var TwoOneTwoZero:Number = 2 * Math.cos(Math.PI / 3);
public function chineseCheckersEuclidian2(node:Node):Number {
var y:int = node.y / TwoOneTwoZero;
var x:int = node.x + node.y / 2;
var dx:Number = x - _endNode.x - _endNode.y / 2;
var dy:Number = y - _endNode.y / TwoOneTwoZero;
return sqrt(dx * dx + dy * dy);
}
private function sqrt(x:Number):Number {
return Math.sqrt(x);
}
public function euclidian2(node:Node):Number {
var dx:Number = node.x - _endNode.x;
var dy:Number = node.y - _endNode.y;
return dx * dx + dy * dy;
}
public function diagonal(node:Node):Number {
var dx:Number = Math.abs(node.x - _endNode.x);
var dy:Number = Math.abs(node.y - _endNode.y);
var diag:Number = Math.min(dx, dy);
var straight:Number = dx + dy;
return _diagCost * diag + _straightCost * (straight - 2 * diag);
}
}
class BinaryHeap {
public var a:Array = [];
public var justMinFun:Function = function(x:Object, y:Object):Boolean {
return x < y;
};
public function BinaryHeap(justMinFun:Function = null){
a.push(-1);
if (justMinFun != null)
this.justMinFun = justMinFun;
}
public function ins(value:Object):void {
var p:int = a.length;
a[p] = value;
var pp:int = p >> 1;
while (p > 1 && justMinFun(a[p], a[pp])){
var temp:Object = a[p];
a[p] = a[pp];
a[pp] = temp;
p = pp;
pp = p >> 1;
}
}
public function pop():Object {
var min:Object = a[1];
a[1] = a[a.length - 1];
a.pop();
var p:int = 1;
var l:int = a.length;
var sp1:int = p << 1;
var sp2:int = sp1 + 1;
while (sp1 < l){
if (sp2 < l){
var minp:int = justMinFun(a[sp2], a[sp1]) ? sp2 : sp1;
} else {
minp = sp1;
}
if (justMinFun(a[minp], a[p])){
var temp:Object = a[p];
a[p] = a[minp];
a[minp] = temp;
p = minp;
sp1 = p << 1;
sp2 = sp1 + 1;
} else {
break;
}
}
return min;
}
}
class Grid {
private var _startNode:Node;
private var _endNode:Node;
private var _nodes:Array;
private var _numCols:int;
private var _numRows:int;
private var type:int;
private var _straightCost:Number = 1.0;
private var _diagCost:Number = Math.SQRT2;
public function Grid(numCols:int, numRows:int){
_numCols = numCols;
_numRows = numRows;
_nodes = new Array();
for (var i:int = 0; i < _numCols; i++){
_nodes[i] = new Array();
for (var j:int = 0; j < _numRows; j++){
_nodes[i][j] = new Node(i, j);
}
}
}
/**
*
* @param type 0四方向 1八方向 2跳棋
*/
public function calculateLinks(type:int = 0):void {
this.type = type;
for (var i:int = 0; i < _numCols; i++){
for (var j:int = 0; j < _numRows; j++){
initNodeLink(_nodes[i][j], type);
}
}
}
public function getType():int {
return type;
}
/**
*
* @param node
* @param type 0八方向 1四方向 2跳棋
*/
private function initNodeLink(node:Node, type:int):void {
var startX:int = Math.max(0, node.x - 1);
var endX:int = Math.min(numCols - 1, node.x + 1);
var startY:int = Math.max(0, node.y - 1);
var endY:int = Math.min(numRows - 1, node.y + 1);
node.links = [];
for (var i:int = startX; i <= endX; i++){
for (var j:int = startY; j <= endY; j++){
var test:Node = getNode(i, j);
if (test == node || !test.walkable){
continue;
}
if (type != 2 && i != node.x && j != node.y){
var test2:Node = getNode(node.x, j);
if (!test2.walkable){
continue;
}
test2 = getNode(i, node.y);
if (!test2.walkable){
continue;
}
}
var cost:Number = _straightCost;
if (!((node.x == test.x) || (node.y == test.y))){
if (type == 1){
continue;
}
if (type == 2 && (node.x - test.x) * (node.y - test.y) == 1){
continue;
}
if (type == 2){
cost = _straightCost;
} else {
cost = _diagCost;
}
}
node.links.push(new Link(test, cost));
}
}
}
public function getNode(x:int, y:int):Node {
return _nodes[x][y];
}
public function setEndNode(x:int, y:int):void {
_endNode = _nodes[x][y];
}
public function setStartNode(x:int, y:int):void {
_startNode = _nodes[x][y];
}
public function setWalkable(x:int, y:int, value:Boolean):void {
_nodes[x][y].walkable = value;
}
public function get endNode():Node {
return _endNode;
}
public function get numCols():int {
return _numCols;
}
public function get numRows():int {
return _numRows;
}
public function get startNode():Node {
return _startNode;
}
}
class Link {
public var node:Node;
public var cost:Number;
public function Link(node:Node, cost:Number){
this.node = node;
this.cost = cost;
}
}
class Node {
public var x:int;
public var y:int;
public var f:Number;
public var g:Number;
public var h:Number;
public var walkable:Boolean = true;
public var parent:Node;
//public var costMultiplier:Number = 1.0;
public var version:int = 1;
public var links:Array;
//public var index:int;
public function Node(x:int, y:int){
this.x = x;
this.y = y;
}
public function toString():String {
return "x:" + x + " y:" + y;
}
}