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