recherche du chemin avec toroïdalité

[Xenos]

C'est pour cette raison que charger toute la carte en mémoire me semble être lourd comme méthode:

en leur passant une matrice de la taille de la map: 0/false: pas d'obstacle, 1/true: obstacle

Pour un 1440x720, on arrive vite à 80M de mémoire en PHP, ce qui me semble excessif
Après, si c'est Python/Java, je ne sais pas ce que cela donnera.
Ne charger que la bouding box (enfin, le rectangle circonscrit puisque c'est 2D) est bien plus léger (d'autant que la matrice de la map doit être chargée, probablement depuis le SQL, ce qui est assez long aussi). Si A* demande une case hors de la bouding box, on élargit cette box d'un cran.

Donc, oui, A* est adapté sur des petits chemins, mais le choix de charger toute la map dans une matrice (mot qui prend un "c" d'ailleur ^^) est bien lourd pour rien.

[niahoo]

hmmm xenos tu parles d'optimisation et ensuite d'interroger ta base de données à chaque itération de A* ?

[Xenos]

Lis tout:

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.

Et je parle plus de faisabilité que d'optimisation: suivant la taille de la carte, PHP peut manquer de mémoire vive et refuser de stocker la matrice.

[Argorate]

En étant malin, on ne stock pas les "0/false" et on laisse vide (null) les cases du tableau à double entrée, il n'est alors stocker que les cases obstacles, ce qui réduit grandement la taille mémoire.
Ensuite, ma map ne fait "que" 145*145.
Enfin, je pense faire une seule requête sql qui chope tout d'un coup, puisque c'est le même script qui fait bouger tous les mobs, ainsi j'ai qu'à récupérer et créer une seule fois la matrice d'obstacles et l'utiliser pour tous les mobs.


Sinon désolé Xenos, j'ai pas compris comment exploiter ton code, avec une taille de map de 145 donc, j'ai testé:

(20;2)->(20;144) = (-0.5;-3.5) [3.5355339059327] //sortie du var_dump

3.5355339059327 //resultat

C'est cool, mais comment j'en déduit le couple x,y de la prochaine case où je dois aller (qui ici est 20;1) ?!

[Xenos]

Remplace le % par fmod() dans modPositive, sinon la virgule sera perdue (d'où le 0.5, qui vient d'un N+0.5, perte de la virgule il reste donc N, N-0.5).

[Argorate]

Ça marche merci, voici ma version finale :

function moduloPositif($p_n, $p_mod)

{

   return fmod((fmod($p_n, $p_mod) + $p_mod), $p_mod);

}





function getVectorToroidale($x1, $y1, $x2, $y2, $limit_x, $limit_y)

{

	return [moduloPositif($x2 - $x1 + $limit_x/2, $limit_x) - $limit_x/2, moduloPositif($y2 - $y1 + $limit_y/2, $limit_y) - $limit_y/2];

}



//DANS UNE CLASSE

function getNextTile($target)

{

	$vector = getVectorToroidale($this->x, $this->y, $target->x, $target->y, 145, 145);



	if($vector[0] > 0) $vector[0] = 1;

	elseif($vector[0] < 0) $vector[0] = -1;

		

	if($vector[1] > 0) $vector[1] = 1;

	elseif($vector[1] < 0) $vector[1] = -1;

	

	return [$this->x + $vector[0], $this->y + $vector[1]];

}

enjoy, merci