Followup to: http://wonderfl.net/c/wWgD
Based on the http://wonderfl.net/c/4NOz
experiment
Now the tilemap is converted into zones
Making pathfinding really fast
So the actors are choosing random points to find path to, and there is many of them to demonstrate the improved speed
/**
* Copyright mutantleg ( http://wonderfl.net/user/mutantleg )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/6H7p
*/
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;
public class FlashTest extends Sprite {
public function FlashTest() {
//using a map of 256x256 because that is the maximum size
//for starcraft2, warcraft3 etc.
map = new BitmapData(256,256,false,0x808080);
var i:int;
var rect:Rectangle;
rect = new Rectangle();
for (i = 0; i < 220; i++)
{
rect.x = Math.random()*256;
rect.y = Math.random()*256;
if (Math.random() < 0.5)
{
rect.width = 2+ Math.random()*16;
rect.height = 1+Math.random()*92;
}
else
{
rect.width = 1+Math.random()*92;
rect.height = 2+ Math.random()*16;
}//endif
map.fillRect(rect, 0);
}//nexti
pic = new Bitmap(map);
addChild(pic);
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() * 256;
a.cy = Math.random() * 256;
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 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;
for (i = 0; i < num; i++)
{
a = vecAct[i];
g.beginFill(a.move <= 0? 0x00FF00 : 0xFF0000,1);
// g.beginFill(0xFF0000,1);
g.drawRect(a.cx-1,a.cy-1,3,3);
g.endFill();
//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;
for (k = 0; k < 64; k++)
{
a.gx = Math.random() * 256;
a.gy = Math.random() * 256;
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
}//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