Bonjour,


Je suis actuellement en plein développement d'un jeu type RPG (en 2D iso).

Dans ce jeu, j'ai une carte qui est formée de plusieurs objets de type "Case".

Chaque case doit pouvoir être retrouvée au sein d'une collection grâce à deux indices x et y (entiers).

Et pour couronner le tout, les entiers en question peuvent être négatifs.

J'ai besoin d'une collection qui me permette de gérer tout ca, tout en sachant que la manière dont est gérée cette liste aura une grande importance dans les performances globales du jeu (cela pourrait rapidement atteindre des centaines de milliers d'éléments). Non seulement au niveau de la lecture (a chaque FPS l'ensemble des cases devant être affichées à l'écran sera recherché dans la liste), mais aussi de l'écriture (pour être un peu plus clair, j'ai un algorithme qui génèrera les zones inexplorées de la carte dès que nécessaire, et donc qui fera pas mal de lectures/écritures). De plus, c'est un jeu multijoueurs donc c'est côté serveur que ca se jouera.

Actuellement j'en suis au tout début donc j'ai opté pour emboiter deux HashMap qui prennent un Integer comme clé. Malheureusement, je me rend compte que c'est très loin d'être optimisé (déja j'ai des objets a la place de simple valeurs, et en plus la comparaison faite par l'algorithme de la HashMap est certainement bien moins efficace qu'une simple comparaison niveau processeur). J'ai donc besoin de gérer ca mieux.

J'ai donc pas mal cherché, mais sans grand succès. J'ai lu des trucs a propos d'une "MultiKeyMap" d'apache, mais est-ce vraiment mieux que deux HashMap ?

D'un autre côté une structure gérant ca à la manière d'un array (à supposer que ca gère les indices négatifs) n'est pas vraiment mieux car il peut y avoir des grandes zones de vides entre les éléments (par exemple il pourrait ne pas y avoir de case entre (0, 10) et (0, 10000), donc on aurait 9990 zones mémoires gaspillées.


Auriez vous des idées ou propositions pour répondre à ce problème ?

Merci d'avance,

Cordialement.

Pourquoi y aurait-il des zones de vide? Normalement toutes les cases existent, non?

Mon algorithme génère la map dès qu'un joueur souhaite aller dans un endroit qui n'est pas encore généré (ce cette façon le monde est plus ou moins infini).

Donc si le joueur se ballade en demi cercle par exemple il peut y avoir un grand vide dans une rangée de x ou de y.

La map en question est dans le client ou dans le serveur? Parce que le serveur peut avoir une map qui se charge au fur et à mesure. S'il y a assez de joueurs, la map sera vite pleine. Si c'est pour le client, tu peux faire une map qui est un peu plus grande que la map affichable (pour charger à l'avance) centrée sur le joueur et qui de décale à chaque mouvement du joueur.

La map sera principalement côté serveur.

Côté client, c'est comme tu l'as dit, seule la partie nécessaire sera en mémoire, donc dans tous les cas on aura une map comportant assez peu d'éléments pour se permettre de négliger un peu les performances.

Pour le serveur, tu parles d'une map qui se charge au fur et a mesure, c'est à dire ? En parallèle il faudra aussi que je trouve un moyen sûr de stocker la map sur disque dur, donc peut être serait-il envisageable d'optimiser en ne gardant en mémoire que le nécessaire, et le reste sur le disque, qui sera chargé quand nécessaire (et en même temps prévoir de quoi vider les éléments inutilisés de la mémoire).

Pour le serveur, j'aurais fait un grand array à deux dimensions qui pourra contenir toute la map. La première fois qu'un client demande une partie de la map, le serveur la charge à partir d'un fichier et la stocke dans l'array. Les fois suivantes, il lui suffit de chercher dans l'array.

Oui mais ca ne résoud presque rien des contraintes citées.

Si il y a assez de joueurs, la map entière servira souvent, ce ne sera donc pas de la mémoire gachée.
En outre, l'accès à des arrays est très rapide.

les arrays ne permettent pas de gérer des indices négatifs. Et bien au contraire, il y aura un immense gaspillage de mémoire, à cause des "trous" (cités plus haut). Les arrays ne permettent pas non plus d'être extensibles (il n'y a pas de nombre déterminé d'éléments).

Si il y a bcp de joueurs, il n'y aura pas de trous.
Et pour les indices négatifs, comme normalement tu connais le minimum atteignable pas tes indices, il suffit de leur rajouter un nombre pour que l'indice le plus petit devienne 0.

Je ne connais pas le minimum atteignable.

Et je t'assure qu'il peut y avoir des trous étant donné que mon algo génère les zones a la demande.

Ensuite ca ne résoud pas le problème de l'extensibilité.

up

up

Je ne peux pas resister a 2 up consécutif ...

Non mais sérieusement, avec une HashMap tu devrait t'en sortir avec de bonnes perormances.
As-tu au moins redéfinie correctement ta méthode HashCode() pour tes objets cases ?

Et au lieu de charger ta map avec des cases vides, tu ne mets rien a l'intérieur et tu identifira donc une case qui n'est pas dans la Map comme une case vide.
ça t'évite d'ajouter du contenu dans la Map (et perdre en performance lors des recherches) donc au final ta map ne contiendra que l'espace occupé.

Cette solution n'est valable que si tes cases vides sont toutes pareilles.

Merci pour ta réponse.

Je n'ai pas redéfini hashcode, mais normalement ce n'est utile que pour les clés je crois, pas les valeurs ?

Actuellement, je n'ai pas de cases vides dans la map.

En fait ce que je me demande c'est si c'est vraiment optimisé d'emboiter deux hashmaps pour au final n'avoir qu'une clé constituée de deux entiers. Il doit bien y avoir moyen de gérer ca un peu mieux.

Constitué de deux entiers ? pourquoi donc ?

Ton jeu donne un truc dans le genre :

-	-1	0	1
-1	val	val	val
0	val	val	val
1	val	val	val

Donc tu a une HashMap<HashMap<Case>>.
La HashMap de la 2e dimension peut très bien contenir plusieurs valeur, et vu comme ça c'est pratique d'utiliser des Hashmap.

Deux entiers pour x et y.

Pour accéder à une case il me faut systématiquement un x et un y ...

Ca veut dire que (si je prends un exemple pour une map de 1000 cases de côté) :
--> Avec deux hashmaps emboitées, j'ai donc une hashmap principale, et 1000 hashmaps correspondant chacune a une colonne x. J'ai donc au total 1001 hashmaps rien que pour une map pas spécialement très grande (ceci sans prendre en compte la mise en cache).
--> Avec une seule structure qui gèrerait des clés x et y, je n'aurais qu'un seul objet de ce côté-ci

c'est le même principe que pour les tableaux a deux dimensions.
je ne voix pas plus optimal que ça