flash on 2011-12-28
package
{
import com.bit101.components.RadioButton;
import com.bit101.components.Style;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
public class Main extends Sprite
{
private var container:Sprite;
private var nodeLayer:Sprite;
private var lineLayer:Sprite;
private var uiLayer:Sprite;
private var clickType:String = Node.TYPE_START;
private var nodeManager:NodeManager;
private const NODE_WIDTH:int = 22;
private const NODE_HEIGHT:int = 19;
private const NODE_SIZE:int = 20;
public function Main()
{
Style.fontName = "";
Style.embedFonts = false;
Style.fontSize = 12;
addChild(container = new Sprite());
container.x = container.y = 2;
container.mouseChildren = false;
container.addChild(nodeLayer = new Sprite());
container.addChild(lineLayer = new Sprite());
container.addEventListener(MouseEvent.MOUSE_DOWN, onMouseDown);
stage.addEventListener(MouseEvent.MOUSE_UP, onMouseUp);
addChild(uiLayer = new Sprite());
uiLayer.x = 20;
uiLayer.y = 380;
new RadioButton(uiLayer, 5, 10, "スタート地点", true, function(event:Event):void { clickType = Node.TYPE_START; } ).groupName = "0";
new RadioButton(uiLayer, 5, 30, "ゴール地点", false, function(event:Event):void { clickType = Node.TYPE_GOAL; } ).groupName = "0";
new RadioButton(uiLayer, 100, 10, "壁(移動不可)", false, function(event:Event):void { clickType = Node.TYPE_WALL; } ).groupName = "0";
new RadioButton(uiLayer, 100, 30, "フィールド(通常)", false, function(event:Event):void { clickType = Node.TYPE_FIELD; } ).groupName = "0";
new RadioButton(uiLayer, 100, 50, "沼(移動時間倍)", false, function(event:Event):void { clickType = Node.TYPE_SWAMP; } ).groupName = "0";
new RadioButton(uiLayer, 250, 10, "DFS", true, function(event:Event):void { nodeManager.searchAlgorithm = new DFS(nodeManager); search(); } ).groupName = "1";
new RadioButton(uiLayer, 250, 30, "BFS", false, function(event:Event):void { nodeManager.searchAlgorithm = new BFS(nodeManager); search(); } ).groupName = "1";
new RadioButton(uiLayer, 250, 50, "DA", false, function(event:Event):void { nodeManager.searchAlgorithm = new Dijkstra(nodeManager); search(); } ).groupName = "1";
new RadioButton(uiLayer, 250, 70, "A*", false, function(event:Event):void { nodeManager.searchAlgorithm = new AStar(nodeManager); search(); } ).groupName = "1";
new RadioButton(uiLayer, 310, 10, "4方向移動", false, function(event:Event):void { nodeManager.dir = NodeManager.DIR4; search(); } ).groupName = "2";
new RadioButton(uiLayer, 310, 30, "8方向移動", true, function(event:Event):void { nodeManager.dir = NodeManager.DIR8; search(); } ).groupName = "2";
var map:Array =
[
"___*____++++__________",
"_g_*_******++****_____",
"___*___**_____________",
"___*____*__**_________",
"_****___*___*_______**",
"+_+*____***_*________*",
"_+_*__+_*_*_*___***___",
"+_+*_*_+++*_**++++*___",
"_+_*_***__*__**+++*___",
"+_+*___**_____*+++*___",
"_+_*_***********__*___",
"+_+__*_++_++_+_**_*___",
"******____++_+________",
"__++___*****__________",
"_______*___******_____",
"_*********_**___******",
"_*___*_____*__*_*_____",
"___*_*_*_***__*____s__",
"_*_*___*______*_______"
];
nodeManager = new NodeManager(NODE_WIDTH, NODE_HEIGHT, NODE_SIZE, nodeLayer);
container.x = (stage.stageWidth - container.width) / 2;
nodeManager.searchAlgorithm = new DFS(nodeManager);
nodeManager.dir = NodeManager.DIR8;
nodeManager.setNodeMap(map);
search();
}
private function onMouseUp(event:MouseEvent = null):void
{
removeEventListener(MouseEvent.MOUSE_MOVE, onMouseMove);
search();
}
private function onMouseDown(event:MouseEvent):void
{
addEventListener(MouseEvent.MOUSE_MOVE, onMouseMove);
onMouseMove(event);
}
private function onMouseMove(event:MouseEvent):void
{
var tileX:int = event.localX / nodeManager.size;
var tileY:int = event.localY / nodeManager.size;
if (!nodeManager.onBoard(tileX, tileY)) return;
nodeManager.changeType(tileX, tileY, clickType);
nodeManager.reset(tileX, tileY);
}
private function search():void
{
nodeManager.resetAll();
var path:Array = nodeManager.getPath();
if (path == null) return;
lineLayer.graphics.clear();
lineLayer.graphics.lineStyle(2.0, 0x0000FF, 0.5);
for each (var nodes:Array in path[1])
{
var prevNode:Node = nodes[0];
var curNode:Node = nodes[1];
lineLayer.graphics.moveTo(prevNode.center.x, prevNode.center.y);
lineLayer.graphics.lineTo(curNode.center.x, curNode.center.y);
}
lineLayer.graphics.lineStyle(8.0, 0xA757A8);
var startNode:Node = path[0][0];
lineLayer.graphics.moveTo(startNode.center.x, startNode.center.y);
for each (var node:Node in path[0])
{
lineLayer.graphics.lineTo(node.center.x, node.center.y);
}
}
}
}
import flash.display.Sprite;
import flash.geom.Point;
class Node extends Sprite
{
public static const TYPE_START:String = "start";
public static const TYPE_GOAL:String = "goal";
public static const TYPE_WALL:String = "wall";
public static const TYPE_FIELD:String = "field";
public static const TYPE_SWAMP:String = "swamp";
public var pos:Point;
public var size:int;
public var distance:Number;
public var prev:Node;
public var type:String = "";
public var cost:Number = 0.0;
public var visited:Boolean = false;
public var g:Number;
public var h:Number;
public var f:Number;
public function Node(size:int)
{
this.size = size;
draw();
}
public function get center():Point
{
return new Point(this.pos.x * size + size / 2, this.pos.y * size + size / 2);
}
public function getDistance(otherNode:Node):Number
{
var dx:Number = Math.abs(this.pos.x - otherNode.pos.x);
var dy:Number = Math.abs(this.pos.y - otherNode.pos.y);
return Math.max(dx, dy);
}
public function draw(color:int = 0xFFFFFF, alpha:Number = 1.0):void
{
graphics.clear();
graphics.lineStyle(2.0);
graphics.beginFill(color, alpha);
graphics.drawRect(0, 0, size, size);
graphics.endFill();
}
}
class Search
{
public var nodeManager:NodeManager;
public function Search(nodeManager:NodeManager)
{
this.nodeManager = nodeManager;
}
public function execute(dir:Array):Array
{
throw new Error();
}
}
class NodeManager
{
public var nodes:Array;
public var width:int;
public var height:int;
public var nodeContainer:Sprite;
public var size:int;
public var startNode:Node;
public var goalNode:Node;
public var search:Search;
public var dir:Array;
public static const COLOR_START:Array = [0x009AD6, 1.0];
public static const COLOR_GOAL:Array = [0xED1A3D, 1.0];
public static const COLOR_WALL:Array = [0x50160B, 1.0];
public static const COLOR_FIELD:Array = [0xFFFFFF, 0.0];
public static const COLOR_SWAMP:Array = [0xF1BB93, 0.7];
public static const DIR4:Array = [[ -1, 0], [1, 0], [0, -1], [0, 1]];
public static const DIR8:Array = [[ -1, -1], [ -1, 0], [ -1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];
public function NodeManager(width:int, height:int, size:int, nodeContainer:Sprite)
{
this.width = width;
this.height = height;
this.size = size;
this.nodeContainer = nodeContainer;
createNodeMap();
startNode = nodes[1][2];
goalNode = nodes[1][1];
startNode.type = Node.TYPE_START;
goalNode.type = Node.TYPE_GOAL;
}
public function createNodeMap():void
{
nodes = [];
for (var y:int = 0; y < height; y++)
{
nodes[y] = []
for (var x:int = 0; x < width; x++)
{
var node:Node = new Node(size);
node.x = x * size;
node.y = y * size;
node.type = Node.TYPE_FIELD;
node.pos = new Point(x, y);
nodeContainer.addChildAt(node, 0);
nodes[y][x] = node;
}
}
}
public function setNodeMap(map:Array):void
{
for (var y:int = 0; y < height; y++)
{
for (var x:int = 0; x < width; x++)
{
switch (map[y].charAt(x))
{
case "s":
changeType(x, y, Node.TYPE_START);
break;
case "g":
changeType(x, y, Node.TYPE_GOAL);
break;
case "_":
changeType(x, y, Node.TYPE_FIELD);
break;
case "+":
changeType(x, y, Node.TYPE_SWAMP);
break;
case "*":
changeType(x, y, Node.TYPE_WALL);
break;
default:
throw new Error();
}
}
}
}
public function reset(x:int, y:int):void
{
var node:Node = nodes[y][x];
changeType(x, y, node.type);
node.visited = false;
node.distance = int.MAX_VALUE;
node.prev = null;
node.g = node.h = node.f = 0.0;
switch (node.type)
{
case Node.TYPE_START:
node.draw(COLOR_START[0], COLOR_START[1]);
break;
case Node.TYPE_GOAL:
node.draw(COLOR_GOAL[0], COLOR_GOAL[1]);
break;
case Node.TYPE_WALL:
node.draw(COLOR_WALL[0], COLOR_WALL[1]);
break;
case Node.TYPE_FIELD:
node.draw(COLOR_FIELD[0], COLOR_FIELD[1]);
break;
case Node.TYPE_SWAMP:
node.draw(COLOR_SWAMP[0], COLOR_SWAMP[1]);
break;
}
}
public function resetAll():void
{
for (var y:int = 0; y < height; y++)
{
for (var x:int = 0; x < width; x++)
{
reset(x, y);
}
}
}
public function onBoard(x:int, y:int):Boolean
{
return 0 <= x && x < width && 0 <= y && y < height;
}
public function getPath():Array
{
return search.execute(dir);
}
public function set searchAlgorithm(value:Search):void
{
search = value;
}
public function changeType(x:int, y:int, type:String):void
{
var node:Node = nodes[y][x];
if (node == startNode || node == goalNode) return;
switch (type)
{
case Node.TYPE_START:
startNode.type = Node.TYPE_FIELD;
startNode = node;
node.cost = 1.0;
break;
case Node.TYPE_GOAL:
goalNode.type = Node.TYPE_FIELD;
goalNode = node;
node.cost = 1.0;
break;
case Node.TYPE_WALL:
break;
case Node.TYPE_FIELD:
node.cost = 1.0;
break;
case Node.TYPE_SWAMP:
node.cost = 2.0;
break;
default:
break;
}
node.type = type;
}
}
class DFS extends Search
{
public function DFS(nodeManager:NodeManager):void
{
super(nodeManager);
}
override public function execute(dir:Array):Array
{
var history:Array = [];
var stack:Array = [[nodeManager.startNode, nodeManager.startNode]];
while (stack.length > 0)
{
var path:Array = stack.pop();
var curNode:Node = path[path.length - 1];
if (curNode.visited || curNode.type == Node.TYPE_WALL) continue;
curNode.visited = true;
var prevNode:Node = path[path.length - 2];
history.push([prevNode, curNode]);
if (curNode == nodeManager.goalNode)
{
return [path, history];
}
for (var i:int = 0; i < dir.length; i++)
{
var yy:int = dir[i][0];
var xx:int = dir[i][1];
var next:Point = new Point(curNode.pos.x + xx, curNode.pos.y + yy);
if (!nodeManager.onBoard(next.x, next.y)) continue;
var nextNode:Node = nodeManager.nodes[next.y][next.x];
if (!nextNode.visited && nextNode.type != Node.TYPE_WALL)
{
stack.push(path.concat(nextNode));
}
}
}
return null;
}
}
class BFS extends Search
{
public function BFS(nodeManager:NodeManager):void
{
super(nodeManager);
}
override public function execute(dir:Array):Array
{
var history:Array = [];
var queue:Array = [[nodeManager.startNode, nodeManager.startNode]];
while (queue.length > 0)
{
var path:Array = queue.shift();
var curNode:Node = path[path.length - 1];
if (curNode.visited) continue;
curNode.visited = true;
var prevNode:Node = path[path.length - 2];
history.push([prevNode, curNode]);
if (curNode == nodeManager.goalNode)
{
return [path, history];
}
for (var i:int = 0; i < dir.length; i++)
{
var yy:int = dir[i][0];
var xx:int = dir[i][1];
var next:Point = new Point(curNode.pos.x + xx, curNode.pos.y + yy);
if (!nodeManager.onBoard(next.x, next.y)) continue;
var nextNode:Node = nodeManager.nodes[next.y][next.x];
if (!nextNode.visited && nextNode.type != Node.TYPE_WALL)
{
queue.push(path.concat(nextNode));
}
}
}
return null;
}
}
class Dijkstra extends Search
{
public function Dijkstra(nodeManager:NodeManager):void
{
super(nodeManager);
}
override public function execute(dir:Array):Array
{
var curNode:Node = nodeManager.startNode;
curNode.distance = 0;
var goalNode:Node;
var node:Node, x:int, y:int;
while (true)
{
if (curNode == nodeManager.goalNode)
{
goalNode = curNode;
break;
}
curNode.visited = true;
for (var i:int = 0; i < dir.length; i++)
{
var yy:int = dir[i][0];
var xx:int = dir[i][1];
if (xx == 0 && yy == 0) continue;
if (!nodeManager.onBoard(curNode.pos.x + xx, curNode.pos.y + yy)) continue;
node = nodeManager.nodes[curNode.pos.y + yy][curNode.pos.x + xx];
if (node.visited) continue;
if (node.type == Node.TYPE_WALL) continue;
var newDistance:Number = curNode.distance + node.cost;
if (newDistance < node.distance)
{
node.distance = newDistance;
node.prev = curNode;
}
}
var nextNode:Node = null;
for (y = 0; y < nodeManager.height; y++)
{
for (x = 0; x < nodeManager.width; x++)
{
node = nodeManager.nodes[y][x];
if (node.visited) continue;
if (node.type == Node.TYPE_WALL) continue;
if (nextNode == null)
{
nextNode = node;
}
else if (node.distance < nextNode.distance)
{
nextNode = node;
}
}
}
if (nextNode == null) break;
else
{
curNode = nextNode;
}
}
if (goalNode == null) return null;
var path:Array = [goalNode];
while (goalNode.prev != null)
{
goalNode = goalNode.prev;
path.push(goalNode);
}
var history:Array = [];
for (y = 0; y < nodeManager.height; y++)
{
for (x = 0; x < nodeManager.width; x++)
{
node = nodeManager.nodes[y][x];
if (node.prev == null) continue;
history.push([node, node.prev]);
}
}
return [path, history];
}
}
class AStar extends Search
{
public function AStar(nodeManager:NodeManager):void
{
super(nodeManager);
}
override public function execute(dir:Array):Array
{
var curNode:Node = nodeManager.startNode;
curNode.g = 0;
curNode.f = curNode.h = curNode.getDistance(nodeManager.goalNode);
var goalNode:Node;
var node:Node, x:int, y:int;
var open:Array = [curNode];
var close:Array = [];
while (open.length > 0)
{
open.sortOn("f", Array.NUMERIC);
curNode = open.shift();
curNode.visited = true;
if (curNode == nodeManager.goalNode)
{
goalNode = curNode;
break;
}
close.push(curNode);
for (var i:int = 0; i < dir.length; i++)
{
var yy:int = dir[i][0];
var xx:int = dir[i][1];
if (xx == 0 && yy == 0) continue;
if (!nodeManager.onBoard(curNode.pos.x + xx, curNode.pos.y + yy)) continue;
node = nodeManager.nodes[curNode.pos.y + yy][curNode.pos.x + xx];
if (node.type == Node.TYPE_WALL) continue;
if (close.indexOf(node) != -1) continue;
var g:Number = curNode.g + node.cost;
var updateFlag:Boolean = false;
if (open.indexOf(node) == -1)
{
open.push(node);
updateFlag = true;
}
else if (g < node.g)
{
updateFlag = true;
}
if (updateFlag)
{
node.prev = curNode;
node.g = g;
node.h = node.getDistance(nodeManager.goalNode);
node.f = node.g + node.h;
}
}
}
if (goalNode == null) return null;
var path:Array = [goalNode];
while (goalNode.prev != null)
{
goalNode = goalNode.prev;
path.push(goalNode);
}
var history:Array = [];
for (y = 0; y < nodeManager.height; y++)
{
for (x = 0; x < nodeManager.width; x++)
{
node = nodeManager.nodes[y][x];
if (node.prev == null) continue;
if (!node.visited) continue;
history.push([node, node.prev]);
}
}
return [path, history];
}
}