QuadTree ?

[bougie]

Bonjour à tous :)

Pour faire un manager de map pour mon jeux en 2D avec SDL, je me suis renseigné et on me parle des quadtree.
Je me suis donc renseigné sur le sujet, et j'aimerai savoir ce que vous en pensez ;)

Y'a t'il de meilleurs façons de gerer une map en 2D ?
Sinon, auriez vous des liens expliquant comment mettre en oeuvre un quadtree, parce que je comprend plus ou moin le fonctionnement, mais j'ai aucune idée pour l'appliquer à mon jeux.

J'espere avoir étais assez claire et precis dans mes question :)
Merci d'avance pour vos reponses

[Laeti²x]

les quadtrees me semble etre une bonne facon de commencer a partitionner son espace 2D.

Le principe :
couper l'espace en morceaux de plus en plus petits, chaque fois en decoupant un grand carré en 4 autres plus petits qui couvrent une des 4 parties de la surface.

C'est le petit frére de l'octree en 3D (decoupage de cube en 8 cubes qui s'inscrivent dedans)

Un objet, si il est plus grand qu'un carré, peut etre contenu dans plusieurs carrés.

"a priori" chaque carré se presente comme un parent dans un arbre a 4 enfants, et peut etre l'enfant d'un seul parent.

Avec tu peux determiner les carres a afficher, les carres ou tester les collisions, etc.

Ah, important, ils ne sont pas tous divisés jusqu'au maximum : on peut en decouper certains en tout petits parce qu'ils contiennent pleins d'objets, et arreter la division de ceux qui n'en contiennent plus. Je crois que generalement, on donne une limite a la division, pour ne pas couper les cheveux en 4.

tu choisi ton echelle, etc... apres il existe une variation, principalement en 3D, les kdtrees. Ce sont des bsps 2D ou 3D dont les plans de coupe sont des plan orthogonaux. La ou un quadtree presentera 4 enfants et un parent, un kdtree presente 1 parent, 2 enfants, eux meme parents de chacun 2 enfants. C'est pas tres repandu et un peu a cote mais c'est une autre approche qui peut t'interesser...

J'arrete d'etaler la confiture; mon portable n'a plus de batteries, bonne soirée et à bientôt.

edit : et voila je relis le message et je m'apercois que je repond a cote. Donc je branche mon cable d'alim et je continue:

tu as des persos dans ton jeu, tu connais leur position sur la carte 2D de ton terrain. Avec l'octree, ce sera une information en concurrence (ou plutot en complement) de la case de l'octree ou ils se trouvent.
Donc quand tu cherches le perso tu cherches sa case, puis son emplacement dans la case.
tu regardes si lui et son ennemi sont sur la meme case, ou des cases contigues avant de tester les collisions entre eux. Tu ne teste que la portion de terrain ou ils se trouvent pour la gravite et pour avancer. Si tu as des elements comme des tresors ou des maisons, tu peux diriger tes persos la bas en suivant les cases, tu peux les diviser tres peu pour faire du pathfind (attention le pathfind astar c'est archi simple en theorie mais a mettre en pratique dans un jeu c'est limite glouton !)

pour l'affichage tu regardes les secteurs vus par la camera et tu n'affiches que ceux la.
a long terme sur un grand decor tu peux faire du "streaming" memoire, en prechargeant les secteurs contigues du tien. bref, y a de quoi jouer, mais il ne faut pas oublier que c'est juste une coquille structurelle (au sens container) et que c'est ce que tu en fais qui compte (mais tu le sais deja).

dernier edit (je viens de lire le bien heureux post de lightness qui remet bien les choses a leur place : c'est du luxe un quadtree pour un petit terrain)

tu dois precompiler le quadtree avant de l'utiliser. Si tu faisait une grille tu pourrais la charger en temps reel peut etre, mais la tu vas devoir faire un editeur ou un compilateur. C'est vraiment si tu aimes la belle algorithmie plus que la fonctionnalitée brute

[Lightness1024!]

bon alors jeu en 2D ca veut dire RTS ou jeu de plateforme ou RPG ou autre ?

bon disons un jeu avec des maps genre age of empires, un découpage en quadtree ne me semble pas utile du fait que nous ne tournons plus avec 16Mo de RAM et des pentiums 100 Mhz, des cartes de grande taille peuvent etre entierement chargées en mémoire et meme affichées a chaque image entierement avec tous les details sans baisse de frame rate.
donc AMHA laisse tomber le découpage ...

surtout que dans un RTS les unités hors écran ne sont pas freezées pour autant, tout doit tout le temps tourner alors le quadtree je vois pas bien l'utilité.
pareil quand tu fais des déplacement, une recherche de chemin se fait sur toute la map. Au pire le seul truc que tu peux optimiser, c'est l'affichage.
Donc mon conseil c'est de découper la carte en secteurs carrés de la taille du champ de vision, ou deux fois plus petits par exemple..
et de déterminer lesquels sont actifs avec le cadrage de caméra actuel.
puis de n'afficher que cela. les parties hors champs qui seront quand meme affichées seront clipées par les méthodes de rendu de SDL.
et le reste de la carte appartenant aux secteurs non-choisis ne sera meme pas passé aux méthodes de rendu.

je reconnait par exemple, que dans warcraft 3, je pense au "mod" tower defense quand on a 70 tourelles qui tirent des sorts sur une 200-aine de bestioles qui font pleins d'effets graphiques ca fait durement ramer déja dans sa zone alors sur toute la map...

l'avantage de découper en arbre plutot qu'en secteurs indexés dans un tableau par exemple c'est de pouvoir faire une recherche des secteurs activés en O(log(n)) plutot qu'en O(n).

pour construire l'arbre de découpage, part du bounding-rectangle de la map, scinde le en 4 puis chaque nouveau secteur alors créé devient un fil de la racine (le bounding rectangle global) qui a leur tours deviennent père de 4 nouveaux secteurs les partagants, etc jusqu'a atteindre la taille du champ de vision sur les secteurs terminaux (les feuilles de l'arbre).
c'est ca, un quadtree.

plus de details ?

[bougie]

Merci pour ces 2 longues explications :)
J'ai plus ou moin compris :)

Si on parlait concret.
En gros, ma map est composée de plusieurs tiles de 32x32.
Je pense faire une fenetre d'affichage de 640.
Donc en gros, il faut que je decoupe mon terrain en carré jusqua atteindre comme dimmension du plus petit enfant de l'arbre 640x480 ?

[Lightness1024!]

lol je me suis quand meme fait un peu grilled pour l'occaz :)

bon, moi je dirais ca oui, Laeti²x à l'air de penser qu'il vaudrait mieux regarder la complexité locale de la map pour fixer la limite de taille.
mais vu que tu marches par tiles de taille fixe c'est comme si la densité complexité par unité de surface était constante donc ca reviendrait a faire des secteurs de tous la meme taille, par exemple 640*480 oui.
(attention a bien convertir en unité de terrain)

[bougie]

Bah la tiles du terrain de base sera d'une taille definie :)
Mais apres, d'autre tiles seront plus petite, plus grosse.

Je cherche surtout la simplicitée mooi, tout en aillant de bonnes perfs.

Mais c'est une bonne idée de limité à la taille de la fenetre, ça permeterai d'envoyer que les tiles qu'on peut voire au blitage, donc à mon avis, on aura un gain de performance :p

Mais de convertir en plus petit peut aussi faciliter les colisions à mon avis

Mais bon, dans un premier temps, je pense essayer an se limitant à la taille de la fenetre, pour affiner apres si necessaire :)

[Lightness1024!]

évidemment si tu as des calculs de collisions sur les objets, faire un quadtree à secteurs plus précis peut parfaitement être un gain.
mais bon, si il y a 35 objets sur un écran, faire la detection des collisions sur 35 plutot que sur 4 ou 5 ne fera pas de différence vu la puissance actuelle des machines. Ce n'est meme pas sure qu'il y ait un gain strict !
parce que la recherche dans le quadtree est plus longue car il comporteras plus de niveaux. on engage un combat log(n) contre linéaire, certains diront qu'asymptotiquement l'algo serait plus efficace avec des secteurs plus serrés, oui mais en pratique ?

a toi de voir :)

[bougie]

Ok, merci de cette reponse :)
Je testerai sans doute les 2 pour me faire une meilleur idée :)