Dijkstra Particle Streams | wonderfl build flash online

※現在、「wonderfl build flash online」求人コンテンツ制作に関してのアンケートを実施中です！みなさまのお力添えを頂いて、続々とアンケート結果が集まっていますが、まだまだ募集しております。ご協力のほど、どうぞよろしくお願いいたします！

wonderfl運営事務局
→アンケートページ（※ログインしてからお答えいただけるようになっています。）

Dijkstra Particle Streams

add to favorites

o8que

notice: Flash editor updated! Join the development! Thanks to MiniBuilder

forked : 2
favorite : 60
lines : 534
license : MIT License
modified : 2010-02-04 09:24:37

embed

Twitterでつぶやく

/* ------------------------------------------------------------------
 * 最短経路を進むパーティクル（のはず）
 * 
 * [inspired by]
 * Desktop Tower Defense
 * http://www.handdrawngames.com/DesktopTD/
 * Dijkstra Visualization
 * http://wonderfl.net/code/6faaab5234abf034417a8e753f6309de0b9560f0
 * and 神の書とwonderflのパーティクル作品群
 * ------------------------------------------------------------------
 * [操作方法]
 * マウスのみ。
 * クリックすると壁を設置・除去できます。
 * ------------------------------------------------------------------
 * [簡単な説明]
 * main : 全体の初期化と更新処理
 * Node : マス目の情報
 * Wall : 壁の情報
 * Particle : パーティクルの情報
 * Start : パーティクルを出現させる場所です
 * Goal : パーティクルの目的地（ここで経路探索処理してます）
 * Parameter : ここのXMLをいじるといろいろ変えられます
 * ------------------------------------------------------------------
 * 
 * とりあえず投稿。内容、コメント等は後で充実させていきます。
 * 
 */
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();
			initializeWalls();
			initializeStreams();	
			
			addEventListener(Event.ENTER_FRAME, update);
			
			initializeCursor();
			
		}
		
		// ノードの初期化
		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(465, 465, false, 0x000000);
			particleLayer.bitmapData = _particleCanvas;
			addChild(particleLayer);
			
			_canvasRect = new Rectangle(0, 0, 465, 465);
			_colorTransform = new ColorTransform(0.9, 0.9, 0.9);
		}
		
		// 壁の初期化
		private function initializeWalls():void {
			_wallLayer = new Sprite();
			var walls:Array = Parameter.getWalls();
			var len:int = int(walls.length);
			for (var i:int = 0; i < len; i++) {
				_wallLayer.addChild(walls[i]);
			}
			addChild(_wallLayer);
		}
		
		// スタートノード、ゴールノードの初期化
		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 initializeCursor():void {
			_cursor = new Shape();
			_cursor.graphics.lineStyle(1, 0xffff00);
			_cursor.graphics.drawRect(0, 0, main.NODE_SIZE * 2 - 0.5, main.NODE_SIZE * 2 - 0.5);
			addChild(_cursor);
			
			stage.addEventListener(MouseEvent.MOUSE_MOVE, moveCursor);
			stage.addEventListener(MouseEvent.CLICK, clickMap);
		}
		
		// カーソルの移動
		private function moveCursor(e:MouseEvent):void {
			_cursor.x = e.stageX - (e.stageX % main.NODE_SIZE);
			_cursor.y = e.stageY - (e.stageY % main.NODE_SIZE);
		}
		
		// マップクリック時の挙動
		private function clickMap(e:MouseEvent):void {
			var wall:Wall;
			
			// クリックした場所が除去できる壁なら除去する
			if (e.target is Wall) {
				wall = e.target as Wall;
				if (wall.removable) {
					wall.remove();
					reSearchGoals();
				}
			// クリックした場所に壁が設置できるなら設置する
			}else {
				var tile:Point = Node.tileFormPos(new Point(e.stageX, e.stageY));
				if (buildableWall(tile.x, tile.y)) {
					wall = new Wall(tile.x, tile.y);
					_wallLayer.addChild(wall);
					reSearchGoals();
				}
			}
		}
		
		// 全てのゴールノードを更新（経路の最探索）をする
		private function reSearchGoals():void {
			var len:int = _goals.length;
			for (var i:int = 0; i < len; i++) {
				_goals[i].search();
			}
		}
		
		// 指定した位置に壁が設置できるか
		private function buildableWall(tilex:int, tiley:int):Boolean {
			return (main.nodes[tiley][tilex].passable &&
			main.nodes[tiley][tilex + 1].passable &&
			main.nodes[tiley + 1][tilex].passable &&
			main.nodes[tiley + 1][tilex + 1].passable);
		}
		
		// 毎フレームの更新処理
		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" />
		<walls>
			<wall x="0" y="0" rem="f"/><wall x="2" y="0" rem="f"/>
			<wall x="4" y="0" rem="f"/><wall x="6" y="0" rem="f"/>
			<wall x="8" y="0" rem="f"/><wall x="10" y="0" rem="f"/>
			<wall x="21" y="0" rem="f"/><wall x="23" y="0" rem="f"/>
			<wall x="25" y="0" rem="f"/><wall x="27" y="0" rem="f"/>
			<wall x="29" y="0" rem="f"/><wall x="31" y="0" rem="f"/>
			
			<wall x="0" y="31" rem="f"/><wall x="2" y="31" rem="f"/>
			<wall x="4" y="31" rem="f"/><wall x="6" y="31" rem="f"/>
			<wall x="8" y="31" rem="f"/><wall x="10" y="31" rem="f"/>
			<wall x="21" y="31" rem="f"/><wall x="23" y="31" rem="f"/>
			<wall x="25" y="31" rem="f"/><wall x="27" y="31" rem="f"/>
			<wall x="29" y="31" rem="f"/><wall x="31" y="31" rem="f"/>
			
			<wall x="0" y="2" rem="f"/><wall x="0" y="4" rem="f"/>
			<wall x="0" y="6" rem="f"/><wall x="0" y="8" rem="f"/>
			<wall x="0" y="10" rem="f"/><wall x="0" y="21" rem="f"/>
			<wall x="0" y="23" rem="f"/><wall x="0" y="25" rem="f"/>
			<wall x="0" y="27" rem="f"/><wall x="0" y="29" rem="f"/>
			
			<wall x="31" y="2" rem="f"/><wall x="31" y="4" rem="f"/>
			<wall x="31" y="6" rem="f"/><wall x="31" y="8" rem="f"/>
			<wall x="31" y="10" rem="f"/><wall x="31" y="21" rem="f"/>
			<wall x="31" y="23" rem="f"/><wall x="31" y="25" rem="f"/>
			<wall x="31" y="27" rem="f"/><wall x="31" y="29" rem="f"/>
		</walls>
		<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"/>
			
			<start dest="5" x="0" y="12"/>
			<start dest="5" x="0" y="13"/>
			<start dest="6" x="0" y="14"/>
			<start dest="6" x="0" y="15"/>
			<start dest="7" x="0" y="16"/>
			<start dest="8" x="0" y="17"/>
			<start dest="8" x="0" y="18"/>
			<start dest="9" x="0" y="19"/>
			<start dest="9" x="0" y="20"/>
		</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"/>
			
			<goal id="5" x="32" y="14"/>
			<goal id="6" x="32" y="15"/>
			<goal id="7" x="32" y="16"/>
			<goal id="8" x="32" y="17"/>
			<goal id="9" x="32" y="18"/>
		</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;
	}
}

*reference DIjkstra TowerDefence的 algorithm beautifl best frocessing ostacoli particelle particle pathfinding strada 勉強最短経路粒子

eternity_hiro

twelvetoes

fardeen

chieinoue

ferv

alumican_net

yoshimax

Skizi

enok

DLabz

cuegraphix

berian

ashtail

ikusu

osamX

OKASUKE

ryogo316

heckmeck

ngtn

Dan0

flabaka

dakkie

oreore

yamat

gong

motikawa_rgm

komatsu

sr_forest

crazy2death

skn

ninehundred

siouxcitizen

nki2

maccyan

sac_p37a1kc9

Makoto_Tanaka

soundkitchen

Mae_ITR

yutaka

paq

uwi

fakestar0826

ish_xxxx

akira_odohira

digitrick

9re

Donyz :

最短経路粒子

keno42 :

TowerDefence的

rintarock :

frocessing pathfinding最短経路

fans8 :

粒子

mrKaizen :

particelle strada ostacoli pathfindingparticelle su strada

pon_zu :

*reference particle

slene :

best

a440hlz :

beautifl

cjcat2266 :

DIjkstra algorithmFantastic combination of algorithm and visual effects!

cpu_t :

最短経路

h1ro :

Particle

kanabun :

勉強

dotton :

最短経路最短経路

clockmaker :

最短経路を進むパーティクル

>sort

Dijkstra Particle Streams Dijkstra Particle Streams (Ver.1.1) [diff(336)]

o8que

/* ------------------------------------------------------------------
* [更新内容]
* ・パフォーマンスを犠牲して、パーティクルを奇麗にしてみた
* ・パーティクルの軌跡を、滑らかに改善（＋経路を塞ぐとフワフワ）
* ・パーティクルが複数のゴール候補から最短のゴールに向かって進むようになった
* ・微妙にコードの整理、微妙なバグを修正
* ------------------------------------------------------------------
* [いじりどころ]
* 下の方にあるParameterクラスに簡単にいじれる値をまとめてあります。
* 是非、Forkしていろいろ試してみてください！
* ------------------------------------------------------------------
* エディタ出来ました。
* Layout Editor (for Dijkstra Particle Streams (Ver.1.1))
* http://wonderfl.net/code/425545196427ae8659973a8bfb13d54cfdeaf425
*/
/* ------------------------------------------------------------------
* 最短経路を進むパーティクル
*
* [inspired by]
* Desktop Tower Defense
* http://www.handdrawngames.com/DesktopTD/
* Dijkstra Visualization
* http://wonderfl.net/code/6faaab5234abf034417a8e753f6309de0b9560f0
* and 神の書とwonderflのパーティクル作品群
* ------------------------------------------------------------------
* [操作方法]
* マウスのみ。
* クリックすると壁を設置・除去できます。
* ------------------------------------------------------------------
* [簡単な説明]
* main : 全体の初期化と更新処理
* Node : マス目の情報
* Wall : 壁の情報
* Particle : パーティクルの情報
* Start : パーティクルを出現させる場所です
* Goal : パーティクルの目的地（ここで経路探索処理してます）
* Parameter : ここをいじるといろいろ変えられます
* ------------------------------------------------------------------
*/
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.Point;
[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 _wallLayer:Sprite;
private var _cursor:Shape;
public function main() {
// ノード、パーティクル、壁、ゴール、スタート、カーソルの順に初期化する
initializeNodes();
initializeParticles();
initializeWalls();
initializeStreams();
initializeCursor();
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();
particles = new Array(Parameter.PARTICLE_NUM);
for (var i:int = 0; i < Parameter.PARTICLE_NUM; i++){
particles[i]= new Particle();
}
var particleLayer:Bitmap = new Bitmap();
_particleCanvas = new BitmapData(465, 465, false, 0x000000);
particleLayer.bitmapData = _particleCanvas;
addChild(particleLayer);
}
// 壁の初期化
private function initializeWalls():void {
_wallLayer = new Sprite();
var walls:Array = Parameter.getWalls();
var len:int = walls.length;
for (var i:int = 0; i < len; i++) {
_wallLayer.addChild(walls[i]);
}
addChild(_wallLayer);
}
// スタートノード、ゴールノードの初期化
private function initializeStreams():void {
_goals = Parameter.getGoals();
_starts = Parameter.getStarts(_goals);
// パーティクルの出現をばらつかせるためにシャッフルする
shuffle(_starts);
}
// 配列をシャッフルする（Fisher-Yatesアルゴリズム）
private function shuffle(arr:Array):void {
var i:int = arr.length;
var j:int;
var tmp:*;
while (i) {
j = int(i * Math.random());
tmp = arr[--i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// カーソルの初期化
private function initializeCursor():void {
_cursor = new Shape();
_cursor.graphics.lineStyle(1, 0xffff00);
_cursor.graphics.drawRect(0, 0, main.NODE_SIZE * 2 - 0.5, main.NODE_SIZE * 2 - 0.5);
addChild(_cursor);
stage.addEventListener(MouseEvent.MOUSE_MOVE, moveCursor);
stage.addEventListener(MouseEvent.CLICK, clickMap);
}
// カーソルの移動
private function moveCursor(e:MouseEvent):void {
_cursor.x = e.stageX - (e.stageX % main.NODE_SIZE);
_cursor.y = e.stageY - (e.stageY % main.NODE_SIZE);
}
// マップクリック時の挙動
private function clickMap(e:MouseEvent):void {
// クリックした場所が除去できる壁なら除去する
if (e.target is Wall) {
if (e.target.removable) {
e.target.remove();
reSearchGoals();
}
// クリックした場所に壁が設置できるなら設置する
}else {
var tile:Point = Node.tileFromPos(new Point(e.stageX, e.stageY));
if (Wall.buildable(tile.x, tile.y)) {
_wallLayer.addChild(new Wall(tile.x, tile.y));
reSearchGoals();
}
}
}
// 全てのゴールノードを更新（経路の最探索）をする
private function reSearchGoals():void {
var i:int;
var len:int = _goals.length;
for (i = 0; i < len; i++) {
_goals[i].search();
}
// 各パーティクルの最短で到達できるゴールノードを更新する
for (i = 0; i < Parameter.PARTICLE_NUM; i++) {
if (main.particles[i].exists) {
main.particles[i].updateNearestGoal();
}
}
}
// 毎フレームの更新処理
private function update(e:Event):void {
spawnParticles();
updateParticles();
}
// スタートノードからパーティクルを出現させる
private function spawnParticles():void {
var len:int = _starts.length;
for (var i:int = 0; i < len; i++) {
_starts[i].update();
}
}
// パーティクルを更新と描画を行う
private function updateParticles():void {
_particleCanvas.lock();
for (var i:int = 0; i < Parameter.PARTICLE_NUM; i++) {
// パーティクルが画面内に存在していたら更新
if(main.particles[i].exists){
main.particles[i].update();
main.particles[i].draw(_particleCanvas);
}
}
_particleCanvas.colorTransform(_particleCanvas.rect, Parameter.CANVAS_COLOR_TRANSFORM);
_particleCanvas.applyFilter(_particleCanvas, _particleCanvas.rect, _particleCanvas.rect.topLeft, Parameter.CANVAS_FILTER);
_particleCanvas.unlock();
}
}
}
import flash.geom.Point;
class Node {
private var _tilex:int;
private var _tiley:int;
private var _centerx:Number; // 中心のX座標
private var _centery:Number; // 中心のY座標
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 tileFromPos(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, Parameter.WALL_BORDER_COLOR);
}
graphics.beginFill(Parameter.WALL_BASE_COLOR);
graphics.drawRect(0, 0, rectSize, rectSize);
graphics.endFill();
}
// 壁を取り除く際に呼ぶ関数
public function remove():void {
setNodePassablity(true);
parent.removeChild(this);
}
// 指定した位置に壁が設置できるか
public static function buildable(tilex:int, tiley:int):Boolean {
return (main.nodes[tiley][tilex].passable &&
main.nodes[tiley][tilex + 1].passable &&
main.nodes[tiley + 1][tilex].passable &&
main.nodes[tiley + 1][tilex + 1].passable);
}
}
import flash.display.BitmapData;
import flash.display.BlendMode;
import flash.display.Shape;
import flash.geom.Matrix;
import flash.geom.Point;
class Particle {
private var _posx:Number; // X座標の位置
private var _posy:Number; // Y座標の位置
private var _vx:Number; // X方向の速度（ベクトル）
private var _vy:Number; // Y方向の速度（ベクトル）
private var _speed:Number; // 速さ（スカラー）
private var _exists:Boolean; // 画面上に存在するかどうか
private var _start:Start; // 出現したスタートノード
private var _nearestGoal:Goal; // 最短で到達できるゴールノード
private var _nextNode:Node; // 次に進むべきノード
private static var _images:Array;
private var _imageIndex:int;
public function get exists():Boolean { return _exists; }
public function Particle() {
_posx = _posy = _vx = _vy = 0;
_speed = ((Parameter.PARTICLE_MAXSPEED - 1) * Math.random()) + 1;
_exists = false;
_start = null;
_nearestGoal = null;
_nextNode = null;
_imageIndex = 0;
}
// スタートノードから出現させる
public function spawn(start:Start):void {
_posx = start.node.centerX;
_posy = start.node.centerY;
_vx = _vy = 0;
_exists = true;
_start = start;
_nearestGoal = _start.getNearestGoalFrom(start.node.tileX, start.node.tileY);
_nextNode = _nearestGoal.getNext(start.node.tileX, start.node.tileY);
_imageIndex = int(Parameter.PARTICLE_COLORS.length * Math.random());
}
public function update():void {
_posx += _vx;
_posy += _vy;
var tile:Point = Node.tileFromPos(new Point(_posx, _posy));
// ゴールに着いたか、移動不可能（かべのなかにいる）なら消滅する
if (arrivedGoal(tile.x, tile.y) || !isMovable(tile.x, tile.y)) {
_exists = false;
return;
}
//次に進むべきノードへ到着していたら、次に進むべきノードを更新する
if (arrivedNextNode(tile.x, tile.y)) {
updateNextNode(tile.x, tile.y);
}
// ゴールノードへの経路が存在しないならフワフワする
if (_nextNode == main.nodes[tile.y][tile.x]) {
_vx = (_vx * 0.5) + (Math.random() - 0.5);
_vy = (_vy * 0.5) + (Math.random() - 0.5);
}else {
var radians:Number = Math.atan2(_nextNode.centerY - _posy, _nextNode.centerX - _posx);
_vx = (_vx + _speed * Math.cos(radians)) * 0.5;
_vy = (_vy + _speed * Math.sin(radians)) * 0.5;
}
}
// 最短で到達できるゴールノードを更新する
public function updateNearestGoal():void {
var tile:Point = Node.tileFromPos(new Point(_posx, _posy));
_nearestGoal = _start.getNearestGoalFrom(tile.x, tile.y);
updateNextNode(tile.x, tile.y);
}
// 次に進むべきノードを更新する
private function updateNextNode(tilex:int, tiley:int):void {
_nextNode = _nearestGoal.getNext(tilex, tiley);
}
// ゴールノードへ到着しているかどうか
private function arrivedGoal(tilex:int, tiley:int):Boolean {
return (tilex == _nearestGoal.node.tileX) && (tiley == _nearestGoal.node.tileY);
}
// パーティクルが移動できるかどうか
private function isMovable(tilex:int, tiley:int):Boolean {
return main.nodes[tiley][tilex].passable;
}
// 次に進むべきノードへ到着しているかどうか
private function arrivedNextNode(tilex:int, tiley:int):Boolean {
return (_nextNode.tileX == tilex) && (_nextNode.tileY == tiley);
}
// canvasにパーティクルの画像を描画する
public function draw(canvas:BitmapData):void {
var matrix:Matrix = new Matrix();
matrix.translate(_posx - Parameter.PARTICLE_RADIUS, _posy - Parameter.PARTICLE_RADIUS);
canvas.draw(_images[_imageIndex], matrix, null, BlendMode.ADD);
}
// パーティクルの画像を予め作成しておく関数
public static function createImages():void {
_images = [];
for (var i:int = 0; i < Parameter.PARTICLE_COLORS.length; i++) {
var bitmapData:BitmapData = new BitmapData(Math.ceil(Parameter.PARTICLE_RADIUS * 2), Math.ceil(Parameter.PARTICLE_RADIUS * 2), true, 0x00ffffff);
var shape:Shape = new Shape();
shape.graphics.beginFill(Parameter.PARTICLE_COLORS[i]);
shape.graphics.drawCircle(Parameter.PARTICLE_RADIUS, Parameter.PARTICLE_RADIUS, Parameter.PARTICLE_RADIUS);
shape.graphics.endFill();
bitmapData.draw(shape);
_images.push(bitmapData);
}
}
}
class Start {
private var _node:Node;
private var _goalGroup:Array; // ゴールノードのグループ
private var _spawnCount:int; // パーティクルを出現させる為のカウント
public function get node():Node { return _node; }
public function getNearestGoalFrom(tilex:int, tiley:int):Goal {
var nearest:Goal = _goalGroup[0];
var len:int = _goalGroup.length;
for (var i:int = 1; i < len; i++) {
if (_goalGroup[i].getCost(tilex, tiley) < nearest.getCost(tilex, tiley)) {
nearest = _goalGroup[i];
}
}
return nearest;
}
public function Start(node:Node, goalGroup:Array) {
_node = node;
_goalGroup = goalGroup;
_spawnCount = int(Parameter.SPAWN_INTERVAL * Math.random());
}
public function update():void {
// ゴールノードへの経路が存在しない場合は何もしない
if (!hasPathToGoal()) { return; }
// 一定の間隔でパーティクルの出現を試みる
if (++_spawnCount >= Parameter.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;
}
}
}
}
// 最低一つのゴールノードへの経路が存在するかどうか
private function hasPathToGoal():Boolean {
var len:int = _goalGroup.length;
for (var i:int = 0; i < len; i++) {
if (_goalGroup[i].accessibleFrom(_node)) {
return true;
}
}
return false;
}
}
class Goal {
private static const DX:Array = [0, -1, 1, 0, -1, 1, -1, 1];
private static const DY:Array = [ -1, 0, 0, 1, -1, -1, 1, 1];
private static const DCOST:Array = [1, 1, 1, 1, Math.SQRT2, Math.SQRT2, Math.SQRT2, Math.SQRT2];
private var _groupID:int; // 所属するグループのID
private var _node:Node; // ゴールとする対象のノード
private var _openNodes:Array; // 保留ノードリスト
private var _nodeCost:Array; // 各ノードの移動コスト
private var _nodeNext:Array; // 各ノードの次の経路となるノード
public function get groupID():int { return _groupID; }
public function get node():Node { return _node; }
public function getCost(tilex:int, tiley:int):Number { return _nodeCost[tiley][tilex]; }
public function getNext(tilex:int, tiley:int):Node { return _nodeNext[tiley][tilex]; }
public function Goal(groupID:int, node:Node) {
_groupID = groupID;
_node = node;
_openNodes = [];
_nodeCost = [];
_nodeNext = [];
for (var row:int = 0; row < main.MAP_SIZE; row++) {
_nodeCost[row] = [];
_nodeNext[row] = [];
}
search();
}
// ダイクストラ法による経路探索
public function search():void {
initialize();
while (_openNodes.length > 0) {
var subject:Node = _openNodes.pop() as Node;
// 周囲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) || isCalculatedNode(test) || !canGoStraightTo(subject, test)) { continue; }
// 移動コストを計算する
_nodeCost[test.tileY][test.tileX] = _nodeCost[subject.tileY][subject.tileX] + Goal.DCOST[i];
// 次の経路ノードをsubjectノードに設定する
_nodeNext[test.tileY][test.tileX] = subject;
// 保留ノードリストに追加する
insertToOpenNodes(test);
}
}
}
private function initialize():void {
for (var row:int = 0; row < main.MAP_SIZE; row++) {
for (var col:int = 0; col < main.MAP_SIZE; col++) {
_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]);
}
// indexの値が有効な値かどうか
private function isValid(index:int):Boolean {
return ((index >= 0) && (index < main.MAP_SIZE));
}
// 既にコストを計算済みのノードかどうか
private function isCalculatedNode(node:Node):Boolean {
return _nodeCost[node.tileY][node.tileX] != int.MAX_VALUE;
}
// 壁が設置されたノードかどうか
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:Number = _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);
}
// nodeからこのゴールノードに到達することができる（経路が存在する）かどうか
public function accessibleFrom(node:Node):Boolean {
return _nodeCost[node.tileY][node.tileX] != int.MAX_VALUE;
}
}
import flash.filters.BitmapFilter;
import flash.filters.BlurFilter;
import flash.geom.ColorTransform;
import flash.geom.Point;
class Parameter {
// パーティクルの最大数
public static const PARTICLE_NUM:int = 1000;
/// パーティクルの半径
public static const PARTICLE_RADIUS:Number = 4.0;
// パーティクルの最大速度
public static const PARTICLE_MAXSPEED:Number = 7.5;
// パーティクルの色（種類）
public static const PARTICLE_COLORS:Array = [0x224488];
// パーティクルの軌跡の色の変化
public static const CANVAS_COLOR_TRANSFORM:ColorTransform = new ColorTransform(0.9, 0.92, 0.95);
// パーティクルを描画するキャンバスに適用するフィルタ
public static const CANVAS_FILTER:BitmapFilter = new BlurFilter(2, 2, 1);
// パーティクルの出現間隔
public static const SPAWN_INTERVAL:int = 10;
// 壁の色
public static const WALL_BASE_COLOR:uint = 0x202020;
// （除去可能な）壁の枠線の色
public static const WALL_BORDER_COLOR:uint = 0x404040;
private static const data:XML =
<root>
<walls>
<wall x="0" y="0" rem="f"/><wall x="2" y="0" rem="f"/>
<wall x="4" y="0" rem="f"/><wall x="6" y="0" rem="f"/>
<wall x="8" y="0" rem="f"/><wall x="10" y="0" rem="f"/>
<wall x="21" y="0" rem="f"/><wall x="23" y="0" rem="f"/>
<wall x="25" y="0" rem="f"/><wall x="27" y="0" rem="f"/>
<wall x="29" y="0" rem="f"/><wall x="31" y="0" rem="f"/>
<wall x="0" y="31" rem="f"/><wall x="2" y="31" rem="f"/>
<wall x="4" y="31" rem="f"/><wall x="6" y="31" rem="f"/>
<wall x="8" y="31" rem="f"/><wall x="10" y="31" rem="f"/>
<wall x="21" y="31" rem="f"/><wall x="23" y="31" rem="f"/>
<wall x="25" y="31" rem="f"/><wall x="27" y="31" rem="f"/>
<wall x="29" y="31" rem="f"/><wall x="31" y="31" rem="f"/>
<wall x="0" y="2" rem="f"/><wall x="0" y="4" rem="f"/>
<wall x="0" y="6" rem="f"/><wall x="0" y="8" rem="f"/>
<wall x="0" y="10" rem="f"/><wall x="0" y="21" rem="f"/>
<wall x="0" y="23" rem="f"/><wall x="0" y="25" rem="f"/>
<wall x="0" y="27" rem="f"/><wall x="0" y="29" rem="f"/>
<wall x="31" y="2" rem="f"/><wall x="31" y="4" rem="f"/>
<wall x="31" y="6" rem="f"/><wall x="31" y="8" rem="f"/>
<wall x="31" y="10" rem="f"/><wall x="31" y="21" rem="f"/>
<wall x="31" y="23" rem="f"/><wall x="31" y="25" rem="f"/>
<wall x="31" y="27" rem="f"/><wall x="31" y="29" rem="f"/>
</walls>
<starts>
<start goal="0" x="13" y="0"/><start goal="0" x="14" y="0"/>
<start goal="0" x="15" y="0"/><start goal="0" x="16" y="0"/><start goal="0" x="17" y="0"/>
<start goal="0" x="18" y="0"/><start goal="0" x="19" y="0"/>
<start goal="1" x="0" y="13"/><start goal="1" x="0" y="14"/>
<start goal="1" x="0" y="15"/><start goal="1" x="0" y="16"/><start goal="1" x="0" y="17"/>
<start goal="1" x="0" y="18"/><start goal="1" x="0" y="19"/>
</starts>
<goals>
<goal id="0" x="13" y="32"/><goal id="0" x="14" y="32"/>
<goal id="0" x="15" y="32"/><goal id="0" x="16" y="32"/><goal id="0" x="17" y="32"/>
<goal id="0" x="18" y="32"/><goal id="0" x="19" y="32"/>
<goal id="1" x="32" y="13"/><goal id="1" x="32" y="14"/>
<goal id="1" x="32" y="15"/><goal id="1" x="32" y="16"/><goal id="1" x="32" y="17"/>
<goal id="1" x="32" y="18"/><goal id="1" x="32" y="19"/>
</goals>
</root>;
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 groupID:int = int(s.@goal);
var goalGroup:Array = [];
for (var i:int = 0; i < len; i++) {
if (goals[i].groupID == groupID) {
goalGroup.push(goals[i]);
}
}
starts.push(new Start(main.nodes[int(s.@y)][int(s.@x)], goalGroup));
}
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;
}
}

Dijkstra Particle Streams forked from: Dijkstra Particle Streams [diff(152)]

crazy2death

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;
}
}