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

forked from: A*(たぶんバグ持ち)

A*
クリックで別のパターン
時々最短じゃないルートが出てる気がする
手順の再現をするようにした
配色すげー見辛い
バグは直してない
黄丸がスタート
赤丸がゴール
赤線が求められたルート
青囲いがオープンリスト入りしているノード
オレンジ囲いがクローズドリスト入りしているノード
灰色のでっかいのが、なんちゃって障害物
/**
 * Copyright awef ( http://wonderfl.net/user/awef )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/wz2V
 */

// forked from awef's A*(たぶんバグ持ち)
package
{
    //A*
    //クリックで別のパターン
    //時々最短じゃないルートが出てる気がする
    //手順の再現をするようにした
    //配色すげー見辛い
    //バグは直してない
    
    //黄丸がスタート
    //赤丸がゴール
    //赤線が求められたルート
    //青囲いがオープンリスト入りしているノード
    //オレンジ囲いがクローズドリスト入りしているノード
    //灰色のでっかいのが、なんちゃって障害物
    
    import flash.display.Sprite;
    import flash.events.MouseEvent;
    import flash.text.TextField;
    import gs.TweenMax;
    import gs.easing.*;
    
    public class main extends Sprite
    {
        //全ての表示オブジェクトをここに突っ込んどく
        private var disp:Sprite;
        //障害物配置用
        private var barricade:Array;
        //ノード格納用配列
        private var nodes:Array;
        //スタート・ゴール
        private var start:node;
        private var goal:node;
        //オープンリスト・クローズドリスト
        private var oNode:Array;
        private var cNode:Array;
        //A*アルゴリズムで使う
        private var current:Object;
        //コードの大幅改変は面倒なので、共通のディレイで対応 ← 初めは大幅に書き換えるつもりだったので、変数のスコープが変わってる。
        private var glbDelay:Number;
        private const duration:Number = 0.1;
        
        
        public function main()
        {
            addChild(disp = new Sprite());
            run();
            
            stage.addEventListener(MouseEvent.CLICK, function(e:MouseEvent):void {
                removeChild(disp);
                addChild(disp = new Sprite());
                run();
            } );
        }
        
        private function run():void
        {
            glbDelay = 0;
            
            //ループ用
            var tmp:*;
            var tmp2:*;
            var i:int;
            var sp:Sprite;
            
            //ランダムに障害物を配置
            barricade = new Array();
            for (i = 0; i < 3; i++)
            {
                sp = new Sprite();
                sp.alpha = 0.1;
                sp.graphics.beginFill(0x000000);
                sp.graphics.drawCircle(0, 0, 50);
                sp.graphics.endFill();
                sp.x = Math.floor(Math.random() * stage.stageWidth);
                sp.y = Math.floor(Math.random() * stage.stageHeight);
                disp.addChild(sp);
                barricade.push(sp);
            }
            
            nodes = new Array();
            //ランダムにノードを散らす
            for (i = 0; i < 90; i++ )
            {
                tmp = new node();
                
                do
                {
                    tmp.x = Math.floor(Math.random() * stage.stageWidth);
                    tmp.y = Math.floor(Math.random() * stage.stageHeight);
                }while (barricade.some(function(item:*, index:int, array:Array):Boolean { return item.hitTestObject(tmp); } ))
                
                nodes.push(tmp);
                disp.addChild(tmp);
            }
            
            //近いノードと接続
            for each(tmp in nodes)
            {
                for each(tmp2 in nodes)
                    if (tmp != tmp2 && 80 > tmp.dist(tmp2))
                        tmp.connect(tmp2, true);
            }
            
            //スタート、ゴールを決定
            start = nodes[0];
            tmp = 1;
            do //スタートとゴールが別のノード、かつ近すぎないようにする
            {
                if (nodes.length <= tmp)
                {
                    alert("スタート・ゴールの設定に失敗しました。クリックでリトライして下さい。");
                    return;
                }
                goal = nodes[tmp];
                tmp++;
            }
            while (start == goal || 300 > start.dist(goal))
            
            //オープンリスト、クローズドリスト {node:node, cost:int, heuristic:int, score:int, parent:Object} ← こんなのを格納
            oNode = new Array();
            cNode = new Array();
            
            oNode.push( {
                "node" : start,
                "cost" : 0,
                "heuristic" : start.dist(goal),
                "score" : start.dist(goal),
                "parent" : new Object() //ダミー
            } );
            oNode[0].parent = oNode[0];
            
            
            //スタートの位置に着色
            sp = new Sprite();
            sp.graphics.beginFill(0xEDD400);
            sp.graphics.drawCircle(0, 0, 8);
            sp.graphics.endFill();
            sp.x = start.x;
            sp.y = start.y;
            sp.scaleX = 0;
            sp.scaleY = 0;
            disp.addChild(sp);
            TweenMax.to(sp, duration, { delay : delay, scaleX : 1, scaleY : 1, ease : Back.easeOut } );
            
            //ゴールの位置に着色
            sp = new Sprite();
            sp.graphics.beginFill(0xCC0000);
            sp.graphics.drawCircle(0, 0, 8);
            sp.graphics.endFill();
            sp.x = goal.x;
            sp.y = goal.y;
            sp.scaleX = 0;
            sp.scaleY = 0;
            disp.addChild(sp);
            TweenMax.to(sp, duration, { delay : delay, scaleX : 1, scaleY : 1, ease : Back.easeOut } );
            
            while (oNode.length > 0)
            {
                //オープンリストをスコアの低い順にソート
                oNode.sortOn("score", Array.NUMERIC);
                //最もスコアの低いノードをcurrentノードに設定
                current = oNode[0];
                
                if (current.node == goal) break;
                else
                {
                    //currentノードの接続先を調査
                    for each(tmp in current.node.connection)
                    {
                        //オープンリストにもクローズドリストにも登録されていない場合、オープンリストに追加
                        if (!oNode.some(function(item:Object, index:int, array:Array):Boolean { return (tmp == item.node); })
                        && !cNode.some(function(item:Object, index:int, array:Array):Boolean { return (tmp == item.node); }))
                        {
                            oNode.push( {
                                "node" : tmp,
                                "cost" : current.cost + tmp.dist(current.node),
                                "heuristic" : tmp.dist(goal),
                                "score" : current.cost + tmp.dist(current.node) + tmp.dist(goal),
                                "parent" : current
                            } );
                            //オープンリスト入りのマーカーを描写
                            sp = new Sprite();
                            sp.x = tmp.x;
                            sp.y = tmp.y;
                            sp.graphics.lineStyle(2, 0x729fcf);
                            sp.graphics.drawCircle(0, 0, 6);
                            sp.alpha = 0;
                            disp.addChild(sp);
                            TweenMax.to(sp, duration, { delay : delay, alpha : 1, ease : Back.easeOut } );
                        }
                    }
                    //currentノードをクローズドリストに移動
                    oNode.splice(0, 1);
                    cNode.push(current);
                    //クローズドリスト入りのマーカーを描写
                    sp = new Sprite();
                    sp.x = current.node.x;
                    sp.y = current.node.y;
                    sp.graphics.lineStyle(2, 0xf57900);
                    sp.graphics.drawCircle(0, 0, 9);
                    sp.alpha = 0;
                    disp.addChild(sp);
                    TweenMax.to(sp, duration, { delay : delay, alpha : 1, ease : Back.easeOut } );
                }
            }
            
            if (current.node == goal) //ルートが見つかった場合、ラインを引く
            {
                tmp = current;
                while (tmp.node != start)
                {
                    sp = new Sprite();
                    sp.alpha = 0;
                    sp.graphics.lineStyle(2, 0xEF2929);
                    sp.graphics.moveTo(0, 0);
                    sp.graphics.lineTo(tmp.parent.node.x - tmp.node.x, tmp.parent.node.y - tmp.node.y);
                    sp.x = tmp.node.x;
                    sp.y = tmp.node.y;
                    sp.scaleX = 0;
                    sp.scaleY = 0;
                    disp.addChild(sp);
                    TweenMax.to(sp, duration, { delay : delay, alpha : 1, scaleX : 1, scaleY : 1, ease : Linear.easeNone } );
                    tmp = tmp.parent;
                }
            }
            else //ルートが見つからなかった場合、
            {
                alert("ルートが見つかりませんでした。");
            }
        }
        
        //ディレイいちいち足すの面倒だし、ゲッタにしといた
        private function get delay():Number
        {
            glbDelay += duration;
            return glbDelay;
        }
        
        private function alert(msg:String):void
        {
            var tf:TextField = new TextField();
            tf.text = msg;
            tf.width = 465;
            disp.addChild(tf);
        }
    }
}

import flash.display.Sprite

//ノード。単純に、ノードの位置と接続の関係のみを表す。
class node extends Sprite
{
    public var connection:Array = new Array();
    
    function node()
    {
        draw();
    }
    
    public function draw():void
    {
        graphics.clear();
        
        graphics.beginFill(0x2e3436, 0.4);
        graphics.drawCircle(0, 0, 4);
        graphics.endFill();
        
        for each(var tmp:node in connection)
        {
            graphics.lineStyle(1, 0x2e3436, 0.1);
            graphics.moveTo(0, 0);
            graphics.lineTo(tmp.x - x, tmp.y - y);
        }
    }
    
    //targetと接続
    //hogehoge == trueの場合、双方向接続にする (引数の良い名前が思い浮かばなかった)
    public function connect(target:node, hogehoge:Boolean = false):void
    {
        disConnect(target); //多重接続対策
        connection.push(target);
        if (hogehoge)
            target.connect(this);
        draw();
    }
    
    //targetと切断。多重接続も全部切ってくれるはず。(未検証)
    public function disConnect(target:node):void
    {
        connection = connection.filter(function(item:node, index:int, array:Array):Boolean { return (target != item); } );
        draw();
    }
    
    //ノード間の距離を測定する
    public function dist(target:node):int
    {
        return Math.sqrt(Math.pow(x - target.x, 2) + Math.pow(y - target.y, 2));
    }
}