Discussion :

[Invité]

Salut!

En ayant recherché un petit peu les différents algorithme du partitionnement de l'espace, j'ai vu qu'il existait pas mal de structures, avec chacune leurs avantages et leurs inconvénients :

-La grille :
-Avantage : simple.
-Inconvénient : Si les objets sont fort proches les un des autres, ont peut se retrouver avec des cases contenant beaucoup d'objets.

-L'octree :

Avantage : Supprime l'inconvénient de la grille.
Inconvénient : l'arbe n'est pas équilibré.

-Le BSP-TREE :

Avantage : L'arbre est équilibré.
Inconvénient : il faut calculer à chaque fois le plan de coupe.

Pour l'instant j'ai eu l'idée de faire ceci : j'utilise tout d'abord une grille qui, stocke chaque objets dans des cellules.

Ensuite, afin d'éviter de tester si toutes les cellules de la grille du monde sont en collision avec la box de la caméra (ce qui prend plus de temps), je fais un parcours qui récupère les cellules d'un endroit à un autre (en fonction du décalage qu'il y a entre deux cellules), et je récupère les objets qui sont dans les cellules.

Afin de palier aux inconvénient de la grille j'ai décidé de faire un BSP-TREE dans chaque cellule de la grille, ainsi je passe la box de la caméra au BSP-TREE en ne récupérant que les entités des feuilles qui sont en collision avec la caméra.

Bref, en y réfléchissant j'aurai peut être pu utiliser directement un BSP-TREE mais j'ai aussi besoin de pouvoir récupérer le chemin d'une entité vers un point en évitant les collisions, ce que je fais grâce à la grille en récupérant chaque centre des cellules voisines et en sélectionnant la plus proche de la position finale jusqu'à arrivé à la cellule qui contient la position finale.

Jusque là, pas de soucis, mais ou je me pose la question, c'est pour les objets dynamiques.

Pour l'instant je me contente de les replacer dans la grille quand ils bougent, de plus, je dois aussi reconstruire le BSP-TREE.

N'est ce pas trop coûteux de faire cela ?
Existe t'il une meilleure solution ?

Si oui laquelle ? (Quel algorithme de partitionnement devrais-je utiliser pour les objets dynamique ?)

[Kannagi]

C'est plutôt relative a chaque jeu , donc répondre qu'il y est une meilleur solution je me prononcerais pas , personnellement je fais une grille + test de collision des objet proches , par exemple avec une maison si le hero est proche de la maison je fais le test sinon non que je soit dans la grille ou pas, du coup avec le system de grille je test très peu de chose , et comme c'est rare que tout les objet se trouverais dans un point ponctuel même s'il y en a 100 par grille c'est peu probable que je testerais plus de 10 en même temps (après ça dépend du jeu comme je l'ai dit).
Ensuite il faut voir dans la pratique , si on utilise une méthode est qu'elle est satisfaisante en terme de perf autant la gardé.

[Invité]

Ok bah je pense que je vais garder la grille alors. (Pour l'instant elle est suffisante en terme de perfs.)

Merci.

Cependant je vais quand même rajouter des classes pour les autres structures dans mon moteur, on ne sait jamais et puis si quelqu'un d'autre en a besoin ça peut aider.