forked from: Dijkstra Visualization

/**
 * Copyright powblue ( http://wonderfl.net/user/powblue )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/rZAO
 */

// forked from nitoyon's Dijkstra Visualization
//実験中！
package {
    import flash.geom.Point;
    import flash.events.MouseEvent;
    import flash.text.TextField;
import flash.display.*;
import flash.events.Event;
import flash.utils.setTimeout;

public class Dijkstra extends Sprite {
    private var maze:Array = [];            // 迷路を格納した配列
    private var open:Array = [];            // 未確定のノード一覧
    private var dx:Array = [0, 1, 1, 1, 0, -1,-1,-1];   // X方向移動用配列
    private var dy:Array = [1, 1, 0,-1,-1, -1, 0, 1];   // Y方向移動用配列
    //private var costs:Array = [1,Math.SQRT2,1,Math.SQRT2,1,Math.SQRT2,1,Math.SQRT2];
    private var costs:Array = [1,2,1,2,1,2,1,2];
    private var angles:Array = [90,45,0,315,270,225,180,135];
    private var W:int;                      // 迷路の横幅
    private var H:int;                      // 迷路の縦幅
    
    private var tf:TextField;
    
    private var complete:Boolean = false;//検索完了
    private var po_goal:Point = new Point();
    
    // コンストラクタ
    public function Dijkstra() {
        stage.scaleMode = "noScale";

        // wonderfl 背景色対策
        graphics.beginFill(0);
        graphics.drawRect(-Node.SIZE, -Node.SIZE, 465, 465);
        graphics.endFill();
        x = y = Node.SIZE;
        
        
        // textfield
        tf = new TextField();
        tf.y = 200;
        tf.width = 300;
        tf.height = 200;
        tf.textColor = 0xffffffff;
        this.addChild(tf);
        trc("debug");
        
        // MAZE のパースを行う
        var mazeArray:Array = MAZE.split(/\r?\n/);
        W = mazeArray[0].length;
        H = mazeArray.length;

        // 各マスを初期化する
        maze = [];
        for (var yy:int = 0; yy < H; yy++) {
            maze[yy] = [];
            for (var xx:int = 0; xx < W; xx++) {
                var block:Node = new Node(mazeArray[yy].charAt(xx), xx, yy,this);
                addChild(block);
                maze[yy][xx] = block;

                // スタート地点のみスコアを 0 とし、open に加える
                if (block.isStart) {
                    block.score = 0;
                    open.push(block);
                }
                
                if(block.isGoal){
                    this.po_goal.x = xx;
                    this.po_goal.y = yy;
                }
            }
        }

        //検索
        search();
        
    }
    
    
    
    public function trc(str:String):void{
        this.tf.text =  str + "\r" + this.tf.text;
        
        
    }
    
    private function reset():void{
        open = []; 
        complete = false;
        for(var yy:int = 0; yy < H;yy++){
            for(var xx:int = 0;xx < W;xx++){
                var node:Node = maze[yy][xx] as Node;
                node.score = Number.MAX_VALUE;
                node.done = false;
                node.prev = null;
                node.isRoute = false;
                if(node.isStart){
                    node.score = 0;
                    open.push(node);
                }
                
            }
        }
        
        
        
    }
    
    public function search():void{
        reset();
        
        while(!complete){
            nextStep();
        }
        
        for(var j:int = 0;j < H;j++){
            for(var i:int = 0;i < W;i++){
                var node:Node = maze[j][i] as Node;
                if(!node.done){
                    node.draw();
                }
            }
        }
    }
    
    // ダイクストラ法の１ステップを実行する
    private function nextStep():void {
        // 未確定ノードの中から、スコアが最小となるノード u を決定する
        var minScore:Number = Number.MAX_VALUE;
        var minIndex:int = -1;
        var u:Node = null;


        
        for (var i:int = 0; i < open.length; i++) {
            var block:Node = open[i] as Node;
            if (block.done) continue;
            if (block.score < minScore) {
                minScore = block.score;
                minIndex = i;
                u = block;
            }
        }

        // 未確定ノードがなかった場合は終了
        if (u == null) {
            complete = true;
            return;
        }

        // ノード u を確定ノードとする
        open.splice(minIndex, 1);
        u.done = true;
        u.draw();
        

        // ノード u の周りのノードのスコアを更新する
        for (i = 0; i < dx.length; i++) {
            // 境界チェック
            if (u.yy + dy[i] < 0 || u.yy + dy[i] >= H || u.xx + dx[i] < 0 || u.xx + dx[i] >= W) continue;

            // ノード v を取得する
            var v:Node = maze[u.yy + dy[i]][u.xx + dx[i]] as Node;

            // 確定ノードや壁だったときにはパスする
            if (v.done || v.isWall) continue;
            
            //斜め移動で通れない形のときパスする
            if(dx[i] != 0 && dy[i] != 0){
                if(Node(maze[u.yy][u.xx + dx[i]]).isWall && Node(maze[u.yy + dy[i]][u.xx]).isWall){
                    continue;
                }
            }   
              
            // 既存のスコアより小さいときのみ更新する
            var tmp_score:Number = Math.sqrt((square(po_goal.x - v.xx) + square(po_goal.y - v.yy)));
            tmp_score = 0;
            
            if ((u.score + costs[i] + tmp_score) < v.score) {
                v.score = u.score + costs[i] + tmp_score;
                v.prev = u;
                v.draw();
                
                v.arrow_rotation = angles[i];

                // open リストに追加
                if (open.indexOf(v) == -1) open.push(v);
            }
        }

        
    }
    
    private function square(num:Number):Number{
           return num * num;
    }

    private var MAZE:String = 
<>**************************
*                       G*
*                        *
*                        *
*                        *
*                        *
*                        *
*                        *
*                        *
*                        *
*                        *
*S                       *
**************************</>;


}

}
import flash.events.MouseEvent;

import flash.display.Sprite;
import flash.text.TextField;
import frocessing.color.ColorHSV;

class Node extends Sprite {
    public var score:Number;        // ダイクストラ法のノードのスコア
    public var done:Boolean;        // ダイクストラ法の確定ノード一覧
    public var prev:Node;          // ダイクストラ法の直前の頂点を記録
    public var isWall:Boolean;      // 壁かどうか
    public var isGoal:Boolean;      // ゴール地点かどうか
    public var isStart:Boolean;     // スタート地点かどうか
    public var isRoute:Boolean;     // スタートからゴールへのルート上の点かどうか
    public var xx:int;              // マスの x 方向インデックス
    public var yy:int;              // マスの y 方向インデックス

    public static const SIZE:Number = 16;   // 描画時の１ブロックサイズ
    public const WALL:uint = 0x666666;      // 壁の色
    public const NORMAL:uint = 0xffffff;    // 通行できる場所の色
    
    private var dikj:Dijkstra;
    
    public var arrow_rotation:int = 0;//→の角度
    private var arrow:Sprite;
    
    // マスの初期化
    public function Node(c:String, _xx:int, _yy:int,_dikj:Dijkstra) {
        dikj = _dikj;
        
        isStart = (c == "S");
        isWall = (c == "*");
        isGoal = (c == "G");
        xx = _xx;
        yy = _yy;
        x = xx * SIZE;
        y = yy * SIZE;

        score = int.MAX_VALUE;
        done = false;
        prev = null;

        // スタートとゴールには文字列を表示する
        if (isStart || isGoal) {
            var t:TextField = addChild(new TextField()) as TextField;
            t.selectable = false;
            t.width = SIZE;
            t.htmlText = '<p align="center"><b>' + c + '</b></p>';
            t.x = t.y = -SIZE / 2;
        }
        
        this.addEventListener(MouseEvent.CLICK,click);
        
        arrow = new Sprite();
        this.addChild(arrow);
        
        draw();
    }
    
    private function click(e:MouseEvent):void{
        this.isWall = !this.isWall;      
        this.dikj.search();
        this.draw();
  
        
    }
    
    // 描画する
    public function draw():void {
        graphics.clear();
        graphics.beginFill(isWall ? WALL : 
                           done ? 0xffffff : 0xaaaaaa);
        graphics.drawRect(-SIZE / 2, - SIZE / 2, SIZE, SIZE);
        graphics.endFill();
        
        arrow.graphics.clear();
        arrow.rotation = this.arrow_rotation;
        
       

        // prev ノードが存在する場合は矢印を描画する
        if (prev) {
            arrow.graphics.lineStyle(0, isRoute ? 0x000000 : 0xdddddd);
            arrow.graphics.moveTo(SIZE * .4, 0);
            arrow.graphics.lineTo(-SIZE * .4, 0);
            arrow.graphics.lineTo(-SIZE * .2, SIZE * .1);
            arrow.graphics.lineTo(-SIZE * .4, 0);
            arrow.graphics.lineTo(-SIZE * .2, -SIZE * .1);
            //if (prev.xx < xx) rotation = 0;
            //if (prev.xx > xx) rotation = 180;
            //if (prev.yy < yy) rotation = 90;
            //if (prev.yy > yy) rotation = 270;
        }

        // ゴールが確定したときには、手前のノードを全て辿って
        // isRoute を true にする
        if (isGoal && done) {
            var b:Node = prev;
            while (b) {
                b.isRoute = true;
                b.draw();
                b = b.prev;
            }
        }
    }
}