Pathfinding issue

I'm having some issues with pathfinding, it works on simple paths, but more complex things become messed up.

Click a tile to find the path to the selected tile. Hold and move mouse to create unwalkable tiles.

Creating a "cage" with just 1 opening is a good example where it foes wrong.

omgnoseat

forked:1
favorite:3
lines:628
license : MIT License
modified : 2011-07-22 07:02:50

Embed: Tweet

package {
    import flash.display.Sprite;
    import flash.events.MouseEvent;
    import caurina.transitions.Tweener;
   
    
    [SWF(width = "465", height = "465", frameRate = "60",backgroundColor="0x222222")]
    public class FlashTest extends Sprite {
        
       private var grid:TileGrid;
       private var mode:String = Mode.EDIT_GRID;
       private var mouseDown:Boolean;
       private var currentTile:Tile;
       
       private var beginPoint:Tile;
       private var endPoint:Tile;
       private var object:Sprite;
       
       private var walkingPath:Boolean = false;
       private var currentPath:Array;
       private var currentPathTile:int = 0;
        
        public function FlashTest() {
            
            WTrace.initTrace(stage);
            
            //init grid
            grid = new TileGrid(1, 15, 15, 32, 32);
            addChild(grid);
            
            grid.initEmptyGrid(1, 20, 20);     
            
            grid.addEventListener(MouseEvent.MOUSE_DOWN, MouseDown);
            grid.addEventListener(MouseEvent.MOUSE_UP, mouseUp);
            grid.addEventListener(MouseEvent.MOUSE_MOVE, mouseMove);
            grid.addEventListener(MouseEvent.CLICK, selectTile);
            
           //object
           object = new Sprite();
           object.graphics.lineStyle(2, 0x000000);
           object.graphics.beginFill(0xFF0000);
           object.graphics.drawRect(0, 0, 32, 32);
           object.graphics.endFill();
           addChild(object);
           
           Pathfinder.addEventListener(PathfinderEvent.PATHFOUND, pathFound);
        }
        
        private function MouseDown(e:MouseEvent):void{
            
            mouseDown = true;
        }

private function mouseUp(e:MouseEvent):void{
            
            mouseDown = false;
        }

private function mouseMove(e:MouseEvent):void{
            
            if(mouseDown){
                
                var tile:Tile = grid.tiles[0][GameMath.PointToTileY(mouseY)][GameMath.PointToTileX(mouseX)]
                
                if(currentTile != tile){
            
                    switch(mode){
                    
                        case Mode.EDIT_GRID:
                            tile.toggleWalkable();
                        break;
                    
                    }
                }
                
            currentTile = tile;
            }

}

private function selectTile(e:MouseEvent):void{
            
            var tile:Tile = grid.tiles[0][GameMath.PointToTileY(mouseY)][GameMath.PointToTileX(mouseX)]
            
            
            Pathfinder.getPath(grid.tiles, GameMath.PointToTileX(object.x), GameMath.PointToTileX(object.y), 
            tile.xID, tile.yID);
        }
        
        private function pathFound(e:PathfinderEvent):void{
            
            
            if(!walkingPath){
                walkingPath = true;
                currentPath = e.path;
                currentPathTile = 0;
                AdvancePath();
            }
        }
            
        
        private function AdvancePath():void 
        {

if (currentPathTile == currentPath.length) {
                
                walkingPath = false;
            }else {
                
                var tileX:int = GameMath.TileToPoint(currentPath[currentPathTile].xID);
                var tileY:int = GameMath.TileToPoint(currentPath[currentPathTile].yID);

Tweener.addTween(object, { x:tileX, y:tileY, time:0.1, onComplete:AdvancePath, transition:"Linear" } );
                currentPathTile ++;
            }
        }

}
}

class Mode{
    
    public static const MOVE_PATH:String = "MOVE_PATH";
    public static const EDIT_GRID:String = "EDIT_GRID";
}

/////////////////////////////////
///// P A T H F I N D E R //////
////////////////////////////////
import flash.display.Sprite;
import flash.events.Event;
import flash.events.EventDispatcher;

class Pathfinder
    {
        public static var grid:Array;
        public static var openList:Array = [];
        public static var closedList:Array = [];
        public static var markers:Array = [];
        
        public static var startNX:int;
        public static var startNY:int;
        public static var endNX:int;
        public static var endNY:int;
        
        public static var path:Array;
        
        private static var eventDispatcher: EventDispatcher;
        
        
        //the array, startnode, endnode
        public static function getPath(_grid:Array, snX:int, snY:int, enX:int, enY:int):void{
            
            grid = _grid
            startNX = snX;
            startNY = snY;
            endNX = enX;
            endNY = enY;
            
            path = [];
            openList = [];
            closedList = [];
            clearMarkers();//just turns em invisible
            
            //mark begin and end grid [overlay]
            var beginNode:PathNode = new PathNode(32, 32, "begin");
            beginNode.xID = snX;
            beginNode.yID = snY;
            
            closedList.push(beginNode);
            //trace("add to closed list: [" + beginNode.xID + "][" + beginNode.yID + "]");
            
            //markers
            markers.push(grid[0][snY][snX].addChild(beginNode));
            markers.push(grid[0][enY][enX].addChild(new PathNode(32, 32, "end")));
    
            //place surrounding grid
            nextNode(beginNode);
        }
        
        //selects the best node out of the open nodes
        static private function findNextNode():void 
        {
            var bestNode:PathNode;
            var F:int = 99999;
            
            for (var i:int = 0; i < openList.length; i++) {
                
                if (openList[i].F < F) {
                    
                    F = openList[i].F;
                    bestNode = openList[i];
                }
            }
            
            bestNode.stroke.visible = true;
            path.push(bestNode);
            
            //drop from open, add to closed
            openList.splice(openList.indexOf(bestNode), 1);
            openList = []; //makes it work better for some reason?
            
            closedList.push(bestNode);
            
            if(!pathfound(bestNode)){
                nextNode(bestNode);
            }else {
                
               //path found
                
                dispatchEvent(new PathfinderEvent(path, PathfinderEvent.PATHFOUND));
            }
        }
        
        static public function nextNode(node:PathNode):void 
        {
            //look at next nodes
            placeNode(node, node.yID + 1, node.xID);
            placeNode(node, node.yID - 1, node.xID);
            placeNode(node, node.yID, node.xID + 1);
            placeNode(node, node.yID, node.xID - 1);
            
            //select the best node
            findNextNode();
            
        }
        
        public static function pathfound(node:PathNode):Boolean {
            
            var xTrue:Boolean = false;
            var yTrue:Boolean = false;
            
            if (node.xID == endNX) {
                xTrue = true;
            }
            
            if (node.yID == endNY) {
                yTrue = true;
            }
            
            if (xTrue && yTrue) {
                return true;
            }else {
                return false;
            }
        }
        
        
        public static function placeNode(parentnode:PathNode, y:int, x:int):void {
            
            //in map range
            if (x >= 0 && x <= grid[0][0].length && y >= 0 && y <= grid[0].length
                && !onClosedListByXYID(x, y)
            ) {
                //not out of range or on closed list

if(grid[0][y][x].walkable == true){
                        //walkable
                        
                        var node:PathNode = onOpenList(x, y);
                        
                        if (node != null) {
                            
                            //if it is already on the open list - check if it is a better option
                            if (node.G > parentnode.G + 10) {
                                
                                //recalculate
                                node.parentNode = parentnode;
                                node.G = parentnode.G + 10;
                                node.F = node.G + node.H
                            }
                        
                        }else {
                        
                            //H = number of tiles horizontal and vertical removed from end tile
                            var H:int = (Math.abs(endNX - x) + Math.abs(endNY - y)) * 10;
                            
                            node = new PathNode(32, 32, "path", parentnode.G + 10, H);
                            node.parentNode = parentnode;
                            node.xID = x;
                            node.yID = y;
                                
                            markers.push( grid[0][y][x].addChild(node) );
                            openList.push(node);
                        
                        }
                    
                }else {
                    
                    //trace("tile not walkable");
                }
                
            }else{
                
                //trace("node out of map range or on closed list");
            }
        }
        
        
        ////// S E A R C H  C L O S E D L I S T ///////
        ///////////////////////////////////////////////
        
        public static function onClosedList(xid:int, yid:int):PathNode {
            
            for (var i:int = 0; i < closedList.length; ++i) {
                
                if (closedList[i].xID == xid && closedList[i].yID == yid) {
                    
                    //trace("------------true --------------");
                    return closedList[i];
                    end;
                }
            }
            //trace("-----------false ---------------");
            return null;
        }
        
        public static function onClosedListByXYID(xid:int, yid:int):Boolean{
            
            for (var i:int = 0; i < closedList.length; ++i) {
                
                if (closedList[i].xID == xid && closedList[i].yID == yid) {
                    
                    return true;
                    end;
                }
            }

return false;
        }
        
        
        ////// S E A R C H  O P E N L I S T ///////
        ///////////////////////////////////////////
        
        public static function onOpenList(xid:int, yid:int):PathNode {
            
            for (var i:int = 0; i < openList.length; ++i) {
                
                if (openList[i].xID == xid && openList[i].yID == yid) {
                    
                    return openList[i];
                    end;
                }
            }
            
            return null;
        }
        
        public static function onOpenListByXYID(xid:int, yid:int):Boolean {
            
            for (var i:int = 0; i < openList.length; ++i) {
                
                if (openList[i].xID == xid && openList[i].yID == yid) {
                    
                    return true;
                    end;
                }
            }
            
            return false;
        }
        
        public static function clearMarkers():void{
            
            for (var i:int = 0; i < markers.length; i++ ) {
                markers[i].visible = false;
            }
            markers = [];
        }
        
        
        
        
        ///////// S T A T I C   E V E N T D I S P A T C H E R /////////
        ///////////////////////////////////////////////////////////////
        
        // === S T A T I C   E V E N T   D I S P A T C H E R ===
        public static function addEventListener( type:String, listener:Function, useCapture:Boolean=false,
            priority:int=0, useWeakReference:Boolean=true ):void
        {
            if ( !eventDispatcher ) {
                eventDispatcher = new EventDispatcher();
            }
            eventDispatcher.addEventListener( type, listener, useCapture, priority, useWeakReference );
        }

public static function removeEventListener( type:String, listener:Function, useCapture:Boolean=false ):void
        {
            if ( eventDispatcher ) eventDispatcher.removeEventListener( type, listener, useCapture );
              }

public static function dispatchEvent( p_event:Event ):void
        {
            
            if ( eventDispatcher ) {
                eventDispatcher.dispatchEvent( p_event );
            }
        }

}

///////////////////////////
//// P A T H N O D E /////
//////////////////////////

import flash.display.Sprite;
    import flash.text.TextField;
    import flash.text.TextFormat;
    /**
     * ...
     * @author Martino Wullems
     */
   class PathNode extends Sprite
    {
        public var H:int;
        public var F:int;
        public var G:int;
        public var parentNode:PathNode;
        public var stroke:Sprite
        
        public var xID:int;
        public var yID:int;
        public var zID:int;
        
        public var debug:Boolean = false;
        
        public function PathNode(width:int, height:int, type:String, _G:int = 0, _H:int = 0, _debug:Boolean = false):void{
                
            G = _G;
            H = _H;
            
                var color:uint;
                
                switch(type) {
                    case "begin":
                        color = 0x000000;
                    break;
                    case "end":
                        color = 0xFFFFFF;
                    break;
                    case "path":
                        color = 0xCC00CC;
                        createValues();
                    break;
                }
                
                graphics.beginFill(color, 0.3);
                graphics.drawRect(0, 0, width, height);
                graphics.endFill();
                
                createStroke();
            }
            
            private function createStroke():void 
            {
                stroke = new Sprite();
                stroke.graphics.beginFill(0xFFFFFF, 0);
                stroke.graphics.lineStyle(1, 0xFF0000, 1);
                stroke.graphics.drawRect(0, 0, this.width, this.height);
                stroke.graphics.endFill();
                addChild(stroke);
                stroke.visible = false;
            }
            
            private function createValues():void 
            {
                F = G + H;
                
                var valuesText:TextField = new TextField();
                addChild(valuesText);
                valuesText.defaultTextFormat = new TextFormat("Arial", 8, 0xFFFFFF);
                valuesText.text = "G:" + String(G) + "| H:" + String(H) + "\n F:" + String(F);
            }
        
    }

////////////////////
///pathfinderevent//
/////////////////////

class PathfinderEvent extends Event
    {
        
        public static const PATHFOUND:String = "PATHFOUND";
        
        public var path:Array;
        
        public function PathfinderEvent(path:Array, type:String, bubbles:Boolean = false, cancelable:Boolean = false):void
        {
            super(type, bubbles, cancelable);
            this.path = path;
            
        }
        
    }

//////////////////////////////////
////// T I L E G R I D///////////
/////////////////////////////////

import flash.display.DisplayObject;
    import flash.display.Loader;
    import flash.display.MovieClip;
    import flash.display.Sprite;
    import flash.events.Event;
    import flash.net.URLLoader;
    import flash.net.URLRequest;
    /**
     * ...
     * @author Martino Wullems
     */
    class TileGrid extends MovieClip
    {
        public var LAYERS:int = 1;
        public var COLLUMNS:int = 1;
        public var ROWS:int = 1;
        public var TILEWIDTH:Number;
        public var TILEHEIGHT:Number;
        //public var WORLD;
        
        public var background:MovieClip;
        public var tiles:Array;
        public var tile:Tile;
        public var testTile:Tile;
        
        public var debug:Boolean = false;
        
        
        public function TileGrid(rows:int = 0, collumns:int = 0, layers:int = 0, tileWidth:Number = 0, tileHeight:Number = 0) 
        {
            LAYERS = layers;
            COLLUMNS = collumns;
            ROWS = rows;
            TILEWIDTH = tileWidth;
            TILEHEIGHT = tileHeight;
            
            GameMath.tilesize = tileWidth;

addEventListener(Event.ADDED_TO_STAGE, onStage);
        }
        
        public function onStage(e:Event):void 
        {
            removeEventListener(Event.ADDED_TO_STAGE, onStage);
            
            //WORLD = parent;
        }
       
 
        public function initEmptyGrid(LAYERZ:int = 0, COLLUMNZ:int = 0, ROWZ:int = 0):void 
        {

//remove map if it is not empty
            try{
            
                if (tiles.length > 0) {
                    
                    clearMap();
                }
                
            }catch(e:*){};
            
            tiles = [];
            
            LAYERS = LAYERZ;
            COLLUMNS = COLLUMNZ;
            ROWS = ROWZ;
            
           
            
            
            for (var z:int = 0; z < LAYERS; z++) {
                
                var zArray:Array = new Array();
                tiles.push(zArray);
                
                //make collumns
                for (var i:int = 0; i < COLLUMNS; i++) {
                    
                    var iArray:Array = new Array();
                    zArray.push(iArray); //plaats kollom in array
                    
                    //maak rows
                    for (var j:int = 0; j < ROWS; ++j) { 
                       
                        //insert tiles
                        tile = new Tile(TILEWIDTH, TILEHEIGHT);
                        tile.GRID = this;
                        addChild(tile);
                        tile.x = TILEWIDTH * j;
                        tile.y = TILEHEIGHT * i;
                        
                        //every tile id 
                        var tileID:String = i + " // " + j;
                        tile.ID = tileID;
                        
                        var tilenr:String = (String(j) + String(i));
                        tile.tileNumber = int(tilenr);
                        
                        tile.xID = j;
                        tile.yID = i;
                        
                        //sla tile op in de array
                        iArray.push(tile);
                                    
                        tile.addEventListener(TileEvent.TILE_CHANGED, tilechanged, false, 0, true);
                    }
                    
                }
            }
        }
        
        public function clearMap():void {
            
            for (var z:int = 0; z < LAYERS; ++z) {
                
                for (var i:int = 0; i < COLLUMNS; ++i) {
                                
                    for (var j:int = 0; j < ROWS; ++j) {
                    
                        if (tiles[z][i][j] != null) {

trace("removing tile!");
                            
                            tiles[z][i][j].removeAllEventListeners();
                            removeChild(tiles[z][i][j]);
                        }else {
                            trace("clear map tile null");
                        }
                    }
                }
            
            }
            tiles = [];
        }
       
        
        public function loadMapArray(mapArray:Array):void {
                
            try{
            
                if (tiles.length > 0) {
                    
                    clearMap();
                }
                
            }catch (e:*) { };
            
            tiles = [];
            
            //maak collommen
            for (var i:int = 0; i < COLLUMNS; i++) { //height
                
                var iArray:Array = new Array();
                tiles.push(iArray); //plaats kollom in array
            
                //maak rijen
                for (var j:int = 0; j < ROWS; ++j) { //width
                    
                    //maak nieuwe tile met ingegeven grote
                    tile = new Tile(TILEWIDTH, TILEHEIGHT);
                    tile.GRID = this;
                    addChild(tile);
                    tile.x = TILEWIDTH * j;
                    tile.y = TILEHEIGHT * i;
                    
                    //geen elk array een nummer en id
                    var tileID:String = j + " // " + i;
                    tile.ID = tileID;
                    
                    var tilenr:String = (String(j) + String(i));
                    tile.tileNumber = int(tilenr);
                    
                    tile.xID = i;
                    tile.yID = j;
                    
                    if (mapArray[i][j] == 2) {
                        
                        tile.walkable = false;
                    }
                    
                    //sla tile op in de array
                    iArray.push(tile);
                    
                    //tile.debugDraw();
        
                }
            }

}
      
    
        
        private function tilechanged(e:TileEvent):void 
        {
            dispatchEvent(new TileEvent(e.tile, TileEvent.TILE_CHANGED));
        }

public function isWalkable (zt:int, xt:int, yt:int):Boolean {
            
            try{
            
                if(xt >= 0 && xt <= ROWS && yt >= 0 && yt <= COLLUMNS){
                
                    if(tiles[zt][yt][xt].walkable == true){
                        return true;
                    }else{
                        return false;
                    }
                }else {
                    
                    return false;
                }
            }catch (e:*) { return false};
            return false;
            
        }
        
        public function getTile(zt:int, xt:int, yt:int):Tile {
            
            if (zt <= LAYERS && xt < ROWS && yt < COLLUMNS && tiles.length > 0) {
                
                if(tiles[zt][yt][xt] != null){
                    return(tiles[zt][yt][xt]);
                }else {
                    return null;
                }
                
            }else {
                
                return null;
            }
        }
    
 
    }

//////////////////////////////////
////////// T I L E ///////////////
/////////////////////////////////

import flash.display.DisplayObject;
import flash.display.MovieClip;
import flash.display.Sprite;
import flash.events.DataEvent;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.text.TextField;
    //import com.martinowullems.tilengine.Events.TileEvent;
    
import flash.display.BlendMode;
    /**
     * ...
     * @author Martino Wullems
     */
    class Tile extends Sprite
    {
        //events
        static public var TILE_CHANGED:String  = "TILE_CHANGED";

public var WIDTH:int;
        public var HEIGHT:int;
        public var GRID:TileGrid;
        
        public var ID:String;
        public var tileNumber:int;
        public var zID:int;
        public var xID:int;
        public var yID:int;
        public var interactive:Boolean = false;
        public var walkable:Boolean = true;
        public var selected:Boolean = false;
        
        public var originalTile:String;
        public var previousTile:String;
        
        public var action:String; //action for tile
        
        private var tileField:TextField;
        public var debug:Boolean = false;
        private var strokeSprite:Sprite;
       
        private var square:Sprite;
        
        public function Tile(width:Number, height:Number) 
        {
            WIDTH = width;
            HEIGHT = height;
            
            addEventListener(Event.ADDED_TO_STAGE, initTile);
        }
        
        public function redraw():void{
            
            var color:uint;
            var strokecolor:uint;
            
            switch(walkable){
                case true:
                    color = 0xFFFFFF;
                    strokecolor = 0x000000;
               break;
                
                case false:
                    color = 0x000000;
                    strokecolor = 0xFFFFFF;
                break;
            }
            
            square.graphics.beginFill(color);
            square.graphics.lineStyle(1, strokecolor, 0.2);
            square.graphics.drawRect(0, 0, WIDTH, HEIGHT);
            square.graphics.endFill();

}

public function toggleWalkable():void{
           
            if(walkable == true){
                walkable = false;
            }else{
                walkable = true;
            }
            
            redraw();
        }

private function initTile(e:Event):void 
        {
            mouseChildren = false;
            removeEventListener(Event.ADDED_TO_STAGE, initTile);
                
            setStroke();
            square = new Sprite();
            redraw();
            addChild(square);

addEventListener(MouseEvent.MOUSE_OVER, overTile);
            addEventListener(MouseEvent.MOUSE_OUT, outTile);
        }

private function overTile(e:MouseEvent):void 
        {
            strokeSprite.visible = true;
        }
        
        private function outTile(e:MouseEvent):void 
        {
            strokeSprite.visible = false;
        }
        
        
        private function setStroke():void 
        {
            strokeSprite = new Sprite();
            strokeSprite.graphics.beginFill(0x000000, 0);
            strokeSprite.graphics.lineStyle(2, 0x000000, 0.5);
            strokeSprite.graphics.drawRect(0, 0, WIDTH - 2, HEIGHT - 2);
            strokeSprite.graphics.endFill();
            addChild(strokeSprite);
            
            strokeSprite.mouseEnabled = false;
            strokeSprite.visible = false;
        }
          
        
}

import flash.display.Sprite;
import flash.events.Event;

class TileEvent extends Event
    {
        public static const TILE_CHANGED:String  = "TILE_CHANGED";
        public static const GRID_COMPLETE:String = "GRID_COMPLETE";
        public var tile:Tile;
        
         public function TileEvent(tile:Tile, type:String, bubbles:Boolean = false, cancelable:Boolean = false):void
        {
            super(type, bubbles, cancelable);
            this.tile = tile;
            
        }
        
    }

////////////////////////////////
//////// G A M E M A T H ///////
///////////////////////////////

class GameMath
    {
        public static var tilesize:int;
        
        
        //works for y aswell! - camera not incporated
        public static function PointToTile(X:Number):Number {
            
            return Math.floor(X / tilesize);
        }
        
        public static function PointToTileX(X:Number):Number {
            
            return Math.floor(X / tilesize);
        }

public static function PointToTileY(Y:Number):Number {
            
            return Math.floor((Y) / tilesize);
        }
        
        public static function TileToPoint(X:int):Number {
            
            return X * tilesize;
        }
        
        
        
    }

///////////////////////////
/////  WONDERFL TRACE /////
///////////////////////////

import flash.display.Sprite;
import flash.display.Stage;
import flash.text.TextField;
import flash.text.TextFormat;

function inittrace(s:Stage):void
{
    WTrace.initTrace(s);
}

//global trace function
var trace:Function;

//wtreace class
class WTrace
{
        private static var FONT:String = "Fixedsys";
        private static var SIZE:Number = 12;
        private static var TextFields:Array = [];
        private static var trace_stage:Stage;
        
        public static function initTrace(stg:Stage):void
        {
            trace_stage = stg;
            trace = wtrace;
        }
        
        private static function scrollup():void
        {
            // maximum number of lines: 100
            if (TextFields.length > 100) 
            {
                var removeme:TextField = TextFields.shift();
                trace_stage.removeChild(removeme);
                removeme = null;
            }
            for(var x:Number=0;x<TextFields.length;x++)
            {
                (TextFields[x] as TextField).y -= SIZE*1.2;
            }
        }
    
        public static function wtrace(... args):void
        {
        
            var s:String="";
            var tracefield:TextField;
            
            for (var i:int;i < args.length;i++)
            {
                // imitating flash:
                // putting a space between the parameters
                if (i != 0) s+=" ";
                s+=args[i].toString();
            }

tracefield= new TextField();
            tracefield.mouseEnabled = false;
            tracefield.autoSize = "left";
            tracefield.text = s;
            tracefield.y = trace_stage.stageHeight - 20;

var tf:TextFormat = new TextFormat(FONT, SIZE);
            tracefield.setTextFormat(tf);
            trace_stage.addChild(tracefield);
            scrollup();                      
            TextFields.push(tracefield);
            
        }
}

Code Fullscreen

Preview Fullscreen

andrewexex88..

novita001

zmaxlin :

a*pathfinding

sort

pv439

forked from: Pathfinding issue..

yooo

forked:0
favorite:0
lines:629 (diff:5)