[PHP] Algorithme Astar sur tuile hexagonale

[Maz]

Bonjour, je suis toujours dans mon algorithme A* sur cases hexagonale:cogne:.

J'ai commencer par développer le script pour des cases carrée, puis j'ai reprogrammer la fonction "casesAdjacentes" qui renvoi les cases adjacentes à celle analysé.
Le script fonctionne (ou presque) puisqu'il arrives à trouver la case final, mais au moment de retracé le chemin, celui-ci est sacadé, voici un petit aperçu du dis problème:

Case verte: départ.
Case rouge: case cherché
Case noir: franchissable
Case bleu foncé: non-franchissable
Case bleu clair: le chemin final

Je penses que le problème est dût à l'update du parent si le score est plus faible, mais je n'arrives pas à trouver le problème...

Voici le code de ma fonction:

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;

}

Si vous voyez quelque chose de louche que je rates, même si je sais qu'un code brut comme ça est pas facile à corriger lorsqu'il n'est pas de soit-même.

[niahoo]

faudrait que tu divises un peu.

Une fonction 'liste des cases adjacentes', une 'case la plus proche d'une case X dans une liste de cases', séparer un peu la gestion des pointeurs sur tes open list / closed list

Et quand ce sera plus lisible non seulement on pourra t'aidear beaucoup plus mais tu trouveras le bug de toi-même

[popayan]

J'aimerai savoir comment tu gères les coordonnées de tes cases hexagonales?

[Maz]

Justement je suis en train de revoir ce système car actuellement, je les gères de la façon "classique". Et je suis en train de calculer pour passer sur un axe Y orienté à 60° de l'axe X et non 90°, comme ici. Ce seras certainement plus facile à gérer pour l'algorithme A star.
Je posterais mes sources si celà t'intéresses, pour l'instant j'essaie de généré une map basique pour comprendre le placement des cases.

[popayan]

Pour les coordonnées, y a ca qui pourrait t'intéresser

[Maz]

Je suis déjà tomber sur ce topic il y a quelques temps, que je n'approuves pas pour le simple fait qu'ajouter une troisième coordonnée deviendrais ingérable pour le joueur, d'autant que le troisième paramètre est obsolète:


Supprime la coordonnée Z dans chacune des cases, et tu verras que chaque cases est déjà parfaitement identifié et unique et ça revient donc à utiliser le système des deux axes orientés chacun l'un de l'autre à 60°.

[Hideaki]

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.

[Maz]

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.

Ton schéma est juste, dans ce cas là, mais quand je me suis lancé sur une map hexagonal, je ne m'attendais pas à tomber sur autant de soucis. Par exemple: les cases adjacentes dans le tableau ne sont pas les mêmes selon si x est pair ou impair, voir pièce jointe.

J'ai fait le script de façon universelle de façon à le proposer à la communauté.

Il gère déjà parfaitement:
les cases carré avec mouvement D G B H
les cases carré avec juste les diagonales (façon jeu de dames)
les cases carré avec 8 directions

Maintenant il ne me reste plus qu'à réglé ce petit soucis. J'ai quasiment fini de restructure ma carte avec le nouveau système de coordonnée, une fois que c'est fini je reprendrais ce script.

[Hideaki]

Oui cela dépend mais une petite condition est toujours mieux qu'un long calcul

Si tu pouvais simplifier ton algo (voir le post de Nihaoo) et nous fournir aussi ton algo de la fonction coût

[Maz]

Je suis en train de simplifier, en attendant, voici la fonction coutCase:

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;

}

Et maintenant que je me relis, je ne suis pas très sur de:

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

EDIT: Finalement simplifier... En fait je ne fait que déplacer du code, ajouter des intermédiaires etc... Je vais directement retranscrire mes fonctions dans une classe où se seras vraiment plus lisible.