package {
    import flash.display.*;
    import flash.events.*;
    import flash.utils.*;
    import flash.filters.*;
    import caurina.transitions.Tweener;
    import flash.geom.Point;

    [SWF(width=440, height=440, backgroundColor=0x888888)]

    /// A*法での経路検索
    public class AStar extends Sprite
    {

        public static const G:int = 0;  ///< ゴール
        public static const S:int = 1; ///< スタート
        public static const O:int = 2;  ///< なにもない通れる所
        public static const X:int = 3;  ///< 通れない
        public static const SCREEN_W:int = 440;         ///< 画面幅
        public static const SCREEN_H:int = 440;         ///< 画面高さ
        public static const TILE_W:int = SCREEN_W/8;    ///< タイル一枚の大きさ

        private var myChr:Shape = null;         ///< 自キャラ
        private var mapNode:Array = new Array();///< マップデータの管理
        private var routeList:Array = new Array;///< 最短経路が保存される
        private var openList:Array = null;      ///< 経路計算用
        private var closeList:Array = null;     ///< 経路計算用
        private var startNode:Node = null;      ///< スタート地点
        private var goalNode:Node = null;       ///< ゴール地点
        private var moveState:int = 0;          ///< 移動状態

        // コンストラクタ
        public function AStar()
        {
            //ステージの設定
            stage.quality = "MEDIUM";
            stage.scaleMode = "noScale";
            stage.align = StageAlign.TOP_LEFT;

            // ベーススプライト作成。マウスクリック用
            var base:Sprite=new Sprite();
            base.graphics.beginFill(0x50AAB3);
            base.graphics.drawRect(0,0,SCREEN_W,SCREEN_H);
            base.graphics.endFill();
            addChild(base);

            // マップデータの作成
            var mapData:Array = new Array();
            mapData[0] = [O,S,O,O,O,O,O,O];
            mapData[1] = [O,O,O,O,X,X,X,X];
            mapData[2] = [X,X,X,O,O,O,O,O];
            mapData[3] = [O,O,O,O,O,O,O,O];
            mapData[4] = [O,O,O,X,X,X,X,X];
            mapData[5] = [O,O,O,O,O,O,O,O];
            mapData[6] = [O,X,X,O,X,O,G,O];
            mapData[7] = [O,O,O,O,O,O,O,O];

            // filter使ったほうがかっこいいよね!
            var wFilters:Array = new Array;
            wFilters.push(makeDropShadowFilter());
            wFilters.push(makeBevelFilter());

            for(var y:int = 0; y < mapData.length; ++y){
                var a:Array = new Array();
                for(var x:int = 0; x < mapData[y].length; ++x){
                    var newNode:Node = new Node(x, y, mapData[y][x]);
                    a.push(newNode);
                    if(mapData[y][x] == X){
                        // 壁を描画
                        var s:Shape = makeRoundRect(TILE_W, TILE_W, 10, 0x1200D9);
                        s.x = x*TILE_W;
                        s.y = y*TILE_W;
                        s.filters = wFilters;
                        addChild(s);
                    }else if(mapData[y][x] == S){
                        // スタート地点にタマを置く
                        myChr = makeShape(0xF2C200, x*TILE_W+TILE_W/2, y*TILE_W+TILE_W/2, TILE_W/2);
                        myChr.filters = wFilters;
                        addChild(myChr);

                        startNode = newNode;
                    }else if(mapData[y][x] == G){
                        goalNode = newNode;
                    }
                }
                mapNode.push(a);
            }

            // マウスクリックイベント追加
            base.addEventListener(MouseEvent.CLICK, mouseDownHandler);
        }

        /// 移動完了したときの呼び出しコールバック
        private function moveComp():void{
            move();
        }

        /// 玉の移動
        private function move():void{

            if( routeList.length == 0 ){
                return;
            }
            if(moveState >= routeList.length){
                routeList = new Array;
                moveState = 0;
                return;
            }

            var retNode:Node = routeList[moveState];
            var xpos:int = retNode.x*TILE_W+TILE_W/2;
            var ypos:int = retNode.y*TILE_W+TILE_W/2;

            Tweener.addTween(myChr,{x:xpos, y:ypos, time:0.15, transition:"easeinoutquad", onComplete:moveComp});
            ++moveState;

        }

        /// 画面上の座標をマップデータ上の座標に変換する
        private function getMapPos(x:int, y:int):Point{
            var ret:Point = new Point;
            ret.x = x/TILE_W;
            ret.y = y/TILE_W;
            return ret;
        }

        /// マウスダウンイベントの処理
        private function mouseDownHandler(evt:MouseEvent):void {

            if(routeList.length != 0){
                // 移動中は受け付けない
                return;
            }

            // スタートとゴールを再設定

            // ゴールを設定
            var goalPos:Point = getMapPos(mouseX, mouseY);
            var goal:Node = getNode(goalPos.x, goalPos.y);
            if(!goal.isWalk()){
                // ゴールがいけないところだったら移動しない
                return;
            }

            startNode.state = O;
            goalNode.state = O;

            goalNode = goal;
            goalNode.state = G;

            // スタート地点を設定
            var startPos:Point = getMapPos(myChr.x, myChr.y);
            startNode = getNode(startPos.x, startPos.y);
            startNode.state = S;

            // ルート計算
            if( !processAStar() ){
                return;
            }

            move();
        }

        /// mからnに移動したときのコストを計算する
        private function cost(m:Node, n:Node):int{
            var disx:int = Math.abs(m.x - n.x);
            var disy:int = Math.abs(m.y - n.y);
            return disx + disy;
        }

        /// h*を計算する
        private function h_star(node:Node):int{
            return cost(goalNode, node);
        }

        /// ノードの取得
        private function getNode(x:int, y:int):Node{
            if( x < 0 || y < 0 ){
                return null;
            }

            if(y >= mapNode.length){
                return null;
            }
            if(x >= mapNode[0].length){
                return null;
            }

            return mapNode[y][x];
        }

        /// ノードのデータを初期化する
        private function nodeClear():void{

            for(var y:int = 0; y < mapNode.length; ++y){
                for(var x:int = 0; x < mapNode[y].length; ++x){
                    var node:Node = mapNode[y][x];
                    if(node!=null){
                        node.clear();
                    }
                }
            }
        }

        /// 隣接するノードの配列を作って返す        
        private function getMNodeArray(node:Node):Array{
            // 左
            var ret:Array = new Array;
            var movex:Array = [-1, 0, 1, 0];
            var movey:Array = [0, 1, 0, -1];

            for(var i:int = 0;i < movex.length; ++i){
                var n:Node = getNode(node.x+movex[i], node.y+movey[i]);
                if(n != null){
                    if(n.isWalk()){
                        ret.push(n);
                    }
                }
            }

            return ret;
        }

        /// openListの中に指定のnodeはあるか判定する
        private function inOpenList(node:Node):int{
            for(var i:int = 0;i < openList.length; ++i){
                var n:Node = openList[i];
                if(n.x == node.x && n.y == node.y){
                    return i;
                }
            }
            return -1;
        }

        /// closeListの中に指定のnodeはあるか判定する
        private function inCloseList(node:Node):int{
            for(var i:int = 0;i < closeList.length; ++i){
                var n:Node = closeList[i];
                if(n.x == node.x && n.y == node.y){
                    return i;
                }
            }
            return -1;
        }

        /// 最短経路を求める。成功なら、routeListに最短距離の経路が保存される
        private function processAStar():Boolean{

            nodeClear();
            this.openList = new Array;
            this.closeList = new Array;

            // スタート位置を探す
            if(startNode == null){
                return false;
            }
            if(goalNode == null){
                return false;
            }

            startNode.f_star = this.h_star(startNode);

            // Openリストに追加
            openList.push(startNode);

            var loopCount:int = 0;

            // Openリストが空ならば検索は失敗           
            while(openList.length > 0){
                // f_starが最小の値のものを探す
                openList.sortOn("f_star", Array.NUMERIC);
                var n:Node = openList[0];

                // GOALだったら検索終了
                if(n.isGoalNode()){
                    break;
                }

                // Closeリストへnを移す
                openList.shift();
                closeList.push(n);

                // 隣のノードの配列を作る
                var mNodeArray:Array = getMNodeArray(n);

                for(var i:int = 0;i < mNodeArray.length; ++i){
                    var m:Node = mNodeArray[i];
                    // f_starを計算
                    m.f_star = (n.f_star - h_star(n)) + h_star(m) + cost(n,m);

                    // 条件分岐
                    var openIndex:int = inOpenList(m);
                    var closeIndex:int = inCloseList(m);
                    var oldM:Node;

                    if( openIndex < 0 && closeIndex < 0 ){
                        // openListにもcloseListにもmがない
                        m.parent = n;
                        openList.push(m);
                    }else if( openIndex >= 0 ){
                        // openListにある
                        oldM = openList[openIndex];
                        if( m.f_star < oldM.f_star ){
                            openList[openIndex] = m;
                        }

                    }else if( closeIndex >= 0 ){
                        // closeListにある
                        oldM = closeList[closeIndex];
                        if( m.f_star < oldM.f_star ){
                            // closeから削除(mが入っていたところを先頭の0で上書きして、先頭削除)
                            closeList[closeIndex] = closeList[0];
                            closeList.shift();
                            // openへ
                            openList.push(m);
                        }
                    }

                    // 無限ループ回避措置(バグ回避用)
                    loopCount++;
                    if(loopCount > 1000){
                        return false;;
                    }
                }

            }

            // 経路を並び替えてrouteListに入れる
            var ret:Array = new Array;
            var node:Node = openList[0];
            while(node.parent != null){
                ret.push(node);
                node = node.parent;
            }
            ret.reverse();

            routeList = ret;
            this.openList = new Array;
            this.closeList = new Array;

            return true;
        }

        //角丸矩形の生成
        private function makeRoundRect(w:uint,h:uint,ew:uint,color:uint):Shape {
            var rrect:Shape=new Shape();
            rrect.graphics.lineStyle(2,0x000000);    //線幅・線色
            rrect.graphics.beginFill(color);         //塗り潰し色
            rrect.graphics.drawRoundRect(0,0,w,h,ew);//XY座標,幅,高さ,角丸幅
            rrect.graphics.endFill();                //塗り潰し終了
            return rrect;
        }

        /// 円を作成する
        private function makeShape(color:uint, x:int, y:int, r:int):Shape {
            var s:Shape = new Shape();
            s.x = x;
            s.y = y;
            s.graphics.beginFill(color);         //塗り潰し色
            s.graphics.lineStyle(3, 0x000000);
            s.graphics.drawCircle(0, 0, r);
            s.graphics.endFill();                //塗り潰し終了
            return s;
        }

        //ベベルフィルタの生成
        private function makeBevelFilter():BitmapFilter {
            var filter:BevelFilter=new BevelFilter();
            filter.angle         =45;      //角度
            filter.blurX         =3;       //水平方向のぼかし量
            filter.blurY         =3;       //垂直方向のぼかし量
            filter.distance      =10;      //オフセットの距離
            filter.highlightAlpha=0.5;     //ハイライトカラーの透明度
            filter.highlightColor=0xddddff;//ハイライトカラー
            filter.knockout      =false;   //ノックアウト効果有無
            filter.quality       =BitmapFilterQuality.HIGH;//クォリティ
            filter.shadowAlpha   =0.8;     //シャドウカラーの透明度
            filter.shadowColor   =0x000000;//シャドウカラー
            filter.strength      =0.5;     //インプリントやスプレッドの長さ
            filter.type          =BitmapFilterType.INNER;//ベベルの種類
            return filter;
        }

        //ドロップシャドウフィルタの生成
        private function makeDropShadowFilter():BitmapFilter {
            var filter:DropShadowFilter=new DropShadowFilter();
            filter.alpha     =1.0;     //シャドウカラーの透明度
            filter.angle     =45;      //シャドウの角度
            filter.blurX     =5;       //水平方向のぼかし量
            filter.blurY     =5;       //垂直方向のぼかし量
            filter.color     =0x000000;//シャドウのカラー
            filter.distance  =5;       //シャドウのオフセット距離
            filter.hideObject=false;   //シャドウのみの表示
            filter.inner     =false;   //内部シャドウか
            filter.knockout  =false;   //ノックアウト効果の有無
            filter.quality   =BitmapFilterQuality.HIGH;//クォリティ
            filter.strength  =1;       //インプリントやスプレッドの長さ
            return filter;
        }

    }
}