Hi all, I've been lurking the forum and following the development of flixel since the v1.25, although only recently I decided to use it for something. I have to say that I fell in love with its ease of use and power, so I decided to give something in return and I developed a class that allows to get the (hopefully) shortest path between two tiles in a tilemap. Of course it's mainly useful for topdown game, although it could be adapted also for platforms or side scrolling games.

I used

http://www.policyalmanac.org/games/aStarTutorial.htm as a reference for the algorithm and I borrowed some good implementative ideas from

http://code.google.com/p/baseoneaslib/ 's AStar.

Features:

-Finds shortest path between any two tiles in a tilemap.

-If a shortest path can't be found, returns the shortest path to the tile nearest to the goal

-Returns the path as an array of points, which are the coordinates of the tiles that belong to the path

-It should be quite fast, since I tried to optimize as much as possible (at the cost of some precision)

-You can specify whether or not allow diagonal movements (diagonal moves cost 1.4 times (that is sqrt(2)) the cost of orthogonal moves)

-Tiles' walkability depends on the collideIndex of the FlxTilemap

What could be added or improved:

-Different costs for traversing different tile types

-Using a sorted list (heap) to optimize the algorithm

-...pretty much anything you can think of

How to use:

First of, you have to istantiate a FlxPathfinding object, passing a FlxTilemap object to it:

var pf:FlxPathfinding = new FlxPathfinding(tilemap);

Then you can call the findPath(point1, point2) function to get an array of points, which is the shortest path. For instance:

var result:Array = pf.findPath(new Point(2,6), new Point(7,7));

Important note: the points are the tile coordinates within the tilemap, ie: you can't use your sprites (x,y), but you'll have to get the coordinates of the tile your sprite is inside. You can do that this way:

var tileX:int = (sprite.x - tilemap.x)/TILE_WIDTH;

var tileY:int = (sprite.y - tilemap.y)/TILE_HEIGHT;

Where of course TILE_WIDTH and TILE_HEIGHT are respectively the width and the height of the tiles in your tilemap (usually 8, 16 or 32).

If you change your tilemap (ie: you remove or add walls and such) you can use the setTilemap(tilemap:FlxTilemap) function to make FlxPathfinding reload the map, although if you do just few changes you can just set the walkability of a specific tile by using getNodeAt(x:int, y:int).walkable = true/false (see the example below).

Finally, you can set the allowDiagonal property to true or false to allow the path to traverse tiles diagonally (but it won't allow the path to cut corners of the walls) (default value is true).

Here are the classes (UPDATED: 22/06/10):

`package `

{

import flash.geom.Point;

import org.flixel.FlxTilemap;

import org.flixel.FlxG;

/**

* Class which implements the A* pathfinding algorithm

* @author Vexhel

* Thanks to Rolpege and Valenti for fixes

*/

public class FlxPathfinding {

private var _map:FlxTilemap;

private var _nodes:Array;

private var _open:Array;

private var _closed:Array;

//we use int (instead of Number) to get better performance

private const COST_ORTHOGONAL:int = 10;

private const COST_DIAGONAL:int = 14

public var allowDiagonal:Boolean = true;

public var calculeNearestPoint:Boolean = false;

public function FlxPathfinding(tilemap:FlxTilemap) {

setMap(tilemap)

}

public function setMap(tilemap:FlxTilemap):void {

_map = tilemap;

//initialize the node structure

_nodes = [];

for (var i:int = 0; i < tilemap.totalTiles; i++) {

_nodes.push(new FlxPathfindingNode(i % _map.widthInTiles, int(i / _map.widthInTiles), (_map.getTileByIndex(i) < _map.collideIndex)));

}

}

//given a start and an end points, returns an array of points representing the shortest path (if any) between them

public function findPath(startPoint:Point, endPoint:Point):Array {

_open = [];

_closed = [];

for (var i:int = 0; i < _nodes.length; i++) {

_nodes[i].parent = null;

}

var start:FlxPathfindingNode = getNodeAt(startPoint.x, startPoint.y);

var end:FlxPathfindingNode = getNodeAt(endPoint.x, endPoint.y);

_open.push(start);

start.g = 0;

start.h = calcDistance(start, end);

start.f = start.h;

while (_open.length > 0) {

var f:int = int.MAX_VALUE;

var currentNode:FlxPathfindingNode;

//choose the node with the lesser cost f

for (var i:int = 0; i < _open.length; i++) {

if (_open[i].f < f) {

currentNode = _open[i];

f = currentNode.f;

}

}

//we arrived at the end node, so we finish

if (currentNode == end) {

return rebuildPath(currentNode);

}

//we visited this node, so we can remove it from open and add it to closed

_open.splice(_open.indexOf(currentNode), 1);

_closed.push(currentNode);

//do stuff with the neighbors of the current node

for each (var n:FlxPathfindingNode in getNeighbors(currentNode)) {

//skip nodes that has already been visited

if (_closed.indexOf(n) > -1) {

continue;

}

var g:int = currentNode.g + n.cost;

if (_open.indexOf(n) == -1) {

_open.push(n);

n.parent = currentNode;

n.g = g; //path travelled so far

n.h = calcDistance(n, end); //estimated path to goal

n.f = n.g + n.h;

} else if (g < n.g) {

n.parent = currentNode;

n.g = g;

n.h = calcDistance(n, end);

n.f = n.g + n.h;

}

}

}

//no path can be found

if(calculeNearestPoint)

{

var min:int = int.MAX_VALUE;

var nearestNode:FlxPathfindingNode;

//find the reachable node that is nearer to the goal

for each(var c:FlxPathfindingNode in _closed) {

var dist:Number = calcDistance(c, end);

if (dist < min) {

min = dist;

nearestNode = c;

}

}

return rebuildPath(nearestNode); //returns the path to the node nearest to the goal

}

else

{

return [];

}

}

public function getNodeAt(x:int, y:int):FlxPathfindingNode {

return _nodes[x + y * _map.widthInTiles];

}

//returns an array from a linked list of nodes

private function rebuildPath(end:FlxPathfindingNode):Array {

var path:Array = new Array();

if (end == null) {

return path;

}

var n:FlxPathfindingNode = end;

while (n.parent != null) {

path.push(new Point(n.x, n.y));

n = n.parent;

}

return path.reverse();

}

private function getNeighbors(node:FlxPathfindingNode):Array {

var x:int = node.x;

var y:int = node.y;

var currentNode:FlxPathfindingNode;

var neighbors:Array = new Array(8);

if (x > 0) {

currentNode = getNodeAt(x - 1, y);

if (currentNode.walkable) {

currentNode.cost = COST_ORTHOGONAL;

neighbors.push(currentNode);

}

}

if (x < _map.widthInTiles - 1) {

currentNode = getNodeAt(x + 1, y);

if (currentNode.walkable) {

currentNode.cost = COST_ORTHOGONAL;

neighbors.push(currentNode);

}

}

if (y > 0) {

currentNode = getNodeAt(x, y - 1);

if (currentNode.walkable) {

currentNode.cost = COST_ORTHOGONAL;

neighbors.push(currentNode);

}

}

if (y < _map.heightInTiles - 1) {

currentNode = getNodeAt(x, y + 1);

if (currentNode.walkable) {

currentNode.cost = COST_ORTHOGONAL;

neighbors.push(currentNode);

}

}

if (allowDiagonal){

if (x > 0 && y > 0) {

currentNode = getNodeAt(x - 1, y - 1);

if (currentNode.walkable && getNodeAt(x - 1, y).walkable && getNodeAt(x, y - 1).walkable) {

currentNode.cost = COST_DIAGONAL;

neighbors.push(currentNode);

}

}

if (x < _map.widthInTiles - 1 && y > 0) {

currentNode = getNodeAt(x + 1, y - 1);

if (currentNode.walkable && getNodeAt(x + 1, y).walkable && getNodeAt(x, y - 1).walkable) {

currentNode.cost = COST_DIAGONAL;

neighbors.push(currentNode);

}

}

if (x > 0 && y < _map.heightInTiles - 1) {

currentNode = getNodeAt(x - 1, y + 1);

if (currentNode.walkable && getNodeAt(x - 1, y).walkable && getNodeAt(x, y + 1).walkable) {

currentNode.cost = COST_DIAGONAL;

neighbors.push(currentNode);

}

}

if (x < _map.widthInTiles - 1 && y < _map.heightInTiles - 1) {

currentNode = getNodeAt(x + 1, y + 1);

if (currentNode.walkable && getNodeAt(x + 1, y).walkable && getNodeAt(x, y + 1).walkable) {

currentNode.cost = COST_DIAGONAL;

neighbors.push(currentNode);

}

}

}

return neighbors;

}

//cheap way to calculate an approximate distance between two nodes

private function calcDistance(start:FlxPathfindingNode, end:FlxPathfindingNode):int {

if (start.x > end.x) {

if (start.y > end.y) {

return (start.x - end.x) + (start.y - end.y);

} else {

return (start.x - end.x) + (end.y - start.y);

}

} else {

if (start.y > end.y) {

return (end.x - start.x) + (start.y - end.y);

} else {

return (end.x - start.x) + (end.y - start.y);

}

}

}

//not sure which one is faster, have to do some test

/*private function calcDistance2(start:FlxPathfindingNode, end:FlxPathfindingNode):int {

return Math.abs(n1.x-n2.x)+Math.abs(n1.y-n2.y);

}*/

}

}

`package`

{

/**

* Support structure for the A* pathfinding algorithm

* @author Vexhel

*/

public class FlxPathfindingNode {

public var x:int;

public var y:int;

public var g:int = 0;

public var h:int = 0;

public var f:int = 0;

public var cost:int;

public var parent:FlxPathfindingNode = null;

public var walkable:Boolean;

function FlxPathfindingNode(x:int, y:int, walkable:Boolean=true) {

this.x = x;

this.y = y;

this.walkable = walkable;

}

}

}

I also uploaded an example:

http://www.swfcabin.com/open/1272490338 (mouse click to add or remove walls, space to draw the path, in console you can see the path's length)

You can download the source for the example here:

http://dl.dropbox.com/u/846721/flash/FlxPathfindingExample.zipThat's all. Note that I made all of this in about 6 hours today, without testing it much, so it might contain bugs and errors. It might even blow up your pc! Well, it's unlikely actually, but whatever.

Hope you find it useful. If you have any suggestions or anything don't hesitate to post