Author Topic: FlxPathfinding  (Read 12230 times)

Vexhel

  • Member
  • **
  • Posts: 30
  • Karma: +0/-0
  • Huh?
    • View Profile
FlxPathfinding
« on: Wed, Apr 28, 2010 »
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):
Code: [Select]
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);
}*/



}
}

Code: [Select]
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.zip

That'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 :)
« Last Edit: Tue, Dec 14, 2010 by Vexhel »

zuperxtreme

  • Contributor
  • ****
  • Posts: 254
  • Karma: +0/-0
    • View Profile
    • Buddah
Re: FlxPathfinding
« Reply #1 on: Wed, Apr 28, 2010 »
Pure genius. This should get implemented in the main Flixel branch, awesome work.   :D
..."without order nothing exists, without chaos nothing evolves"... 
Zoklet.net

hanuman

  • Member
  • **
  • Posts: 30
  • Karma: +0/-0
    • View Profile
    • Physics Games
Re: FlxPathfinding
« Reply #2 on: Thu, Apr 29, 2010 »
Wow, amazing... :)

UberGeorge

  • Member
  • **
  • Posts: 99
  • Karma: +0/-0
    • View Profile
Re: FlxPathfinding
« Reply #3 on: Thu, Apr 29, 2010 »
This is great Vexhel , but I do have an observation/criticism.

You say in the features list that "If a shortest path can't be found, returns the shortest path to the tile nearest to the goal". If I'm understanding this correctly, it really doesn't make a lot of sense.

If there is no path between the two tiles then the algorithm should return a value indicating failure to find a path. It should be up to the user of this algorithm to decide whether to search the next nearest tile or let the player know that their attempted move is invalid and so on.

A path finding algorithm should just return the shortest/cheapest path or return failure, nothing else.

Vexhel

  • Member
  • **
  • Posts: 30
  • Karma: +0/-0
  • Huh?
    • View Profile
Re: FlxPathfinding
« Reply #4 on: Fri, Apr 30, 2010 »
You say in the features list that "If a shortest path can't be found, returns the shortest path to the tile nearest to the goal". If I'm understanding this correctly, it really doesn't make a lot of sense.

If there is no path between the two tiles then the algorithm should return a value indicating failure to find a path. It should be up to the user of this algorithm to decide whether to search the next nearest tile or let the player know that their attempted move is invalid and so on.

A path finding algorithm should just return the shortest/cheapest path or return failure, nothing else.

I thought about this, and indeed I should create a flag or something that can be set to activate or deactivate (deactivated by default) that feature. At the moment, the user would have to check if the last node in the path (ie: the last point in the array) is equal to the chosen goal. Thanks for noting that :)

Richard Kain

  • Active Member
  • ***
  • Posts: 231
  • Karma: +0/-0
    • View Profile
Re: FlxPathfinding
« Reply #5 on: Fri, Apr 30, 2010 »
Thank you for posting this interesting development you've made, Vexhel. I've actually thought of a potential use for this. I'll see if I can't try it out over the weekend.

Rolpege

  • Guest
Re: FlxPathfinding
« Reply #6 on: Sun, May 23, 2010 »
A little edition to make the calculation of the nearest node (if the exact path to the goal was not found) optional. You have to make true "calculeNearestPoint" to calculate it.

If it's disabled, it will return an array containing only false.

Code: [Select]
package 
{
import flash.geom.Point;
import org.flixel.FlxTilemap;
import org.flixel.FlxG;
/**
* Class which implements the A* pathfinding algorithm
* @author Vexhel
*/
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.heightInTiles), (_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 = [];
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 [false];
}
}


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);
}*/

}
}

biomechanic

  • Active Member
  • ***
  • Posts: 107
  • Karma: +0/-0
    • View Profile
Re: FlxPathfinding
« Reply #7 on: Sat, Jun 19, 2010 »
Damn, I should have done that forum search hours ago -_-. I've just finished a pathfinding class - based on the same tut - and was about to post it, but decided to check if there's anything similar in the forum (I'm glad I did 'cause yours is way better).

Thanks for sharing :)


vieko

  • Member
  • **
  • Posts: 11
  • Karma: +0/-0
    • View Profile
    • LeGrudge & Rugged
Re: FlxPathfinding
« Reply #8 on: Mon, Jun 21, 2010 »
This is excellent. Thanks for saving me a ton of time!

Valenti

  • Member
  • **
  • Posts: 20
  • Karma: +0/-0
    • View Profile
Re: FlxPathfinding
« Reply #9 on: Mon, Jun 21, 2010 »
Hey Vexhel,

    Amazing code that works great in your example.  After spending a while implementing it I have came across a few tweaks that need to be made.

Firstly, in setMap() the body of the loop needs to be changed from:
Code: [Select]
_nodes.push(new FlxPathfindingNode(i % _map.widthInTiles, int(i / _map.heightInTiles), (_map.getTileByIndex(i) < _map.collideIndex)));To:
Code: [Select]
_nodes.push(new FlxPathfindingNode(i % _map.widthInTiles, int(i / _map.widthInTiles), (_map.getTileByIndex(i) < _map.collideIndex)));
The difference being int(i / _map.heightInTiles) is now int(i / _map.widthInTiles).  This is because using i for both height and width in the same loop will cause errors on any map that is not square. 

The next tweak is clearing the nodes of their linkage before every new findPath() call.  You have correctly cleared the other arrays:
Code: [Select]
_open = [];
_closed = [];
But, although you don't want to clear _nodes of all its data, it still contains linkages from the previous call.  And what I mean by this is, a bunch of your nodes now have parents. 

I added the following loop after clearing _open and _closed at the start of findPath():
Code: [Select]
for (var i:int = 0; i < _nodes.length; i++) {
_nodes[i].parent = null;
}

The reason this doesn't cause a problem in your example is that you have a static starting point.  I found that once the same object starts calling findPath() from different tiles I got infinite loops as pairs of nodes would end up as parents of each other.

Having tweaked this code I now have it working and you can see this in the latest iteration of my Flixel Dungeon game here (the crappy fire-type enemies):  http://flashgamedojo.com/u/j0yp3v/

Once again I'd like to thank you for this code, it has been a great help.  I really hope this makes it into the next official Flixel update as it is a great class to have in your library.

-Valenti

Vexhel

  • Member
  • **
  • Posts: 30
  • Karma: +0/-0
  • Huh?
    • View Profile
Re: FlxPathfinding
« Reply #10 on: Tue, Jun 22, 2010 »
Thank you Valenti for the fixes, I definitely missed those issues. I updated the first post, and I also implemented the calculeNearestPoint thing from Rolpege =)

Barts

  • Member
  • **
  • Posts: 61
  • Karma: +0/-0
    • View Profile
Re: FlxPathfinding
« Reply #11 on: Tue, Jun 29, 2010 »
Great stuff, I was thinking about writing A* myself. :)

luc

  • Member
  • **
  • Posts: 97
  • Karma: +0/-0
  • no ablo anything except french
    • View Profile
    • scribbles
Re: FlxPathfinding
« Reply #12 on: Thu, Sep 16, 2010 »
Hi, thanks a lot Vexhel for this class and Valenti for the fixes.
I'm trying to get an enemy to follow the player.
It generates the path correctly but I can't figure how to translate this Array of Points into enemy velocity.
Can somebody explain how to do it or link to an explanation,please ?

The mockup I did to test pathfinding. Space to generate the path.
http://www.swfcabin.com/open/1284648949

Retro-Rob

  • Active Member
  • ***
  • Posts: 164
  • Karma: +0/-0
    • View Profile
Re: FlxPathfinding
« Reply #13 on: Thu, Sep 16, 2010 »
Hi, thanks a lot Vexhel for this class and Valenti for the fixes.
I'm trying to get an enemy to follow the player.
It generates the path correctly but I can't figure how to translate this Array of Points into enemy velocity.
Can somebody explain how to do it or link to an explanation,please ?

The mockup I did to test pathfinding. Space to generate the path.
http://www.swfcabin.com/open/1284648949


I'm pretty interested in t his as well.   Thanks in advance to anyone that comes through!

zuperxtreme

  • Contributor
  • ****
  • Posts: 254
  • Karma: +0/-0
    • View Profile
    • Buddah
Re: FlxPathfinding
« Reply #14 on: Thu, Sep 16, 2010 »
What I did was to make the enemy move to the next point in the array at a set speed, then when he's there(or near it), to just go to the next and so on. Don't know if that's of any help. :/
..."without order nothing exists, without chaos nothing evolves"... 
Zoklet.net

luc

  • Member
  • **
  • Posts: 97
  • Karma: +0/-0
  • no ablo anything except french
    • View Profile
    • scribbles
Re: FlxPathfinding
« Reply #15 on: Thu, Sep 16, 2010 »
yes but how to code that ?
Each time I'm trying to write something it turns into a big mess, I wonder what's the right way ?
I'm really not a coder, it might be really simple (here's me hoping :))
« Last Edit: Thu, Sep 16, 2010 by luc »

Billy

  • Active Member
  • ***
  • Posts: 159
  • Karma: +0/-0
  • Herper of Derps
    • View Profile
    • billy.wenge-murphy.com
Re: FlxPathfinding
« Reply #16 on: Fri, Sep 17, 2010 »
For the point to point solution, use some simple algebra. Treat the x and y velocities as the slope of a line

With enemy and destination position both as points, and the slope of a line calculated as...

m = (x2 - x1) / (y2 - y1)

It becomes clear you can just set the two velocities accordingly:

enemy.velocity.x = (path[0].x - enemy.x) / speed;
enemy.velocity.y = (path[0].y - enemy.y) / speed;

Where speed is just arbitrary, however fast you want them to move

The enemy won't hit the point exactly - these are floating point numbers, after all, and you might overshoot the destination at high velocity - but you can check the absolute value of the distance between the enemy and destination

if (Math.abs(path[0].x - enemy.x) < 0.2) ......
« Last Edit: Fri, Sep 17, 2010 by Billy »

bobbybaker82

  • Active Member
  • ***
  • Posts: 155
  • Karma: +0/-0
    • View Profile
Re: FlxPathfinding
« Reply #17 on: Fri, Sep 17, 2010 »
That's how I do it as well, but keep in mind you should update your path every so often so if your player moves, your enemy will adjust correctly.

Retro-Rob

  • Active Member
  • ***
  • Posts: 164
  • Karma: +0/-0
    • View Profile
Re: FlxPathfinding
« Reply #18 on: Fri, Sep 17, 2010 »
could anyone post some source code i'm not following

luc

  • Member
  • **
  • Posts: 97
  • Karma: +0/-0
  • no ablo anything except french
    • View Profile
    • scribbles
Re: FlxPathfinding
« Reply #19 on: Fri, Sep 17, 2010 »
thanks a lot Billy !!
I just had to multiply the path points by the height of my tilemap because findPath is returning tiles coordinates.
thanks again.
Retro-Rob I will post my code tomorrow if I get things to work properly.