Bonjour,

Ce sujet est plus une question d'algorithmique que de Java, mais je ne vois pas trop ou poster...

J'ai donc implémenté A*, pour qu'une unité trouve le chemin le plus court pour aller d'un point A à un point B. (sans obstacles pour cet exemple)
Mon code fonctionne parfaitement
Mais j'ai quand même un problème
http://nsa20.casimages.com/img/2010/11 [...] 211195136.jpg
Regardez cette image. Pour aller du point orange en bas à celui en haut, les 2 chemins (rouge et bleu) sont valables et sont identiques niveau longueur!
Mais si mon unité emprunte le chemin bleu, son mouvement sera saccadé, ça ne fait pas très naturel. Tandis que le chemin rouge, avec un seul changement de direction ne choque pas.
Mais A* en prend un au hasard, puisque qu'ils ont la même longueur.

Donc est ce que vous auriez des idées sur la façon d'améliorer mon algorithme? (que je veux bien poster, mais je n'en vois pas trop l'intérêt, et si vous répondez, c'est que vous devez connaitre son fonctionnement )

merci!

Tu peux demander à ton algorithme de générer tous les chemins ayant la longueur la plus petite. Ensuite, tu fais une fonction qui calcule le nombre de changements de direction pour chaque chemin et tu sélectionnes le meilleur.

Edit: Exemple:

class Path{
	private Point[] path;
	
	public Path(Point[] p){
		path=p;
	}
	
	public int directionChangeCount(){
		if(path.length<1)
			return 0;
		int dcc=0;
		int lastdirx=path[1].getX()-path[0].getX();
		int lastdiry=path[1].getY()-path[0].getY();
		for(int i=2; i<path.length; i++){
			int curdirx=path[i].getX()-path[i-1].getX();
			int curdiry=path[i].getY()-path[i-1].getY();
			
			if(curdirx!=lastdirx || curdiry!=lastdiry)
				dcc++;
			
			lastdirx=curdirx;
			lastdiry=curdiry;
		}
			
			return dcc;
	}
}

Merci, j'avais pas pensé à faire ça.
L'idée est bonne, je vais essayer de mettre ça en place

Je profite de ce sujet pour poser une autre question sur A*: il parait que A* est optimisé... et bien pas chez moi
Et encore, la recherche du chemin avec le moins de changement de direction (voir réponse de Nadrieril) n'est pas encore incorporé au programme.

j'ai un plateau de 80 cases sur 80 cases.
Quand je demande des petites distances, ça va. Mais quand je veux faire traverser le plateau à mon unité en diagonale, l'algorithme me passe toutes les cases en revues, et ça met 1 à 2 secondes à calculer.
Et il n'y a pour l'instant qu'une unité qui calcule à la fois! Alors avec 50...

Alors je me doute bien que quelque chose ne va pas dans mon algorithme, mais quoi? J'ai pourtant a peu près suivit les conseils du tuto de ce site.
j'ai essayé d'enlever tout ce qui pourrait faire ralentir le programme (calcul de collision dans A* par exemple), et je n'ai laissé que l'essentiel (calcul de poids de la case, liste fermée et ouverte, c'est tout)
Et pourtant, ça lag.
A* est il adapté pour des plateaux de cette taille? Une idée sur le défaut de mon algorithme?

merci!

Salut,
tout d'abord il faut savoir que l'algorithme a* est un algorithme avec Heuristique donc les performances dépende grandement de ton heuristique.
Ensuite, l'algorithme est optimal donc il trouve toujours le chemin optimal. par contre il y a de nombreux algorithme qui vont sacrifié cette optimalité pour plus de performance (par exemple le BestFirstSearch).

Bonne continuation.

Citation

un algorithme avec Heuristique

c'est à dire?^^ Que ça dépend de la façon dont on le programme???

Je vais le clarifier et je vous posterais mon algo tout à l'heure ou demain, pour que vous puissiez me conseiller.
Et je vais aussi me renseigner sur les autres algos existants.
Mais c'est vrai que là j'ai une précison optimale, presque au pixel près, donc je peux sacrifier un peu de précision.

Mon jeu est un jeu de stratégie en temps réel: donc une centaine d'unité peuvent avoir à chercher leur chemin en même temps...

EDIT: 1 à 2 seconde j'ai exagéré: pour 3500 nodes ajoutées à la liste fermée, l'algo met 360 millisecondes.
Et juste 2 ms si la node est proche.
Mais c'est quand même beaucoup trop!!!

salut,
une heuristique est une estimation du coup restant. s'est se qu'utilise l'algorithme A*. donc plus l'heuristique est réaliste plus le calcule est rapide!

je te conseil de lire ces 2 bref article sur wikipedia:
A*
Heuristique
Autres algo plus performant mais pas optimal:
Greedy best first search

Comme promis, le code (un peu long )
Je vous explique rapidement le fonctionnement:
D'abord, vous avez l'algo en lui même, et en bas, toutes les fonctions auxquelles il fait appel.
J'ai un tableau de Case: ce sont les cases qui sont dessinées, avec unités, décors, etc
Et un tableau de Node: ce sont elles qui servent à l'algo (j'utilise une classe interne, elles ont juste 4 paramètres)

1) je prends la node de la liste ouverte ayant le poids le plus petit
2) j'en fait le tour, je regarde si une unité se trouvant en son centre pourrait aller au centre des cases adjacentes
==> j'utilise pour cela la méthode intersects() de Polygon (je trace donc plusieurs polygon). Ceci se fait dans la méthode collision()
3) Si il n'y a pas de collision (et que le node n'est pas dans la liste fermée), je là met à jour, à l'aide de la méthode attribuerPoids()
==>
* D est la distance parcourue depuis le départ
* A la distance restante à "vol d'oiseau"
* F le poids, la somme de A et de D
* parent la node parent
4) On fait ça jusqu'à ce que la node d'arrivée soit testée
==> on arrête tout, on prends la node d'arrivée, et grâce aux parent, on crée un tableau de Point appelé destinations[], que l'on envoie à l'unité qui veut se déplacer.

Voilà... Faire le tour d'une node (et donc en tester 8) prend environ 0,33 millisecondes.
Multiplié par 2500, ça fait beaucoup.

Mon code n'est certainement pas des plus clair, mais je ne pense pas non plus que ce soit illisible, surtout que vous n'avez pas besoin de le lire en entier. Si vous ne comprenez pas, n'hésitez pas à demander.
--------
ok Ligarnes, merci, j'ai tout lu
Tu peux me donner ton avis sur mon heuritique donc?
Je me renseigne sur les autres types d'algo.


edit: le code est mal... incrémenté? Je sais plus comment on dit, quand les lignes ne sont pas alignés^^
C'est pas ma faute, sur eclipse j'ai fait ctrl+I, mais ça décale avec les balises je pense...

class Node{
		int D = 0;
		int F,  A, ligne, colonne; // force, distance parcourue depuis le départ et distance restante à vol d'oiseau jusqu'à l'arrivée
		Node parent; // les parents serviront à tracer le chemin départ-arrivée

	};
if (bouton == 1){ // (clic droit)	
			Node[][] nodes = new Node[colonnes][lignes];
			for (int i=0; i < colonnes; i++){						
				for (int v=0; v < lignes; v++){						
					nodes[i][v] = new Node();
					nodes[i][v].colonne = i;
					nodes[i][v].ligne = v;
				}}			
			Node nodeArrivee = nodes[chercherColonne(x, y)][chercherLigne(x, y)];	

			// pour chaque unité
			for (Unite unite: selection){
				ArrayList<Node> ouverte = new ArrayList<Node>();
				ArrayList<Node> fermee = new ArrayList<Node>();


				// ajoute la node de départ à la liste ouverte
				Node nodeDepart = nodes[chercherColonne( unite.getLosange().getPoint(1)[0], unite.getLosange().getPoint(0)[1])][chercherLigne( unite.getLosange().getPoint(1)[0], unite.getLosange().getPoint(0)[1])];
				Case caseTestee = cases[nodeDepart.colonne][nodeDepart.ligne];				

				nodeDepart.D =  0;
				int distanceX = x-caseTestee.getPositionX()+caseTestee.getLargeur()/2;
				int distanceY = y-caseTestee.getPositionY()+caseTestee.getHauteur()/2;
				nodeDepart.A = (int) Math.sqrt(distanceX*distanceX+distanceY*distanceY);
				nodeDepart.F = nodeDepart.A + 0;
				ouverte.add(nodeDepart);


				while (ouverte.size() != 0){					
					// la node dont on va faire le tour (qui sera définie dans la boucle qui suit)
					Node node = ouverte.get(0);

					// prend la node avec le poids le plus bas (qui se trouve dans la liste ouverte)						
					for (Node maNode: ouverte){							
						if (maNode.F <= node.F)
							node = maNode;
					}					

					int colonneNode = node.colonne;
					int ligneNode = node.ligne;
					fermee.add(node);

					ouverte.remove(node);

					// si la node est la node d'arrivée, on arrête					
					if (node == nodeArrivee){
						break;}


					// on fait le tour de la node (en commençant par la node du haut, dans le sens des aiguilles d'une montre, on regarde les 8)


					int colonne = colonneNode;
					int ligne = ligneNode-1;


					// case haut					
					try{if (fermee.contains(nodes[colonne][ligne]) == false){								
						float[] XY = {(int) gauche(unite, cases[colonneNode][ligneNode]).getX(),  (int) gauche(unite, cases[colonneNode][ligneNode]).getY(),(int)droite(unite, cases[colonneNode][ligneNode]).getX(), (int)droite(unite, cases[colonneNode][ligneNode]).getY(),(int)droite(unite, cases[colonne][ligne]).getX(), (int)droite(unite, cases[colonne][ligne]).getY(),(int)haut(unite, cases[colonne][ligne]).getX(), (int)haut(unite, cases[colonne][ligne]).getY(),(int)gauche(unite, cases[colonne][ligne]).getX(),(int)gauche(unite, cases[colonne][ligne]).getY()};
						Polygon polygon = new Polygon(XY);
						// si le polygon de déplacement est en collision avec un terrain, un décor, ou une unité (on doit renseigner l'unité qui se déplace pour éviter les collisions avec soi même)
						if (collision(polygon, unite) == false){								
							// met à jour les attributs de la node si l'unité peut se déplacer dans cette direction
							nodes[colonne][ligne] = attribuerPoids(node,nodes[colonne][ligne], x, y, ouverte,hauteurTile);						
						}}}
					catch (java.lang.ArrayIndexOutOfBoundsException e){}

					// case haut-droite	
					if (colonneNode%2 != 0){ // est impair
						colonne = colonneNode+1;
						ligne = ligneNode;}
					else{								
						colonne = colonneNode+1;
						ligne = ligneNode-1;}
					try{if (fermee.contains(nodes[colonne][ligne]) == false){	
						float[] XY = {(int) haut(unite, cases[colonneNode][ligneNode]).getX(),(int) haut(unite, cases[colonneNode][ligneNode]).getY(),  (int)droite(unite, cases[colonneNode][ligneNode]).getX(),(int)droite(unite, cases[colonneNode][ligneNode]).getY(), (int)droite(unite, cases[colonne][ligne]).getX(), (int)droite(unite, cases[colonne][ligne]).getY(),(int)haut(unite, cases[colonne][ligne]).getX(),(int)haut(unite, cases[colonne][ligne]).getY()};
						Polygon polygon = new Polygon(XY);
						if (collision(polygon, unite) == false){									
							nodes[colonne][ligne] = attribuerPoids(node,nodes[colonne][ligne], x, y, ouverte,distanceDiagonale);							
						}}}
					catch (java.lang.ArrayIndexOutOfBoundsException e){}

					// case droite		
					colonne = colonneNode+2;
					ligne = ligneNode;
					try{if (fermee.contains(nodes[colonne][ligne]) == false){
						float[] XY = {(int) bas(unite, cases[colonneNode][ligneNode]).getX(),(int) bas(unite, cases[colonneNode][ligneNode]).getY(),  (int)haut(unite, cases[colonneNode][ligneNode]).getX(),(int)haut(unite, cases[colonneNode][ligneNode]).getY(), (int)haut(unite, cases[colonne][ligne]).getX(),(int)haut(unite, cases[colonne][ligne]).getY(), (int)droite(unite, cases[colonne][ligne]).getX(),(int)droite(unite, cases[colonne][ligne]).getY(), (int)bas(unite, cases[colonne][ligne]).getX(), (int)bas(unite, cases[colonne][ligne]).getY()};
						Polygon polygon = new Polygon(XY);
						if (collision(polygon, unite) == false){								
							nodes[colonne][ligne] = attribuerPoids(node,nodes[colonne][ligne], x, y, ouverte,largeurTile);		
						}}}
					catch (java.lang.ArrayIndexOutOfBoundsException e){}

					// case bas-droite		
					if (colonneNode%2 != 0){ // est impair
						colonne = colonneNode+1;
						ligne = ligneNode+1;}
					else{								
						colonne = colonneNode+1;
						ligne = ligneNode;}
					try{if (fermee.contains(nodes[colonne][ligne]) == false){
						float[] XY = {(int) droite(unite, cases[colonneNode][ligneNode]).getX(),(int) droite(unite, cases[colonneNode][ligneNode]).getY(),  (int)bas(unite, cases[colonneNode][ligneNode]).getX(),(int)bas(unite, cases[colonneNode][ligneNode]).getY(), (int)bas(unite, cases[colonne][ligne]).getX(),(int)bas(unite, cases[colonne][ligne]).getY(), (int)droite(unite, cases[colonne][ligne]).getX(), (int)droite(unite, cases[colonne][ligne]).getY()};
						Polygon polygon = new Polygon(XY);
						if (collision(polygon, unite) == false){									
							nodes[colonne][ligne] = attribuerPoids(node,nodes[colonne][ligne], x, y, ouverte,distanceDiagonale);
						}}}
					catch (java.lang.ArrayIndexOutOfBoundsException e){}

					// case bas			
					colonne = colonneNode;
					ligne = ligneNode+1;
					try{if (fermee.contains(nodes[colonne][ligne]) == false){
						float[] XY = {(int) droite(unite, cases[colonneNode][ligneNode]).getX(),(int) droite(unite, cases[colonneNode][ligneNode]).getY(),  (int)gauche(unite, cases[colonneNode][ligneNode]).getX(),  (int)gauche(unite, cases[colonneNode][ligneNode]).getY(),(int)gauche(unite, cases[colonne][ligne]).getX(),(int)gauche(unite, cases[colonne][ligne]).getY(), (int)bas(unite, cases[colonne][ligne]).getX(), (int)bas(unite, cases[colonne][ligne]).getY(),(int)droite(unite, cases[colonne][ligne]).getX(), (int)droite(unite, cases[colonne][ligne]).getY()};
						Polygon polygon = new Polygon(XY);
						if (collision(polygon, unite) == false){								
							nodes[colonne][ligne] = attribuerPoids(node,nodes[colonne][ligne], x, y, ouverte,hauteurTile);							
						}}}
					catch (java.lang.ArrayIndexOutOfBoundsException e){}

					// case bas-gauche	
					if (colonneNode%2 != 0){ // est impair
						colonne = colonneNode-1;
						ligne = ligneNode+1;}
					else{								
						colonne = colonneNode-1;
						ligne = ligneNode;}
					try{if (fermee.contains(nodes[colonne][ligne]) == false){
						float[] XY = {(int) gauche(unite, cases[colonneNode][ligneNode]).getX(),(int) gauche(unite, cases[colonneNode][ligneNode]).getY(),  (int)bas(unite, cases[colonneNode][ligneNode]).getX(), (int)bas(unite, cases[colonneNode][ligneNode]).getY(), (int)bas(unite, cases[colonne][ligne]).getX(),(int)bas(unite, cases[colonne][ligne]).getY(), (int)gauche(unite, cases[colonne][ligne]).getX(), (int)gauche(unite, cases[colonne][ligne]).getY()};
						Polygon polygon = new Polygon(XY);
						if (collision(polygon, unite) == false){									
							nodes[colonne][ligne] = attribuerPoids(node,nodes[colonne][ligne], x, y, ouverte,distanceDiagonale);
						}}}
					catch (java.lang.ArrayIndexOutOfBoundsException e){}

					// case gauche	
					colonne = colonneNode-2;
					ligne = ligneNode;
					try{if (fermee.contains(nodes[colonne][ligne]) == false){
						float[] XY = {(int) haut(unite, cases[colonneNode][ligneNode]).getX(),(int) haut(unite, cases[colonneNode][ligneNode]).getY(),  (int)bas(unite, cases[colonneNode][ligneNode]).getX(), (int)bas(unite, cases[colonneNode][ligneNode]).getY(),(int)bas(unite, cases[colonne][ligne]).getX(),(int)bas(unite, cases[colonne][ligne]).getY(), (int)gauche(unite, cases[colonne][ligne]).getX(),(int)gauche(unite, cases[colonne][ligne]).getY(), (int)haut(unite, cases[colonne][ligne]).getX(), (int)haut(unite, cases[colonne][ligne]).getY()};
						Polygon polygon = new Polygon(XY);
						if (collision(polygon, unite) == false){									
							nodes[colonne][ligne] = attribuerPoids(node,nodes[colonne][ligne], x, y, ouverte,largeurTile);
						}}}
					catch (java.lang.ArrayIndexOutOfBoundsException e){}

					// case haut-gauche		
					if (colonneNode%2 != 0){ // est impair
						colonne = colonneNode-1;
						ligne = ligneNode;}
					else{								
						colonne = colonneNode-1;
						ligne = ligneNode-1;}
					try{if (fermee.contains(nodes[colonne][ligne]) == false){
						float[] XY = {(int) gauche(unite, cases[colonneNode][ligneNode]).getX(),(int) gauche(unite, cases[colonneNode][ligneNode]).getY(),  (int)haut(unite, cases[colonneNode][ligneNode]).getX(), (int)haut(unite, cases[colonneNode][ligneNode]).getY(),(int)haut(unite, cases[colonne][ligne]).getX(), (int)haut(unite, cases[colonne][ligne]).getY(),(int)gauche(unite, cases[colonne ][ligne]).getX(),(int)gauche(unite, cases[colonne ][ligne]).getY()};
						Polygon polygon = new Polygon(XY);				
						if (collision(polygon, unite) == false){							
							nodes[colonne][ligne] = attribuerPoids(node,nodes[colonne][ligne], x, y, ouverte,distanceDiagonale);
						}}}
					catch (java.lang.ArrayIndexOutOfBoundsException e){}



				}		
				// met à jour les destinations de l'unité
				if (ouverte.size() != 0){
					ArrayList<Point> destinations = new ArrayList<Point>();	
					// ajoute le point précis d'arrivée
					destinations.add(new Point(x,y));
					if (nodeDepart != nodeArrivee){
						Node nodeCourante = nodeArrivee.parent;				

						// tant que la node courante n'est pas la node de départ, on ajoute le centre de la case aux destinations, et la nodeCourante devient le parent de la nodeCourante précédente
						while (nodeCourante != nodes[chercherColonne( unite.getLosange().getPoint(1)[0], unite.getLosange().getPoint(0)[1])][chercherLigne( unite.getLosange().getPoint(1)[0], unite.getLosange().getPoint(0)[1])]){
							Case maCase = cases[nodeCourante.colonne][nodeCourante.ligne];				
							destinations.add(new Point((int)maCase.getLosange()[1].getX(),(int)maCase.getLosange()[0].getY()));
							nodeCourante = nodeCourante.parent;							
						}}			

					test = destinations;
					unite.setDestinations(destinations);


				}}

		}


	}
	public Point gauche(Unite unite, Case maCase){
		Point point = new Point (maCase.getPositionX()+maCase.getLargeur()/2-unite.getLargeur()/2, maCase.getPositionY()+maCase.getHauteur()/2);	
		return point;}			
	public Point haut(Unite unite, Case maCase){
		Point point = new Point (maCase.getPositionX()+maCase.getLargeur()/2, maCase.getPositionY()+maCase.getHauteur()/2-unite.getLargeur()/4);	
		return point;}		
	public Point droite(Unite unite, Case maCase){
		Point point = new Point (maCase.getPositionX()+maCase.getLargeur()/2+unite.getLargeur()/2, maCase.getPositionY()+maCase.getHauteur()/2);	
		return point;}		
	public Point bas(Unite unite, Case maCase){
		Point point = new Point (maCase.getPositionX()+maCase.getLargeur()/2, maCase.getPositionY()+maCase.getHauteur()/2+unite.getLargeur()/4);	
		return point;}	


	public Node attribuerPoids(Node nodeParent, Node node, int x, int y, ArrayList<Node> ouverte, int distance){
		Case caseTestee = cases[node.colonne][node.ligne];
		if (ouverte.contains(node) == false ){		
			ouverte.add(node);
			node.D = nodeParent.D + distance;							
			int distanceX = (int) (x- caseTestee.getLosange()[1].getX());
			int distanceY = (int) (y- caseTestee.getLosange()[0].getY());			
			node.A = (int) Math.sqrt(distanceX*distanceX+distanceY*distanceY);

			node.F = node.A + node.D;

			node.parent = nodeParent;	
			caseTestee.setTest(nodeParent.ligne);

		}	
		//si est déjà dans la liste ouverte, regarde D est plus petit par ce chemin. Si oui, on change.
		else if (nodeParent.D +distance < node.D){			
			node.D = nodeParent.D + distance;
			int distanceX = (int) (x- caseTestee.getLosange()[1].getX());
			int distanceY = (int) (y- caseTestee.getLosange()[0].getY());
			node.A = (int) Math.sqrt(distanceX*distanceX+distanceY*distanceY);
			node.F = node.A + node.D;								
			node.parent = nodeParent;
			caseTestee.setTest(nodeParent.ligne);
		}

		return node;

	}
	public boolean collision(Polygon polygon, Unite unite){
		boolean collision = false;   
		// collision?		
		Rectangle box = new Rectangle(polygon.getX(), polygon.getY(), polygon.getWidth(), polygon.getHeight() );
		int ligneDebut = chercherLigne(box.getX(), box.getY())-1;  	    		  	    		
		int colonneDebut = chercherColonne(box.getX(), box.getY())-1;  	    	
		int ligneFin = chercherLigne(box.getX(), box.getY()+box.getHeight())+1;
		int colonneFin = chercherColonne(box.getX()+box.getWidth(), box.getY())+1;  

		for (int i=colonneDebut; i <= colonneFin; i++){					
			for (int v=ligneDebut; v <= ligneFin; v++){	
				try{   						
					if ((cases[i][v].getTerrain().isFranch() == false || (cases[i][v].getDecor()!= null &&cases[i][v].getDecor().isFranch() == false))&& polygon.intersects(cases[i][v]) ){
						collision = true;break;}
					else{   for (Unite monUnite: cases[i][v].getUnites()){

						if (monUnite != unite){ // (pas de collision avec soi même...)

							if (polygon.intersects(monUnite.getLosange())){
								collision = true; break;}
						}}
					}
				}
				catch(java.lang.ArrayIndexOutOfBoundsException e){}	

			}}


		return collision;			
	}

salut,
je n'ai pas encore pris la peine de lire ton code
mais se que je peux déjà te dire c'est:
- A (la distance a vol d'oiseaux est ton heuristique)
- ensuite toi tu veux du temps réel donc A* n'est pas optimal pour la simple est bonne raison que pour chaque déplacement que va faire ton unité le terrain aura évolué, d'autre unité se seront déplacer, celle-ci peut-être bloquant ton passage etc...

Conclusion:
Dans l'ordre du plus lent au plus rapide:
1) Pour une optimalité en tout temps comme tu est en temps réels tu refais un A* a chaque changement de case (ou chaque déplacement car l'environnement évolue).
2) tu peux continuer ton A* et avant chaque déplacement vérifié que la case suivante est libre, sinon refaire un A* pour la distance restante.
3) tu fait un A* avec une profondeur maximal (si tu parcours 5000 cases ta pas besoin de connaitre ton chemin exact jusqu'au bout les chose vont évolué...), après a toi de voir la profondeur optimal. (cette méthode peut être combinée avec la 1) et la 2))
4) Soit solution moins optimal mais beaucoup plus rapide tu prends la case la meilleurs a chaque déplacement (mais pas efficace si il y a beaucoup de cul de sac!)

Citation

2) tu peux continuer ton A* et avant chaque déplacement vérifié que la case suivante est libre, sinon refaire un A* pour la distance restante.

C'est ce que j'avais l'intention de faire

3) ajouté à d'autres solutions, c'est une bonne idée.

Je vais essayer quelque chose pour alléger le code, je pense que ça devrait marcher, je te tiens au courant.

Sinon je vois pas trop la différence entre Greedy best first search et A*... surtout que la page est en anglais
J'ai regardé l'extrait d'algo, ça me semble similaire.

Salut,
voila un exemple des differents algo

tu peut comparé l'algo best et A* tu vas voir la différence

Bonne continuation

Si il y a peu d'obstacles et qu'ils sont petits (personnages, par exemple), tu pourrais faire un algorithme très simple qui consiste à aller en ligne droite et dès qu'on rencontre un obstacle, de le contourner.

Résultat avec best: 10 ms au lieu de 360ms^^ Mais c'est effectivement moins précis. Moi qui me trouvais en début de topic que le déplacement ne faisait pas naturel, c'est maintenant catastrophique, dès qu'il y a un obstacle^^ Car je ne pourrais en plus même pas choisir le chemin avec lequel il y a moins de changement de direction.
Oui, Nadrieril, c'est ce que je m'étais dit: pour le terrain (arbre, rocher, etc) qui ne bougeront pas ou presque jamais, j'utiliserais un algo (A* ou autre). Tandis que pour les unités (calculs beaucoup plus complexes), je ferais comme tu dis.
Je vais donc faire ça et voir à quel point ça améliore la rapidité, et je verrais ensuite!

edit: pfff... je viens de passer à 44ms rien qu'en enlevant mes "if (liste.contains(node))" et en les remplaçant par un booléen^^ objectif 10ms...

Voilà, je suis à 30ms Mais maintenant il faut que je trouve un moyen pour que les unités ne se percutent pas, puisque l'algo ne gère pas les collisions entre unités... (si vous avez des idées je suis preneur )

En tout cas merci pour votre aide!