In case Flash no longer exists; a copy of this site is included in the Flashpoint archive's "ultimate" collection.

Dead Code Preservation :: Archived AS3 works from wonderfl.net

ChineseCheckers

...跳棋
@author lizhi
/**
 * Copyright lizhi ( http://wonderfl.net/user/lizhi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/3TcG
 */

// 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;
    }
}