/*
 * OutdoorPathFinder
 * 
 * Find outdoor paths for the MotionManager.
 */

/**
 * Constructor.
 */
function OutdoorPathFinder(motionManager, mapPaths, mapTeleporters)
{
	this.PathFinder(motionManager, mapPaths, mapTeleporters);
	
	//The path finding work with graph. The map path are organized in nodes.
	this.pathNodes = null; //Contain a list of the path nodes (one path tile = one node)
	this.adjacencyMatrix = null; //Contains the information of how the path nodes are linked
}
copyPrototype(OutdoorPathFinder, PathFinder);

/**
 * Build a path between 2 positions (i.e.: from the current player position to a section).
 *
 * @param startPosition first grid position of the path
 * @param endPosition last grid position of the path
 * @return true if success, false if an error occurs
 */
OutdoorPathFinder.prototype.buildPathBetweenLocations = function(startPosition, endPosition)
{
	this.clearComputedPath();
	
	//Compute the adjacency matrix if it wasn't computed before
	if(this.adjacencyMatrix == null || this.pathNodes == null)
		this.buildPathGraph();
	
	//Find the path nodes associated with the start and end positions
	var startNode = -1;
	var endNode = -1;
	for(var indexNode in this.pathNodes)
	{
		var pathNode = this.pathNodes[indexNode];
		if(pathNode.x == startPosition.x && pathNode.y == startPosition.y) startNode = Number(indexNode);
		if(pathNode.x == endPosition.x   && pathNode.y == endPosition.y  ) endNode   = Number(indexNode);
	}
	if(startNode == -1 || endNode == -1) return false;
	
	//Use the dijkstra'a algorithm to find the path
	var shortestPathNodes = this.findShortestPathInGraph(startNode, endNode);
	if(shortestPathNodes == null) return false;
	
	//Convert the computed path into directions
	// (note: the shortestPathNodes is given from the end to the start)
	for(var indexNode = shortestPathNodes.length-1; indexNode > 1; indexNode--)
	{
		var pathNode = shortestPathNodes[indexNode];
		var nextPathNode = shortestPathNodes[indexNode-1];
		
		//Check if it's a tile path or a teleporter
		if(this.mapTeleporters[pathNode.y][pathNode.x] > 1)
		{
			//Set the JOKER in order to not clear the computedPath and
			// let the buildPathBetweenTeleporters function to build and add the teleporter path
			this.computedPath[pathNode.y][pathNode.x] = this.motionManager.JOKER_DIRECTION;
		}
		else
		{
			//Compute the direction
			var direction = 0;
			if(pathNode.x > nextPathNode.x) direction = this.motionManager.KEY_LEFT;
			else if(pathNode.x < nextPathNode.x) direction = this.motionManager.KEY_RIGHT;
			else if(pathNode.y > nextPathNode.y) direction = this.motionManager.KEY_UP;
			else if(pathNode.y < nextPathNode.y) direction = this.motionManager.KEY_DOWN;
			
			this.computedPath[pathNode.y][pathNode.x] = direction;
		}
	}
	
	this.lastComputedPathTilePosition = endPosition;
	
	return true;
}

/**
 * Build a graph which contains the paths.
 */
OutdoorPathFinder.prototype.buildPathGraph = function()
{
	//Build the path node list
	//
	
	this.pathNodes = new Array();
	
	//Scan all path tiles
	for(var row = 0; row < this.mapPaths.length; row++)
	{
		for(var column = 0; column < this.mapPaths[row].length; column++)
		{
			//Add the path tile to the pathNode list
			if(this.mapPaths[row][column] != 0)
				this.pathNodes.push({"x":column, "y":row});
		}
	}
	
	//Build the adjacency matrix
	//
	
	//Instanciate the array
	this.adjacencyMatrix = new Array(this.pathNodes.length);
	for(var indexNode in this.pathNodes)
		this.adjacencyMatrix[indexNode] = new Array(this.pathNodes.length);
	
	//Scan all the path nodes
	for(var indexNode in this.pathNodes)
	{
		var pathNode = this.pathNodes[indexNode];
		
		//Check if it's a teleporter or a normal path tile
		if(this.mapTeleporters[pathNode.y][pathNode.x] > 1)
		{
			//Get the exit position
			var exitPosition = this.getExitTeleporterLocation(pathNode);
			
			//Find the path node linked with this exit position
			var indexExitNode = -1;
			for(var indexSearch in this.pathNodes)
			{
				var searchPathNode = this.pathNodes[indexSearch];
				if(searchPathNode.x == exitPosition.x && searchPathNode.y == exitPosition.y)
				{
					indexExitNode = indexSearch;
					break;
				}
			}
			
			//Save the neighboor information in the adjacency matrix
			this.adjacencyMatrix[indexNode][indexExitNode] = 1;
			this.adjacencyMatrix[indexExitNode][indexNode] = 1;
		}
		else
		{
			//Scan all the other path nodes in order to find a neighboor
			for(var indexSearch in this.pathNodes)
			{
				var searchPathNode = this.pathNodes[indexSearch];
				if((pathNode.x+1 == searchPathNode.x && pathNode.y   == searchPathNode.y) ||
				   (pathNode.x-1 == searchPathNode.x && pathNode.y   == searchPathNode.y) ||
				   (pathNode.x   == searchPathNode.x && pathNode.y+1 == searchPathNode.y) ||
				   (pathNode.x   == searchPathNode.x && pathNode.y-1 == searchPathNode.y))
				{
					this.adjacencyMatrix[indexNode][indexSearch] = 1;
					this.adjacencyMatrix[indexSearch][indexNode] = 1;
				}
			}
		}
	}
}

/**
 * Look for the shortest path by using the Dijkstra's algorithm.
 * Thanks to http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
 * 
 * @param startNode index of the start tile path in this.pathNodes
 * @param endNode index of the end tile path in this.pathNodes
 * @return path node list of the shortest path
 */
OutdoorPathFinder.prototype.findShortestPathInGraph = function(startNode, endNode)
{
	//Initialization
	var d = new Array(this.pathNodes.length); // Distances computed from the starting node
	var p = new Array(this.pathNodes.length); // Preceding nodes in the path
	var setQ = new Array(); // Set of not-processed nodes
	for(var i = 0; i < this.pathNodes.length; i++)
	{
		d[i] = Number.MAX_VALUE;
		p[i] = -1;
		setQ.push(i);
	}
	d[startNode] = 0;
	
	//Processing
	while(setQ.length > 0)
	{
		//Extract the node with the shortest distance from setQ
		var u = setQ[0];
		var indexU = 0;
		for(var indexNode in setQ)
			if(d[u] > d[setQ[indexNode]])
			{
				u = setQ[indexNode];
				indexU = indexNode;
			}
		setQ.splice(indexU, 1);
		
		//Check if the graph is connected
		if(d[u] == Number.MAX_VALUE) return null;
		
		//Refresh the distances
		for(var indexNode in setQ)
		{
			var v = setQ[indexNode];
			
			if(this.adjacencyMatrix[u][v] > 0)
			{
				var alt = d[u]+this.adjacencyMatrix[u][v];
				if(alt < d[v])
				{
					d[v] = alt;
					p[v] = u;
				}
			}
		}
	}
	
	//Build the return path
	var shortestPath = new Array();
	var node = endNode;
	while(node != -1)
	{
		shortestPath.push(this.pathNodes[node]);
		node = p[node];
	}
	
	return shortestPath;
}