recherche du chemin avec toroïdalité

[Argorate]

Bonjour,

j'aimerais bien un coup de main sur comment faire la chose suivante:

pour l'instant mes mobs se déplace en ligne droite faire un bâtiment cible, mais sans prendre en compte la toroïdalité de la map.

Du coup comment trouver le chemin en ligne droite avec des coordonnées qui peuvent être opposé, par exemple aller en "-1" revient à passé de l'autre coté en "144" en l’occurrence, du coup pour sortir la liste des cases x,y en ligne droite avec cette règle, j'ai comme un soucis^^

[Xenos]

J'ai pas bien saisis:

Tu cherches la liste des cases constituant le chemin partant de (x;y) dans une direction donnée?
Ou tu cherches le plus court chemin entre deux points (x;y) et (u;v), considérant un "recouvrement" des bords gauche/droite et haut/bas de la carte 2D?

[Thêta Tau Tau]

Il faut prendre en compte qu'un point peux avoir différentes abscisses et ordonnées, par exemple x, x-width ou x+width. Il faut donc choisir celle qu'on veux.
On va prendre l'exemple du calcul de distance :

def distance(xa, ya, xb, yb, width, height):

	xb_possibles = [xb-width, xb, xb+width]

	yb_possibles = [yb-height, yb, yb+height]

	

	dist_xa_xb_possible = [abs(xbp - xa) for xbp in xb_possibles]

	dist_ya_yb_possible = [abs(ybp - ya) for ybp in yb_possibles]

	

	#On prends le "xb_possible" le plus proche de xa

	xb_bis = xb_possibles[dist_xa_xb_possible.index(min(dist_xa_xb_possible))]

	#Meme chose pour les y

	yb_bis = yb_possibles[dist_ya_yb_possible.index(min(dist_ya_yb_possible))]

	

	#Ensuite on utilise xb_bis et yb_bis comme on ferait sur une carte rectangle.

	#La seule difference c'est qu'on peux avoir des valeurs de x ou y negatives ou

	#superieures a widht/height donc si on veut recuperer des coordonees il faut

	#faire un modulo width/height

	

	

	 #Calcul classique d'une distance avec Pythagore, juste pour l'exemple 

	return ( (xa-xb_bis)**2 + (ya-yb_bis)**2 )**0.5

On peux aussi utiliser un algorithme A* de la même façon qu'avec une carte rectangle, juste en prenant en compte que "les bords se touchent".

[Xenos]

Oui, mais s'il ne cherche que le chemin en ligne droite, alors A* est très lourd pour rien: il n'y a aucun obstacle et aucune variation de l'indice de réfraction (ouais, j'suis pas sûr du nom, disons qu'on n'a pas à prendre en compte le fait que traverser un marais prenne plus de temps que rouler sur une route en bitume).

Sinon, s'il s'agit d'un vrai chemin, oui, ton A* modifié me semble être la bonne solution.
Pour gérer le bouclage, j'ai de mon coté stocké, pour chaque case, l'identifiant des cases qui lui sont voisines. Ainsi, je sais directement que la case (0,10) est voisine de la case (1439,11), de l'autre coté de la carte. On sépare ainsi clairement la création de la carte de son utilisation: peut importe la forme réelle de la carte (tore, 2D simple, sphère,...) le jeu et le mob ne se focaliseront que sur le test "quelles sont les cases voisines de celle où je suis".

Pour générer les données de voisinages, j'ai d'abord généré le voisinage général ( la case [x,y] est voisine des quatre cases [x+/-1,y+/-1] formant ainsi un damier), et j'ai ensuite traité les cas particuliers des bords (bouclage X ou bouclage Y), puis le cas particulier des sommets ( [0,0], [X,0], [0,Y], [X,Y] avec X Y la taille de carte).

Sinon, pour la ligne droite, je te rédige le code utilisable...
<codage en cours...>

[Thêta Tau Tau]

J'avais lu trop vite ton message Xenos, je sais pas pourquoi j'avais cru que ça parlait de pathfinding (du coup j'ai édité mon post pour que ce soit plus clair).

Sinon pour expliquer un peu mon script, je me représente pas la carte comme un tore mais comme une carte rectangle répétée à l'infinie (ça reviens au même). Mon script va simplement calculer les coordonées de la "copie" du point B la plus proche du point A.
J'ai utilisé ces coordonées pour un calcul de distance par flemme de faire le script pour avoir les coordonées des cases du trajet. Argorate ayant déjà fait cette partie là il aura pas de mal à mixer mon script et le sien.

[Xenos]

Code de principe

Principe pour trouver la ligne droite entre A(Ax,Ay) et B(Bx, By) dans une carte de taille [X,Y] dont le bord droit rejoint le gauche et dont le bord haut rejoint le bas:

Code :

X = (Bx - Ax + X/2) % X - X/2
Y = (By - Ay + Y/2) % Y - Y/2

Démonstration rapide

(Bx - Ax) est un réel quelconque, de ]-infinity .. 0 .. +infinity[
(Bx - Ax + X/2) ∈ ]-infinity .. X/2 .. +infinity[
(Bx - Ax + X/2) % X ∈ [0 .. X/2 .. X[
(Bx - Ax + X/2) % X - X/2 ∈ [-X/2 .. 0 .. X/2[
Ce dernier intervalle est centré autour de zéro, et de rayon X/2, le rayon de la carte en abscisse. Idem sur Y. On obtient donc un vecteur dont les coordonnées sont toutes deux inférieures au rayon de la carte (en valeur absolu), et on a bien le bouclage.






Code PHP complet

Use case complet en PHP, la classe TorusVectorCalculator en est le coeur; attention au modulo négatif de PHP.

<?php

	interface IVector2D

	{

		public function __construct($p_x, $p_y);	// constructeur, (abscisse; ordonnée)

		public function getX();						// get abscisse

		public function getY();						// get ordonnée

		public function setX($p_x);					// set abscisse

		public function setY($p_y);					// set ordonnée

		public function getLength2();				// longueur au carré

		public function getLength();				// longueur du vecteur

	}

	

	interface IVectorCalculator			// Calcul vectoriel dans une carte

	{

		public function getAB(\IVector2D $p_A, \IVector2D $p_B);		// renvoit le vecteur AB dans la carte

	}

	

	/**

	 *  Vecteur 2D classique, quelque soit le repère

	 */

	class vec2d implements IVector2D

	{

		protected $x, $y;

		public function __construct($p_x, $p_y)

		{

			$this->setX($p_x);

			$this->setY($p_y);

		}

		public function getX()

		{

			return $this->x;

		}

		public function getY()

		{

			return $this->y;

		}

		public function setX($p_x)

		{

			$this->x = (double)$p_x;

		}

		public function setY($p_y)

		{

			$this->y = (double)$p_y;

		}

		public function __toString()

		{

			return '('.$this->getX().';'.$this->getY().')';

		}

		public function getLength2()

		{

			return ($this->getX()*$this->getX() + $this->getY()*$this->getY());

		}

		public function getLength()

		{

			return sqrt($this->getLength2());

		}

	}

	/**

	 *  Calculateur vectoriel dans un espace type "tore"

	 */

	class TorusVectorCalculator implements IVectorCalculator

	{

		const tailleX = 1000; // taille de la carte à l'horizontale

		const tailleY = 800; // taille de la carte à la verticale

		

		public function getAB(\IVector2D $p_A, \IVector2D $p_B)

		{

			$ABVector = new vec2d(

				modPositive($p_B->getX() - $p_A->getX() + $this::tailleX/2, $this::tailleX) - $this::tailleX/2,

				modPositive($p_B->getY() - $p_A->getY() + $this::tailleY/2, $this::tailleY) - $this::tailleY/2

			);

				

			var_dump($p_A . '->' . $p_B . ' = ' . $ABVector . ' ['.$ABVector->getLength().']');

			// ouais, le var_dump ne devrait pas être dans la classe mais bon, tant pis

			

			return $ABVector;

		}

	}

	/**

	 *  Renvoie le reste dans la division euclidienne de $p_n par $p_mod

	 *  Ou, autrement dit, le modulo mais toujours positif

	 */

	function modPositive($p_n, $p_mod)

	{

		// return ($p_n % $p_mod);		// PHP renvoie le modulo dans ]-mod .. +mod[

		return (($p_n % $p_mod) + $p_mod)%$p_mod;

	}

	/**

	 *  Teste si $p_value = $p_expected

	 */

	function test($p_value, $p_expected)

	{

		assert($p_value == $p_expected);

	}

	

	//

	// Tests du calculateur vectoriel

	// Les 2 derniers comparent les carrés des distances, car leur racine ne serait pas un entier

	// et comparer des flottants, on oublie !

	//

	test( (new TorusVectorCalculator())->getAB(new vec2D(120, 100), new vec2D(200, 100))->getLength(), 80);

		// le bouclage n'influe pas

	test( (new TorusVectorCalculator())->getAB(new vec2D(120, 100), new vec2D(900, 100))->getLength(), 220);

		// bouclage horizontal seul

	test( (new TorusVectorCalculator())->getAB(new vec2D(900, 100), new vec2D(120, 100))->getLength(), 220);

		// bouclage horizontal seul

	test( (new TorusVectorCalculator())->getAB(new vec2D(120, 100), new vec2D(120, 700))->getLength(), 200);

		// bouclage vertical seul

	test( (new TorusVectorCalculator())->getAB(new vec2D(120, 700), new vec2D(120, 100))->getLength(), 200);

		// bouclage vertical seul

	test( (new TorusVectorCalculator())->getAB(new vec2D(120, 100), new vec2D(900, 700))->getLength2(), 88400);

			// les 2 bouclages

	test( (new TorusVectorCalculator())->getAB(new vec2D(900, 700), new vec2D(120, 100))->getLength2(), 88400);

			// les 2 bouclages

	

	// Test si A et B sont hors de la carte

	// La distance ne doit pas changer

	test( (new TorusVectorCalculator())->getAB(new vec2D(900+4*1000, 700+2*800), new vec2D(120-6*1000, 100-4*800))->getLength2(), 88400);

			// les 2 bouclages

	test( (new TorusVectorCalculator())->getAB(new vec2D(900+4*1000, 700-2*800), new vec2D(120-6*1000, 100+4*800))->getLength2(), 88400);

			// les 2 bouclages

	test( (new TorusVectorCalculator())->getAB(new vec2D(900-4*1000, 700+2*800), new vec2D(120+6*1000, 100-4*800))->getLength2(), 88400);

			// les 2 bouclages

	test( (new TorusVectorCalculator())->getAB(new vec2D(900-4*1000, 700-2*800), new vec2D(120+6*1000, 100+4*800))->getLength2(), 88400);

			// les 2 bouclages



	// Résultats:

	// string '(120;100)->(200;100) = (80;0) [80]' (length=34)

	// string '(120;100)->(900;100) = (-220;0) [220]' (length=37)

	// string '(900;100)->(120;100) = (220;0) [220]' (length=36)

	// string '(120;100)->(120;700) = (0;-200) [200]' (length=37)

	// string '(120;700)->(120;100) = (0;200) [200]' (length=36)

	// string '(120;100)->(900;700) = (-220;-200) [297.32137494637]' (length=52)

	// string '(900;700)->(120;100) = (220;200) [297.32137494637]' (length=50)

	// string '(4900;2300)->(-5880;-3100) = (220;200) [297.32137494637]' (length=56)

	// string '(4900;-900)->(-5880;3300) = (220;200) [297.32137494637]' (length=55)

	// string '(-3100;2300)->(6120;-3100) = (220;200) [297.32137494637]' (length=56)

	// string '(-3100;-900)->(6120;3300) = (220;200) [297.32137494637]' (length=55)

	//

	// Tous les tests validés

?>

---

Proposition de correction du code Python

Pour le code Python proposé, si A et B sont tous deux hors de la carte central, il y a un problème, non?

Si la carte fait 1000x1000, mais que A est en (-10.000, -10.000) et B en (10.000, 10.000), alors le calcul n'est plus correct.
Il faudrait ajuster les "xb_possibles" avec le modulo de la taille de la carte:

	xb_mod = [xb % width]

	yb_mod = [yb % width]

	xa_mod = [xa % width]

	ya_mod = [ya % width]



	# On remplace ensuite les xb, yb, xa, ya du code de ThetaTauTau par le *_mod correspondant

	# Je ne connais pas bien le Python, donc je ne suis pas certain de ma syntaxe !

[Thêta Tau Tau]

Code :

X = (Bx - Ax + X/2) % X - X/2
Y = (By - Ay + Y/2) % Y - Y/2

Je me disait bien qu'il y avait plus simple que ce que je faisait.
Du coup vous pouvez oublier mon script.

[Argorate]

ok je testerais ça ce soir chez moi, merci !

Mais puisque vous semblez chaud. A terme je comptais mettre un algorithme de vrai pathfinding (A*) pour les mobs, en leur passant une matrisse de la taille de la map: 0/false: pas d'obstacle, 1/true: obstacle, et ainsi prendre ainsi en compte les batiments, joueurs, mines... etc. Car pour l'instant ils vont tout droit comme des neuneux, ce qui amene des situations idiotes du genre ils sont autorisés a traverser les murs...^^

Si vous avez une idée de comment inclure la toroidalité dans un algo A*, je suis preneur !

merci.

[Xenos]

Avec exactement le même principe que plus haut ou que thetaTauTau l'a suggéré:

au lieu de dire "A* est en M[x,y] et il teste M[x±1, y±1]", tu changes pour
"A* est en M[x,y] et il teste M[(x±1)%X, (y±1)%Y]"

avec X, Y la taille de la carte, et % l'opération modulo positif (aka -5%3 = 1 et pas -2).

Utiliser une matrice, même avec des booléens, me semble assez lourd, surtout si tu utilises PHP, qui est un vrai boulet pour ce qui est de l'optimisation mémoire (à part les chaînes de caractères, tout prend une place de dingue en mémoire je crois).
De mon coté, j'ai stocké les liens entre les cases ("on peut aller de la case ... à la case ..."). Partant de là, si je veux implémenter A*, à chaque étape de calcul je peux interroger la BDD pour récupérer les cases voisines de la case en cours de test. L'intérêt est qu'A* utilise bien un graphe, quelconque, et que l'algorithme implémenté n'est alors plus dépendant de la forme de la carte: je peux changer de forme de carte sans difficulté

Une petite variante pour éviter de faire une requête SQL à chaque case à récupérer peut consister à extraire seulement les cases qui se trouvent dans la bouding box et de ne récupérer une "couche" supplémentaire de cases (aka, élargir la bounding box et récupérer les cases qui se trouvent dans l'intervalle) que si le besoin s'en fait sentir.

Je me demande si certains SGDB n'auraient pas A* directement implémenté...

[Thêta Tau Tau]

Le grand intérêt de A* c'est que c'est très très simple et que pour la plupart des utilisations ça fait très bien l'affaire.
Pour se déplacer sur 10 cases en faisant le tour d'un bâtiment doit pas y avoir trop de problèmes de performances même avec un A* bourrin.

Après pour des déplacement vraiment longs, avec de gros détours, des cul de sacs etc. faut pas utiliser A* mais d'autres algorithmes plus performants, mais beaucoup plus complexes.