[PHP] Algorithme Astar sur tuile hexagonale

[Hideaki]

Ta formule heuristique des coût est à changer,

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

Tu peux utiliser la même formule pour les cases carrés et hexagonales.
Concernant la forum de Manathan, je ne vois pas pourquoi tu l'as multiplier par 10 ( cela sert à rien), je te conseillerais d'utiliser la formule euclidienne qui un aspect plus naturel au déplacement.
http://fr.wikipedia.org/wiki/Distance_(m...vectoriels

Ton coût g est le coût de déplacement déjà effectué, le + 14 ou le + 10 ne sert à rien.

[Maz]

Ta formule heuristique des coût est à changer,

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

Tu peux utiliser la même formule pour les cases carrés et hexagonales.
Concernant la forum de Manathan, je ne vois pas pourquoi tu l'as multiplier par 10 ( cela sert à rien), je te conseillerais d'utiliser la formule euclidienne qui un aspect plus naturel au déplacement.
http://fr.wikipedia.org/wiki/Distance_(m...vectoriels

Ton coût g est le coût de déplacement déjà effectué, le + 14 ou le + 10 ne sert à rien.

Je multiplies par 10 car un déplacement = 10.

Le +14 et +10 servent: en fait je récupère le cout g du parent, auquel j'ajoutes 10 ou 14. Si je n'ajoutes pas 10 ou 14, g vaudras toujours 0.

[Hideaki]

Voici un lien en français http://khayyam.developpez.com/articles/algo/astar/

Ce n'est pas à ta fonction de calcul des coûts de définir g, g est le coût de déplacement déjà effectué.

[Maz]

Voici un lien en français http://khayyam.developpez.com/articles/algo/astar/

Ce n'est pas à ta fonction de calcul des coûts de définir g, g est le coût de déplacement déjà effectué.

Ok pigé. En fait je n'ai qu'à incrémenter une variable pour savoir le nombre d'itération de la boucle qui a été exécuté, et g vaudras cette variable*10(j'y tiens à mon *10 ^^')
EDIT: et oui mai snon. Comment peut-on connaître le coût de déplacement déjà effectué si on ne passe par par son parent? C'est pas pensable si on prends les diagonale = 14.

[Hideaki]

Tout simplement en le fournissant à ta fonction en paramètre, il utilise une structure, c'est pour cela que je t'ai dit de le faire en objet.

J'avoue ne pas comprendre pourquoi tu souhaites mettre un coût à 14 alors qu'il s'agit d'une case adjacente, il s'agirait d'une case particulière...

Ne fessant pas de PHP et ne voulant pas en faire, je ne pourrais pas te fournir un algo en php et ceux trouver sur le net ne me satisfait pas. Ajoute ton nouveau code simplifier clair etc et je pense que niahoo pourra t'aider facilement pour le côté php.

[Maz]

Le coût à 14 est pour déprécier les déplacement en diagonales.
Et dans le futur (lorsque ce seras opérationnelle) j'aurais surement aussi des coûts à 20, 25 etc... pour les déplacement dans de l'eau par exemple qui sont plus "long" que sur la terre ferme. Enfin l'eau c'est juste pour pousser le vice, mais je tiens à ce 14.
EDIT: et le passage en paramètre du cout du déplacement "parent", c'est déjà ce que je fait o.0

[niahoo]

peut être

En tout cas je ne comprends pas le coup des 14 puisque on est en cases hexagonales ! elles sont toutes équidistantes.

[Hideaki]

je comprends pour l'eau etc mais j'ai la même réflexion que nihaoo ^^

Edit: Pour le joueur hormis deux cases tout est en diagonal

[Maz]

peut être

En tout cas je ne comprends pas le coup des 14 puisque on est en cases hexagonales ! elles sont toutes équidistantes.

Ok, je comprends pourquoi vous vous obstiné sur ce 14 et c'est entièrement de ma faute.

Dans le soucis de proposer à la communauté un script qui gères les cases carrés & hexagonales, on peut choisir le mode, les trois premier mode sont pour les tuiles carré. Donc si on regarde de plus près:

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; parent

Ceci ne seras exécuté que sur les carte à tuile carré!

J'aurais du vous montrer la fonction casesAdjacentes, où tout est expliqué:

private function casesAdjacentes($x, $y) {

			/* Mode: 

				1: Tuile carré classique(4 directions)

				2: Tuile carré façon jeu de dames(4 diagonales)

				3: Tuile carré avancé(4 directions + 4 diagonales)

				4: Tuile hexagonal orienté verticalement(partie "plate" en haut & en bas) X pair

				5: Tuile hexagonal orienté verticalement(partie "plate" en haut & en bas) X impair -- Réservé

				6: Tuile hexagonal orienté horizontalement(partie "plate" à droite & à gauche) Y pair

				7: Tuile hexagonal orienté horizontalement(partie "plate" à droite & à gauche) Y impair -- Réservé */

			$mode = $this->mode;

			if($mode == 4 AND !is_int($x/2)) $mode = 5;

			else if ($mode == 6 AND !is_int($y/2)) $mode = 7;

			$casesAdjacentes = array();

			if(in_array($mode, array(1,3,4,5,6,7)) AND isset($this->map[$x][$y-1]) AND $this->map[$x][$y-1] == "franchissable")		// X;	Y-1

				$casesAdjacentes[] = array($x, $y-1);

			if(in_array($mode, array(2,3,4,6)) AND isset($this->map[$x+1][$y-1]) AND $this->map[$x+1][$y-1] == "franchissable")	// X+1;	Y-1

				$casesAdjacentes[] = array($x+1, $y-1);

			if(in_array($mode, array(1,3,4,5,6,7)) AND isset($this->map[$x+1][$y]) AND $this->map[$x+1][$y] == "franchissable")		// X+1; Y

				$casesAdjacentes[] = array($x+1, $y);

			if(in_array($mode, array(2,3,5,6)) AND isset($this->map[$x+1][$y+1]) AND $this->map[$x+1][$y+1] == "franchissable")	// X+1;	Y+1

				$casesAdjacentes[] = array($x+1, $y+1);

			if(in_array($mode, array(1,3,4,5,6,7)) AND isset($this->map[$x][$y+1]) AND $this->map[$x][$y+1] == "franchissable")		// X;	Y+1

				$casesAdjacentes[] = array($x, $y+1);

			if(in_array($mode, array(2,3,5,7)) AND isset($this->map[$x-1][$y+1]) AND $this->map[$x-1][$y+1] == "franchissable")	// X-1;	Y+1

				$casesAdjacentes[] = array($x-1, $y+1);

			if(in_array($mode, array(1,3,4,5,6,7)) AND isset($this->map[$x-1][$y]) AND $this->map[$x-1][$y] == "franchissable")		// X-1;	Y

				$casesAdjacentes[] = array($x-1, $y);

			if(in_array($mode, array(2,3,4,7)) AND isset($this->map[$x-1][$y-1]) AND $this->map[$x-1][$y-1] == "franchissable")	// X-1;	Y-1

				$casesAdjacentes[] = array($x-1, $y-1);

			return $casesAdjacentes;

		}

EDIT: d'ailleurs c'est éronné, celà devrait etre if $mode == 3, je viens de le corriger sur mon code local
EDIT²: vous pouvez voir le rendu pour les carte à tuiles carrés ici.

EDIT^3: après quelque F5 en mode 3, j'ai remarqué que le problème de parenté se posé ici aussi. (voir pièce jointe).

EDIT^4: et pire en mode 1... Mon script à vraiment un problème =(

EDIT^5: ma classe actuelle est la suivante: http://mazdesign.free.fr/aStar/class-highlight.html au vue des derniers rendu en mode "carré", je vais plutôt me pencher sur un problème sur la liste ouverte et non parent.

[Hideaki]

Petit conseil : au lieu de faire n modes, fait plutôt des classes représentant chaque mode(plus simple à débugger) et tu n'auras plus qu'à modifier chaque spécificité, d'autre part il sera plus simple d'ajouter de nouveau mode, comme une forme triangulaire sans tout à avoir à modifier.