A* pathfinder

A quick and dirt A* implementation
(only distance heuristic)

The black areas are walkable

Click to set start point,
click again to set goal

mutantleg

forked:7
favorite:26
lines:230
license : MIT License
modified : 2012-01-28 19:37:39

Embed: Tweet

package {
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.geom.Rectangle;
    import flash.display.BitmapData;
    import flash.display.Bitmap;
    import flash.display.Sprite;
    
    //a quick and dirty A* pathfinding example
    
    public class FlashTest extends Sprite {
        
        public var pic:Bitmap;
        public var screen:BitmapData;
        
  //      public var disp:Bitmap;
  //      public var dispdat:BitmapData;
        public var debpic:Bitmap;
        public var debscr:BitmapData;
        
        
        public var mwidth:int = 0;
        public var mheight:int = 0;
        public var vecMap:Vector.<pNode>;
        
        public var curFrame:int = 0;
        
    
        public var vecOpen:Vector.<pNode>;
        
        public var bFinish:Boolean = true;
        public var lastNode:pNode;
        
        public var sx:int = 0;
        public var sy:int = 0;
        
        public var gx:int = 63;
        public var gy:int = 63;
        
        public var gridx:Number = 1; //8;
        public var gridy:Number = 1; //8;
        
        public function FlashTest() {
            // write as3 code here..
        
            screen = new BitmapData(384,384, false, 0);
            pic = new Bitmap(screen);
                pic.scaleX = gridx;
                pic.scaleY = gridy;
                    addChild(pic);
   
           debscr = new BitmapData(screen.width, screen.height, true, 0);
           debpic = new Bitmap(debscr);
               debpic.scaleX = gridx;
               debpic.scaleY = gridy;
                   addChild(debpic);
                   
           // debscr.fillRect(debscr.rect, 0xFFFF0000);
   
        
            genMap(screen, 0, 512+256);
            
            loadTestMap(screen);
            
            stage.addEventListener(MouseEvent.CLICK, click);
            stage.addEventListener(Event.ENTER_FRAME, onEnter);
        }//ctor
        
        public var state:int = 0;    
        
        public function clearDebugPic():void
        {
            debscr.fillRect(debscr.rect, 0);
        }//cleardeb
        
        public function click(e:MouseEvent):void
        { 
        
        //debscr.fillRect(new Rectangle(mouseX-2,mouseY-2,5,5), 0xFFFFFFFF) ;
        
               if (!bFinish)  return;
            
            if (state <= 0)
            {
                clearDebugPic();
                
             state = 1;   
             
                 sx = mouseX / gridx;
                 sy = mouseY / gridy;
                 
                 debscr.fillRect(new Rectangle(sx-2,sy-2,5,5), 0xFF00FF00) ;
            }
            else
            {
            
                    gx = mouseX / gridx;
                    gy = mouseY / gridy;
                  debscr.fillRect(new Rectangle(gx-2,gy-2,5,5), 0xFFFFFF00) ;
                       
                startFindPath();    
            
             state = 0;
            }
        }//click
        
        public function onEnter(e:Event):void
        {
           // nodeDat.lock();
           debscr.lock();
                //findPath(256);
                findPath(1024);
           // nodeDat.unlock();
           debscr.unlock();
           
        }//onenter
        
        
        
        //generate a more or less random image suitable for this
        public function genMap(bm:BitmapData, c:uint = 0, num:int = 256):void
        {
            if (bm == null) {return;}
            
            bm.noise(4231, 0, 255, 7, true);
            
            var rt:Rectangle = new Rectangle();
            var i:int;
            
            for (i = 0; i < num; i++)
            {
               rt.x = Math.random() * bm.width;
               rt.y = Math.random() * bm.height;
               rt.width = Math.random() * 32;
               rt.height = Math.random() * 32;
               
               bm.fillRect(rt, c); 
            }//nexti
            
        }//genmap
        
        //generate nodes based on image
        public function loadTestMap(bm:BitmapData):void
        {
            if (bm == null) {return;}
            
            var i:int;
            var k:int;
            var j:int;
            var n:pNode;
            //var col:uint;
            
            mwidth = bm.width;
            mheight = bm.height;
            
            vecMap = new Vector.<pNode>(mwidth * mheight, true);
            
            i = 0;
            
            for (j = 0; j < mheight; j++)
            {
                
                for (k = 0; k < mwidth; k++)
                {
                    n = new pNode();
                        n.tx = k;
                        n.ty = j;
 
                    //open space is black (0x00000000)
                    //everything else is wall
                        if (bm.getPixel(k, j) != 0) 
                        {
                            n.bWall = true;
                            //debscr.setPixel32(k,j, 0xFFFF0000);
                         }//endif
                    
                    vecMap[i] = n;
                    i += 1;
                    
                }//nextk
            }//nextj        
            
        }//loadtestmap
        
        
        //highly unoptimised method
        //get node with lowest cost
        public function getLowest():pNode
        {
            var i:int;
            var num:int;
            var mdist:Number = 999999;
            var n:pNode;
            var m:pNode = null;
            var k:int = 0;
            
            num = vecOpen.length;
            
            for (i = 0; i < num; i++)
            {
                n = vecOpen[i];
                if (n.dist < mdist)
                {
                 m = n;
                 k = i;
                 mdist = n.dist;
                }//endif
            }//nexti
            
            //important -- delete the picked one
            if (m != null)
            {
                vecOpen[k] = vecOpen[num - 1];
                vecOpen.pop();
                
                //nodeDat.setPixel32(m.tx, m.ty, 0xFF3F0000);
            }//endif
            
            return m;
        }//getlowest
        
        
        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;
            
            var n:pNode;
            n = vecMap[tx_ + (ty_ * mwidth)];
        
            return n.bWall;
        }//iswall
        
        public function addOpen(tx_:int, ty_:int, p:pNode):void
        {
            if (tx_ < 0) return;
            if (ty_ < 0) return;
            if (tx_ >= mwidth) return;
            if (ty_ >= mheight) return;
            
            var n:pNode;
            
                n = vecMap[tx_ + (ty_ * mwidth)];
                
            if (n.bWall) return;
            if (n.frame == curFrame) return;
                n.frame = curFrame;
            
            n.parent = p;
            n.dist = Math.sqrt( (gx - n.tx)*(gx - n.tx) + (gy - n.ty)*(gy - n.ty) );
            
               // nodeDat.setPixel32(tx_, ty_, 0xFF00A0FF);
               debscr.setPixel32(tx_, ty_, 0xFF00A033);
            
            vecOpen.push(n);
        }//addopen
        
        
        public function resetOpen():void
        {
            vecOpen = new Vector.<pNode>;
        }//resetopen
        
        
        public function pathFinished():void
        {
            if (lastNode == null) return;
        
            var n:pNode;
            n = lastNode;
            
            while (n != null)
            {
                //nodeDat.setPixel32(n.tx, n.ty, 0xFF00F122);
                debscr.setPixel32(n.tx, n.ty, 0xFFFFF122);
                n = n.parent;
            }//wend
            
        }//pathfinish
        
        
        public function findPath(numstep:int=256):void
        {
            if (bFinish) return;
            
           // trace("findpath ");
            
            var i:int;
            var n:pNode;
            
            for (i = 0; i < numstep; i++)
            {
                n = getLowest(); //get node with lowest cost
                
                
                if (n == null) { bFinish = true; trace("enda");  return; } //no more options
                if (n.tx == gx && n.ty == gy) { bFinish = true; lastNode = n; pathFinished(); trace("endb"); return; } //found path
                if (n.bWall) { bFinish = true; trace("endc");  return; }
                
                addOpen(n.tx - 1, n.ty, n);
                addOpen(n.tx + 1, n.ty, n);
                addOpen(n.tx , n.ty - 1, n);
                addOpen(n.tx , n.ty + 1, n);
                
                
            }//nexti
        }//findpath
        
        
        public function startFindPath():void
        {
           
            //clearDebugPic();
            
            //note -- order is important
            resetOpen();
                curFrame += 1;
                
                //todo -- (not really important)
                //if we happen to go over 0xFFffFFff reset frames for all nodes (wont happen anytime soon)
                
                    addOpen(sx, sy, null);
                    
            
            bFinish = false;
            //nodeDat.fillRect(nodeDat.rect, 0); //clear canvas
            //nodeDat.setPixel32(sx, sy, 0xFF00F02F);

//update -- 2012-01-28
            //what do ya know, i actually forgot to finish this quick optimisation  part 
            //(so now it is finsihed)
                      
               //quick optimisiation
               //do a (built in) flood fill test
               //to see if we can reach the point at all
               //(only important if you work with flash) 
                    var bound:Rectangle;
                    var testbm:BitmapData = new BitmapData(mwidth, mheight, false, 0);
                    testbm.draw(screen);
                    testbm.floodFill(sx, sy, 0xFFFF0000);
                 
                    
                if (testbm.getPixel32(gx, gy) != 0xFFFF0000) 
                { 
                    debscr.draw(testbm);
                    bFinish = true; 
                    return;
                }///endif
            
            if (isWall(gx, gy)) { bFinish = true; return; } //dont go into walls
            
            //nodeDat.fillRect(nodeDat.rect, 0xFFaaFFaa);
        }//findp
        
        
        
    }//flashtest
}//package

internal class pNode
{
        public var tx:int = 0;
        public var ty:int = 0;
        
        public var dist:Number = 0;
        public var frame:int = -1;
        
        public var bWall:Boolean = false;
        
        public var parent:pNode;
        
    //    public var cost:Number = 0;
        
        public function pNode() 
        {
            
        }//ctor
    
    
}//pNode

Code Fullscreen

Preview Fullscreen