import java.util.ArrayList;
import java.util.Collections;

public class AStar {
	/** The set of map that have been searched through */
	private ArrayList<AITile> closed = new ArrayList<AITile>();
	/** The set of map that we do not yet consider fully searched */
	private ArrayList<AITile> open = new ArrayList<AITile>();
	/** The return path */
	private ArrayList<AITile> path = new ArrayList<AITile>();
	
	/** The map being searched */
	private AITile[][] map;
	/** The maximum depth of search we're willing to accept before giving up */
	private int maxSearchDistance;
	private int maxIterations;
	
	private int mapWidth;
	private int mapHeight;
	
	/**
	 * Create a path finder 
	 * 
	 * @param heuristic The heuristic used to determine the search order of the map
	 * @param map The map to be searched
	 * @param maxSearchDistance The maximum depth we'll search before giving up
	 */
	public AStar(AITile[][] map, int mapWidth, int mapHeight, int maxSearchDistance, int maxIterations) {
		this.map = map;
		this.mapWidth = mapWidth;
		this.mapHeight = mapHeight;
		this.maxSearchDistance = maxSearchDistance;
		this.maxIterations = maxIterations;
	}
	
	/**
	 * @see PathFinder#findPath(Mover, int, int, int, int)
	 */
	public ArrayList<AITile> findPath(int sx, int sy, int tx, int ty) {
		// easy first check, if the destination is blocked, we can't get there

		AITile[][] map = this.map;
		ArrayList<AITile> closed = this.closed;
		ArrayList<AITile> open = this.open;
		int maxSearchDistance = this.maxSearchDistance;
		int maxIterations = this.maxIterations;
		
		if (map[tx][ty].state == AITile.CLOSED) {
			return null;
		}

		// initial state for A*. The closed group is empty. Only the starting

		// tile is in the open list and it'e're already there
		map[sx][sy].cost = 0;
		map[sx][sy].depth = 0;
		closed.clear();
		open.clear();
		open.add(map[sx][sy]);
		
		map[tx][ty].parent = null;
		
		// while we haven'n't exceeded our max search depth
		int maxDepth = 0;
		// reusable declarations for this loop and nested loops
		AITile current;
		int x, y;
		int xp, yp;
		float nextStepCost;
		AITile neighbor;
		float hc;
		boolean added;
		int iterations = 0;
		while ((iterations < maxIterations) && (maxDepth < maxSearchDistance) && (open.size() != 0)) {
			iterations++;
			// pull out the first AITile in our open list, this is determined to 
			// be the most likely to be the next step based on our heuristic
			current = open.get(0);
			//System.out.println("A-Star examining tile [" + current.x + "," + current.y + "]");
			if (current == map[tx][ty]) {
				break;
			}
			open.remove(current);
			closed.add(current);
			
			// search through all the neighbors of the current AITile evaluating
			// them as next steps
			for (x = -1; x < 2; x++) {
				for (y = -1; y < 2; y++) {
					// not a neighbor, its the current tile
					if ((x == 0) && (y == 0)) {
						continue;
					}
					// if we're not allowing diagonal movement then only
					// one of x or y can be set
					if ((x != 0) && (y != 0)) {
						continue;
					}
					// determine the location of the neighbor and evaluate it
					xp = x + current.x;
					yp = y + current.y;
					if (isValidLocation(map, sx, sy, xp, yp)) {
						// the cost to get to this AITile is cost the current plus the movement
						// cost to reach this AITile. Note that the heuristic value is only used
						// in the sorted open list
						nextStepCost = current.cost;
						neighbor = map[xp][yp];
						map[xp][yp].visited = true;
						// if the new cost we've determined for this AITile is lower than 
						// it has been previously makes sure the AITile hasn'e've
						// determined that there might have been a better path to get to
						// this AITile so it needs to be re-evaluated
						if (nextStepCost < neighbor.cost) {
							if (open.contains(neighbor)) {
								open.remove(neighbor);
							}
							if (closed.contains(neighbor)) {
								closed.remove(neighbor);
							}
						}
						// if the AITile hasn't already been processed and discarded the
						// reset it's cost to our current cost and add it as a next possible
						// step (i.e. to the open list)
						if (!open.contains(neighbor) && !(closed.contains(neighbor))) {
							neighbor.cost = nextStepCost;
							neighbor.heuristic = getHeuristicCost(xp, yp, tx, ty);
							maxDepth = Math.max(maxDepth, neighbor.setParent(current));
							//System.out.println("neighbor [" + neighbour.x + "," + neighbour.y + "] now has parent [" + current.x + "," + current.y + "]");
							//Add to open in order of heuristic + cost
							hc = nextStepCost + neighbor.heuristic;
							added = false;
							for (int i = 0; i < open.size(); i++) {
								AITile tile = open.get(i);
								if (hc < tile.cost + tile.heuristic) {
									open.add(i, neighbor);
									added = true;
									break;
								}
							}
							if (!added) {
								open.add(neighbor);
							}
						}
					}
				}
			}
		}
		// since we'e've run out of search 
		// there was no path. Just return null
		if (map[tx][ty].parent == null) {
			return null;
		}
		// At this point we've definitely found a path so we can uses the parent
		// references of the map to find out way from the target location back
		// to the start recording the map on the way.
		// thats it, we have our path 
		path.clear();
		AITile target = map[tx][ty];
		while (target.x != sx || target.y != sy) {
			path.add(target);
			target = target.parent;
		}
		Collections.reverse(path);
		return path;
	}
	
	/**
	 * Check if a given location is valid for the supplied mover
	 * 
	 * @param mover The mover that would hold a given location
	 * @param sx The starting x coordinate
	 * @param sy The starting y coordinate
	 * @param x The x coordinate of the location to check
	 * @param y The y coordinate of the location to check
	 * @return True if the location is valid for the given mover
	 */
	protected boolean isValidLocation(AITile[][] map, int sx, int sy, int x, int y) {
		if ((x < 0) || (y < 0) || (x >= mapWidth) || (y >= mapHeight)) {
			return false;
		}
		if (((sx != x) || (sy != y))) {
			return (map[x][y].state != AITile.CLOSED);
		}
		return true;
	}
	
	/**
	 * Get the heuristic cost for the given location. This determines in which 
	 * order the locations are processed.
	 * 
	 * @param mover The entity that is being moved
	 * @param x The x coordinate of the tile whose cost is being determined
	 * @param y The y coordiante of the tile whose cost is being determined
	 * @param tx The x coordinate of the target location
	 * @param ty The y coordinate of the target location
	 * @return The heuristic cost assigned to the tile
	 */
	public float getHeuristicCost(int x, int y, int tx, int ty) {
		float dx = tx - x;
		float dy = ty - y;
		float result = (float) (Math.sqrt((dx*dx)+(dy*dy)) * 1.02f);
		// stupid euclidean distance.  try manhattan instead with 1/50th tiebreaker
		//float result = (Math.abs(x - tx) + Math.abs(y - ty)) * 1.02f;

		return result;
	}
}


public class AITile {
	public static final int OPEN = 0;
	public static final int CLOSED = 1;
	public static final int SELF = 2;
	public static final int TARGET = 3;
	public static final int INVALID = 4;
	
	public int state = OPEN;
	public int topLeftX;
	public int topLeftY;
	public int width;
	public int height;
	
	public int x;
	public int y;
	// A* Stuff
	public float cost;
	/** The parent of this node, how we reached it in the search */
	public AITile parent;
	/** The heuristic cost of this node */
	public float heuristic;
	/** The search depth of this node */
	public int depth;
	public boolean visited;
	
	public void resetAStar() {
		x = 0;
		y = 0;
		cost = 0f;
		parent = null;
		heuristic = 0f;
		depth = 0;
		visited = false;
	}
	
	public int setParent(AITile parent) {
		depth = parent.depth + 1;
		this.parent = parent;
		
		return depth;
	}
}

import java.util.ArrayList;import java.util.Collections;public class AStar {	/** The return path */	private ArrayList<AITile> path = new ArrayList<AITile>();	/** The map being searched */	private AITile[][] map;	/** The maximum depth of search we're willing to accept before giving up */	private int maxSearchDistance;	private int maxIterations;	private int mapWidth;	private int mapHeight;	/**	 * Create a path finder	 * 	 * @param heuristic	 *            The heuristic used to determine the search order of the map	 * @param map	 *            The map to be searched	 * @param maxSearchDistance	 *            The maximum depth we'll search before giving up	 */	public AStar(AITile[][] map, int mapWidth, int mapHeight, int maxSearchDistance, int maxIterations) {		this.map = map;		this.mapWidth = mapWidth;		this.mapHeight = mapHeight;		this.maxSearchDistance = maxSearchDistance;		this.maxIterations = maxIterations;	}	/**	 * @see PathFinder#findPath(Mover, int, int, int, int)	 */	public ArrayList<AITile> findPath(int sx, int sy, int tx, int ty) {		// easy first check, if the destination is blocked, we can't get there		AITile[][] map = this.map;		int maxSearchDistance = this.maxSearchDistance;		int maxIterations = this.maxIterations;		int mapWidth = this.mapWidth;		int mapHeight = this.mapHeight;		if (map[tx][ty].state == AITile.CLOSED) {			return null;		}		// initial state for A*. The closed group is empty. Only the starting		// tile is in the open list and it'e're already there		map[sx][sy].cost = 0;		map[sx][sy].depth = 0;		// this is where the open list starts		AITile firstOpen = map[sx][sy];		firstOpen.isAstarOpen = true;		map[tx][ty].pathParent = null;		// while we haven'n't exceeded our max search depth		int maxDepth = 0;		// reusable declarations for this loop and nested loops		AITile current;		int x, y;		int xp, yp;		float nextStepCost;		AITile neighbor;		float hc;		int iterations = 0;		while ((iterations < maxIterations) && (maxDepth < maxSearchDistance) && (firstOpen != null)) {			iterations++;			// pull out the first AITile in our open list, this is determined to			// be the most likely to be the next step based on our heuristic			current = firstOpen;			// System.out.println("A-Star examining tile [" + current.x + "," + current.y + "]");			if (current == map[tx][ty]) {				break;			}			current.isAstarOpen = false;			// This may assign firstOpen to null.			firstOpen = current.openNext;			if (firstOpen != null) {				firstOpen.openPrev = null;			}			current.isAstarClosed = true;			// search through all the neighbors of the current AITile evaluating			// them as next steps			for (x = -1; x < 2; x++) {				for (y = -1; y < 2; y++) {					// not a neighbor, its the current tile					if ((x == 0) && (y == 0)) {						continue;					}					// if we're not allowing diagonal movement then only					// one of x or y can be set					if ((x != 0) && (y != 0)) {						continue;					}					// determine the location of the neighbor and evaluate it					xp = x + current.x;					yp = y + current.y;					if (isValidLocation(map, sx, sy, xp, yp, mapWidth, mapHeight)) {						// the cost to get to this AITile is cost the current plus the movement						// cost to reach this AITile. Note that the heuristic value is only used						// in the sorted open list						nextStepCost = current.cost;						neighbor = map[xp][yp];						map[xp][yp].visited = true;						// if the new cost we've determined for this AITile is lower than						// it has been previously makes sure the AITile hasn't						// determined that there might have been a better path to get to						// this AITile so it needs to be re-evaluated						if (nextStepCost < neighbor.cost) {							// remove from open list							neighbor.isAstarOpen = false;							if (neighbor.openPrev != null) {								neighbor.openPrev.openNext = neighbor.openNext;							}							neighbor.openNext = null;							// it's neither open nor closed.							neighbor.isAstarClosed = false;						}						// if the AITile hasn't already been processed and discarded the						// reset it's cost to our current cost and add it as a next possible						// step (i.e. to the open list)						if (!neighbor.isAstarClosed && !neighbor.isAstarOpen) {							neighbor.cost = nextStepCost;							neighbor.heuristic = getHeuristicCost(xp, yp, tx, ty);							maxDepth = Math.max(maxDepth, neighbor.setParent(current));							// System.out.println("neighbor [" + neighbour.x + "," + neighbour.y + "] now has parent ["							// + current.x + "," + current.y + "]");							// Add to open in order of heuristic + cost							hc = nextStepCost + neighbor.heuristic;							// we're opening it, so let's just mark it now.							neighbor.isAstarOpen = true;							if (firstOpen == null) {								firstOpen = neighbor;							} else {								AITile tile = firstOpen;								while (true) {									// find the spot to insert it, either at the beginning, middle or end.									if (hc < tile.cost + tile.heuristic) {										// insert this node before tile										neighbor.openNext = tile;										neighbor.openPrev = tile.openPrev;										if (tile.openPrev == null) {											// head of list.											firstOpen = neighbor;										} else {											tile.openPrev.openNext = neighbor;										}										tile.openPrev = neighbor;										break;									}									if (tile.openNext == null) {										// hc was bigger than all current values - it goes on the end.										tile.openNext = neighbor;										neighbor.openPrev = tile;										break;									}									tile = tile.openNext;								}							}						}					}				}			}		}		// since we'e've run out of search		// there was no path. Just return null		if (map[tx][ty].pathParent == null) {			return null;		}		// At this point we've definitely found a path so we can uses the parent		// references of the map to find out way from the target location back		// to the start recording the map on the way.		// thats it, we have our path		path.clear();		AITile target = map[tx][ty];		while (target.x != sx || target.y != sy) {			path.add(target);			target = target.pathParent;		}		Collections.reverse(path);		return path;	}	/**	 * Check if a given location is valid for the supplied mover	 * 	 * @param mover	 *            The mover that would hold a given location	 * @param sx	 *            The starting x coordinate	 * @param sy	 *            The starting y coordinate	 * @param x	 *            The x coordinate of the location to check	 * @param y	 *            The y coordinate of the location to check	 * @return True if the location is valid for the given mover	 */	protected boolean isValidLocation(AITile[][] map, int sx, int sy, int x, int y, int mapWidth, int mapHeight) {		if ((x < 0) || (y < 0) || (x >= mapWidth) || (y >= mapHeight)) {			return false;		}		if (((sx != x) || (sy != y))) {			return (map[x][y].state != AITile.CLOSED);		}		return true;	}	/**	 * Get the heuristic cost for the given location. This determines in which order the locations are processed.	 * 	 * @param mover	 *            The entity that is being moved	 * @param x	 *            The x coordinate of the tile whose cost is being determined	 * @param y	 *            The y coordiante of the tile whose cost is being determined	 * @param tx	 *            The x coordinate of the target location	 * @param ty	 *            The y coordinate of the target location	 * @return The heuristic cost assigned to the tile	 */	public float getHeuristicCost(int x, int y, int tx, int ty) {		float dx = tx - x;		float dy = ty - y;		float result = (float) (Math.sqrt((dx * dx) + (dy * dy)) * 1.02f);		// stupid euclidean distance. try manhattan instead with 1/50th tiebreaker		// float result = (Math.abs(x - tx) + Math.abs(y - ty)) * 1.02f;		return result;	}}public class AITile {	public static final int OPEN = 0;	public static final int CLOSED = 1;	public static final int SELF = 2;	public static final int TARGET = 3;	public static final int INVALID = 4;		public int state = OPEN;	public int topLeftX;	public int topLeftY;	public int width;	public int height;		public int x;	public int y;	// A* Stuff	public float cost;	/** The parent of this node, how we reached it in the search */	public AITile pathParent;	/** The heuristic cost of this node */	public float heuristic;	/** The search depth of this node */	public int depth;	public boolean visited;	public boolean isAstarClosed;	public boolean isAstarOpen;	public AITile openNext;	public AITile openPrev;		public void resetAStar() {		x = 0;		y = 0;		cost = 0f;		pathParent = null;		heuristic = 0f;		depth = 0;		visited = false;		isAstarClosed = false;		isAstarOpen = false;		openNext = null;		openPrev = null;	}		public int setParent(AITile parent) {		depth = parent.depth + 1;		this.pathParent = parent;				return depth;	}}