/**
* Copyright Albert ( http://wonderfl.net/user/Albert )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/zoNS
*/
// forked from mutantleg's Pathfinder2: Path Harder
package {
import flash.display.Graphics;
import flash.events.Event;
import flash.geom.Rectangle;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Sprite;
import flash.geom.ColorTransform;
public class FlashTest extends Sprite {
private var wi: int = 460;
private var he: int = 460;
private var colortrans: ColorTransform = new ColorTransform(1.0, 1.0, 0.999, 0.999);
public function FlashTest() {
//using a map of 256x256 because that is the maximum size
//for starcraft2, warcraft3 etc.
map = new BitmapData(wi, he,false,0x808080);
footsteps = new BitmapData(wi, he, true, 0x0);
var i:int;
var rect:Rectangle;
rect = new Rectangle();
for (i = 0; i < 320; i++)
{
rect.x = Math.random()*wi;
rect.y = Math.random()*he;
if (Math.random() < 0.5)
{
rect.width = 3 + Math.random()*16;
rect.height = 1 + Math.random()*150;
}
else
{
rect.width = 1 + Math.random()*150;
rect.height = 3 + Math.random()*16;
}//endif
map.fillRect(rect, 0);
}//nexti
pic = new Bitmap(map);
addChild(pic);
addChild(new Bitmap(footsteps));
mwidth = map.width;
mheight = map.height;
vecGrid = getGrid(map);
pfind = new xPathFind();
pfind.buildZone(vecGrid, mwidth, mheight, 1,1);
addChild(pfind.debLayer);
pfind.debLayer.alpha = 0.1;
var a:xActor;
var k:int;
vecAct = new Vector.<xActor>(0, false);
for (i = 0; i < 512; i++)
{
a = new xActor();
for (k = 0; k < 64; k++)
{
a.cx = Math.random() * wi;
a.cy = Math.random() * he;
if (isWall(a.cx,a.cy) == false) { k=65; }
}//nextk
vecAct.push(a);
}//nexti
layerAct = new Sprite();
addChild(layerAct);
stage.addEventListener(Event.ENTER_FRAME, onEnter);
}//ctor
public var layerAct:Sprite;
public var map:BitmapData;
public var footsteps:BitmapData;
public var pic:Bitmap;
public var vecGrid:Vector.<int> = null;
public var mwidth:int = 0;
public var mheight:int = 0;
public var pfind:xPathFind;
public var vecAct:Vector.<xActor>;
public function onEnter(e:Event):void
{
var a:xActor;
var num:int;
var i:int;
var g:Graphics;
var p:xPoint;
var vx:Number;
var vy:Number;
var dx:Number;
var dy:Number;
var jx:Number;
var jy:Number;
var ang:Number;
var k:int;
g = layerAct.graphics;
g.clear();
// g.lineStyle(1,0xFF0000);
num = vecAct.length;
footsteps.lock();
for (i = 0; i < num; i++)
{
a = vecAct[i];
g.beginFill(a.move <= 0? 0x00FF00 : 0xFF0000 * i / num, 1);
// g.beginFill(0xFF0000,1);
g.drawCircle(a.cx,a.cy,2);
g.endFill();
var color:uint = footsteps.getPixel32(a.cx, a.cy);
var alpha:uint = color >> 24;
alpha = 0xff - (0xff-alpha)*5/7;
color = (alpha << 24) | 0x900000;
footsteps.setPixel32(a.cx, a.cy, color);
//find random point to go to
if (a.move <= 0)
{
// a.cx += 1;
a.wait += 1 + Math.random()*7;
}
if (a.wait >= 30)
{
a.wait = 0;
if (stage.mouseX > 10 && stage.mouseX < wi-10 &&
stage.mouseY > 10 && stage.mouseY < he-10)
{
a.gx = stage.mouseX;
a.gy = stage.mouseY;
}
else
{
for (k = 0; k < 64; k++)
{
a.gx = Math.random() * wi;
a.gy = Math.random() * he;
if (isWall(a.gx, a.gy)==false) { k=65; }
}//nextk
}
if (isWall(a.gx, a.gy)) { continue; }
var err:int;
err = pfind.startPath(a.cx, a.cy, a.gx, a.gy);
if (err != 1) { continue; }
//something went wrong
//e.g. we want to move in the same zone, zone is unreachable etc.
//i'm not handling them for now because i cant be arsed
while (pfind.bFinish == false) { pfind.findPath(256); }
a.vecPath = pfind.getPath();
a.cur = 0;
a.move = 1;
}//endif
//follow path
if (a.move > 0)
{
if (a.cur >= a.vecPath.length) { a.move = 0; continue;}
jx = a.vecPath[a.cur].cx;
jy = a.vecPath[a.cur].cy;
dx = jx - a.cx;
dy = jy - a.cy;
ang = Math.atan2(dy, dx);
vx = Math.cos(ang) * 1.0;
vy = Math.sin(ang) * 1.0;
//note -- no wall checking for now
a.cx += vx;
a.cy += vy;
if (Math.abs(dx) <= 2 && Math.abs(dy) <= 2)
{
a.cur += 1;
//note -- no string pulling for now
}//endif2
//draw path (debug)
/*
g.lineStyle(1,0xFF0000);
var vxp:xPoint;
var vi:int;
var vn:int;
var vp:Vector.<xPoint>;
vp = a.vecPath;
if (vp == null) { continue; }
vn = vp.length;
for (vi = 0; vi < vn; vi++)
{
vxp = vp[vi];
// g.drawCircle(vxp.cx, vxp.cy, 4);
}
for (vi = 0; vi < vn; vi++)
{
vxp = vp[vi];
//g.drawCircle(vxp.cx, vxp.cy, 4);
if (vi == 0) { g.moveTo(vxp.cx, vxp.cy); }
else {
g.lineTo(vxp.cx, vxp.cy); }
}//nextvi
*/
}//endif
}//nexti
footsteps.unlock();
footsteps.colorTransform(map.rect, colortrans);
}//onenter
public function isWall(tx:int, ty:int):Boolean
{
if (tx < 0) { return true; }
if (ty < 0) { return true; }
if (tx >= mwidth) { return true; }
if (ty >= mheight) { return true; }
return vecGrid[(ty * mwidth) + tx] <= 0;
}//iswall
public function getGrid(m:BitmapData):Vector.<int>
{
var vec:Vector.<int>;
var mw:int;
var mh:int;
var i:int;
var k:int;
var num:int;
var yt:int;
mw = m.width;
mh = m.height;
num = mwidth * mheight;
vec = new Vector.<int>(num, false);
for (i = 0; i < mh; i++)
{
yt = i * mw;
for (k = 0; k < mw; k++)
{
vec[yt+k] = m.getPixel(k, i) <= 0 ? 1 : 0;
}//nextk
}//nexti
return vec;
}//getgrid
}//classend
}
import flash.display.Sprite;
internal class xActor
{
public var cx:Number = 0;
public var cy:Number = 0;
public var gx:Number = 0;
public var gy:Number = 0;
public var cur:int = 0;
public var vecPath:Vector.<xPoint> = null;
public var move:int = 0;
public var wait:int = 0;
}//xactor
internal class xPoint
{
public var cx:Number = 0;
public var cy:Number = 0;
public function xPoint(x:Number=0, y:Number=0)
{
cx = x;
cy = y;
}//ctor
}//xpoint
internal class xZone
{
public var cx:Number = 0;
public var cy:Number = 0;
public var cw:Number = 0;
public var ch:Number = 0;
public var mx:Number = 0; //center
public var my:Number = 0;
public var group:int = 0;
public var col:uint = 0; //color (debug)
public var cost:Number = 0;
public var frame:int = 0; //if same as curframe we already checked this one (eliminating the closed array)
public var parent:xZone = null; //used for building final path
public var vecNext:Vector.<xZone> = new Vector.<xZone>(0,false); //neighboring zones
}//xzone
internal class xPathFind
{
public var vecZone:Vector.<xZone> = new Vector.<xZone>;
public var maxOpen:int;
public var vecOpen:Vector.<xZone> = new Vector.<xZone>(8192, false);
public var curFrame:int = 0;
public var it:int = 0;
public var startx:Number = 0;
public var starty:Number = 0;
public var endx:Number = 0;
public var endy:Number = 0;
public var start:xZone;
public var goal:xZone;
public var lastZone:xZone;
public var bFinish:Boolean = true;
public var debLayer:Sprite = new Sprite();
public function startPath(sx:Number, sy:Number, ex:Number, ey:Number):int
{
var a:xZone;
var b:xZone;
a = getZone(sx, sy);
b = getZone(ex, ey);
bFinish = true;
if (a == null) { return -1; } //no start
if (b == null) { return -2; } //no goal
if (a == b) { return 0; } //same zone
if (a.group != b.group) { return -99; } //unreachable //(maybe it should be the same for no goal?)
startx = sx;
starty = sy;
endx = ex;
endy = ey;
startPath2(a, b);
return 1;
}//startpath
//so far this might be the slowest one (goes through all zones)
public function getZone(wx:Number, wy:Number):xZone
{
var i:int;
var num:int;
var a:xZone;
num = vecZone.length;
for (i = 0; i < num; i++)
{
a = vecZone[i];
if (wx < a.cx) { continue;}
if (wy < a.cy) { continue; }
if (wx > a.cx+a.cw) { continue; }
if (wy > a.cy+a.ch) { continue; }
return a;
}//nexti
return null;
}//getzone
public function startPath2(startzone:xZone, goalzone:xZone):void
{
bFinish = false;
lastZone = null;
start = startzone;
goal = goalzone;
curFrame += 1;
vecOpen[0] = start;
it = 1;
start.frame = curFrame;
start.parent = null;
start.cost = 0; //set first zone cost to 0
}//startpath2
public function findPath(numstep:int=256):void
{
if (bFinish) return;
var i:int;
var a:xZone;
var k:int;
var vec:Vector.<xZone>;
var b:xZone;
var num:int;
var nk:int;
var mcost:Number;
//no function calls, no worry about overflowing the stack
for (i = 0; i < numstep; i++)
{
if (it <= 0)
{
bFinish = true;
lastZone = null;
return;
} //endif
//todo -- check vecopen size
//get node with lowest cost
mcost = 9999999;
a = vecOpen[0];
for (k = 0; k < it; k++)
{
b = vecOpen[k];
if (b.cost < mcost)
{
mcost = b.cost;
a = b;
nk = k;
}
}//nextk
//take out the node from the open
vecOpen[nk] = vecOpen[it - 1];
it -= 1;
//check if goal is reached
if (a == goal)
{
lastZone = a;
bFinish = true;
return;
}//endif
//add neighbours of node to open
vec = a.vecNext;
num = vec.length;
for (k = 0; k < num; k++)
{
b = vec[k];
if (b.frame == curFrame) { continue; }
b.frame = curFrame;
//todo -- since rectangles are used for zones
//just getting the center for calculating the distance
//is fast but not accurate
if (a == start)
{
b.cost = mcost + Math.sqrt((startx - b.mx) * (startx - b.mx) + (starty - b.my) * (starty - b.my));
}
else
{
b.cost = mcost + Math.sqrt((a.mx - b.mx) * (a.mx - b.mx) + (a.my - b.my) * (a.my - b.my));
}//endif
b.parent = a;
vecOpen[it] = b;
it += 1;
}//nextk
}//nexti
}//findpath
//usage:
//buildzone -- use it to refresh the zone data for path finding
//startpath -- then use findpath until bFinished
//then claim your finished path
//note: string pulling is not performed in this one
//its expected to be done in realtime
public function getPath():Vector.<xPoint>
{
var a:xZone;
var b:xZone;
var vec:Vector.<xPoint>;
vec = new Vector.<xPoint>(0, false);
a = lastZone;
if (a == null) { return null; }
var prevx:Number;
var prevy:Number;
var kx:Number;
var ky:Number;
var ry:Number;
var sy:Number;
prevx = -1;
prevy = -1;
kx = a.mx;
ky = a.my;
vec.push(new xPoint(endx, endy) );
while (a != null)
{
b = a;
a = a.parent;
if (a == null) { break; }
if (a.cx + a.cw-0.1 < b.cx)
{
kx = a.cx + a.cw;
ry = a.cy > b.cy ? a.cy : b.cy;
sy = a.cy + a.ch < b.cy + b.ch ? a.cy + a.ch : b.cy + b.ch;
ky = (ry + sy) * 0.5;
//correction -- visit the center if both portals are on the same side
//todo -- sometimes it doest it, sometimes it dont (???)
//maybe we need a.mx in some(?)
if (prevx == kx) { vec.push(new xPoint(b.mx, b.my)); }
vec.push(new xPoint(kx, ky) );
}
else if (b.cx + b.cw-0.1 < a.cx)
{
kx = b.cx + b.cw;
ry = a.cy > b.cy ? a.cy : b.cy;
sy = a.cy + a.ch < b.cy + b.ch ? a.cy + a.ch : b.cy + b.ch;
ky = (ry + sy) * 0.5;
if (prevx == kx) { vec.push(new xPoint(b.mx, b.my)); }
vec.push(new xPoint(kx, ky) );
}
else if (a.cy + a.ch-0.1 < b.cy)
{
ky = a.cy + a.ch;
ry = a.cx > b.cx ? a.cx : b.cx;
sy = a.cx + a.cw < b.cx + b.cw ? a.cx + a.cw : b.cx + b.cw;
if (prevy == ky) { vec.push(new xPoint(b.mx, b.my)); }
kx = (ry + sy) * 0.5;
vec.push(new xPoint(kx, ky) );
}
else //b.cy+b.ch < a.cy
{
ky = b.cy + b.ch;
ry = a.cx > b.cx ? a.cx : b.cx;
sy = a.cx + a.cw < b.cx + b.cw ? a.cx + a.cw : b.cx + b.cw;
if (prevy == ky) { vec.push(new xPoint(b.mx, b.my)); }
kx = (ry + sy) * 0.5;
vec.push(new xPoint(kx, ky) );
}
prevx = kx;
prevy = ky;
}//wend
vec.push(new xPoint(startx, starty) );
return vec.reverse();
}//drawpath
//so the maximum size of a zone is 16x16
//so an open map will have at least 256 zones
//ok so for the vecgrid -- 0 wall bigger than 0 walkable
//need to convert your grid according to that first
public function buildZone(vecGrid:Vector.<int>, mw:int, mh:int, cellw:Number=1.0, cellh:Number=1.0):void
{
var a:xZone;
var i:int;
var k:int;
var yt:int;
var t:int;
var vec:Vector.<int>;
debLayer.graphics.clear();
debLayer.graphics.lineStyle(1, 0xFF, 0.5);
vec = copyVec(vecGrid);
vecZone = new Vector.<xZone>(0, false);
var n:int;
var h:int;
var m:int;
for (i = 0; i < mh; i++)
{
yt = i * mw;
for (k = 0; k < mw; k++)
{
t = vec[yt+k];
if (t <= 0) { continue; }
n = getClosex(vec, mw, k, i);
// var wn:int;
// wn = n - k;
//limit size
if ((n - k) > 16) { n = k + 16; }
for (h = i; h < mh; h++)
{
m = getClosex(vec, mw, k, h);
if (m < n) { break; }
//limit size
if ((h - i) > 16) { break; }
}//nexth
a = new xZone();
a.cx = k; a.cw = n - k;
a.cy = i; a.ch = h - i;
a.group = 0; a.col = 0xff;
vecZone.push(a);
setRect(vec, mw, mh, a.cx,a.cy,a.cw,a.ch, 0);
vec[yt+k] = 1;
//convert to cell size
a.cx *= cellw; a.cy *= cellh;
a.cw *= cellw; a.ch *= cellh;
a.mx = a.cx + (a.cw * 0.5);
a.my = a.cy + (a.ch * 0.5);
k = n;
debLayer.graphics.drawRect(a.cx,a.cy,a.cw,a.ch);
}//nextk
}//nexti
//build connections
var num:int;
var b:xZone;
num = vecZone.length;
for (i = 0; i < num; i++)
{
a = vecZone[i];
for (k = 0; k < num; k++)
{
if (i == k) { continue; }
b = vecZone[k];
if (a.cx + a.cw < b.cx) { continue; }
if (a.cy + a.ch < b.cy) { continue; }
if (b.cx + b.cw < a.cx) { continue; }
if (b.cy + b.ch < a.cy) { continue; }
//new -- corner fix
if ((a.cx + a.cw) == b.cx && (a.cy+a.ch) == b.cy) { continue; }
if ((b.cx + b.cw) == a.cx && (b.cy+b.ch) == a.cy) { continue; }
if ((a.cx + a.cw) == b.cx && (b.cy+b.ch) == a.cy) { continue; }
if ((b.cx + b.cw) == a.cx && (a.cy+a.ch) == b.cy) { continue; }
a.vecNext.push(b);
}//nextk
}//nexti
genGroup();
}//buildzone
public function genGroup():void
{
var temp:Vector.<xZone>;
var ti:int;
var vec:Vector.<xZone>;
var numk:int;
var num:int;
var i:int;
var k:int;
var a:xZone;
var b:xZone;
var group:int;
var debcol:uint;
group = 1; //dont start at 0 or its infinite loop
num = vecZone.length;
temp = new Vector.<xZone>(num, false);
for (i = 0; i < num; i++)
{
a = vecZone[i];
if (a.group != 0) { continue; }
debcol = 0x888888 + (Math.random()*0x777777);
group += 1;
ti = 0;
temp[0] = a;
ti = 1;
while (ti > 0)
{
a = temp[ti - 1];
ti -= 1;
if (a.group != 0) { continue;}
a.group = group;
a.col = debcol;
vec = a.vecNext;
numk = vec.length;
for (k = 0; k < numk; k++)
{
b = vec[k];
temp[ti] = b;
ti += 1;
}//nextk
}//wend
}//nexti
}//gengroup
//compacted these small functions according to my eternal battle with readability
public function getClosex(vec:Vector.<int>, mw:int, ax:int, ay:int):int
{
var k:int; var yt:int; var t:int;
yt = ay * mw;
for (k = ax; k < mw; k++)
{ t = vec[yt + k]; if (t <= 0) { return k;} }
return mw;
}//getclose
public function copyVec(vec:Vector.<int>):Vector.<int>
{
var i:int; var num:int; var ret:Vector.<int>;
num = vec.length; ret = new Vector.<int>(num, false);
for (i = 0; i < num; i++) { ret[i] = vec[i]; }
return ret;
}//copyvec
public function setRect(vec:Vector.<int>,mw:int,mh:int, ax:int, ay:int, aw:int, ah:int, c:int):void
{
var ex:int; var ey:int; var i:int; var k:int; var yt:int;
ex = ax + aw; ey = ay + ah;
if (ax < 0) { ax = 0; } if (ay < 0) { ay = 0; }
if (ex > mw) { ex = mw; } if (ey > mh) { ey = mh; }
if (ax >= mw) { return; } if (ay >= mh){ return; }
if (ex < 0) { return; } if (ey < 0) { return; }
for (i = ay; i < ey; i++) { yt = i * mw; for (k = ax; k < ex; k++) { vec[yt+k] = c; } }
}//setrect
}//classend