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.
/**
* Copyright omgnoseat ( http://wonderfl.net/user/omgnoseat )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/hRtO
*/
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);
}
}