forked from: forked from: Dijkstra Particle Streams

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

// forked from crazy2death's forked from: Dijkstra Particle Streams
package {
    import flash.display.Bitmap;
    import flash.display.BitmapData;
    import flash.display.Shape;
    import flash.display.Sprite;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.geom.ColorTransform;
    import flash.geom.Point;
    import flash.geom.Rectangle;
    
    [SWF(frameRate=30)]
    public class main extends Sprite {        
        public static const MAP_SIZE:int = 33;
        public static const NODE_SIZE:int = 15;
        
        
        public static var nodes:Array;
        public static var particles:Array;
        private var _starts:Array;
        private var _goals:Array;
        
        
        private var _particleCanvas:BitmapData;
        private var _canvasRect:Rectangle;
        private var _colorTransform:ColorTransform;
        private var _wallLayer:Sprite;
        private var _cursor:Shape;
        
        public function main() {
            // ノード、パーティクル、壁、ゴール、スタートの順で初期化
            initializeNodes();
            initializeParticles();
            initializeStreams();    
            
            addEventListener(Event.ENTER_FRAME, update);
            

            
        }
        
        // ノードの初期化
        private function initializeNodes():void {
            main.nodes = [];
            for (var row:int = 0; row < main.MAP_SIZE; row++) {
                main.nodes[row] = [];
                for (var col:int = 0; col < main.MAP_SIZE; col++) {
                    main.nodes[row][col] = new Node(col, row);
                }
            }
        }
        
        // パーティクルの初期化
        private function initializeParticles():void {
            Particle.createImages();
            
            var numParticles:int = Parameter.numParticles;
            particles = new Array(numParticles);
            for (var i:int = 0; i < numParticles; i++){
                particles[i]= new Particle();
            }
            
            var particleLayer:Bitmap = new Bitmap();
            _particleCanvas = new BitmapData(500, 400, false, 0x000000);
        
            
            particleLayer.bitmapData = _particleCanvas;

            addChild(particleLayer);
            
            _canvasRect = new Rectangle(0, 0, 500, 400);

            _colorTransform = new ColorTransform(0.9,0.9,0.9)
        }
        
        // 壁の初期化

        
        // スタートノード、ゴールノードの初期化
        private function initializeStreams():void {
            _goals = Parameter.getGoals();
            _starts = Parameter.getStarts(_goals);
            Start.setSpawnInterval();
            
            // パーティクルの出現をばらつかせるためにシャッフルする
            shuffle(_starts);
        }
        
        // 配列をシャッフルする
        private function shuffle(arr:Array):void {
            var i:int = arr.length;
            while (i) {
                var j:int = Math.floor(i * Math.random());
                var tmp:* = arr[--i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }

        
    
        // 毎フレームの更新処理
        private function update(e:Event):void {
            spawnParticles();    
            updateParticles();
        }
        
        // スタートノードからパーティクルを出現させる
        private function spawnParticles():void {
            var numStarts:int = _starts.length;
            for (var i:int = 0; i < numStarts; i++) {
                _starts[i].update();
            }
        }
        
        // パーティクルの更新を行う
        private function updateParticles():void {
            _particleCanvas.lock();
            for (var i:int = 0; i < Parameter.numParticles; i++) {
                // パーティクルが画面内に存在していたら更新
                if(main.particles[i].exists){
                    main.particles[i].update();
                    main.particles[i].draw(_particleCanvas);
                }
            }
            _particleCanvas.colorTransform(_canvasRect, _colorTransform);
            _particleCanvas.unlock();
        }
    }
}

import flash.display.Shape;
import flash.geom.Point;

class Node {
    private var _tilex:int;
    private var _tiley:int;
    private var _centerx:Number;
    private var _centery:Number;
    private var _passable:Boolean;
    
    public function get tileX():int { return _tilex; }
    public function get tileY():int { return _tiley; }
    public function get centerX():Number { return _centerx; }
    public function get centerY():Number { return _centery; }
    public function get passable():Boolean { return _passable; }
    public function set passable(arg:Boolean):void { _passable = arg; }
    
    public function Node(tilex:int, tiley:int) {
        _tilex = tilex;
        _tiley = tiley;
        var pos:Point = Node.posFromTile(new Point(_tilex, _tiley));
        _centerx = pos.x + (main.NODE_SIZE / 2);
        _centery = pos.y + (main.NODE_SIZE / 2);
        _passable = true;
    }
    
    // タイル縦横値からXY座標値を求める
    public static function posFromTile(tile:Point):Point {
        var pos:Point = new Point();
        
        pos.x = (tile.x * main.NODE_SIZE) - main.NODE_SIZE;
        if (pos.x < -main.NODE_SIZE) {
            pos.x = -main.NODE_SIZE;
        }else if (pos.x > (main.NODE_SIZE * (main.MAP_SIZE - 1))) {
            pos.x = (main.NODE_SIZE * (main.MAP_SIZE - 1));
        }
        
        pos.y = (tile.y * main.NODE_SIZE) - main.NODE_SIZE;
        if (pos.y < -main.NODE_SIZE) {
            pos.y = -main.NODE_SIZE;
        }else if (pos.y > (main.NODE_SIZE * (main.MAP_SIZE - 1))) {
            pos.y = (main.NODE_SIZE * (main.MAP_SIZE - 1));
        }
        
        return pos;
    }
    
    // XY座標値からタイル縦横値を求める
    public static function tileFormPos(pos:Point):Point {
        var tile:Point = new Point();
        
        tile.x = Math.floor(pos.x / main.NODE_SIZE) + 1;
        if (tile.x < 0) {
            tile.x = 0;
        }else if (tile.x > main.MAP_SIZE - 1) {
            tile.x = main.MAP_SIZE - 1;
        }
        
        tile.y = Math.floor(pos.y / main.NODE_SIZE) + 1;
        if (tile.y < 0) {
            tile.y = 0;
        }else if (tile.y > main.MAP_SIZE - 1) {
            tile.y = main.MAP_SIZE - 1;
        }
        
        return tile;
    }
}

import flash.display.Sprite;
import flash.geom.Point;

class Wall extends Sprite {
    private var _tilex:int;
    private var _tiley:int;
    private var _removable:Boolean;
    
    public function get removable():Boolean { return _removable; }
    
    public function Wall(tilex:int, tiley:int, removable:Boolean = true) {
        _tilex = tilex;
        _tiley = tiley;
        var pos:Point = Node.posFromTile(new Point(_tilex, _tiley));
        this.x = pos.x;
        this.y = pos.y;
        _removable = removable;
        
        setNodePassablity(false);
        draw();
    }
    
    // 壁を設置した部分のノードの通行可能性を変更する
    private function setNodePassablity(passable:Boolean):void {
        main.nodes[_tiley][_tilex].passable = passable;
        main.nodes[_tiley][_tilex + 1].passable = passable;
        main.nodes[_tiley + 1][_tilex].passable = passable;
        main.nodes[_tiley + 1][_tilex + 1].passable = passable;
    }
    
    // 壁の画像を描画する
    private function draw():void {
        var rectSize:Number = main.NODE_SIZE * 2;
        
        if (_removable) {
            rectSize -= 0.5;
            graphics.lineStyle(1, 0x222222);
        }
        
        graphics.beginFill(0x111111);
        graphics.drawRect(0, 0, rectSize, rectSize);
        graphics.endFill();
    }
    
    // 壁を取り除く際に呼ぶ関数
    public function remove():void {
        setNodePassablity(true);
        parent.removeChild(this);
    }
}


import flash.display.BitmapData;
import flash.display.BlendMode;
import flash.display.Shape;
import flash.geom.Matrix;
import flash.geom.Point;
import flash.geom.Rectangle;

class Particle {
    private static const IMAGE_COLORS:Array =
    [0x0000ff, 0x3333ff, 0x6666ff, 0x9999ff, 0xccccff, 0xffffff,
     0x0033ff, 0x0066ff, 0x0099ff, 0x00ccff, 0x00ffff,
     0x33ffff, 0x66ffff, 0x99ffff, 0xccffff];
    private static var IMAGE_RADIUS:int;
    
    private var _posx:Number;
    private var _posy:Number;
    private var _vx:Number;
    private var _vy:Number;
    
    private var _speed:Number;
    private var _exists:Boolean;
    private var _start:Start;
    
    private static var _images:Array;
    private var _imageIndex:int;
    private static var _sourceRect:Rectangle;
    
    public function get exists():Boolean { return _exists; }
    
    public function Particle() {
        _posx = _posy = _vx = _vy = 0;
        _speed = ((Parameter.particleMaxSpeed - 1) * Math.random()) + 1;
        _exists = false;
        _start = null;
        _imageIndex = 0;
    }
    
    // スタートノードから出現させる
    public function spawn(start:Start):void {
        _posx = start.node.centerX;
        _posy = start.node.centerY;
        _exists = true;
        _start = start;
        _imageIndex = Math.floor(Particle.IMAGE_COLORS.length * Math.random());
    }
    
    public function update():void {
        _posx += _vx;
        _posy += _vy;
        
        var tile:Point = Node.tileFormPos( new Point(_posx, _posy));
        // ゴールに着いたか、移動不可能（かべのなかにいる）なら消滅する
        if (arrivedGoal(tile.x, tile.y) || !isMovable(tile.x, tile.y)) {
            _exists = false;
            return;
        }
        
        var nextNode:Node = _start.destination.getNext(tile.x, tile.y);
        // ゴールノードへの経路が存在しないなら止まる
        if (nextNode == main.nodes[tile.y][tile.x]) {
            _vx = 0;
            _vy = 0;
        }else {
            var radians:Number = Math.atan2(nextNode.centerY - _posy, nextNode.centerX - _posx);
            _vx = _speed * Math.cos(radians);
            _vy = _speed * Math.sin(radians);
        }
    }
    
    // ゴールノードへ到着しているかどうか
    private function arrivedGoal(tilex:int, tiley:int):Boolean {
        var goalNode:Node = _start.destination.node;
        
        return (tilex == goalNode.tileX) && (tiley == goalNode.tileY);
    }
    
    // パーティクルが移動できるかどうか
    private function isMovable(tilex:int, tiley:int):Boolean {
        return main.nodes[tiley][tilex].passable;
    }
    
    public function draw(canvas:BitmapData):void {
        var destPoint:Point = new Point(_posx - Particle.IMAGE_RADIUS, _posy - Particle.IMAGE_RADIUS);
        canvas.copyPixels(_images[_imageIndex], _sourceRect, destPoint);
    }
    
    // パーティクルの画像を予め作成しておく関数
    public static function createImages():void {
        Particle.IMAGE_RADIUS = Parameter.particleRadius;
        _images = [];
        _sourceRect = new Rectangle(0, 0, Particle.IMAGE_RADIUS * 2, Particle.IMAGE_RADIUS * 2);
        for (var i:int = 0; i < Particle.IMAGE_COLORS.length; i++) {
            var bitmapData:BitmapData = new BitmapData(Particle.IMAGE_RADIUS * 2, Particle.IMAGE_RADIUS * 2, 
true, 0x00ffffff);
            var shape:Shape = new Shape();
            shape.graphics.beginFill(Particle.IMAGE_COLORS[i]);
            shape.graphics.drawCircle(Particle.IMAGE_RADIUS, Particle.IMAGE_RADIUS, Particle.IMAGE_RADIUS);
            shape.graphics.endFill();
            bitmapData.draw(shape);
            _images.push(bitmapData);
        }
    }
}


class Start {
    private static var SPAWN_INTERVAL:int;
    
    private var _node:Node;
    private var _destination:Goal;
    private var _spawnCount:int;
    
    public function get node():Node { return _node; }
    public function get destination():Goal { return _destination; }
    
    public function Start(node:Node, dest:Goal) {
        _node = node;
        _destination = dest;
        _spawnCount = 0;
    }
    
    public function update():void {
        // ゴールノードへの経路が存在しない場合は何もしない
        if (_destination.getCost(node.tileX, node.tileY) == int.MAX_VALUE) { return; }
        
        // 一定の間隔でパーティクルの出現を試みる
        if (++_spawnCount >= Start.SPAWN_INTERVAL) {
            // 画面上に存在しないパーティクルがあればそれをここから出現させる
            var len:int = main.particles.length;
            for (var i:int = 0; i < len; i++) {
                if (!main.particles[i].exists) {
                    main.particles[i].spawn(this);
                    _spawnCount = 0;
                    break;
                }
            }
        }
    }
    
    public static function setSpawnInterval():void {
        Start.SPAWN_INTERVAL = Parameter.spawnInterval;
    }
}


class Goal {
    private static const DX:Array = [ -1, 0, 1, -1, 1, -1, 0, 1];
    private static const DY:Array = [ -1, -1, -1, 0, 0, 1, 1, 1];
    private static const DCOST:Array = [Math.SQRT2, 1, Math.SQRT2, 1, 1, Math.SQRT2, 1, Math.SQRT2];
    
    private var _ID:int;
    private var _node:Node;
    
    private var _openNodes:Array;    // 保留ノードリスト
    private var _closedNodes:Array;    // 確定ノードリスト
    private var _nodeCost:Array;    // 各ノードの移動コスト
    private var _nodeNext:Array;    // 各ノードの次の経路となるノード
    
    public function get ID():int { return _ID; }
    public function get node():Node { return _node; }
    public function getCost(tilex:int, tiley:int):int { return _nodeCost[tiley][tilex]; }
    public function getNext(tilex:int, tiley:int):Node { return _nodeNext[tiley][tilex]; }
    
    public function Goal(ID:int, node:Node) {
        _ID = ID;
        _node = node;
        
        _openNodes = [];
        _closedNodes = [];
        _nodeCost = [];
        _nodeNext = [];
        for (var row:int = 0; row < main.MAP_SIZE; row++) {
            _closedNodes[row] = [];
            _nodeCost[row] = [];
            _nodeNext[row] = [];
        }
        
        search();
    }
    
    private function initialize():void {
        for (var row:int = 0; row < main.MAP_SIZE; row++) {
            for (var col:int = 0; col < main.MAP_SIZE; col++) {
                _closedNodes[row][col] = false;
                _nodeCost[row][col] = int.MAX_VALUE;
                _nodeNext[row][col] = main.nodes[row][col];
            }
        }
        
        // Goalのノードを経路探索のスタートノードとする
        _nodeCost[_node.tileY][_node.tileX] = 0;
        _openNodes.push(main.nodes[_node.tileY][_node.tileX]);
    }
    
    // ダイクストラ法による経路探索
    public function search():void {
        initialize();
        
        while (_openNodes.length > 0) {
            var subject:Node = _openNodes.pop() as Node;
            _closedNodes[subject.tileY][subject.tileX] = true;
            
            // 周囲8方向のノードを訪問する
            for (var i:int = 0; i < 8; i++) {
                // 画面外の存在しないノードを指すなら次の周囲ノードへ進む
                if (!isValid(subject.tileX + Goal.DX[i]) || !isValid(subject.tileY + Goal.DY[i])) { 
continue; }
                
                // 壁が設置されているノード、確定ノード、直進することができないノードなら次の周囲ノードへ進む
                var test:Node = main.nodes[subject.tileY + Goal.DY[i]][subject.tileX + Goal.DX[i]];
                if (isWall(test) || isClosedNode(test) || !canGoStraightTo(subject, test)) { continue; }
                
                // 既存の移動コストより小さかったら更新する
                if (_nodeCost[test.tileY][test.tileX] > _nodeCost[subject.tileY][subject.tileX] + 
Goal.DCOST[i]) {
                    _nodeCost[test.tileY][test.tileX] = _nodeCost[subject.tileY][subject.tileX] + 
Goal.DCOST[i];
                    // 次の経路ノードをsubjectノードに設定する
                    _nodeNext[test.tileY][test.tileX] = subject;
                    // 保留ノードリストに追加する
                    insertToOpenNodes(test);
                }
            }
        }
    }
    
    // indexの値が有効な値かどうか
    private function isValid(index:int):Boolean {
        return ((index >= 0) && (index < main.MAP_SIZE));
    }
    
    private function isClosedNode(node:Node):Boolean {
        return _closedNodes[node.tileY][node.tileX];
    }
    
    // 壁が設置されたノードかどうか
    private function isWall(node:Node):Boolean {
        return !node.passable;
    }
    
    // subjectノードからtestノードへ直進できるかどうか
    private function canGoStraightTo(subject:Node, test:Node):Boolean {
        return (main.nodes[subject.tileY][test.tileX].passable && main.nodes[test.tileY][subject.tileX].passable);
    }
    
    // nodeを保留ノードリストの適切な場所に挿入する
    private function insertToOpenNodes(node:Node):void {
        var insertIndex:int;
        var len:int = _openNodes.length;
        var nodeCost:int = _nodeCost[node.tileY][node.tileX];
        
        for (insertIndex = 0; insertIndex < len; insertIndex++) {
            var openNode:Node = _openNodes[insertIndex];
            if (nodeCost > _nodeCost[openNode.tileY][openNode.tileX]) { break; }
        }
        _openNodes.splice(insertIndex, 0, node);
    }
}


import flash.geom.Point;

class Parameter {
    private static const data:XML =
    <root>
        <particles num="1000" radius="2" maxspeed="8" />

        <starts interval="10">
            <start dest="0" x="12" y="0"/>
            <start dest="0" x="13" y="0"/>
            <start dest="1" x="14" y="0"/>
            <start dest="1" x="15" y="0"/>
            <start dest="2" x="16" y="0"/>
            <start dest="3" x="17" y="0"/>
            <start dest="3" x="18" y="0"/>
            <start dest="4" x="19" y="0"/>
            <start dest="4" x="20" y="0"/>
            

        </starts>
        <goals>
            <goal id="0" x="14" y="32"/>
            <goal id="1" x="15" y="32"/>
            <goal id="2" x="16" y="32"/>
            <goal id="3" x="17" y="32"/>
            <goal id="4" x="18" y="32"/>
            

        </goals>
    </root>;
    
    public static function get numParticles():int {
        return int(Parameter.data.particles.@num);
    }
    
    public static function get particleRadius():int {
        return int(Parameter.data.particles.@radius);
    }
    
    public static function get particleMaxSpeed():Number {
        return Number(Parameter.data.particles.@maxspeed);
    }
    
    public static function get spawnInterval():int {
        return int(Parameter.data.starts.@interval);
    }
    
    public static function getWalls():Array {
        var walls:Array = [];
        for each(var w:XML in Parameter.data.walls.*) {
            var removable:Boolean = ((w.@rem == "t") ? true : false);
            var wall:Wall = new Wall(int(w.@x), int(w.@y), removable);
            walls.push(wall);
        }
        return walls;
    }
    
    public static function getStarts(goals:Array):Array {
        var starts:Array = [];
        var len:int = goals.length;
        
        for each(var s:XML in Parameter.data.starts.*) {
            var destID:int = int(s.@dest);
            var i:int;
            for (i = 0; i < len; i++) {
                if (destID == goals[i].ID) { break; }
            }
            if (i >= len) { i = 0; }
            
            var node:Node = main.nodes[int(s.@y)][int(s.@x)];
            var dest:Goal = goals[i];
            var start:Start = new Start(node, dest);
            starts.push(start);
        }
        return starts;
    }
    
    public static function getGoals():Array {
        var goals:Array = [];
        for each(var g:XML in Parameter.data.goals.*) {
            var node:Node = main.nodes[int(g.@y)][int(g.@x)];
            var goal:Goal = new Goal(int(g.@id), node);
            goals.push(goal);
        }
        return goals;
    }
}