Discussion :

[khayyam90]

Bien le bonjour,

Je suis à sec sur la manière de stocker et gérer mes données. Pour la réalisation d'un jeu de stratégie j'ai besoin de stocker des informations relatives à des endroits sur la carte.

Ces informations peuvent être de diverses natures, mais disons qu'il s'agit de stocker les valeurs de certains indicateurs tels que l'influence d'un joueur à un endroit précis ou encore la faiblesse d'un joueur ou les zones souvent traversées par tel ou tel joueur.

Il n'est pas nécessaire que ces données soient stockées à l'unité près, c'est pourquoi j'avais dans l'idée de faire correspondre un tableau 2D avec ma carte. Le problème est que le tableau est vite démesuré. Pour que les données aient un quelconque sens, je devais prendre une granularité de tableau assez fine, d'où explosion de la mémoire. Qu'à cela ne tienne, je suis parti ensuite pour faire un quadtree et ainsi ne stocker que les zones contenant des données. Malheureusement je peux potentiellement avoir à stocker des données dans chaque case ou presque.

De plus, je dois pouvoir avoir un accès rapide à une case du tableau et je dois pouvoir me balader facilement d'une case à l'autre.

La solution viable serait de prendre un tableau démesuré, en diminuant la taille de la carte pour éviter de saturer la mémoire, mais cette solution n'est pas idéale.

Avez-vous des autres idées plus pertinentes que les miennes ?

[BugFactory]

Vous avez peut-être de larges plages rectangulaires avec les mêmes valeurs?

[bafman]

un systeme plutot efficace et relativement generique est d'utiliser des cercles pour decrire l'info.
avec une position et rayon et une petite interpolation, on peut obtenir de tres bon résultats.
par contre, si tu utilise un map a base de cases, alors, les rectangles peuvent effectivement etre très efficaces pour reduire le taux d'info stockées.

[khayyam90]

Il est possible que j'aie de grandes plages avec les mêmes valeurs, mais je ne veux faire aucune supposition de ce côté. Le modèle utilisé doit pouvoir refléter tous les cas de figure.

L'idée des cercles me plait bien, d'autant que je n'utilise pas a priori de carte à base de cases. Ma carte est tout ce qu'il y a de plus continue.

[Kurisu]

L'idée d'utiliser des textures en tant que tableau te permettrait de ne regarder que la partie de ta carte visible à l'écran.
M'enfin, ceci n'est qu'une idée rapide...

[Mat.M]

? pour le problême exposé rien ne vaut les listes !
Pour faire correspondre une entité au décor il suffit de transformer les coordonnées de l'entité x,y en fonction du "viewport" et savoir si ces coordonnées appartiennent à ce viewport ( nécessité de faire un "clipping")
Je ne pige pas trop ou est le problème.
Si tu veux faire un jeu de stratégie il faut utiliser des conteneurs comme std::list..etc
C'est comme cela qu'ils ont fait dans Civilisation II Call to Power ( regarder dans le code source)
Pour les entitées la POO est parfaite avec des classes en tout genre

La solution viable serait de prendre un tableau démesuré, en diminuant la taille de la carte pour éviter de saturer la mémoire, mais cette solution n'est pas idéale.

Avez-vous des autres idées plus pertinentes que les miennes ?

faut procéder à un découpage et gérer des fenêtres de zone de vue ( viewport).
Si on fait défiler l'écran alors le viewport change on ne fait apparaitre que les entités comprises dans ce viewport

[khayyam90]

L'idée de viewport ne convient pas à mes besoins, j'ai besoin de manipuler des zones de la carte qui ne sont pas forcément comprises dans le frustum. Ca sera d'ailleurs la grande majorité des cas. Je peux avoir à manipuler des données situées à des endroits très différents, notamments dans les traitements liés aux IA.

L'idée de liste ne me convient pas non plus puisque j'aurais des accès en O(n) beaucoup trop longs. Il faut qu'avec une position (x,y) je puisse accèder très rapidement aux données d'un lieu.

[bafman]

si tu trie tes positions dans un multi set en fonctions de leur distance à l'origine du monde, tu peut avoir des temps d'acces très satisfaisant

[Mat.M]

L'idée de viewport ne convient pas à mes besoins, j'ai besoin de manipuler des zones de la carte qui ne sont pas forcément comprises dans le frustum. Ca sera d'ailleurs la grande majorité des cas. Je peux avoir à manipuler des données situées à des endroits très différents, notamments dans les traitements liés aux IA.

L'idée de liste ne me convient pas non plus puisque j'aurais des accès en O(n) beaucoup trop longs. Il faut qu'avec une position (x,y) je puisse accèder très rapidement aux données d'un lieu.

Ah il fallait préciser que c'était un jeu 3d ; je pensais que c'était un jeu 2d de stratégie.
C'est certain que les listes c'est pas trop adapté et que le viewport est géré par les fonctionnalités 3d
J'aurais plutot une préférence pour les arbres binaires plutot que des conteneurs de la STL.
Mais c'est plus complexe à mettre en oeuvre