Discussion :

[SebSplo]

Bonjour.

Ces jours-ci, je fais des tests afin de développer, plus tard, mon premier vrai jeu, qui devrait être un shoot-em-up 2D programmé en C++. Rien de très original mais peu importe pour l'instant. Mais ma question est applicable a d'autres types de jeu et de langages.

Je voudrais savoir quelle est, selon vous, la meilleure structure de données afin de gérer les objets (graphiques ou non) qui composent mon jeu.

Je cherche une structure de données qui permet d'ajouter/supprimer environ 100 objets/seconde, d'effectuer des tests de collision le plus rapidement possible, et d'afficher les objets dans le bon ordre.

Pour cela, dois-je séparer mes données en fonction du type d'objet ? Par exemple :
1 - Collection d'objets appartenant a l'UI (menu, boutons, score, ...).
2 - Collection d'objets dynamiques (ennemis, tirs du joueur (beaucoup/seconde), tirs des ennemis, vaisseau du joueur, ...).
3 - Collection d'objets statiques sujets aux tests de collision (murs qui bloquent les joueur/ennemis et leur tirs, ...).
4 - Collection d'objets statiques non sujets aux tests de collision (background, animation d'explosion des ennemis, ...).

Devrais-je fusionner les collections 2 et 3 vu qu'ils sont sujets aux tests de collision ? Mais les objets du groupe 2 doivent pouvoir être ajoutés/supprimés très vite, tandis que les objets du groupe 3 ne changent pas beaucoup, mais peuvent être en grande quantité (beaucoup de "tile" de mur) ...
Devrais-je fusionner aussi avec la collection 4 ? Car si je sépare tout ça, comment faire pour afficher les objets dans le bon ordre ?

Peut-être devrais-je séparer ainsi :
1 - Couches ("layer") arrière-plan.
2 - Couche du jeu (contenant joueur + ennemis + murs).
3 - UI.

Pour le type de collection d'objets, j'ai pensé à un graphe triangulé a l'aide de l'ami Delaunay. Est-ce une bonne idée ? Si oui, quelle bibliothèque utiliser ? CGAL ou Triangle qui sont en licence GPL (je préfèrerais éviter) ou Boost.Graph et implémenter moi-même Delaunay ? C'est pas un peu compliqué ?..

Ou bien une table de hachage ? Une map triée ? Un bête tableau de vecteurs ferait l'affaire ?
Est-ce que je me pose trop de questions stupides ?

[Mindiell]

Salut,

Sincèrement, je pense que tu te poses les bonnes questions, mais un peu trop tôt. Je m'explique :
Séparer les objets en "types" est une très bonne idée. En effet, le fond du jeu ne sera pas modifié, alors que les "objets" seront constamment en movuement, pourront être détruits, etc...
Maintenant, se demander si un vecteur, une map ou d'autres choses sont mieux, tu ne devrais pas faire ca maintenant (bien que le choix entre un vecteur et une map, tu peux le faire rien qu'en te demandant de quoi tu as beoisn).

Réfléchissons :
Tu as des tas d'objets (ennemis), et leurs tirs (un tir ennemi ne détruit pas un autre ennemi à priori). Rencontrer un ennemi ou son tir fait mourir le joueur (ou baisser ses boucliers, etc...). Tout cela je le mettrais donc dans un seul veteur d'objets.
Tu as des objets statiques (murs, etc...) qui pourraient être comme un ennemi ou un tir qiu ne bougent pas : le joueur explose quand il rentre dans un mur ou est-il seulement bloqué ?
Tu as donc un premier vecteur qui contient toutes les rencontres que peut faire le joueur. Dès que le joueur entre en collision avec un de ces objets, il perd n points de vie (0 pour un simple mur bloquant, et de plus en plus pourdes tirs plus ou moins gros, etc...) et il peut rester bloqué (un tir ne bloque pas, un mur oui, un ennemi oui tant qu'il est vivant, etc...).

Tu fais la même chose pour les tirs du joueur (un deuxième vecteur "tirs") qui, lui, va provoquer des rencontres avec les "adversaires" (le vecteur ci-dessus).

Enfin, tu as un simple objet joueur qui n'a pas besoin de vecteur pour le véhicule du joueur.

Ainsi tu limites les collisions entre "adversaires" et "joueur", ce qui provoque le blocage et/ou des pertes de points de vie au joueur. Puis tu testes les collisions entre "tirs" et "adversaires" pour savoir si le joueur détruit ou abime les ennemis.

Ce qui va être le plus gourmand ce sont les tests entre "tirs" et "adversaires", car ils peuvent être nombreux. Tu pourrais imaginer limiter tes tests à certaines zones :
Je découpe l'écran en 4, puis à nouveau en 4 (16 parties donc). A chaque déplacement d'objet, je lui dis dans quelles zones il se situe (plusieurs possibles, puisqu'il peut être à la croisée de 4 zones maxi). Quand je fais mes tests, je vérifie uniquement si mon tir rencontre un adversaire situé dans les mêmes zones.
Cette partie là vient plus tard : C'est de l'optimisation, ce n'est pas important au départ !

Le fond et compagnie, ne subit jamais de test de collision. Il doit être dessiné en premier. Après, il est préférable, je pense, de dessiner les "adversaires", puis les "tirs", puis le joueur. De toute facon, ces 3 derniers types d'objets ne sont jamais les uns sur les autres, puisqu'ils se bloquent ou disparaissent à leur rencontre...

Voilà !

[Mat.M]

Pour le type de collection d'objets, j'ai pensé à un graphe triangulé a l'aide de l'ami Delaunay. Est-ce une bonne idée ? Si oui, quelle bibliothèque utiliser ? CGAL ou Triangle qui sont en licence GPL (je préfèrerais éviter) ou Boost.Graph et implémenter moi-même Delaunay ? C'est pas un peu compliqué ?..

Cela m'a l'air empoyé des grands moyens pour pas grand chose ;une simple std::list ou std::vector suffit

Pour cela, dois-je séparer mes données en fonction du type d'objet ? Par exemple :
1 - Collection d'objets appartenant a l'UI (menu, boutons, score, ...).
2 - Collection d'objets dynamiques (ennemis, tirs du joueur (beaucoup/seconde), tirs des ennemis, vaisseau du joueur, ...).
3 - Collection d'objets statiques sujets aux tests de collision (murs qui bloquent les joueur/ennemis et leur tirs, ...).
4 - Collection d'objets statiques non sujets aux tests de collision (background, animation d'explosion des ennemis, ...).

Devrais-je fusionner les collections 2 et 3 vu qu'ils sont sujets aux tests de collision

Pourquoi fusionner ? Il suffit de faire une méthode générique qui teste la collision entre 2 entités.
Si tu détermines la collision entre 2 points par exemple une simple fonction suffit non membre d'une classe
Sinon tu peux utiliser l'héritage de classe et définir une méthode de la classe de base pour déterminer les collisions

[kremvax]

Je rejoins Mindiell pour séparer les objets en "types", et j'irais même plus loin dans ce sens : quel intérêt d'avoir une liste qui contienne à la fois les tirs ennemis et les ennemis eux-même? C'est pas se compliquer la vie pour rien? Autant faire une liste dédiée aux tirs ennemis, une liste dédiée aux ennemis, une liste dédiée au tirs du joueur et basta. Ca simplifiera la lecture du code, et je ne vois aucune contre-partie.

[Mindiell]

Je rejoins Mindiell pour séparer les objets en "types", et j'irais même plus loin dans ce sens : quel intérêt d'avoir une liste qui contienne à la fois les tirs ennemis et les ennemis eux-même? C'est pas se compliquer la vie pour rien? Autant faire une liste dédiée aux tirs ennemis, une liste dédiée aux ennemis, une liste dédiée au tirs du joueur et basta. Ca simplifiera la lecture du code, et je ne vois aucune contre-partie.

Bah c'est simplement que si un tir ou un ennemi provoque la "mort" du joueur, ils sont suffisamment identiques pour les mettre dans la même liste

[SebSplo]

Je vois.
Je pense que je vais faire une liste par type. Là j'ai d'autres trucs à faire avant de passer à l'implémentation mais je vous donnerais des nouvelles.