Discussion :

[ElSpopo]

Bonjour,

Je développe un outil java donnant diverses informations sur un jeu en ligne et la fonctionnalité que j'essaye d'y intégrer en ce moment, c'est le calcul du chemin le plus court entre deux cases.
je pensais donc utiliser l'algorithme de dijkra en lui passant en entrée le graphe de la carte représenté par une matrice d'entier

Néanmoins, je me heurte à un problème.
La carte fait 190 cases sur 190 cases. soit 36100 cases.
ce qui donne une matrice représentant le graphe de 36100 sur 36100 soit plus d'un milliard de cases

Donc rien que le fait d'initialiser mon tableau d'entier

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
 
int[][] tab = new int[36100][36100];

fait planter la jvm.

Voilà, donc je pars à la pêche aux bonnes idées pour contourner le problème.
Sinon je m'inquiète du temps d'exécution d'un tel calcul, une idée de ce que ça pourrait donner?


Sinon, quelques infos supplémentaires au cas ou:
-la carte du jeu change quotidiennement donc le cout en déplacement d'une case change aussi, ce qui implique que la matrice doit être reconstruite à chaque exécution. Je ne peut donc pas la calculer une bonne fois pour toute.
-il s'agit d'un outil local que les joueurs installent sur leur machine. Donc des bidouilles de la machine utilisateurs sont envisageable mais à éviter autant que possible.

Voilà, merci d'avance pour les réponses

[vic]

Hello,

tu n'as pas du tout besoin d'un tel tableau pour implémenter Dijkstra! Il suffit de 2 listes, qui dans le pire des cas contiennent à elles 2 la totalité des cases. Donc au maximum 36100 cases.

Relis un peu la description de l'algo, et reviens si tu as des questions.

Question perfs, c'est un algorithme qui croit comme n^2, avec n nombre de nœuds du graphe (je crois). Ça risque donc d'être assez lent pour un graphe de ta taille. Utilise plutôt l'algorithme A* qui est la variante optimale de Dijkstra. La différence est l'ajout d'une heuristique qui permet d'estimer les distances et d'améliorer considérablement le temps de calcul dans certains cas. Tu peux étudier cet algo dans un second temps.

Pour info j'ai fait un test sur ma machine (proc@2.67GHz) avec un graphe de 136x136 le temps de calcul pour relier 2 coins opposés est d'environ 8s avec Dijkstra. Avec A*, selon la nature du graphe (simple ou bien tortueux avec de nombreux chemins à évaluer) on va de 8s à 0.01s...

[JulienDuSud]

Tu peux également diviser ta "carte" en secteurs, calculer les chemins entre ces secteurs une fois, et ensuite tu n'auras plus qu'à calculer de très petites distances, peu importe le fait que ta carte fasse (10^x)^2.

Exemple:

Ta carte fait 1000*1000 cases: Tu la divises en secteurs de 50*50 (sous-carte). Tu viens de passer d'une carte d'1 million de cases à une carte de 2500 cases.

Tu calcules le chemin entre tous tes secteurs (par exemple pour aller du secteur A au secteur Z il faut passer par le secteur B, D, F, H ).

Ensuite tu n'as plus qu'à calculer, à chaque itération, le chemin entre A et B, puis de B à D, puis de D à F, puis de F à H et finalement de H à Z. Tu peux enregistrer cette donnée sur un fichier.

En gros, au lieu d'avoir 1 calcul sur une matrice de 1000*1000, tu auras au plus 2500 calculs sur des matrices de 50 sur 50.

Le gain de perf est tout simplement énorme.

[ElSpopo]

Bonjour.

déjà, merci pour l'aide

comme vous me l'avez suggérez, j'ai essayé de représenter mon graphe autrement que part sa matrice. J'utilise donc une HashMap avec comme clef une case et comme valeur la liste des arcs sortant de la case.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
 
protected HashMap<Case, ArrayList<Arc>> noeuds;

les variables d'instance de la classe Case(qui me permet déjà de gérer ma carte pour le reste de l'outil, je ne créé pas de nouvelles cases à mettre dans la hashmap, ce sont des références aux objet existant).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
 
public class Case implements Serializable{
	public Short terrain;
	public Short x;
	public Short y;
	public Short batiment;
	public Short niveauBatiment;
	public Short race;
}

Et la classe Arc créée pour l'occasion

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
public class Arc implements Serializable {
	Case arrivee;
	short cout;
 
	public Arc(Case arrivee, short cout) {
		super();
		this.arrivee = arrivee;
		this.cout = cout;
	}
 
 
}

Néanmoins j'obtiens toujours une erreur du dépassement de la mémoire (java heap space, out of memory) lorsque je remplis la HashMap sur ma machine perso(2 giga de ram proc dual core). L'erreur arrive au bout du traitement d'environs 75 lignes de la carte soit un peu moins de la moitié de la carte.

J'ai fait une sérialisation du hashmap au bout de 30 lignes traités pour avoir une idée de l'espace mémoire utilisé, ça me donne un fichier de 800ko, ce qui pour un traitement complet(mes 190 lignes donc) devrait donner environ 5 mega.

Je viens d'essayer sur mon poste de travail du boulot(4 giga de ram, dual core) et ça passe sans problème avec une création de la hashmap en moins d'une seconde.

Je me demande donc si l'utilisation mémoire de cette façon de faire vous parait raisonnable, le fait que ma machine ne le supporte pas peut'il venir d'un problème de mon pc?

[wax78]

Tes parametres Xms et Xmx sont mis a combien de mega ?

[ElSpopo]

Ah bonne question.
En fait avant ton message je ne savais pas que ça existait.

Donc je vais essayer ce soir voir ce que ça donne en les mettant.
Merci pour la piste

Sinon, par curiosité, comment je peux savoir a quelle valeurs sont affecté ses paramètres par défaut?