function chemin(&$tableau, $xDepart, $yDepart, $xFinal, $yFinal, $mode = 1) {

	// Note : pour simplifier les traitements et pouvoir utiliser des cases comme index de tableau,

	// on utilisera une représentation sous forme de chaine dans le déroulement de l'algo

	$open = array(); // liste ouverte (cases à traiter)

	$closed = array(); // liste fermée (cases traitées)

	$f = array(); // coût f

	$parent = array(); // case parente d'une autre ($parent[$enfant] = $parent)

	

	// Valeurs initiales

	$caseDepart = "$xDepart,$yDepart"; // case de départ

	$caseFinale = "$xFinal,$yFinal"; // case d'arrivée

	$open[] = $caseDepart; // la case de départ est déjà traitée d'office

	$coutCaseDepart = coutCase($xDepart, $yDepart, $xFinal, $yFinal, $mode);

	$f[$caseDepart] = $coutCaseDepart["f"];

	$caseCourrante = $caseDepart; // case courrante

	$coutCourrant = $coutCaseDepart;

	$iCourrant = 0; // Identifiant de la case courrante, permettras de localiser $caseCourrante dans $open et $closed

	$while = 0;

	while ($caseCourrante != $caseFinale) {

		if (count($open) == 0) // si la liste ouverte est vide, alors échec dans la recherche du chemin

			return false;

		

		list($xCourrante, $yCourrante) = explode(",", $caseCourrante);

		$casesAdjacentes = casesAdjacentes($tableau, $xCourrante, $yCourrante, $mode); // On récupère la liste des cases adjacentes

		$fMin = NULL;

		$iFMin = NULL;

		$xFMin = NULL;

		$yFMin = NULL;

		foreach ($casesAdjacentes as $iCaseAnalyse => $caseAnalyse) { // On les analyse une par une

			list($xAnalyse,$yAnalyse) = $caseAnalyse;

			$coordAnalyse = "$xAnalyse,$yAnalyse";

			if(in_array($coordAnalyse, $closed)) // Si la case a déjà été traité

				continue; // On saute une itération

			$open[] = $coordAnalyse;

			if($fMin === NULL) { // Si c'est la première itération

				$iOpen = array_search($caseCourrante, $open); // On recherche dans la liste ouverte la case analysé

				$closed[] = $open[$iOpen]; // On met la case courrante dans la liste fermé

				array_splice($open, $iOpen, 1); // Et on l'enlève de la liste ouverte

				$firstIteration = false;

			}

			$coutAnalyse = coutCase($xAnalyse, $yAnalyse, $xFinal, $yFinal, $mode, $coutCourrant, $xCourrante, $yCourrante);

			if($fMin === NULL OR $fMin > $coutAnalyse["f"]) { // Si c'est la première itération ou que la case analyse a un plus faible coût que les précédentes

				$fMin = $coutAnalyse["f"];

				$iFMin = $iCaseAnalyse;

				$xFMin = $xAnalyse;

				$yFMin = $yAnalyse;

				$coutCourrant = $coutAnalyse;

			}

			if(!array_key_exists($coordAnalyse, $parent) OR $f[$coordAnalyse] > $coutAnalyse["f"]) ///////////////// ICI SERAIT LE PROBLEME...

				$parent[$coordAnalyse] = $caseCourrante;

			$f[$coordAnalyse] = $coutAnalyse["f"];

			if($caseAnalyse == $caseFinale)

				break;

		}

		$caseCourrante = "$xFMin,$yFMin";

	}

	$caseParcouru = $caseFinale;

	$cheminFinal = array();

	while($caseParcouru != $caseDepart) {

		list($xParcouru,$yParcouru) = explode(",",$caseParcouru);

		if($caseParcouru == $caseFinale)

			$tableau[$xParcouru][$yParcouru] = "arrivee";

		else

			$tableau[$xParcouru][$yParcouru] = "parcouru";

		$cheminFinal[] = $caseParcouru;

		$caseParcouru = $parent[$caseParcouru];

		if($caseParcouru == $caseDepart) {

			list($xParcouru,$yParcouru) = explode(",",$caseParcouru);

			$tableau[$xParcouru][$yParcouru] = "depart";

		}

	}

	return $parent;

}

(21-08-2011, 02:23 PM)Hideaki a écrit : Comme indiqué sur ma pièce joint, je transpose de cette manière les tuiles hexagonales en tableau.
On peut apercevoir que seul les 2 cases en diagonale ont un déplacement impossible (en un seul mouvement d'une case).
Cette transposition à l'intérêt d'être plus compréhensible pour nous humain

Pour ton code, je suis de l'avis de nihaoo ...

Tu pourrais utiliser la conception objet pour t'aider ce qui rendrait ton code plus compréhensible ou plus simple.

function coutCase($xCourrant, $yCourrant, $xFinal, $yFinal, $mode, $coutParent = NULL, $xParent = NULL, $yParent = NULL) {

	$couts = array("f" => NULL, "g" => NULL, "h" => NULL);

	if($mode <= 3) // Pour les cases carrées

		$couts["h"] = (abs($xCourrant-$xFinal)+abs($yCourrant-$yFinal))*10; // Calcul du cout H: distance de Manhattan entre la case courrante et la case finale

	else // Pour les cases hexagonales

		$couts["h"] = ceil(sqrt(($xCourrant*$xFinal)+($yCourrant*$yFinal)));

	

	if($coutParent !== NULL AND $xParent !== NULL AND $yParent !== NULL) {

		$couts["g"] = (($mode == 2) AND (!is_int(($xCourrant-$xParent)/2) OR !is_int(($yCourrant-$yParent)/2))) ? $coutParent["g"] + 14 : $coutParent["g"] + 10; // Calcul du cout G (14 si déplacement en diagonal en mode 2, sinon 10) + cout de déplacement du parent

	} else // En théorie appelé seulement pour le calcul de la case départ qui n'as aucun parent

		$couts["g"] = 0;

	$couts["f"] = $couts["h"] + $couts["g"]; // Calcul du cout total F

	return $couts;

}

$couts["h"] = ceil(sqrt(($xCourrant*$xFinal)+($yCourrant*$yFinal)));