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

A*(たぶんバグ持ち)

A*
クリックで別のパターン
時々最短じゃないルートが出てる気がする
黄がスタート
青がゴール
赤が求められたルート
紫がクローズリスト入りしているノード
緑がオープンリスト入りしているノード
灰色のでっかいのが、なんちゃって障害物
Get Adobe Flash player
by awef 09 Sep 2009
/**
 * Copyright awef ( http://wonderfl.net/user/awef )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/zQxr
 */

package
{
    //A*
    //クリックで別のパターン
    //時々最短じゃないルートが出てる気がする
    
    //黄がスタート
    //青がゴール
    //赤が求められたルート
    //紫がクローズリスト入りしているノード
    //緑がオープンリスト入りしているノード
    //灰色のでっかいのが、なんちゃって障害物
    
    import flash.display.Sprite;
    import flash.events.MouseEvent;
    import flash.text.TextField;
    
    public class main extends Sprite
    {
        private var disp:Sprite = new Sprite();
        public function main()
        {
            addChild(disp);
            run();
            
            stage.addEventListener(MouseEvent.CLICK, function(e:MouseEvent):void {
                removeChild(disp);
                disp = new Sprite();
                addChild(disp);
                run();
            } );
        }
        
        private function run():void
        {
            //障害物配置用
            var barricade:Array;
            //ノード格納用配列
            var nodes:Array;
            //スタート・ゴール
            var start:node;
            var goal:node;
            //オープンリスト・クローズリスト
            var oNode:Array;
            var cNode:Array;
            //A*アルゴリズムで使う
            var current:Object;
            
            //手順の可視化用
            var nav:Sprite;
            
            //ループ用
            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 //スタートとゴールが別のノード、かつ近すぎないようにする
            {
                goal = nodes[tmp];
                tmp++;
                if (nodes.length <= tmp)
                {
                    alert("スタート・ゴールの設定に失敗しました。クリックでリトライして下さい。");
                    return;
                }
            }
            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];
            
            while (oNode.length > 0)
            {
                //オープンリストをスコアの低い順にソート
                oNode.sortOn("score", Array.NUMERIC);
                //最もスコアの低いノードをcurrentノードに設定
                current = oNode[0];
                
                if (current.node == goal) break;
                else
                {
                    //currentノードをクローズリストに移動
                    oNode.splice(0, 1);
                    cNode.push(current);
                    //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
                            } );
                        }
                    }
                }
            }
            
            //手順可視化レイヤの追加
            nav = new Sprite();
            nav.alpha = 0.6;
            disp.addChild(nav);
            
            //スタート・ゴールの位置に着色
            nav.graphics.beginFill(0xFFFF00);
            nav.graphics.drawCircle(start.x, start.y, 6);
            nav.graphics.endFill();
            
            nav.graphics.beginFill(0x0000FF);
            nav.graphics.drawCircle(goal.x, goal.y, 6);
            nav.graphics.endFill();
            
            //オープンリストを塗る
            for each(tmp in oNode)
            {
                nav.graphics.lineStyle(2, 0x00FF00);
                nav.graphics.drawCircle(tmp.node.x, tmp.node.y , 4);
            }
            //クローズリストを塗る
            for each(tmp in cNode)
            {
                nav.graphics.lineStyle(2, 0xFF00FF);
                nav.graphics.drawCircle(tmp.node.x, tmp.node.y , 4);
            }
            
            if (current.node == goal) //ルートが見つかった場合、ラインを引く
            {
                nav.graphics.lineStyle(2, 0xFF0000);
                nav.graphics.moveTo(current.node.x, current.node.y);
                
                tmp = current;
                while (tmp.node != start)
                {
                    nav.graphics.moveTo(tmp.node.x, tmp.node.y);
                    nav.graphics.lineTo(tmp.parent.node.x, tmp.parent.node.y);
                    nav.graphics.beginFill(0xFF0000);
                    nav.graphics.drawCircle(tmp.node.x, tmp.node.y, 4);
                    nav.graphics.endFill();
                    tmp = tmp.parent;
                }
            }
            else //ルートが見つからなかった場合、
            {
                alert("ルートが見つかりませんでした。");
            }
        }
        
        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(0x000000, 0.4);
        graphics.drawCircle(0, 0, 4);
        graphics.endFill();
        
        for each(var tmp:node in connection)
        {
            graphics.lineStyle(1, 0, 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));
    }
}