Fast path finding
/**
* Copyright Rzer ( http://wonderfl.net/user/Rzer )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/8apM
*/
package {
import flash.filters.DropShadowFilter;
import flash.text.TextFormat;
import flash.text.TextField;
import flash.utils.ByteArray;
import flash.geom.Point;
import flash.filters.ColorMatrixFilter;
import flash.display.*;
import flash.utils.getTimer;
[SWF(backgroundColor=0,frameRate=31)]
public class FlashTest extends Sprite {
private var info:TextField = new TextField();
private var start:CheckPoint = new CheckPoint("start",0x00ff00);
private var end:CheckPoint = new CheckPoint("finish",0xff0000);
private var bitmap:Bitmap;
private var aTime:int;
private var BT:Bitmap;
private var BA:ByteArray;
private var BD:BitmapData;
private var anEnd:int;
private var aStart:int;
private var allCount:int;
private var aPosition:int;
private var aColor:int;
private var aWave:Array;
private var aFront:Array;
private var aPoint:Point;
private var aResult:Boolean;
private var aWay:Array;
public function FlashTest() {
graphics.beginFill(0x000,1);
graphics.drawRect(0,0,stage.stageWidth,stage.stageHeight);
graphics.endFill();
generateMap();
start.x = 50; start.y = 60;
addChild(start);
end.x = 15; end.y = 415;
addChild(end);
info.width = 300;
info.x = 280;info.y = 20;
info.multiline = true;
info.wordWrap = true;
info.defaultTextFormat = new TextFormat("Arial",11,0xffff00,true);
info.filters =[new DropShadowFilter(0,45,1,10,10)];
info.text = "Start 4 directional path find \n";
addChild(info);
startFind();
}
private function generateMap():void{
var bd:BitmapData = new BitmapData(stage.stageWidth,stage.stageHeight,false,0x000);
bitmap = new Bitmap(bd);
addChild(bitmap);
var seed:int = 111;
bd.perlinNoise(45, 45, 3, seed, true, true, 7, true);
//To Black and White
var bw2_matrix:Array = [ 3.5,6.5,1,0,-1100, 3.5,6.5,1,0,-1100, 3.5,6.5,1,0,-1100, 0, 0, 0, 1, 0 ];
var myFilter:ColorMatrixFilter = new ColorMatrixFilter(bw2_matrix);
bd.applyFilter(bd,bd.rect,new Point(),myFilter);
for (var i:int = 0; i<bd.width;i++){
bd.setPixel(i,bd.height-1,0x000);
bd.setPixel(i,1,0x000);
}
for (var j:int = 0; j<bd.height;j++){
bd.setPixel(bd.width-1,j,0x000);
bd.setPixel(1,j,0x000);
}
}
public function startFind():void{
aTime = getTimer();
captureBytes();
info.appendText("read map passable: " + (getTimer() - aTime) + "ms \n");
aStart = (start.x + start.y * 1000) * 2;
anEnd = (end.x + end.y * 1000) * 2;
info.appendText("only one time!\n");
aResult = false;
aColor = 0x000000;
aFront = [aStart];
aTime = getTimer();
findPath();
if (aResult)
{
aWay = [anEnd];
recoverPath();
info.appendText("answer find in " + (getTimer() - aTime) + "ms. Nodes: " + aWay.length + "\n");
}
bitmap.bitmapData = BD;
}
private function captureBytes():void {
var aPixel:uint;
BD = new BitmapData(1000, 1000, false);
BD.draw(bitmap.bitmapData);
BA = new ByteArray();
BA.length = 1000 * 1000 * 2;
for (var i:int = 0; i < 1000; i++)
{
for (var j:int = 0; j < 1000; j++)
{
aPixel = BD.getPixel(i, j);
if (aPixel > 0xCCCCCC) aPixel = 0xffffff;
BA.position = (j * 1000 + i) * 2;
BA.writeShort(aPixel);
}
}
}
private function findPath():void {
allCount = 0;
try
{
do
{
var anIndex:int;
aColor++;
aWave = aFront;
aFront = new Array();
for (var i:int = 0; i < aWave.length; i++)
{
anIndex = aWave[i];
BA.position = anIndex + 2;
if (BA.readUnsignedShort() == 0xFFFF)
{
BA.position = anIndex + 2;
BA.writeShort(aColor);
if (anIndex + 2 == anEnd)
{
throw(new Error("!"));
}
else
{
allCount++;
aFront[aFront.length] = anIndex + 2;
}
}
BA.position = anIndex - 2;
if (BA.readUnsignedShort() == 0xFFFF)
{
BA.position = anIndex - 2;
BA.writeShort(aColor);
if (anIndex - 2 == anEnd)
{
throw(new Error("!"));
}
else
{
allCount++;
aFront[aFront.length] = anIndex - 2;
}
}
BA.position = anIndex + 1000 * 2;
if (BA.readUnsignedShort() == 0xFFFF)
{
BA.position = anIndex + 1000 * 2;
BA.writeShort(aColor);
if (anIndex + 1000 * 2 == anEnd)
{
throw(new Error("!"));
}
else
{
allCount++;
aFront[aFront.length] = anIndex + 1000 * 2;
}
}
BA.position = anIndex - 1000 * 2;
if (BA.readUnsignedShort() == 0xFFFF)
{
BA.position = anIndex - 1000 * 2;
BA.writeShort(aColor);
if (anIndex - 1000 * 2 == anEnd)
{
throw(new Error("!"));
}
else
{
allCount++;
aFront[aFront.length] = anIndex - 1000 * 2;
}
}
}
}
while (aFront.length > 0);
}
catch (error:Error)
{
aResult = true;
}
}
private function recoverPath():void {
var anIndex:int;
anIndex = anEnd;
do
{
BD.setPixel((anIndex / 2) % 1000, int(anIndex / 2 / 1000), 0x00FF00);
aColor--;
BA.position = anIndex - 2;
if (aColor == BA.readUnsignedShort())
{
anIndex = anIndex - 2;
aWay.push(anIndex);
continue;
}
BA.position = anIndex + 2;
if (aColor == BA.readUnsignedShort())
{
anIndex = anIndex + 2;
aWay.push(anIndex);
continue;
}
BA.position = anIndex - 1000 * 2;
if (aColor == BA.readUnsignedShort())
{
anIndex = anIndex - 1000 * 2;
aWay.push(anIndex);
continue;
}
BA.position = anIndex + 1000 * 2;
if (aColor == BA.readUnsignedShort())
{
anIndex = anIndex + 1000 * 2;
aWay.push(anIndex);
continue;
}
}
while (aColor > 1);
aWay.push(aStart);
}
private function markPoint(index:int, color:int):void {
BA.position = index;
if (BA.readUnsignedShort() == 0xFFFF)
{
BA.position = index;
BA.writeShort(color);
if (index == anEnd)
{
throw(new Error("!"));
}
else
{
aFront[aFront.length] = index;
}
}
}
}
}
import flash.text.TextFormat;
import flash.display.Graphics;
import flash.text.TextField;
import flash.display.Sprite;
internal class CheckPoint extends Sprite{
private var tf:TextField
public function CheckPoint(text:String, color:uint):void{
var canvas:Graphics = this.graphics;
canvas.beginFill(color);
canvas.drawCircle(0,0,2);
canvas.endFill();
tf = new TextField();
addChild(tf);
tf.defaultTextFormat = new TextFormat("Arial",10,color,true);
tf.text = text;
}
}