PathFindTest
...
@author lizhi http://matrix3d.github.io
/**
* Copyright lizhi ( http://wonderfl.net/user/lizhi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/gG03
*/
package {
/**
* ...
* @author lizhi http://matrix3d.github.io
*/
import com.bit101.components.CheckBox;
import com.bit101.components.InputText;
import com.bit101.components.Label;
import com.bit101.components.PushButton;
import com.bit101.components.VBox;
import com.bit101.components.Window;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.system.System;
import flash.utils.getTimer;
public class PathFindTest extends Sprite {
private var cellSize:int = 5;
private var player:Sprite;
private var index:int;
private var path:Array;
private var tf:Label;
private var astar:AStar;
private var pathView:Sprite = new Sprite();
private var image:Bitmap = new Bitmap(new BitmapData(1, 1));
private var imageWrapper:Sprite = new Sprite();
private var isClick:Boolean = false;
private var numColsInput:InputText;
private var numRowsInput:InputText;
private var cellSizeInput:InputText;
private var densityInput:InputText;
private var isEightBox:CheckBox;
public function PathFindTest(){
stage.align = StageAlign.TOP_LEFT;
stage.scaleMode = StageScaleMode.NO_SCALE;
addChild(imageWrapper);
imageWrapper.addChild(image);
makePlayer();
var w:Window = new Window(this, 20, 20, "tool");
var vbox:VBox = new VBox(w.content, 5, 5);
numColsInput = new InputText(vbox,0,0,"50");
numRowsInput = new InputText(vbox,0,0,"50");
cellSizeInput = new InputText(vbox,0,0,"10");
densityInput = new InputText(vbox,0,0,".1");
tf = new Label(vbox,0,0,"info");
var btn:PushButton = new PushButton(vbox,0,0,"new", newMap);
w.setSize(150, 200);
imageWrapper.addEventListener(MouseEvent.CLICK, onGridClick);
addEventListener(Event.ENTER_FRAME, onEnterFrame);
imageWrapper.addChild(pathView);
makeGrid();
}
private function newMap(e:Event):void {
makeGrid();
}
private function makePlayer():void {
player = new Sprite();
player.graphics.beginFill(0xff00ff);
player.graphics.drawCircle(0, 0, 2);
player.graphics.endFill();
imageWrapper.addChild(player);
}
private function makeGrid():void {
var rows:int = int(numRowsInput.text);
var cols:int = int(numColsInput.text);
cellSize = int(cellSizeInput.text);
astar = new AStar;
for (var y:int = 0; y < rows;y++ ) {
for (var x:int = 0; x < cols; x++ ) {
if (Math.random()<.9) {
if (astar.nodes[y]==null) {
astar.nodes[y] = { };
}
astar.nodes[y][x] = new Node(x,y);
}
}
}
drawGrid();
isClick = false;
player.x = 0;
player.y = 0;
pathView.graphics.clear();
}
private function drawGrid():void {
imageWrapper.graphics.clear();
imageWrapper.graphics.beginFill(0);
imageWrapper.graphics.drawRect(0, 0, 1000, 1000);
imageWrapper.graphics.beginFill(0xffffff);
for (var y:String in astar.nodes) {
for (var x:String in astar.nodes[y]) {
imageWrapper.graphics.drawRect(cellSize * int(x), cellSize * int(y), cellSize, cellSize);
}
}
}
private function onGridClick(event:MouseEvent):void {
findPath(mouseX / cellSize,mouseY / cellSize,player.x / cellSize,player.y / cellSize);
}
private function findPath(startX:int,startY:int,endX:int,endY:int):void {
var time:int = getTimer();
if (astar.findPath(startX,startY,endX,endY)){
index = 0;
isClick = true;
path = astar.path;
time = getTimer() - time;
tf.text = time + "ms length:" + astar.path.length+",mem"+int(System.totalMemory/1024/1024);
pathView.graphics.clear();
for (var i:int = 0; i < astar.path.length; i++){
var p:Node = astar.path[i];
pathView.graphics.lineStyle(0, 0xff0000);
pathView.graphics.drawCircle((p.x + 0.5) * cellSize, (p.y + 0.5) * cellSize, 2);
pathView.graphics.lineStyle(0, 0xff0000, 0.5);
pathView.graphics.moveTo(player.x, player.y);
}
} else {
time = getTimer() - time;
tf.text = time + "ms, no path";
}
}
private function onEnterFrame(event:Event):void {
if (!isClick){
return;
}
var targetX:Number = path[index].x * cellSize + cellSize / 2;
var targetY:Number = path[index].y * cellSize + cellSize / 2;
var dx:Number = targetX - player.x;
var dy:Number = targetY - player.y;
var dist:Number = Math.sqrt(dx * dx + dy * dy);
if (dist < 1){
index++;
if (index >= path.length){
isClick = false;
}
} else {
player.x += dx * .5;
player.y += dy * .5;
pathView.graphics.lineTo(player.x, player.y);
}
}
}
}
class AStar {
private var open:BinaryHeap;
public var path:Array;
private var nowVersion:int = 1;
public var nodes:Object = { };
public function AStar(){
}
private function justMin(x:Object, y:Object):Boolean {
return x.f < y.f;
}
public function findPath(startX:int,startY:int,endX:int,endY:int):Boolean {
nowVersion++;
open = new BinaryHeap(justMin);
if (nodes[startY]&&nodes[startY][startX]&&nodes[endY]&&nodes[endY][endX]) {
var startNode:Node = nodes[startY][startX];
startNode.g = 0;
var endNode:Node = nodes[endY][endX];
}else {
return false;
}
var node:Node = startNode;
node.version = nowVersion;
while (node != endNode) {
for (var y:int = -1; y < 2; y++ ) {
if ((y!=0||x!=0)&&nodes[node.y+y]) {
for (var x:int = -1; x < 2; x++ ) {
if (nodes[node.y+y][node.x+x]) {
var test:Node = nodes[node.y + y][node.x + x];
if(nodes[node.y][test.x]&&nodes[test.y][node.x]){
if (x==0||y==0) {
var cost:Number = 1;
}else {
cost = Math.SQRT2;
}
var g:Number = node.g + cost;
var h:Number = manhattan(test,endNode);
var f:Number = g + h;
if (test.version == nowVersion){
if (test.f > f){
test.f = f;
test.g = g;
test.parent = node;
}
} else {
test.f = f;
test.g = g;
test.parent = node;
open.ins(test);
test.version = nowVersion;
}
}
}
}
}
}
if (open.a.length == 1){
return false;
}
node = open.pop() as Node;
}
path = [];
node = endNode;
path.push(node);
while (node != startNode){
node = node.parent;
path.push(node);
}
return true;
}
public function manhattan(node:Node,endNode:Node):Number {
return Math.abs(node.x - endNode.x) + Math.abs(node.y - endNode.y);
}
public function euclidian(node:Node,endNode:Node):Number {
var dx:Number = node.x - endNode.x;
var dy:Number = node.y - endNode.y;
return Math.sqrt(dx * dx + dy * dy);
}
public function diagonal(node:Node,endNode:Node):Number {
var dx:Number = Math.abs(node.x - endNode.x);
var dy:Number = Math.abs(node.y - endNode.y);
var diag:Number = Math.min(dx, dy);
var straight:Number = dx + dy;
return Math.SQRT2 * diag + straight - 2 * diag;
}
}
class BinaryHeap {
public var a:Array = [];
public var justMinFun:Function = function(x:Object, y:Object):Boolean {
return x < y;
};
public function BinaryHeap(justMinFun:Function = null){
a.push(-1);
if (justMinFun != null)
this.justMinFun = justMinFun;
}
public function ins(value:Object):void {
var p:int = a.length;
a[p] = value;
var pp:int = p >> 1;
while (p > 1 && justMinFun(a[p], a[pp])){
var temp:Object = a[p];
a[p] = a[pp];
a[pp] = temp;
p = pp;
pp = p >> 1;
}
}
public function pop():Object {
var min:Object = a[1];
a[1] = a[a.length - 1];
a.pop();
var p:int = 1;
var l:int = a.length;
var sp1:int = p << 1;
var sp2:int = sp1 + 1;
while (sp1 < l){
if (sp2 < l){
var minp:int = justMinFun(a[sp2], a[sp1]) ? sp2 : sp1;
} else {
minp = sp1;
}
if (justMinFun(a[minp], a[p])){
var temp:Object = a[p];
a[p] = a[minp];
a[minp] = temp;
p = minp;
sp1 = p << 1;
sp2 = sp1 + 1;
} else {
break;
}
}
return min;
}
}
class Node {
public var x:int;
public var y:int;
public var f:Number;
public var g:Number;
public var parent:Node;
public var version:int = 1;
public function Node(x:int, y:int){
this.x = x;
this.y = y;
}
}