package rpc.entities.pathfinder;

import java.util.ArrayList;
import java.util.PriorityQueue;

import org.newdawn.slick.Graphics;
import org.newdawn.slick.SlickException;

import rpc.entities.EntityBase;
import rpc.map.MapModule;
import rpc.objects.ObjectBase;
import rpc.objects.ObjectModule;
import rpc.resources.ResourceModule;
import rpc.resources.ResourceModule.ResourceType;
import rpc.states.StateBase;
import rpc.utilities.OrderedPair;
import rpc.utilities.Utilities;

public class PathFinder {
	private MapModule map = StateBase.getMapModule();;
	private ResourceModule resource = StateBase.getResourceModule();
	private ObjectModule object = StateBase.getObjectModule();

	private PriorityQueue<PathNode> openPathNodes = new PriorityQueue<PathNode>();
	private PriorityQueue<SearchNode> openSearchNodes = new PriorityQueue<SearchNode>();
	private PathNode basePathNode;
	private SearchNode baseSearchNode;
	private int mapWidth, mapHeight;
	
	private PathNode[][] pathNodes;
	private SearchNode[][] searchNodes;

	//For faster reading of entitylists, to find targets
	byte[][] entityMap;
	
	public PathFinder() throws SlickException{
		mapWidth = map.getMapWidth();
		mapHeight = map.getMapHeight();
		
		entityMap = new byte[mapWidth][mapHeight];
				
		pathNodes = new PathNode[mapWidth][mapHeight];
		searchNodes = new SearchNode[mapWidth][mapHeight];
		for (int x = 0; x < pathNodes.length; x++){
			for (int y = 0; y < pathNodes[x].length; y++){
				pathNodes[x][y] = new PathNode();
				searchNodes[x][y] = new SearchNode();
			}
		}
	}
		
	public ArrayList<OrderedPair> findPath(int startX, int startY, int goalX, int goalY, boolean allowBlocked) {
		if ((goalX < 0) || (goalX > map.getMapWidth()-1) || (goalY < 0) || (goalY > map.getMapHeight()-1))
			return null;
		
		//We are already here, so just return the coordinates at your feet.
		if ((startX == goalX) && (startY == goalY)){
			ArrayList<OrderedPair> returnedPath = new ArrayList<OrderedPair>();
			returnedPath.add(OrderedPair.getOrderedPair(goalX, goalY));
			return returnedPath;
		}
		
		boolean running = true;
		boolean searchBlocked = false;
		
		int pathVariance = Utilities.randomInt(10)+1;
		
		while (running){
			for (int x = 0; x < pathNodes.length; x++){
				for (int y = 0; y < pathNodes[x].length; y++){
					pathNodes[x][y].flagResettable();
					//pathNodes[x][y].resetNode(x, y, goalX, goalY, pathVariance);
				}
			}
	
			openPathNodes.clear();
			basePathNode = pathNodes[startX][startY];
			openPathNodes.add(pathNodes[startX][startY]);
			
			pathNodes[startX][startY].openNode();
			pathNodes[startX][startY].resetNode(startX, startY, goalX, goalY, pathVariance);
			
			boolean foundPath = false;
			
			while (!foundPath){
				//baseNode = openNodes.get(openNodes.size()-1);
				basePathNode = openPathNodes.poll();
				
				//Check the values around the next ordered pair.
				int thisX = basePathNode.getX();
				int thisY = basePathNode.getY();
				
				for (int x = -1; x < 2; x++) {
					y:
					for (int y = -1; y < 2; y++) {
						if ((x == 0) && (y == 0))
							continue;
						
						int checkX = thisX+x;
						int checkY = thisY+y;
						if ((checkX > map.getMapWidth()-2) || (checkX < 2) || (checkY > map.getMapHeight()-2) || (checkY < 2))
							continue;
						
						//If the node needs to be reset, reset it!
						if (pathNodes[checkX][checkY].isResettable())
							pathNodes[checkX][checkY].resetNode(checkX, checkY, goalX, goalY, pathVariance);
						
						// If it's not on the closed list, add it to the checkList to look at later.
						if (pathNodes[checkX][checkY].isClosed())
							continue;
						
						//If you're not allowed to pass blocked tiles, don't!
						if (map.getBlockMap()[checkX][checkY] > 0){
							if (searchBlocked){
								for (int l = 0; l < map.getMapLayers(); l++) {
									int tileID = map.getTileId(checkX, checkY, l);
									if (map.getMapTileLoader().isTileInvulnerable(tileID)){
										continue y;
									}
								}
							}else{
								continue y;
							}
						}
						
						//TODO: This works for now, although there are situations where when the second pass to dig a path triggers,
						//it may cause a logical shortest path to be ignored.
						//Check the diagonal movement to see if it's valid.
						if ((checkX > thisX) && (checkY > thisY)
								&& (map.getBlockMap()[checkX-1][checkY] > 0 || map.getBlockMap()[checkX][checkY-1] > 0)){
							continue;
						}else if ((checkX < thisX) && (checkY < thisY)
								&& (map.getBlockMap()[checkX+1][checkY] > 0 || map.getBlockMap()[checkX][checkY+1] > 0)){
							continue;
						}else if ((checkX > thisX) && (checkY < thisY)
								&& (map.getBlockMap()[checkX-1][checkY] > 0 || map.getBlockMap()[checkX][checkY+1] > 0)){
							continue;
						}else if ((checkX < thisX) && (checkY > thisY)
								&& (map.getBlockMap()[checkX+1][checkY] > 0 || map.getBlockMap()[checkX][checkY-1] > 0)){
							continue;
						}
						
						PathNode checkNode = pathNodes[checkX][checkY];
						//Calculate movement costs for this tile.
						//Remember terrain movement costs should also be increased on diagonals from their base, not just added.
						int movementCost = 0;
						int nodeMValue = checkNode.getM();
						if (((checkX > thisX) && (checkY > thisY))
							|| ((checkX < thisX) && (checkY < thisY))
							|| ((checkX > thisX) && (checkY < thisY))
							|| ((checkX < thisX) && (checkY > thisY))){
							movementCost = (int)(10+nodeMValue+((10+nodeMValue)*0.4));
						}else{
							movementCost = 10+nodeMValue;
						}			
						
						// We are already on the open list.
						if (checkNode.isOpen()){
							int gValueCheck = basePathNode.getG()+movementCost;
							if (gValueCheck < checkNode.getG())
								checkNode.setParent(basePathNode);
						}else{
							//Open tile.
							checkNode.openNode();
							
							//Assign parent to this tile, should be the original we're fetching
							checkNode.setParent(basePathNode);
							
							//Calc gCost (NOTE: Incomplete. Is this where terrain would come in?)
							checkNode.setG(basePathNode.getG()+movementCost);
							
							//Calc fCost
							checkNode.calcF();
							
							openPathNodes.add(checkNode);
							
							//Break if you find the goal.
							if ((checkX == goalX) && (checkY == goalY))
								return buildPath(checkNode);
						}
					}
				}
				//Close the node.
				basePathNode.closeNode();
				
				//I've searched everywhere I could, and I've ran out of nodes.
				if (openPathNodes.size() <= 0)
					break;
			}
			if (allowBlocked && !searchBlocked){
				searchBlocked = true;
			}else{
				running = false;
			}
		}
		return null;
	}
	
	/**
	 * Get a list of valid coordinates that are within the movement cost of the starting position.
	 * 
	 * @param startX - The X coordinate we will start on.
	 * @param startY - The Y coordinate we will start on.
	 * @param range - The maximum range in tiles. Note, that the value inputed will be multiplied by 10 internally
	 * for proper movement cost calculations.
	 * @param allowBlocked - If we are allowed to search through blocked tiles.
	 * 
	 * @return The movement cost map to reach all the tiles in range.
	 */
	public ArrayList<OrderedPair> getCoordinatesInRange(int startX, int startY, int range, boolean allowBlocked) {
		//Only reset nodes and maps in range, why bother with the rest?
		for (int x = startX-range; x < startX+range; x++){
			for (int y = startY-range; y < startY+range; y++){
				if ((x > 250) || (x < 2) || (y > 250) || (y < 2))
					continue;
				searchNodes[x][y].flagResettable();
			}
		}
		
		int movementCostMax = range*10;
		
		ArrayList<OrderedPair> list = new ArrayList<OrderedPair>();

		openSearchNodes.clear();
		baseSearchNode = searchNodes[startX][startY];
		openSearchNodes.add(searchNodes[startX][startY]);
		
		searchNodes[startX][startY].openNode();
		searchNodes[startX][startY].resetNode(startX, startY);
		
		boolean foundPath = false;
	
		while (!foundPath){
			//baseNode = openNodes.get(openNodes.size()-1);
			baseSearchNode = openSearchNodes.poll();
			
			//Check the values around the next ordered pair.
			int thisX = baseSearchNode.getX();
			int thisY = baseSearchNode.getY();
			
			for (int x = -1; x < 2; x++) {
				for (int y = -1; y < 2; y++) {
					if ((x == 0) && (y == 0))
						continue;
					
					int checkX = thisX+x;
					int checkY = thisY+y;
					if ((checkX > map.getMapWidth()-2) || (checkX < 2) || (checkY > map.getMapHeight()-2) || (checkY < 2))
						continue;
					
					//If the node needs to be reset, reset it!
					if (searchNodes[checkX][checkY].isResettable())
						searchNodes[checkX][checkY].resetNode(checkX, checkY);
					
					// If it's not on the closed list, add it to the checkList to look at later.
					if (searchNodes[checkX][checkY].isClosed())
						continue;
					
					SearchNode checkNode = searchNodes[checkX][checkY];
					//Calculate movement costs for this tile.
					//Remember terrain movement costs should also be increased on diagonals from their base, not just added.
					int movementCost = 0;
					int nodeMValue = checkNode.getM();
					if (((checkX > thisX) && (checkY > thisY))
						|| ((checkX < thisX) && (checkY < thisY))
						|| ((checkX > thisX) && (checkY < thisY))
						|| ((checkX < thisX) && (checkY > thisY))){
						movementCost = (int)(10+nodeMValue+((10+nodeMValue)*0.4));
					}else{
						movementCost = 10+nodeMValue;
					}						
										
					// We are already on the open list.
					if (checkNode.isOpen()){
						int gValueCheck = baseSearchNode.getG()+movementCost;
						if (gValueCheck < checkNode.getG())
							checkNode.setParent(baseSearchNode);
					}else{
						//Open tile.
						checkNode.openNode();
						
						//Assign parent to this tile, should be the original we're fetching
						checkNode.setParent(baseSearchNode);
						
						//Calc gCost and add it to the nodelist if it's below range.
						if (baseSearchNode.getG()+movementCost <= movementCostMax){
							checkNode.setG(baseSearchNode.getG()+movementCost);
							openSearchNodes.add(checkNode);
							list.add(OrderedPair.getOrderedPair(checkX, checkY));
						}
					}
				}
			}
			//Close the node.
			baseSearchNode.closeNode();
			
			//I've searched everywhere I could, and I've ran out of nodes.
			if (openSearchNodes.size() <= 0)
				break;
		}
		
		return list;
	}
	
	public ArrayList<OrderedPair> buildPath(PathNode node) {
		ArrayList<OrderedPair> returnedPath = new ArrayList<OrderedPair>();
		PathNode nextNode = node;
		OrderedPair nextPair = OrderedPair.getOrderedPair(node.getX(), node.getY());
		returnedPath.add(nextPair);
		
		while (nextNode.getParent() != null){
			nextNode = nextNode.getParent();
			nextPair = OrderedPair.getOrderedPair(nextNode.getX(), nextNode.getY());
			returnedPath.add(nextPair);
		}
		return returnedPath;
	}
	
	public ArrayList<OrderedPair> buildPath(SearchNode node) {
		ArrayList<OrderedPair> returnedPath = new ArrayList<OrderedPair>();
		SearchNode nextNode = node;
		OrderedPair nextPair = OrderedPair.getOrderedPair(node.getX(), node.getY());
		returnedPath.add(nextPair);
		
		while (nextNode.getParent() != null){
			nextNode = nextNode.getParent();
			nextPair = OrderedPair.getOrderedPair(nextNode.getX(), nextNode.getY());
			returnedPath.add(nextPair);
		}
		return returnedPath;
	}
}