In case Flash no longer exists; a copy of this site is included in the Flashpoint archive's "ultimate" collection.

Dead Code Preservation :: Archived AS3 works from wonderfl.net

Pathfinder2: Path Harder

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
Get Adobe Flash player
by mutantleg 20 Jun 2013
/**
 * 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