Prototype ¬ Detail

PROTOTYPE I'm Not Only The Prototype, I'm Also A Member.

home ▪ stats ▪ search ▪ linkback ▪ about ▪ FAQ | user: guest, login, register

author: zeh [+], Submitted: 07.16.03 6a • Last Edit: 05.28.04 6a
Avg. Rating: 4

/*
===============================================================================
= PATHFINDING FUNCTION
=------------------------------------------------------------------------------
= Version: 1.1.4
= Last changes: jul 15 (1.0.0) - first version
=               aug 09 (1.0.1) - several speed improvements, thanks tonypa
=               aug 10 (1.0.2) - even more speed improvements by tonypa (again)
=               aug 31 (1.0.3) - return NULL if error (instead of error string)
=               aug 31 (1.1.3) - added cornering option. thanks for LAlex for
=                                his suggestions
=          2004 may 28 (1.1.4) - fixed "undefined != 0" error on MX 2004 when
=                                compiling as flash 7. Thanks Inkog for finding
=                                the error and the solution
=------------------------------------------------------------------------------
= This function finds the path between two points (the START and the END point)
= on a given map, taken into account walls/obstacles and terrain costs.
=
= It uses an A* ("a star") algorithm with heuristic approximation for a faster
= result. Much of this function is basic on theory learnt from this language
= independent tutorial:
= http://www.policyalmanac.org/games/aStarTutorial.htm
=------------------------------------------------------------------------------
= How to use:
=
= my_path_array = findPath (map, start_y, start_x, end_y, end_x)
=
= Parameters:
=  map = bidimensional array with rows and columns. Each cell contains a value
=        of 0 (wall) or 1+ (terrain - the higher, the more expensive to ride)
===============================================================================
*/
_global.findPath = function(map, startY, startX, endY, endX) {
  // Finds the way given a certain path

  // Constants/configuration - change here as needed! --------------------------------
  var HV_COST = 10; // "Movement cost" for horizontal/vertical moves
  var D_COST = 14; // "Movement cost" for diagonal moves
  var ALLOW_DIAGONAL = true; // If diagonal movements are allowed at all
  var ALLOW_DIAGONAL_CORNERING = true; // If diagonal movements over corners are allowed

  // Complimentary functions =========================================================
    
  isOpen = function (y, x) {
    // Return TRUE if the point is on the open list, false if otherwise
    return mapStatus[y][x].open;
  };
  isClosed = function (y, x) {
    // Return TRUE if the point is on the closed list, false if otherwise
    return mapStatus[y][x].closed;
  };
  nearerSquare = function() {
    // Returns the square with a lower movementCost + heuristic distance
    // from the open list
    var minimum = 999999;
    var indexFound = 0;
    var thisF = undefined;
    var thisSquare = undefined;
    var i = openList.length;
    // Finds lowest
    while (i-->0) {
      thisSquare = mapStatus[openList[i][0]][openList[i][1]];
      thisF = thisSquare.heuristic + thisSquare.movementCost;
      if (thisF <= minimum) {
        minimum = thisF;
        indexFound = i;
      }
    }
    // Returns lowest
    return indexFound;
  };
  closeSquare = function(y, x) {
    // Drop from the open list
    var len = openList.length;
    for (var i=0; i < len; i++) {
      if (openList[i][0] == y) {
        if (openList[i][1] == x) {
          openList.splice(i, 1);
          break;
        }
      }
    }
    // Closes an open square
    mapStatus[y][x].open = false;
    mapStatus[y][x].closed = true;
  };
  openSquare = function(y, x, parent, movementCost, heuristic, replacing) {
    // Opens a square
    if (!replacing) {
      openList.push([y,x]);
      mapStatus[y][x] = {heuristic:heuristic, open:true, closed:false};
    }
    mapStatus[y][x].parent = parent;
    mapStatus[y][x].movementCost = movementCost;
  };

  // Ok, now go back to our regular schedule. Find the path! -------------------------

  // Caches dimensions
  var mapH = map.length;
  var mapW = map[0].length;

  // New status arrays
  var mapStatus = new Array();
  for (var i=0; i<mapH; i++) mapStatus[i] = new Array();

  if (startY == undefined || startX == undefined) return null; // Error: no starting point
  if (endY == undefined || endX == undefined) return null; // Error: no ending point

  // Now really starts
  var openList = new Array();
  openSquare (startY, startX, undefined, 0);
  
  // Loops until there's no other way to go OR found the exit
  while (openList.length > 0 && !isClosed(endY, endX)) {
    // Browse through open squares
    var i = nearerSquare();

    var nowY = openList[i][0];
    var nowX = openList[i][1];

    // Closes current square as it has done its purpose...
    closeSquare (nowY, nowX);
    // Opens all nearby squares, ONLY if:
    for (var j=nowY-1; j<nowY+2; j++) {
      for (var k=nowX-1; k<nowX+2; k++) {
        if (j >= 0 && j < mapH && k >= 0 && k < mapW && !(j==nowY && k==nowX) && (ALLOW_DIAGONAL || j==nowY || k==nowX) && (ALLOW_DIAGONAL_CORNERING || j==nowY || k==nowX || (map[j][nowX] != 0 && map[nowY][k]))) {
          // If not outside the boundaries or at the same point or a diagonal (if disabled) or a diagonal (with a wall next to it)...
          if (map[j][k] != 0) {
            // And if not a wall...
            if (!isClosed(j,k)) {
              // And if not closed... THEN open.
              var movementCost = mapStatus[nowY][nowX].movementCost + ((j==nowY || k==nowX ? HV_COST : D_COST) * map[j][k]);
              if (isOpen(j,k)) {
                // Already opened: check if it's ok to re-open (cheaper)
                if (movementCost < mapStatus[j][k].movementCost) {
                  // Cheaper: simply replaces with new cost and parent.
                  openSquare (j, k, [nowY, nowX], movementCost, undefined, true); // heuristic not passed: faster, not needed 'cause it's already set
                }
              } else {
                // Empty: open.
                var heuristic = (Math.abs (j - endY) + Math.abs (k - endX)) * 10;
                openSquare (j, k, [nowY, nowX], movementCost, heuristic, false);
              }
            } else {
              // Already closed, ignore.
            }
          } else {
            // Wall, ignore.
          }
        }
      }
    }
  }
  // Ended
  var pFound = isClosed(endY, endX); // Was the path found?
  // Clean up temporary functions
  delete isOpen;
  delete isClosed;
  delete nearerSquare;
  delete closeSquare;
  delete openSquare;
  if (pFound) {
    // Ended with path found; generates return path
    var returnPath = new Array();
    var nowY = endY;
    var nowX = endX;
    while ((nowY != startY || nowX != startX)) {
      returnPath.push([nowY,nowX]);
      var newY = mapStatus[nowY][nowX].parent[0];
      var newX = mapStatus[nowY][nowX].parent[1];
      nowY = newY;
      nowX = newX;
    }
    returnPath.push([startY,startX]);
    return (returnPath);
  } else {
    // Ended with 0 open squares; ran out of squares, path NOT found
    return null;
  }
};
ASSetPropFlags(_global, "findPath", 1, 0);

usage

This function finds the path between two given points using an A* algorithm. It's usually
needed on games that need pathfinding/navigating AI.

It uses a bidimensional map (the MAP), a START point (defined as an Y and X value, in this
order to maintain standard with the way the map is built), and an END point (Y and X values).

Each MAP cell have a value of 0 (when it means a wall, or a cell it can't be visited on the
route) or a value of 1 or greater. In this case, this value means the COST to navigate through
that point. On an standard map, for example, a value of 1 would be used for a road, a value of
2 for normal terrain, and a value of 3 for mountains.

You can also modify the "CONSTANT variables" inside the function. For instance, you can
set ALLOW_DIAGONAL to to TRUE to allow diagonal movements or to FALSE to disallow it.

Example of usage:

// Creates a map
map = [[2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,0,0,0,0,0,0,0,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2]];

// Finds the path from point 2,2 to point 9,9
fpath = findPath (map, 2, 2, 9, 9);

// Draw results
for (i=0; i<map.length; i++) {
  for (j=0; j<map[0].length; j++) {
    switch (map[i][j]) {
    case 0:
      _root.beginFill (0x333366);
      break;
    case 2:
      _root.beginFill (0xdddddd);
      break;
    case 1:
      _root.beginFill (0xeeeeee);
      break;
    }
    _root.moveTo (j*20, i*20);
    _root.lineTo ((j+1)*20,i*20);
    _root.lineTo ((j+1)*20,(i+1)*20);
    _root.lineTo (j*20,(i+1)*20);
    _root.lineTo (j*20,i*20);
    _root.endFill();
  }
}

for (i=0; i<fpath.length; i++) {
  x = fpath[i][1];
  y = fpath[i][0];
  _root.beginFill (0x993333, 70);
  _root.moveTo (x*20, y*20);
  _root.lineTo ((x+1)*20,y*20);
  _root.lineTo ((x+1)*20,(y+1)*20);
  _root.lineTo (x*20,(y+1)*20);
  _root.lineTo (x*20,y*20);
  _root.endFill();
}

msg1 { zeh [+], posted: 07.16.03 6a•07.16.03 6a, top [^] }

Here's an example of it working. In this case I've used a Advance Wars (a GBA game) screen just to display. Clicking on the map will highlight the best route the soldier could take to that point. Roads are fast (cost 1), grass terrain are ok (cost 2), while forest, small mountains and big mountains are expensive to travel by (3, 4 and 5, respectively), so he'll avoid it unless it's really better to go through it.

msg2 { zeh [+], posted: 02.05.04 9a•-, top [^] }

There was a wrong legacy reference on the code. I've fixed it now.

msg3 { nomadx [+], posted: 04.13.04 10p•-, top [^] }

it doesn't work when it tries to solve an unreachable point. perhaps you could just find the nearest reachable point?

msg4 { Inkog [+], posted: 05.24.04 7a•-, top [^] }

I've implemented this pathfinding routine and it works perfectly when ALLOW_DIAGONAL is set to false, but when enabled, the path always prefers diagonal paths no matter how they are weighted. Anyone know why this might be? My map does not implement any terrain costs at all and consists of only walls (0) and same cost terrain (1). Is the code for diagonal paths correct/working in this function?

Thanks in advance,

~G~

Nice site by the way :)

msg5 { zeh [+], posted: 05.24.04 5p•-, top [^] }

Inkog: it'll prefer diagonal movements when they're cheaper then horizontal or vertical moves. If you want it to *prefer* h/v moves but still allow it to go through diagonal moves as a last chance, you can do that by increasing the diagonal movement cost. The default one is 14 which is a good all around value; if you set it to 21, which is more than the cost of a horizontal AND diagonal movement (10+10=20, it's what he compares against a diagonal value), it'll prefer horizontal or vertical moves but still be able to perform diagonal ones when needed (I can't think of such situation though).

I've tested it now and it's working fine. If you have some problem with it please let me know.

msg6 { Inkog [+], posted: 05.24.04 8p•-, top [^] }

Zeh,

To test that there was nothing wrong with my implementation, I copied just the pathfinding function and your example of usage into a new .swf and tested.

The only thing I changed was the start point (4,2) and destination to (4,9) make it easier to test:
change:
fpath = findPath (map, 4, 2, 4, 9);
weights were left at H/V = 10, diag = 14.
On my machine with MX 2004, I got this path:
[---------------]
[-----XX--------]
[----X--X-------]
[---X----X------]
[--S------D-----]

Interestingly enough, after I got to work and saw your reply, I tested again on a machine with MX (not 2004) installed and got a correct path:
[---------------]
[---------------]
[---------------]
[---------------]
[--SXXXXXXD-----]

Is there any reason why this function might fail on MX 2004? Thus far I cannot see any reason, but I'm not 100% up to speed on the changes in 2004.

Unfortunatly, I don't have access to MX 2004 at work, so I can't do any further testing right now. As soon as I get home, I'll try again just to make sure I'm not seeing things.

msg7 { zeh [+], posted: 05.25.04 5a•-, top [^] }

HMM, that's funny. Thanks for letting me know; this is *probably* some case mismatch I've done; it'd work on MX but it would fail on MX 2004. I wasn't working on MX 2004 so I never noticed that. I'll test it throughly and post a fix later.

msg8 { Inkog [+], posted: 05.25.04 7a•05.25.04 10a, top [^] }

zeh,

I think I got it figured out. After stepping through the debugger in MX 2004, I noticed that movementCost always = NaN.

It looks to me that this is cause by the code below. When first starting the search from the initial "square", the first openSquare call does not send the movementCost param, so it's initially assigned as undefined.

// Now really starts
var openList = new Array();
openSquare (startY, startX);

Since every square you check gets its movementCost assigned by adding the "rolling cost" with it's cost, it appears that this is causing it to be undefined for all squares.

It appears that undefined + aNumber = NaN in 2004. Then again I'm a novice, so I may be wrong... but this worked as a resolution:

openSquare (startY, startX, undefined, 0, undefined, undefined);

Please let me know if I'm off base here, as I haven't fully tested this "fix", but thus far it appears to work perfectly.

Thanks for your work on this function, it's the fastest Flash A* routine I've seen yet.

~G~

*Edit - I just wanted to add... After studying your code, I came to appreciate how effecent it is. Only one * or / in the whole function (and just for the heuristic), that impressive to say the least. I've been able to implement this for all my agents real-time without any noticeable frame rate drop. It is saving me tons of time not having to devise yet another algorithm as I suspected. Now to finish that particle effects engine….

Thank you

msg9 { zeh [+], posted: 05.28.04 6a•-, top [^] }

Well, I sure took my damn time (I was busy with other work), but after testing it a bit, I've been able to certify that the error is exactly what you've pointed out. I was just relaying on an undefined variable working as 0 and it's not very secure, I shouldn't have done that... passing the first cost as 0 (as you suggested) solves it though. Thanks, the code's fixed and updated now. :)

msg10 { larsman [+], posted: 11.03.04 8a•-, top [^] }

hi,

i made this post already on zeh's page but i think there is much more going on here.
i was wondering if you guys are still improving the a* pathfinder?
if so, i may have something for you.

you can find a binary heap here:
http://larsman.net/projects/binheap.zip

it uses a binary heap to keep track of the lowest f node in the open list.
speed improves when there are over 30 nodes in the open list.

hope it helps
larsman

msg11 { zeh [+], posted: 11.03.04 9a•-, top [^] }

Thanks lars. I've saw your post there on the page. I'm not improving it anymore because it does what's supposed to do, but I'll test your stuff later.

msg12 { pcpackrat [+], posted: 04.18.05 5p•-, top [^] }

Hello all,

We used the above code in a group project for school. We are using Flash Player 7, Flash MX 2004, and ActionScript 2.0

The code worked beautifully except for the first function call. When first calling the find path function our character would walk through any walls that were there.

It turned out, after quite a bit of head scratching, that the value returned from the openList Array when initializing nowY and nowX was being treated as a string. This caused the loop to continue for way to long.

For example if nowY = 5 then nowY+2 should equal 7, but since nowY was a string nowY+2 yielded the value 52.

The solution that worked for us was to type cast the return value of openList when assigning it to the variable.

var nowY:Number = Number(openList[i][0]);
var nowX:Number = Number(openList[i][1]);

Granted this code was written for ActionScript 1.0, but we figured that some one else may try to use the code with AS2 at some point and this comment would help them out.

- Illinois Institute of Technology IPRO 329 team

msg13 { wildbilly7 [+], posted: 02.03.06 11a•-, top [^] }

I've been having a small issue running this code. I've designed a simple interface where the 2D map array is represented on screen with one square that represents the starting position. The user can click on any other square to move to the new position. First the new path is generated using 'findpath', then the square is moved along the path to the destination.
My problem is that occasionally I get this 'warping' behavior, where findpath will only generate a path with the starting points and endpoints, but none of the in between steps. I know its not my display code, because I've run traces in all the functions and findpath starts with the correct points and map, it just generates an invalid path for some reason. Oddly enough, the path will work sometimes, and sometimes do the 'warp'. Perhaps this is simply some array pointer issue? Anyone else ever experience this? Thanks very much for any help!

msg14 { wildbilly7 [+], posted: 02.03.06 12p•-, top [^] }

haha oops actually the post right above my earlier one solves this problem! Different results but apparently the same cause.

msg15 { Xandr [+], posted: 12.10.06 12p•12.10.06 12p, top [^] }

AS2.0 class Pathfinding
Part #1

/*
* 
* [AS2.0 class Pathfinding]
* Usage:
* 	Put this code to Pathfinding.as file.
* 	
* 	var path = Pathfinding.findPath(map, start_y, start_x, end_y, end_x);
* 	
* 
* Converted from:
* <a href="http://proto.layer51.com/d.aspx?f=998" target="_blank">http://proto.layer51.com/d.aspx?f=998</a>
* Converted by: Xandr, xandrx (dog) gmail (dot) com
* 
===============================================================================
= PATHFINDING FUNCTION
=------------------------------------------------------------------------------
= Version: 1.1.4
= Last changes: jul 15 (1.0.0) - first version
=               aug 09 (1.0.1) - several speed improvements, thanks tonypa
=               aug 10 (1.0.2) - even more speed improvements by tonypa (again)
=               aug 31 (1.0.3) - return NULL if error (instead of error string)
=               aug 31 (1.1.3) - added cornering option. thanks for LAlex for
=                                his suggestions
=          2004 may 28 (1.1.4) - fixed "undefined != 0" error on MX 2004 when
=                                compiling as flash 7. Thanks Inkog for finding
=                                the error and the solution
=------------------------------------------------------------------------------
= This function finds the path between two points (the START and the END point)
= on a given map, taken into account walls/obstacles and terrain costs.
=
= It uses an A* ("a star") algorithm with heuristic approximation for a faster
= result. Much of this function is basic on theory learnt from this language
= independent tutorial:
= <a href="http://www.policyalmanac.org/games/aStarTutorial.htm" target="_blank">http://www.policyalmanac.org/games/aStarTutorial.htm</a>
=------------------------------------------------------------------------------
= How to use:
=
= my_path_array = findPath (map, start_y, start_x, end_y, end_x)
=
= Parameters:
=  map = bidimensional array with rows and columns. Each cell contains a value
=        of 0 (wall) or 1+ (terrain - the higher, the more expensive to ride)
===============================================================================
*/
class Pathfinding
{	
	// Constants/configuration - change here as needed! --------------------------------
	var HV_COST = 10; // "Movement cost" for horizontal/vertical moves
	var D_COST = 14; // "Movement cost" for diagonal moves
	var ALLOW_DIAGONAL = true; // If diagonal movements are allowed at all
	var ALLOW_DIAGONAL_CORNERING = true; // If diagonal movements over corners are allowed
  
	var mapStatus:Array;
	var openList:Array;
	function Pathfinding()
	{		
	}
	
  // Complimentary functions =========================================================    
	function isOpen (y:Number, x:Number) {
    // Return TRUE if the point is on the open list, false if otherwise
    return mapStatus[y][x].open;
  };
  function isClosed (y:Number, x:Number) {
    // Return TRUE if the point is on the closed list, false if otherwise
    return mapStatus[y][x].closed;
  };
  function nearerSquare() {
    // Returns the square with a lower movementCost + heuristic distance
    // from the open list
    var minimum = 999999;
    var indexFound = 0;
    var thisF = undefined;
    var thisSquare = undefined;
    var i = openList.length;
    // Finds lowest
    while (i-->0) {
      thisSquare = mapStatus[openList[i][0]][openList[i][1]];
      thisF = thisSquare.heuristic + thisSquare.movementCost;
      if (thisF <= minimum) {
        minimum = thisF;
        indexFound = i;
      }
    }
    // Returns lowest
    return indexFound;
  };
  
  function closeSquare (y:Number, x:Number) {
    // Drop from the open list
    var len = openList.length;
    for (var i=0; i < len; i++) {
      if (openList[i][0] == y) {
        if (openList[i][1] == x) {
          openList.splice(i, 1);
          break;
        }
      }
    }
    // Closes an open square
    mapStatus[y][x].open = false;
    mapStatus[y][x].closed = true;
  };
  
  function openSquare (y:Number, x:Number, parent, movementCost, heuristic, replacing) {
    // Opens a square
    if (!replacing) {
      openList.push([y,x]);
      mapStatus[y][x] = {heuristic:heuristic, open:true, closed:false};
    }
    mapStatus[y][x].parent = parent;
    mapStatus[y][x].movementCost = movementCost;
  };
	function findPathInternal (map:Array, startY:Number, startX:Number, endY:Number, endX:Number):Array {
		// Finds the way given a certain path
		if (startY == undefined || startX == undefined) return null; // Error: no starting point
		if (endY == undefined || endX == undefined) return null; // Error: no ending point
		

		// Ok, now go back to our regular schedule. Find the path! -------------------------

		// Caches dimensions
		var mapH = map.length;
		var mapW = map[0].length;

msg16 { Xandr [+], posted: 12.10.06 12p•-, top [^] }

AS2.0 class Pathfinding
Part #2

		// New status arrays
		mapStatus = new Array();
		for (var i=0; i<mapH; i++) mapStatus[i] = new Array();

		// Now really starts
		openList = new Array();
		openSquare (startY, startX, undefined, 0);

		// Loops until there's no other way to go OR found the exit
		while (openList.length > 0 && !isClosed(endY, endX)) {
		// Browse through open squares
		var i = nearerSquare();

		var nowY = openList[i][0];
		var nowX = openList[i][1];

		// Closes current square as it has done its purpose...
		closeSquare (nowY, nowX);
		// Opens all nearby squares, ONLY if:
		for (var j=nowY-1; j<nowY+2; j++) {
		  for (var k=nowX-1; k<nowX+2; k++) {
			if (j >= 0 && j < mapH && k >= 0 && k < mapW && !(j==nowY && k==nowX) && (ALLOW_DIAGONAL || j==nowY || k==nowX) && (ALLOW_DIAGONAL_CORNERING || j==nowY || k==nowX || (map[j][nowX] != 0 && map[nowY][k]))) {
			  // If not outside the boundaries or at the same point or a diagonal (if disabled) or a diagonal (with a wall next to it)...
			  if (map[j][k] != 0) {
				// And if not a wall...
				if (!isClosed(j,k)) {
				  // And if not closed... THEN open.
				  var movementCost = mapStatus[nowY][nowX].movementCost + ((j==nowY || k==nowX ? HV_COST : D_COST) * map[j][k]);
				  if (isOpen(j,k)) {
					// Already opened: check if it's ok to re-open (cheaper)
					if (movementCost < mapStatus[j][k].movementCost) {
					  // Cheaper: simply replaces with new cost and parent.
					  openSquare (j, k, [nowY, nowX], movementCost, undefined, true); // heuristic not passed: faster, not needed 'cause it's already set
					}
				  } else {
					// Empty: open.
					var heuristic = (Math.abs (j - endY) + Math.abs (k - endX)) * 10;
					openSquare (j, k, [nowY, nowX], movementCost, heuristic, false);
				  }
				} else {
				  // Already closed, ignore.
				}
			  } else {
				// Wall, ignore.
			  }
			}
		  }
		}
		}
		// Ended
		var pFound = isClosed(endY, endX); // Was the path found?
		// Clean up temporary functions


		if (pFound) {
			// Ended with path found; generates return path
			var returnPath:Array = new Array();
			
			var nowY = endY;
			var nowX = endX;
			while ((nowY != startY || nowX != startX)) {
				returnPath.push([nowY,nowX]);
				var newY = mapStatus[nowY][nowX].parent[0];
				var newX = mapStatus[nowY][nowX].parent[1];
				nowY = newY;
				nowX = newX;
			}
			returnPath.push([startY,startX]);
			
			// First START, last END			
			returnPath.reverse();
			
			return (returnPath);
		} else {
			// Ended with 0 open squares; ran out of squares, path NOT found
			return null;
		}
	};  
	
  public static function findPath (map:Array, startY:Number, startX:Number, endY:Number, endX:Number):Array {
	  var pf:Pathfinding = new Pathfinding();
	  var ret:Array=pf.findPathInternal(map, startY,startX,endY,endX);
	  delete pf;
	  return ret
  }	
}