text: /*
  	@source https://github.com/qiao/PathFinding.js/
  */
  
  	/**
  	 * Backtrace according to the parent records and return the path.
  	 * (including both start and end nodes)
  	 * @param {Node} node End node
  	 * @return {Array.<Array.<number>>} the path
  	 */
  	export function backtrace(node) {
  		var path = [node];
  		while (node._parent) {
  			node = node._parent;
  			path.push(node);
  		}
  		return path.reverse();
  	}
  
  	/**
  	 * Backtrace from start and end node, and return the path.
  	 * (including both start and end nodes)
  	 * @param {Node}
  	 * @param {Node}
  	 */
  	export function biBacktrace(nodeA, nodeB) {
  		var pathA = this.backtrace(nodeA),
  			pathB = this.backtrace(nodeB);
  		return pathA.concat(pathB.reverse());
  	}
  
  	/**
  	 * Compute the length of the path.
  	 * @param {Array.<Array.<number>>} path The path
  	 * @return {number} The length of the path
  	 */
  	export function pathLength(path) {
  		var i, sum = 0, a, b, dx, dy;
  		for (i = 1; i < path.length; ++i) {
  			a = path[i - 1];
  			b = path[i];
  			dx = a[0] - b[0];
  			dy = a[1] - b[1];
  			sum += Math.sqrt(dx * dx + dy * dy);
  		}
  		return sum;
  	}
  
  
  	/**
  	 * Given the start and end coordinates, return all the coordinates lying
  	 * on the line formed by these coordinates, based on Bresenham's algorithm.
  	 * http://en.wikipedia.org/wiki/Bresenham's_line_algorithm#Simplification
  	 * @param {number} x0 Start x coordinate
  	 * @param {number} y0 Start y coordinate
  	 * @param {number} x1 End x coordinate
  	 * @param {number} y1 End y coordinate
  	 * @return {Array.<Array.<number>>} The coordinates on the line
  	 */
  	export function interpolate(x0, y0, x1, y1) {
  		var abs = Math.abs,
  			line = [],
  			sx, sy, dx, dy, err, e2;
  
  		dx = abs(x1 - x0);
  		dy = abs(y1 - y0);
  
  		sx = (x0 < x1) ? 1 : -1;
  		sy = (y0 < y1) ? 1 : -1;
  
  		err = dx - dy;
  
  		while (x0 !== x1 || y0 !== y1) {
  			line.push([x0, y0]);
  
  			e2 = 2 * err;
  			if (e2 > -dy) {
  				err = err - dy;
  				x0 = x0 + sx;
  			}
  			if (e2 < dx) {
  				err = err + dx;
  				y0 = y0 + sy;
  			}
  		}
  
  		return line;
  	}
  
  
  	/**
  	 * Given a compressed path, return a new path that has all the segments
  	 * in it interpolated.
  	 * @param {Array.<Array.<number>>} path The path
  	 * @return {Array.<Array.<number>>} expanded path
  	 */
  	export function expandPath(path) {
  		var expanded = [],
  			len = path.length,
  			coord0, coord1,
  			interpolated,
  			interpolatedLen,
  			i, j;
  
  		if (len < 2) {
  			return expanded;
  		}
  
  		for (i = 0; i < len - 1; ++i) {
  			coord0 = path[i];
  			coord1 = path[i + 1];
  
  			interpolated = this.interpolate(coord0[0], coord0[1], coord1[0], coord1[1]);
  			interpolatedLen = interpolated.length;
  			for (j = 0; j < interpolatedLen - 1; ++j) {
  				expanded.push(interpolated[j]);
  			}
  		}
  		expanded.push(path[len - 1]);
  
  		return expanded;
  	}
  
  
  	/**
  	 * Smoothen the give path.
  	 * The original path will not be modified; a new path will be returned.
  	 * @param {PF.Grid} grid
  	 * @param {Array.<Array.<number>>} path The path
  	 */
  	export function smoothenPath(grid, path) {
  		var len = path.length,
  			x0 = path[0][0],        // path start x
  			y0 = path[0][1],        // path start y
  			x1 = path[len - 1][0],  // path end x
  			y1 = path[len - 1][1],  // path end y
  			sx, sy,                 // current start coordinate
  			ex, ey,                 // current end coordinate
  			newPath,
  			lastValidCoord,
  			i, j, coord, line, testCoord, blocked;
  
  		sx = x0;
  		sy = y0;
  		newPath = [[sx, sy]];
  
  		for (i = 2; i < len; ++i) {
  			coord = path[i];
  			ex = coord[0];
  			ey = coord[1];
  			line = this.interpolate(sx, sy, ex, ey);
  
  			blocked = false;
  			for (j = 1; j < line.length; ++j) {
  				testCoord = line[j];
  
  				if (!grid.isWalkableAt(testCoord[0], testCoord[1])) {
  					blocked = true;
  					break;
  				}
  			}
  			if (blocked) {
  				lastValidCoord = path[i - 1];
  				newPath.push(lastValidCoord);
  				sx = lastValidCoord[0];
  				sy = lastValidCoord[1];
  			}
  		}
  		newPath.push([x1, y1]);
  
  		return newPath;
  	}
  
  
  	/**
  	 * Compress a path, remove redundant nodes without altering the shape
  	 * The original path is not modified
  	 * @param {Array.<Array.<number>>} path The path
  	 * @return {Array.<Array.<number>>} The compressed path
  	 */
  	export function compressPath(path) {
  
  		// nothing to compress
  		if (path.length < 3) {
  			return path;
  		}
  
  		var compressed = [],
  			sx = path[0][0], // start x
  			sy = path[0][1], // start y
  			px = path[1][0], // second point x
  			py = path[1][1], // second point y
  			dx = px - sx, // direction between the two points
  			dy = py - sy, // direction between the two points
  			lx, ly,
  			ldx, ldy,
  			sq, i;
  
  		// normalize the direction
  		sq = Math.sqrt(dx*dx + dy*dy);
  		dx /= sq;
  		dy /= sq;
  
  		// start the new path
  		compressed.push([sx,sy]);
  
  		for (i = 2; i < path.length; i++) {
  
  			// store the last point
  			lx = px;
  			ly = py;
  
  			// store the last direction
  			ldx = dx;
  			ldy = dy;
  
  			// next point
  			px = path[i][0];
  			py = path[i][1];
  
  			// next direction
  			dx = px - lx;
  			dy = py - ly;
  
  			// normalize
  			sq = Math.sqrt(dx*dx + dy*dy);
  			dx /= sq;
  			dy /= sq;
  
  			// if the direction has changed, store the point
  			if (dx !== ldx || dy !== ldy) {
  				compressed.push([lx,ly]);
  			}
  		}
  
  		// store the last point
  		compressed.push([px,py]);
  
  		return compressed;
  	}
  
  