import com.lalex.core.Array2;
import com.lalex.core.Point2;
class com.lalex.map.PathFinder {
	
	// Les diagonales sont autorisées ?
	public static var ALLOW_DIAG:Boolean = true;
	
	// Les diagonales traversant un coin sont autorisées ?
	public static var ALLOW_DIAG_CORNER:Boolean = false;
	
	// Cout par défaut d'un déplacement pour l'heuristique
	public static var DEFAULT_COST:Number = 10;
	
	// Utilisation des arbres binaires
	public static var BINARY_HEAPS:Boolean = false;
	
	public static function findPath(mp:Array, x0:Number, y0:Number, x1:Number, y1:Number):Array {

		// On crée un tableau a deux dimensions de la taille de la map
		var cloneMap:Array2 = new Array2(mp.length,mp[0].length);
		
		// On crée les listes ouvertes et fermées
		var openList:Array = new Array();
		var closeList:Array = new Array();
		
		// Case en cours
		var pnt = new Point2(x0,y0);

		// Le cout de la case en cours (depart) est de 0
		pnt.pathCost = 0;
		pnt.totCost = PathFinder.heuristic(mp,x0,y0,x1,y1);
		
		// On met la case en cours dans la map "clone"
		cloneMap[x0][y0] = pnt;
		// On rajoute le point de départ à la liste ouverte
		PathFinder.open(openList, pnt);
		
		// Case en cours
		var curPnt:Point2 = null;
		
		// On commence la recherche
		while (openList.length > 0) {

			// On cherche l'indice de point de la liste
			// ouverte ayant le plus faible cout F
			var nearestInd:Number = PathFinder.getLowestCostIndex(openList);

			// Le point en cours
			curPnt = openList[nearestInd];

			// Si cette case est la case d'arrivée, on arrete la boucle
			if (curPnt.compare(x1,y1)) {
				break;
			}
			
			// La case passe de la "liste ouverte" à la "liste fermée"
			PathFinder.close(nearestInd, openList, closeList);

			// On teste les case alentours
			for (var i=-1 ; i<=1 ; i++) {
				for (var j=-1 ; j<=1 ; j++) {
					// Cooronnées de la case testée
					var curX = curPnt.x+i;
					var curY = curPnt.y+j;
					// Condition pour tester la case
					// > i || j : i ou j sont différents de 0 : on est pas sur la case en cours
					// > ALLOW_DIAG || !(i && j) : soit les diagonales sont autorisées, soit on est pas sur une diagonale
					// > !cloneMap[curX][curY].close : la case testée n'est pas dans la liste fermée
					// > this[curX][curY].throwable : la case testée est "traversable"
					// > ALLOW_DIAG_CORNER || !(i && j && (!this[curX][curPnt.y].throwable || !this[curPnt.x][curY].throwable)) : soit on peut couper les coins, soit on ne coupe pas un coin actuellement
					if ((i || j) && (ALLOW_DIAG || !(i && j)) && !cloneMap[curX][curY].close && mp[curX][curY] && (ALLOW_DIAG_CORNER || !(i && j && (!mp[curX][curPnt.y] || !mp[curPnt.x][curY])))) {
						
						// On calule le cout pour arriver jusq'à la case testée (cout G)
						var curPathCost = curPnt.pathCost + Math.round(mp[curX][curY]*Math.sqrt(Math.abs(i)+Math.abs(j)));

						// Données deja connues sur la case
						var existPoint:Point2 = cloneMap[curX][curY];
						
						// Si la case testée est dans la "liste ouverte"
						// On compare les couts G (pathCost)
						if (existPoint.open) {
							// On compare les couts G (pathCost)
							// Si c'est plus avantageux, on recalcule le cout et le parent
							// de la case deja présente. Si nécessaire, on re-trie la liste
							// ouverte
							if (curPathCost < existPoint.pathCost) {
								existPoint.props  = { parent:curPnt, pathCost:curPathCost, totCost:curPathCost+existPoint.togoCost };
								PathFinder.updateOpenList(openList,existPoint);
							}
						
						// Si la case n'est pas dans la liste ouverte, on l'y ajoute
						// Et on calcule ses couts, avec la case en cours comme parent.
						} else {
							var heur:Number = PathFinder.heuristic(mp,curX,curY,x1,y1);
							var newPt:Point2 = new Point2(curX,curY, {pathCost:curPathCost, togoCost:heur, totCost:curPathCost+heur, parent:curPnt});
							cloneMap[curX][curY] = newPt;
							PathFinder.open(openList, newPt);
						}
					}
				}
			}
		}
		// curPnt contient le dernier point "minimum"
		// si ce n'est pas le point d'arrivé, c'est qu'on a pas trouvé le chemin
		if (curPnt.x != x1 || curPnt.y != y1) {
			// On retourne un objet avec le temps de calcul et un chemin vide (false)
			return;

		// Si le chemin a été trouvé, il contient donc le point d'arrivé
		} else {
			// On crée un tableau qui va contenir le chemin dans l'ordre inverse
			var returnArray:Array = new Array();
			// On commence par le point d'arrivée
			returnArray[returnArray.length] = curPnt;
			// On rajoute le parent jusqu'à arriver à une case sans parent
			// qui est forcément le point de départ
			do {
				curPnt = curPnt.parent;
				var newPt = new Point2(curPnt.x,curPnt.y);
				newPt.moveCost = curPnt.pathCost;
				returnArray[returnArray.length] = newPt;
			} while (curPnt.parent);
			// On retourne le temps et le chemin inversé (donc dans le bon ordre)
			returnArray.reverse();
			return returnArray;
		}
	}
	
	// Heuristique Manhatan
	private static function heuristic(mp:Array, x0, y0, x1, y1):Number {
		return (Math.abs(x1-x0)+Math.abs(y1-y0))*DEFAULT_COST;
	}
	
	// Ajout d'une case dans la "liste ouverte"
	private static function open(lst:Array, pnt:Point2) {
		pnt.open = true;
		pnt.close = false;
		// Un tableau représentant un arbre binaire commence à 1
		// donc si nécessaire on rempliut la case 0
		if (BINARY_HEAPS) {
			if (!lst[0]) {
				lst[0] = "nopoint";
			}
			lst[lst.length] = pnt;
			// Une fois la case insérée, on trie l'arbre
			PathFinder.sortOpenListFrom(lst,lst.length-1);
		} else {
			lst[lst.length] = pnt;
		}
	}
	
	// Lorsque l'on a recalculé le coût d'une case, il faut
	// re-trier l'arbre binaire a partir de la case modifiée
	private static function updateOpenList(lst,pnt) {
		if (BINARY_HEAPS) {
			// On cherche la position de la case modifiée
			var lstLen = lst.length;
			var curInd:Number = lstLen;
			while (curInd-- > 0) {
				if (lst[curInd].equals(pnt)) {
					break;
				}
			}
			// On trie à partir de cette case
			PathFinder.sortOpenListFrom(lst,curInd);
		}
	}
	
	// Trie l'arbre binaire à partir d'une position donnée
	// jusqu'au début
	private static function sortOpenListFrom(lst,ind) {
		if (BINARY_HEAPS) {
			var curInd:Number = ind;
			// On trie d'un enfant vers son parent
			// Si l'indice est 1, on arrete car on est en
			// haut de l'arbre
			while (curInd > 1) {
				var parInd = Math.floor(curInd/2);
				// Si le parent a un cout inferieur, on arrete le tri
				if (lst[curInd].totCost >= lst[parInd].totCost) {
					break;
				}
				var tmp:Point2 = lst[parInd];
				lst[parInd] = lst[curInd];
				lst[curInd] = tmp;
				curInd = parInd;
			}
		}
	}
	
	// Retrouve l'indice de la case ayant le cout le plus faible
	// dans la liste ouverte
	private static function getLowestCostIndex(lst:Array, trueIndex:Boolean):Number {
		// Pour les arbres binaires, c'est toujours 1
		if (BINARY_HEAPS) {
			return 1;
		}
		// Indice de la case ayant le plus faible cout "total" (F)
		var nearestInd = 0;
		// Indice de la case étudié
		var curOpenInd = lst.length;

		var min:Number = Number.MAX_VALUE;
		
		// Case en cours
		var curPnt:Point2 = null;
		while (curOpenInd--) {
			// Le point a étudier pour voir s'il a le cout le plus faible
			curPnt = lst[curOpenInd];

			// Si le cout est plus petit que le minimum actuel, on remplace
			// l'indice par celui de cette case (recherche de minimum classique)
			if (curPnt.totCost < min) {
				nearestInd = curOpenInd;
				min = curPnt.totCost;
			}
		}
		
		// La case avec le coût le plus faible devient
		// la case en cours
		return nearestInd;
	}
	
	private static function close(ind, lst, cls) {
		// Le point a "fermer"
		var pnt = lst[ind];
		
		// On change les propriétés du point
		pnt.open = false;
		pnt.close = true;
		// On rajoute le point à la liste fermée
		cls[cls.length] = pnt;
		
		// Si on utilise le BH, on retrie le tableau
		if (BINARY_HEAPS) {
			// Si on a plus d'un élément
			if (lst[2]) {
				// Le dernier élement vient en première position
				lst[1] = lst.pop();
				var curInd:Number;
				var chInd:Number = 1;
				var lstLen = lst.length;
				// Variable tampon pour les permutations
				var tmp:Point2;
				// Boucle infinie
				while(true) {
					// On permute l'élement avec un de ses deux enfants
					// (celui qui a le coût le plus faible)
					curInd = chInd;
					if (lstLen > curInd*2+1) {
						if (lst[curInd].totCost > lst[curInd*2].totCost) {
							chInd = curInd*2;
						}
						if  (lst[chInd].totCost > lst[curInd*2+1].totCost) {
							chInd = curInd*2+1;
						}
					} else if (lstLen > curInd*2) {
						if (lst[curInd].totCost > lst[curInd*2].totCost) {
							chInd = curInd*2;
						}
					}
					// Si on a pas trouvé d'enfant avec un coût
					// plus faible, on sort de la boucle
					if (curInd != chInd) {
						tmp = lst[curInd];
						lst[curInd] = lst[chInd];
						lst[chInd] = tmp;
					} else {
						break;
					}
				}
			// S'il n'y avait qu'un seul élément, on l'enlève
			} else {
				lst.pop();
			}
		// Sans les arbres binaires, on se contente
		// de supprimer la case de la liste ouverte
		} else {
			lst.splice(ind,1);
		}
	}
}