Avant de poser ma question, je vais planter le décor :
---------------------------
J'ai un algo qui génère une map (carte geophysique) avec pour chaque point (ou case) de la carte, une information sur sa hauteur (info codée sur un octet signé car j'indique aussi les hauteurs en dessous du niveau de la mer). Un seul octet suffit pour les besoins.

Un des criteres de la carte est d'etre extremement grande (disons au minimum un carré de plus de 10000 cases de coté : ce qui donne ici une taille en mémoire de plus de 100Mo pour l'exemple)

Donc pour éviter d'avoir à stocker tous ces Mo pour rien, je génère un nombre discret de points de référence à partir desquels je vais "interpoler" la carte (en l'occurence j'utilise un algo de ponderation par l'inverse de la distance au carré : voici un lien sur cet algo pour ceux qui désirent avoir plus d'infos : http://fr.wikipedia.org/wiki/Pond%C3%A9ration_inverse_%C3%A0_la_distance)
Pour une map de 10000 cases de coté, le nombre de points est d'environ 35000 (donc plus que 35ko en mémoire et on a TOUTE la carte : pfiouu ça va déjà mieux pour les petites neurones du PC ;-) )

Quand je souhaite n'afficher une partie de la map (et c'est ce qui est le cas lorsque l'on parcourt un monde dans un jeu, on a pas en mémoire la totalité de la carte mais juste une partie), je vais rechercher les points de référence concernés et lancer l'interpolation.
---------------------------
Mon souci est dans la recherche des points de référence : en fait je ne sais pas comment les organiser dans la mémoire et comment les parcourir pour minimiser les temps de traitements.

Ma premiere implémentation a été de parcourir tout le tableau, calculer les distances au carré par rapport à la case à interpoler puis de prendre les N plus proches pour alimenter l'algo : bien sur c'est horriblement ridicule comme solution surtout quand le nombre de points de ref est grand.

2° etape, je parcours toujours TOUT le tableau des points de référence, mais cette fois je ne calcule plus la distance que si ce point est "relativement proche" de la case à interpoler. On limite qq calculs : c pas mal mais ça ne me satisfait pas encore du fait que l'on parcourt tout le tableau.
---------------------------
Etape suivante à laquelle j'ai pensé, etait d'organiser ma liste de points de référence en Quad-Tree pour les parcourir plus vite mais je ne sais pas trop si c'est une bonne solution ou non.
---------------------------
Bref ma question est simple :
pour mon exemple ici, quelle est selon vous la meilleure méthode d'organisation en mémoire et de parcourt pour minimiser les temps de traitements ??

Merci par avance

Haaaa, enfin une question interessante =)

J'imagine que ta distribution de points de reference est non uniforme? (sinon la question aurait pas vraiment de sens, mais bon ca fait pas de mal de verifier

Perso j'essayerai une variante de kd-tree (pas de leafs sur les axes de split, faire un algo base sur la distribution / distance / etc pour determiner l'axe de split, etc). Vu que tu fais de l'interpolation, tu veux eviter le cas ou tes leafs contiennent pas assez de point et que tu dois reparser une partie de l'arbre pour conserver une approx correcte; un quadtree de base ne se basant pas sur la distribution, il faudrait utiliser plusieures leaves pour ca.
Ensuite, je ferai en sorte que mon arbre soit facilement serializable en un seul blob, et que les valeures des leafs soient dans la leaf elle-meme, histoire d'eviter des acces memoires et etre un peu plus cache friendly!

/kufa

NB: ce topic fait suite a ce topic du forum creation de jeu: https://www.jeuxvideo.com/forums/1-31-8615524-1-0-1-0-optimisation-de-parcours-de-tableau.htm

J'avais penser rendre la decision du nombre de point a prendre en consideration calculant des points supplementaire que l'on insere dans la structure de donne. L'idee etant de construire une grille de point ou l'on connait la hauteur et on calcul les interpolations a partir de ces points la. Comme les points supplementaire sont dispose en grille, ils sont relativement facil a acceder.

Ca marcherait probablement bien si l'interpolation etait lineaire. Mais elle ne l'est pas et inserer des interpolations au milieu de la structure va changer le resultat.

my .02 dollars

Si on se fout du temps de génération de la structure de donnée et qu'elle n'est pas amenée à être modifiée souvent, et que les points de références sont vraiment disposés de manière irrégulière, personnellement je conseillerais un arbre BSP.

Si on a des contraintes de temps réel, que les points de référence vont être modifiés souvent et que les points de références sont disposés de manière relativement uniforme, personnellement je conseillerais le quadtree

Un autre avantage du quadtree est qu'il est très facile à implémenter : il est régulier et ne nécessite pas de calculs pour les axes de séparation. Il est également très facile de calculer l'intersection entre un rectangle (comme un viewport) et les noeuds du quadtree (pour savoir lesquels afficher).

Une question que je me pose : est-ce qu'on peut se téléporter dans ton modèle ? Où est-ce que les déplacements sont forcément continus ?

Merci pr tous vos coms deja. Ca fait plaisir d'avoir ce genre de retour.

Pour les infos supp, mes points de reference sont generes aleatoirement une seule fois : on a dc la position x y et la 'hauteur' du point.
Ils ne sont donc pas repartis de maniere uniforme forcement. J'avais pensé genre interpoler uniquement des points de maniere reguliere pour obtenir une grille bien droite, bcp plus facile pr les calculs ensuite mais cela ne me satisfait pas.

Ds l'idee du deplacement, je n'ai jamais pensé a la 'teleportation'. Cette derniere impliquant de devoir recalculer toute la nouvelle zone a afficher : en fait c le pire cas.

Je vais me documenter sur les differentes reponses que vs m'avez donné et voir ce qui me semble le plus judicieux.

Merci encore.

Apres reflexion(s) je pense que je vais caler un petit quadtree ds l'algo
mes pts de reference restent malgre tout relativement uniformes ds leur repartition (ca fluctue suivant les zones mais bon)

comme je ne suis pas du genre a recuperer du code deja fait, je vais me coder ca 'from scratch'
vous auriez des conseils sur 'la forme' de cette bibliotheque ou classe ?
Si on parle objet je suppose que j'ai besoin de methodes add/remove node dans mon arbre forcement.
Je suppose une methode qui retourne une liste de pts dans une zone donnee, une methode qui retourne le pt le plus proche d'une position definie, ...
Faut il que chaque noeud fasse reference au noeud pere : je suppose que oui. Je pense que ca se gere comme une liste chainee dont chaque element a soit 0 soit 4 fils b correct ?

Bonne nuit les loulous
et faites des momes .... Ca reveille la nuit pr que vs puissiez tchater sur les forums JV.com ;-)

J'ai eu à coder récemment un quadtree. Globalement j'ai suivi le même schéma que toi. J'avais bien mis un lien vers le père dans chacun des noeuds, et j'avais aussi stocké dans chacun des noeuds l'information géométrique qui lui était liée : centre, hauteur et largeur du noeud.

Utiliser un quadtree ici me parait completement overkill. Je ne suis pas expert dans le domain, mais OP dit que la distribution des points de references est uniforme. Du coup, le quad tree sera relativement bien equilibre et donnera le meme resultat qu'un simple quadrillage. C'est certainment plus simple a implementer.

Godrik j'ai reflechi a ce que tu as marqué.
Alors voici mon idee : j'aimerai avoir un avis dessus.

Si je divise ma map en petits carres : chacun de ces carrés est un element d'un tableau statique (puisqe je connais la taille de la map et de chaque carre je sais combien il y a de carres logique)
chacun de ces elements contient 1 entier pour indiquer le nb de pts de reference dans ce carré et un pointeur permet d'acceder a ces pts de references.

Ainsi, pour n'importe quelle coordonnee je peux retrouver les 'carrés' alentours et ne tester QUE les pts de reference contenus dans ces carres

c un peu ma vision de ce que tu appelais un quadrillage

alors, ca parait correct comme methode ?

deeplo, c'est ce que je suggerais.

En pratique tu peux faire un petit peu mieux. Tu peux stocker tout les points de references de facon contigue en memoire et groupe par carre logique et tu stocke dans un tableau ou commence la list des points de reference de ton bloc. Tu sais implicitement ou elle fini: a la case d'avant celle du prochian bloc.

Claaaassse !!
et bien je vais faire ca. Ca me plait bien
merci encore pour l'aide apportee