calcul itinéraire comme Age of Empire et autres

[Sephi-Chan]

Une requête Ajax ou plus simplement :

<script type="text/javascript">

  var map = <?php echo json_encode($map); ?>;

</script>

Sephi-Chan

[dryzd]

La carte faisant 1 million de cellules, ça ne risque pas de prendre du temps et de la bande passante à l'envoyer à chaque fois que qqn veut faire des déplacements de troupes ?

[Sephi-Chan]

Si, mais je suis sûr que tu peux ruser pour fragmenter ça. Mais ça, toi seul le sait !


Sephi-Chan

[dryzd]

ben je pensais fragmenter les déplacements en étapes.
Par exemple, on pourrait calaculer un déplacement dans un périmètre de 20 cases. Ensuite, si le joueur veut aller plus loin, il rajoute une étape.
On aurait donc un premier déplacement à calculer. Puis quand le résultat de ce premier est arrivé, on calcule le second (avec comme point de départ la fin de la précédente étape).

Est-ce que ça vous semble une bonne méthode d'un point de vue technique ? Au niveau jouabilité ?

[stef]

Bonjour, voici quelques remarques/questions/opinions:

1. D'accord avec Sephi-Chan sur le "tu vas vraiment en chier".

2. L'algo A* est plus adaptée à une représentation matricielle du terrain.

3. Je n'ai pas compris le principe de la fragmentation. Comment cela marcherait-il?
- On lance l'algo avec un maillage moins dense du terrain pour trouver des points intermédiaires? (je dis ça au hasard: ça ne me paraît pas réaliste)
- On utilise une représentation vectorielle (avec les routes par exemples) pour limiter le nombre de nœuds?
- On coupe des branches de l'algo en fonction de certains seuils (du genre, on laisse tomber si on s'éloigne trop de la destination)?
- A quoi correspond le premier déplacement de 20 cases? A un point choisi par le joueur? Un peu contraignant, non?

4. Un calcul coté client peu paraître séduisant au niveau de la charge CPU mais je préfère le calcul coté serveur:
- C'est plus dans l'esprit d'un client léger vers lequel tu t'orientes.
- Ça évite le transfert de la map vers le client (qui ne doit peut-être pas tout connaître).
- C'est plus simple car moins d'aller-retours client-serveur (requête de la map + check du path).
- Ça permet de faire des choses genre:
1. Calcul d'un path pour le joueur A.
2. Le joueur A se déconnecte.
3. Un joueur B crée un obstacle sur ce path avant que A n'arrive à destination.
4. Le serveur peut recalculer un nouveau path même si A est déconnecté.
- Ca n'économise pas la création de process coté serveur puisque de toute manière, il en faudra un pour les calculs temps-réel.

5. Si tu charges le serveur de ces calculs, il reste beaucoup de questions de design. Il n'est en effet pas réaliste d'intégrer ces calculs dans la création de page: trop couteux. Alors, qui doit s'en charger?
- Le process temps-réel? S'il est schédulé à la minute, il n'aura pas forcément le temps, à moins d'un multiplexage temporel de l'algo (à chaque cycle, on ne réalise qu'un nombre fixé d'itérations), mais ça complique beaucoup les choses!
- Un ou plusieurs threads asynchrones (suivant le nombre de CPU)? C'est plus réaliste. Ça nécessite juste la gestion de file d'attente de requête de trajectoire. Les problèmes d'accès concurrent devraient être limités si tu ne communiques que par la BDD.
- Un thread par requête: ca permet à un joueur de ne pas avoir à attendre le calcul des requêtes précédentes mais attention aux problèmes mémoire car idéalement, chaque thread doit travailler avec un snapshot du terrain. Donc si tu charges tout en mémoire, que tu as 20 requêtes simultanées et 100 octets en moyenne par cellule, tu arrives à 2 GO. Ce qui ne tient pas avec un système 32 bits sous Windows. Ou alors, il faut utiliser des process différents. Mais bon, je préfère la solution précédente.

6. Ne pas oublier que si tu vises 100 joueurs simultanés, par exemple, avec un update par minute, ça te fait à peine plus d'une demi-seconde pour répondre à chacun... rien d'insurmontable mais il ne faut perdre ça de vue pendant tes devs...

[dryzd]

Salut Stef !

1. D'accord avec Sephi-Chan sur le "tu vas vraiment en chier".

Même pas peur

2. L'algo A* est plus adaptée à une représentation matricielle du terrain.

Ok, c'est donc définitivement confirmé.

3. Je n'ai pas compris le principe de la fragmentation. Comment cela marcherait-il?
(...)
- On utilise une représentation vectorielle (avec les routes par exemples) pour limiter le nombre de nœuds?

De ce que j'ai compris de A*, il commence par regarder la direction et privilégie les branches allant dans ce sens avant de traiter les autres.

- On coupe des branches de l'algo en fonction de certains seuils (du genre, on laisse tomber si on s'éloigne trop de la destination)?

Ca rejoins l'idée de limiter la taille des trajets par étape, non ?

- A quoi correspond le premier déplacement de 20 cases? A un point choisi par le joueur? Un peu contraignant, non?

Cf. plus haut, ça permettrai de limiter les tailles des trajets en les découpants par tronçons (ou étapes). 20 cases max pour une étape est purement arbritraire, ça serait à voir en fonction de la charge de calcul. Non ?

4. Un calcul coté client peu paraître séduisant au niveau de la charge CPU mais je préfère le calcul coté serveur:

Spontanément moi aussi, mais je suis ouvert à faire du côté client aussi. J'imagine plutôt le côté client pour ce qui est animations et fenêtres. Les calculs côté serveur.

5. Si tu charges le serveur de ces calculs,

Oui, et du langage : PHP ou C++ ?

il reste beaucoup de questions de design. (...)
- Un ou plusieurs threads asynchrones (suivant le nombre de CPU)? C'est plus réaliste. Ça nécessite juste la gestion de file d'attente de requête de trajectoire. Les problèmes d'accès concurrent devraient être limités si tu ne communiques que par la BDD.

Mmm ... là tu n'es pas en php. Je me trompe ?

6. Ne pas oublier que si tu vises 100 joueurs simultanés, par exemple, avec un update par minute, ça te fait à peine plus d'une demi-seconde pour répondre à chacun... rien d'insurmontable mais il ne faut perdre ça de vue pendant tes devs...

C'est vrai.

En aglo A*, j'ai trouvé ça. Il fait les diagonales, ce que je ne souhaite pas, mais ça pourrait servir de base. Sauf si ça se fait en C++. Qu'en pensez-vous ?

//*****************************************************************************************************************************************************************

// A* ou AStar est un Algorithme de Pathfinding permettant de déterminer quel est le chemin le plus court (dans la plupart des cas) entre un point de départ et un point d'arrivée en tenant compte des "obstacles"

// Le principe étant d'analyser toutes cases autour de la case courante (la première étant le départ) et leur donner des valeurs qui permettront de savoir si elles interessantes pour etre examinés afin de trouver l'arrivée 

// Ces valeurs prennent en compte la distance qui sépare (grossièrement avec la méthode Manhattan - voir les explications dans le code) la case et l'arrivée et le coût d'un déplacement pour relier une case à une autre

// Le cumul des valeurs de déplacement et de distance indique une valeur de reference (la valeur F) et donne à chaque case une évaluation qui permet de chercher le chemin

// Les cases avec le F le plus bas sont potentiellement bonnes et sont celles qui seront les suivantes à etre analysées.

// A chaque nouvelle case analysée, une case parente est indiquée pour determiner d'ou elle vient. Une case peut changer de parent (tres important) si l'analyse depuis une nouvelle case Parent montre un coût plus intéressant que précédement

// Une fois qu'une analyse tombe sur la case d'arrivée c'est qu'un chemin a été trouvé. Il suffit de remonter les Parents de chaque case depuis l'arrivée jusqu'à la case parent originale, le départ.

// Pour savoir quelles sont les cases encore a traiter on fait entrer les cases en cours d'analyse dans une Liste Ouverte. Les cases Parents entre dans une Liste Fermée et sorte de la liste Ouverte.

// Tutorial de cet Algorithme en français : http://www.lostonthepath.com/nc/03.12.2008/trd.htm

//  L'auteur original se nomme Patrick Lester et l'article original se situe à l'adresse suivante : http://www.policyalmanac.org/games/aStarTutorial.htm

// Adaptation personnelle en PHP de cet Algorithme.

//*****************************************************************************************************************************************************************

class Astar

{

	var $listeouverte;

	var $listeparent;

	var $listeferme;

	var $coutG;

	var $coutF;

	var $progressionX;

	var $progressionY;

	var $diagonal = 14; // 14 pour une preference à la diagonale | 34 pour une preference à la ligne droite quand c'est possible

	

	

	//*****************************************************************************************************************************************************************

	// Analyse des 9 neuf cases depuis la case en cours et indique pour chacune le "poids" des cases (avec les valeurs G, H et F)

	//*****************************************************************************************************************************************************************

	function neufCase($destinationX, $destinationY, &$obj_renduvisuel, $time_start)

	{

		$cp = 0;

		// Double boucle pour analyser toutes les cases autour de la courante

		for ($caseY = $this->progressionY - 1; $caseY <= $this->progressionY + 1; $caseY++)

		{

			for ($caseX = $this->progressionX - 1; $caseX <= $this->progressionX + 1; $caseX++)

			{

				// Si la case en cours d'analyse n'est pas un mur et n'est pas dans la liste ouverte 

				if (!isset($obj_renduvisuel->mur[$caseX][$caseY]) && !isset($this->listeouverte[$caseX][$caseY]))

				{

					// Si la case en cours n'est pas une case déjà analysée (liste fermée) C'est donc une case vierge 

					// On procede à son entrée en listeouverte et on note ses valeurs

					if (!isset($this->listeferme[$caseX][$caseY])) 

					{	

						// La case entre en liste ouverte, c'est à dire qu'elle est traitée et qu'elle est dans la liste des cases "regardable"

						$this->listeouverte($caseX, $caseY);

						// On indique à la case en cours d'analyse de qui elle dépend (la case en cours 'progression')

						$this->listeparent($caseX, $caseY);

						// On calcul sa valeur de déplacement (en cumulé avec la case parent)

						$this->calculcoutG($caseX, $caseY);

						// On calcul la distance de la case en cours d'analyse avec l'arrivée en additionnant le nombre de case en X et en Y

						$this->calculManathan($caseX, $caseY, $destinationX, $destinationY);

						// On calcul le F de la case, c'est à dire la valeur cumulé de G et H qui determine la qualité de la case (Un F petit est meilleur)

						$this->calculF($caseX, $caseY);

					}

				}

				// La case a déjà été analysée, elle est dans la liste ouverte (et donc) n'a jamais été une une case "Parent" 

				// On regarde si depuis la case en cours ('progression') elle est plus interessante que l'analyse précedente

				elseif (isset($this->listeouverte[$caseX][$caseY]))

				{	

					// On regarde si la case en cours d'analyse est en ligne droite ou en diagonale depuis la case en cours 'progression'

					$G = $this->testDirection($caseX, $caseY, $this->progressionX, $this->progressionY);

					

					// On verifie si depuis la case en cours 'progression' le cout en deplacement est meilleurs que celui qui existe sur cette case

					// Si c'est le cas, on recalcule le cout G, H et F et on change le parent de la case en cours d'analyse

					if ($this->coutG[$this->progressionX][$this->progressionY] + $G < $this->coutG[$caseX][$caseY])

					{	

						// La case en cours d'analyse devient Parent de la case nouvelle case 'progression'

						$this->listeparent($caseX, $caseY);

						// On racalcul la valeur G

						$this->calculcoutG($caseX, $caseY);

						// On indique la nouvelle valeur F pour la case

						$this->calculF($caseX, $caseY);

					}

				}

				

				// Verification si il reste un chemin possible

				if (!isset($this->listeouverte[$caseX][$caseY])) 

				{ 

					$cp++;

					if ($cp == 9) 

					{ 

						echo "pas de chemin possible<br>";

						$time_end = microtime(true);

						$time = $time_end - $time_start;

						$T = number_format ($time, 4);

						echo "<br>Resolution en <b>$T</b> seconde";

						exit();	

					}

				}

			}

		}

	}

	

	

 	//***********************************************************************************************************************

	// Si une case "Parent" est traitée elle entre dans la liste fermée et elle sort de la liste ouverte

	//***********************************************************************************************************************

	function listeferme()

	{	

		$this->listeferme[$this->progressionX][$this->progressionY] = array($this->progressionX, $this->progressionY);

		unset($this->listeouverte[$this->progressionX][$this->progressionY]);

	}

	

	

	//*****************************************************************************************************************************************************************

	// Fait entrer la case en cours d'analyse dans une Liste Ouverte

	//*****************************************************************************************************************************************************************

	function listeouverte($caseX, $caseY)

	{

		$this->listeouverte[$caseX][$caseY] = array($caseX, $caseY);

	}

	

	

	//************************************************************

	// Donne à une case les coordonnées de sa case parent

	//************************************************************

	function listeparent($caseX, $caseY)

	{

		$this->listeparent[$caseX][$caseY] = array ($this->progressionX, $this->progressionY);	

	}	



	

	//*****************************************************************************************************************************************************************

	// Calcul du deplacement en valeur cumulé

	//*****************************************************************************************************************************************************************

	function calculcoutG($caseX, $caseY)

	{

		// On retrouve les coordonées de la case Parent de la case en cours de traitement

		$parentX = $this->listeparent[$caseX][$caseY][0];

		$parentY = $this->listeparent[$caseX][$caseY][1];

		

		// On regarde si c'est une case en diagonal ou en ligne de droite depuis la case parent.

		$G = $this->testDirection($caseX, $caseY, $parentX, $parentY);

			

		// Si la case en cours d'anamyse n'a jamais été visité, elle prend zero pour valeur par défaut

		if (!isset($this->coutG[$caseX][$caseY]))

			{ 	$this->coutG[$caseX][$caseY] = 0;		}

			

		// Si la case parent n'a jamais eu de cout, elle prend zero comme valeur par defaut

		if (!isset($this->coutG[$parentX][$parentY]))

			{ 	$this->coutG[$parentX][$parentY] = 0;	}

			

		// On donne à la case en cours d'analyse le cumul de la case Parent + la valeur de direction

		$this->coutG[$caseX][$caseY] = $this->coutG[$parentX][$parentY] + $G;

	}

	

	

	//*****************************************************************************************************************************************************************

	// Si la case Parent à une valeur commune avec ses coordonées X ou Y c'est que c'est une droite, autrement c'est une diagonale

	//*****************************************************************************************************************************************************************

	function testDirection($caseX, $caseY, $parentX, $parentY)

	{

		if ($parentX == $caseX || $parentY == $caseY)

			{	$G = 10;	}

		else

			{	$G = $this->diagonal;	}  

		

		return $G;

	}

	

	

	//*****************************************************************************************************************************************************************

	// On determine la valeur de H par la methode dite de Manhattan c'est à dire le cumul de la distance X et Y (sans passer par une diagonale) depuis la case jusqu'à l'arrivée

	//*****************************************************************************************************************************************************************

	function calculManathan($caseX, $caseY, $destinationX, $destinationY)

	{

		// Difference entre la case en cours et la case d'arrivée

		$distx = abs($destinationX - $caseX);

		$disty = abs($destinationY - $caseY);

		

		// Cumul des 2 valeurs

		$H = $distx + $disty;

		// On multiplie le resultat pour le rendre parfaitement distinct sensible

		$this->coutH[$caseX][$caseY] = $H * 10;

	}

	

	

	//******************************************************************************************************************************************************************************

	// On donne à la case une valeur F qui est le cumul entre G et H. Cette valeur servira de reference pour savoir qu'elle doit etre la prochaine case à prendre pour la progression

	//******************************************************************************************************************************************************************************

	function calculF($caseX, $caseY)

	{

		$this->coutF[$caseX][$caseY] = $this->coutH[$caseX][$caseY] + $this->coutG[$caseX][$caseY];

	}

	

	//***********************************************************************************************************************************************************

	// Pour connaitre quelle case va etre la suivante pour tester un chemin, on determine celle qui le poid le plus petit (donc potentiellement la plus proche de l'arrivée)

	//***********************************************************************************************************************************************************

	function plusPetitF()

	{

		$distance = 9999999; // Valeur au dessus de toute par defaut

		// Pour toutes les case avec une valeur F on extrait les coordonées X et Y ($id1 et îd2)

		foreach ($this->coutF as $id1 => $contenu)

		{

			foreach ($contenu as $id2 => $contenu2)

			{

				// On garde uniquement les coordonées de la valeur F la plus petite

				if ($this->coutF[$id1][$id2] < $distance && isset($this->listeouverte[$id1][$id2]))

				{	

					// Nouvelle plus petite distance en cours de verification 

					$distance = $this->coutF[$id1][$id2]; 

					// Nouvelle coordonnées de la case "gagnante" en cours de verification 

					$this->progressionX = $id1; 

					$this->progressionY = $id2;	

				}

			}

		}

	}

}

[stef]

Ben... je n'ai toujours pas compris la fragmentation... Comment détermine-t-on les étapes? Ça nécessite de connaitre tout le path, non? Du coup, ça limite l'intérêt du tronçonnage...

Le choix du langage ne dépend pas que du pathfinding. Il faudrait connaitre toutes les specs du serveur pour choisir le plus adapté. Mais avec 1 million de cellules et un scheduling d'une minute, il se peut que tu arrives aux limites du php...

Pour l'algo, je ne sais pas les exécuter de tête. Il est surement très bien, il faut le tester...

[php_addict]

oui ben t'a essayé ce code avec 1 million de case...pour des chemins compliqué ca prends une plombe...je sais pu qui a dis mon script php de a star s'execute en 3 secondes, bein moi j'aimerais bien le voir...

je persiste: php n'est pas adapté pour le astar...surtout sur 1 million de cases...

[niahoo]

j'ai déjà vu des grilles comme ça aussi, mais je n'ai jamais réfléchi à l'implémentation ni à la construction d'une telle grille

chaque carré représente une zone dans laquelle A* n'est pas nécéssaire car on peut aller de n'importe quel point à n'importe quel autre sans obstacle.

tu peux aussi faire un tel carré sur une grande zone avec quelques petits obstacles, ou A* ne sera utilisé qu'à la rencontre de l'obstacle, pour calculer un contournement. et dans ce cas, un arbre ou un rocher ne faisant que 2-3 cases maximum, le détour n'est pas grave.

[gameprog2]

Moi ce qui me gene dans le path finding c'est que le perso a l'air de connaitre d'avance le chemin le plus court comme s'il connaissait déjà alors que c'est la premiere fois qu'il le parcourt
Comme s'il voyait les obstacles à travers les premiers obstacles.