Function to determine the path between to tiles in a 2D world.

GetPath.java

  /**
     * Calculates the path between two tiles.
     * 
     * @param dst The destination tile of the path
     * @param start The start tile of the path
     * @return A list containing all tiles of the found path
     */
    public ArrayList<Tile> getPath(Tile dst, Tile start) {
	closed.clear();
	open.clear();

	ArrayList<Tile> path = new ArrayList<Tile>();

	Tile currentStep = start;
	open.add(0, currentStep);

	float G = 0f;

	int depth = 0;
	int depthMax = 1000;

	while (true) {

	    /*
	     * Limit the amount of loops for better performance
	     */
	    if (depth >= depthMax) {
		return null;
	    }

	    /*
	     * If the tile which is currently checked (currentStep) is the
	     * destination tile search can be stopped (break). The same goes for
	     * an empty list of potential tiles suited for path (openlist).
	     */
	    if (currentStep.equals(dst)) {
		break;
	    } else if (open.isEmpty()) {
		break;
	    } else {

		/*
		 * Get tile with lowest F cost from openlist.
		 */
		currentStep = getBest();

		/*
		 * Add to closed list (already expanded).
		 */
		closed.add(currentStep);

		/*
		 * Check all neighbors of the currentstep.
		 */
		for (int i = 0; i < currentStep.getNeighbours().size(); i++) {

		    Tile neighbour = currentStep.getNeighbours().get(i);

		    if (neighbour.equals(dst)) {
			neighbour.setParent(currentStep);
			currentStep = neighbour;
			break;
		    }


		    /*
		    * If node (tile) is already in closed list ignore it.
		    */
		    if (closedList.contains(neighbour))
			continue;

		    /*
		     * Get the moving costs from the start to the
		     * neighbor.
		     */
		    G = neighbour.moveCost(currentStep);

		    if (!openList.contains(neighbour)) {
			open.add(neighbour);
		    } else if (G >= neighbour.G) {
			continue;
		    }

		    //Memorize it (Calculate total costs including heuristic)
		    //Set parent to the current step
		    neighbour.parent = currentStep;
		    neighbour.G = G;
		    neighbour.calcCostH(dst);
		    neighbour.calcCostF();
		}

	    }
	    depth += 1;
	}

	/*
	 * Build the path reversly iterating over the tiles by accessing their
	 * parent tile.
	 */
	Tile startTmp = dst;

	while (!start.equals(startTmp)) {

	    if (startTmp.getParent() == null)
		break;

	    startTmp = startTmp.getParent();
	    if (path.contains(startTmp)) {
		return null;
	    }
	    path.add(startTmp);
	}

	/*
	 * Reverse to get the path from start to dst.
	 */
	Collections.reverse(path);

	/*
	 * If no path is found return null.
	 */
	if (path.isEmpty())
	    return null;

	return path;
    }