Bonjour

Je recherche un exemple de librairie ou de classe (C/C++) permettant de gérer les QuadTrees.

J'essaye de développer un jeu de strategie au tour par tour et en ce moment je m'attaque à la gestion du "sol" (affichage et animation des textures suivant le type de case (eau, herbe, ...)
Pour ne pas parcourir toute la map et tester si chaque case doit etre "rafraichie" à l'ecran ou non (je ne rafraichit que les cases qui sont animées (eau, ...) ou les cases qui sont situés sous d'autres graphiques (là où se situe un personnage qui se déplace par exemple), je souhaitais utiliser le systeme de quadtrees pour optimiser et réduire le temps de traitement.

Merci par avance si vous avez des sources là dessus, ou meme des conseils sur la manière de concevoir ce type de module)

Je vois mal comment le quadtree pourrait tellement t'aider. Puisque tu connais les caractéristiques des cases qui doivent être rafraichies, ce n'est pas plus simple et beaucoup plus efficace de tout simplement en garder une liste? :o

Une simple liste d'IDs ou de coordonnées, à chaque fois que tu crée une case d'eau tu la rajoute à la liste.

les arbres binaires sont utiles pour cibler des parties spécifiques de grand ensembles complexes (3D par exemple). Si ton jeu n'a que 2 dimensions, cela ne t'aidera pas beaucoup je pense.

d'autant plus que dans un quadtree, la notion de voisinnage devient plus difficile a gerer (deux elements peuvent etre tres proches physiquement, mais dans des cellules a l'oppose de l'arbre du fait de la partition abitraire)

une autre structure de donnees semblerait plus adaptee

en fait je pensais utiliser l'arbre comme une representation graphique de ma 'map'

je m'explique : chacun des elements de l'arbre représente un quart de l'ecran. chaque element peut prendre 3 valeurs ON, OFF, BOTH qui indiquent respectivement si toutes les valeurs des elements 'fils' de l'element courant valent toutes ON, ou bien toutes OFF, ou alors si les valeurs sont différentes (BOTH)

Dans le cas de ON ou OFF, on sait que toutes les cases faisant partie de l'ensemble ont toutes la meme valeur (et on sait alors en un seul test quel process appliquer sans avoir à tester toutes les cases une à une)
Dans le cas de BOTH, il faut regarder les 'fils' de l'element avec cette valeur particuliere pour voir comment les valeurs ON et OFF sont réparties (on divise encore en quatre l'espace)...

C'était une idée comme ça à faire murir mais en cherchant sur le net hier, j'ai trouvé ça :
http://en.wikipedia.org/wiki/Quadtree
En fait c'est exactement ça que je voulais comme principe : on divise l'espace en 4 puis chaque sous espace en 4 et ainsi de suite jusqu'à ce que chaque sous-branche de l'arbre ne contienne que des valeurs identiques dans toute la zone qu'il décrit. Bon là ils décrivent des valeurs "NOIR, BLANC, GRIS"
pour décrire la chose mais je m'aperçois qu'on parle le meme langage.

Je vais voir si je peux trouver une classe deja faite sur une gestion des données comme expliqué, sinon je la ferais moi meme.

Le Quadtree n'est pas toujours le manière la plus optimisée de faire ce genre de choses.

Peut être que tu peux juste découper ta map en une grille, et mettre à jour X cases autour de chaque personnage. Tu as juste à savoir dans quelle case ton personnage est, puis après, un petit algo mets à jour X cases autour.

oui c'est une idée mais cela veut dire que l'info "mise a jour" est incluse dans les objets "personnages" et non plus dans l'objet "map".

En fait aujourd'hui ma map est deja découpée en "cells" et chaque cellule possède une propriété "to update" qui est un booléen indiquant si on doit mettre a jour l'affichage de cette case à l'ecran.
Je ne parcours QUE les cases qui sont visibles à l'ecran (la map est plus grande que la zone d'affichage) et parmi ces NxM cases, je regarde chacune si la propriété "to update" vaut 'true' et je blit à l'ecran la cellule si c'est le cas. Puis je repasse la propriété à 0

Ce qui m'embetait c'etait de parcourir avec deux boucles imbriquées et tester chaque cellule unitairement.

Mais ta réponse me fait penser que je pourrais tout simplement créer une liste dynamique des cases à modifier et je n'ai qu'à parcourir cette liste (en fait dans le principe c'est ce que je voulais faire)

Cela reviendrait à déporter l'information "to update" dans une liste exterieure plutot que de la mettre en propriété de chaque case. Cett eliste contiendrait donc TOUTES les propriétés "update" de toutes les cases à mettre a jour. Mon quadtree n'etait rien d'autre qu'une liste chaine des cases à modifier.

C'est une très bonne chose : merci pour ta réponse
je vais faire ça ... c'est bien plus simple à implémenter

Merci encore.

Romuald ..... très content XD

J'voudrais pas dire, mais c'est ce que j'avais suggéré dès le départ :P

oui !
mais c'est ça l'experience : c'est quand on prend conscience des erreurs, des mauvais choix ou des choix inadaptés, trop complexes par rapport à la situation

Il me fallait juste "prendre conscience"

Si il suffisait d'ecouter les "sages" pour faire bien du premier coup, les ados ne feraient pas de conneries

Merci mec