Discussion :

[hbx360]

Bonjour, je ne sais pas si je suis dans la bonne section. Désolé par avance.

Je suis en train de faire un petit jeu sur SDL, J'ai un vaisseau, et quand je tire, s'il y a collision avec une balle, je voudrais l'effacer du jeu. Pas seulement ne plus l'afficher sur l'écran mais aussi et surtout effacer toutes les données concernant la balle.

Actuellement mes balles sont gérées par un tableau de struct. je souhaiterais savoir en fait s'il vaut mieux passer par un tableau de struct ou par une liste chainée ?
C'est sûr qu'avec une liste chainée, on n'a pas besoin de réorganiser son tableau ni de le trier : on a juste à supprimer les données de la balle en supprimant de la liste la struct concernée.

Merci.

[Obsidian]

Bonjour,

Actuellement mes balles sont gérées par un tableau de struct. je souhaiterais savoir en fait s'il vaut mieux passer par un tableau de struct ou par une liste chainée ?

Tu mets le doigt sur quelques notions fondamentales en programmation de relativement bas niveau (c'est-à-dire « proche de la machine ») : la gestion de la mémoire et le choix des bonnes structures de données.

Concrètement, l'approche optimale va dépendre du nombre de balles que tu mets en jeu et de la manière dont tu les passes en revue.

Une liste chaînée te permet de réorganiser facilement ta liste mais t'oblige à la parcourir séquentiellement lorsque tu veux retrouver un élément. Un tableau, a contrario, te permet d'accéder directement à un élément si tu connais un index mais t'oblige à copier les données si tu veux déplacer ses éléments, ce qui peut être très coûteux si ces éléments sont volumineux.

C'est sûr qu'avec une liste chainée, on n'a pas besoin de réorganiser son tableau ni de le trier : on a juste à supprimer les données de la balle en supprimant de la liste la struct concernée.

Attention : garde à l'esprit qu'une fois l'élément retiré de ta liste, il persiste en mémoire si tu ne le libère pas d'une façon ou d'une autre. En langage C, il n'y a pas de garbage collector pour faire le travail à ta place de façon transparente…

[hbx360]

Merci pour ta réponse, donc a moi de choisir en fonction de ce que je souhaites faire.

Est-ce les 2 seules solutions ou y en a t-il d'autre?

Dans le jeux vidéo est-ce qu'il y a une méthode plus utilisé qu'une autre si quelqu'un sait ?

[Sve@r]

Une liste chaînée te permet de réorganiser facilement ta liste mais t'oblige à la parcourir séquentiellement lorsque tu veux retrouver un élément. Un tableau, a contrario, te permet d'accéder directement à un élément si tu connais un index mais t'oblige à copier les données si tu veux déplacer ses éléments, ce qui peut être très coûteux si ces éléments sont volumineux.

Bonjour

Il y a peut-être une 3° solution qui combine (en partie) les avantages des deux: laisser les éléments en vrac mais stocker leurs adresses dans un tableau (d'adresses). On conserve l'avantage de pouvoir accéder à l'élément [i] et si on doit supprimer l'élément [x], on a juste des adresses à manipuler dans le tableau.

Et pour éviter de tout décaler on peut alors remplacer l'élément [x] qui disparait par juste le dernier. Exemple: mon tableau contient "a", "b", "c", "d", "e" ; je supprime le "b" alors mon tableau devient "a", "e", "c", "d" (un seul déplacement au lieu de 3)...

[hbx360]

Merci pour ton aide.

[CodeurPlusPlus]

Est-ce les 2 seules solutions ou y en a t-il d'autre?

Il y en a d'autres, autant qu'on veut.

Tableau : accès à un élément en temps constant, ajout ou suppression en temps constant si l'ordre n'a aucune importance, en temps linéaire sinon.

Liste chaînée : accès à un élément en temps linéaire, ajout ou suppression en temps constant si on sait déjà à quel endroit ajouter ou supprimer.

Tableau et liste chaînée : recherche en temps linéaire que les données soient triées ou non.

D'une manière générale les tableaux et les listes chaînées font partie de ce que l'on appelle les séquences. Une séquence est une succession d'éléments qui se suivent les uns les autres dans un certain ordre, que parfois, on ne doit pas changer. Un arbre ou un graphe ne font donc généralement pas partie des séquences car leurs sommets ne sont pas rangés "à la queue-leu-leu" comme les cellules d'une liste ou les cases d'un tableau.

Tes sprites peuvent être stockés dans n'importe quel type de séquence... ou même dans une structure plus complexe si c'est nécessaire (tout dépend de la complexité de ton jeu).

Il existe un type d'arbre qui est parfois utilisé pour stocker les éléments d'une séquence : les arbres 2-4. Le principe est que les éléments de la séquence sont stockées dans les feuilles, "de gauche à droite"... les noeuds internes servent uniquement à accélerer les opérations de recherche, ajout, suppression, etc. Cette structure de données est assez difficile à implémenter (l'algorithmique des arbres n'a jamais été simple...) mais, ce qui est génial, c'est que toutes les opérations de type recherche, ajout, suppression sont en temps logarithmique.

Bilan des courses :
- si on a surtout besoin d'accéder rapidement à des éléments dans un ordre non séquentiel, on fait plutôt avec un tableau ;
- si on a surtout besoin d'ajouter ou supprimer rapidement, une liste chaînée fera mieux l'affaire ;
- si on a besoin de faire autant d'accès directs que des opérations d'ajout ou de suppression, les arbres 2-4 peuvent être un bon compromis.

Mais dans tout cela, il y a une autre question qu'il faut se poser avant : combien y'a-t-il de sprites de balles (ou de sprites tout court) en même temps à l'écran dans ton jeu ? Un nombre sans doute très petit par-rapport à, mettons, le nombre de cycles d'horloge du ou des microprocesseur(s) par seconde. Donc que tu te serves de tableaux, de listes, et ce quel que soit la stratégie de gestion de la mémoire que tu choisis, il est peu probable que ton jeu perdre en performance à cause de ces choix. Le mieux c'est donc que tu choisisses une structure simple (tableau ou liste chaînée par exemple), que tu testes le jeu avec... quitte à changer plus tard si cela pose un problème de performance, ce qui m'étonnerait.

Sinon, pour ce qui est des cycles d'allocations / désallocations de mémoire. Souvent, tu vas désallouer une balle (par ce qu'elle est entrée en collision avec un sprite ou un mur, parce qu'elle est sortie de l'écran), pour en réallouer une autre peu de temps après, une nouvelle qui vient d'être "tirée". Donc pour éviter de faire des appels hyper fréquents à malloc et à free (ou à leurs amis), on peut utiliser des memory pools ou des buffers circulaires, qui aident à réutiliser sans cesse les zones de mémoires allouées pour d'anciennes balles pour les nouvelles... mais là encore : commence par quelque chose de simple et naïf, et puis passe à quelque chose de plus complexe seulement si c'est nécessaire (ou pour apprendre). Et puis le plus important quand on programme en C : s'assurer que son programme n'a pas de fuite de mémoire !

Dans mon jeu Nullotron II, il peut y avoir plusieurs centaines de sprites en même temps (en comptant les très nombreuses petites ballounettes) dans les niveaux avancés. Les sprites (plus précisément des pointeurs vers ceux-ci) sont rangés dans un tableau de listes chaînées (cool, pas besoin d'abres 2-4 à la con). Dans la première liste du tableau sont par exemple rangés tous les sprites ennemis, dans la deuxième toutes les balles tirées par le joueur, dans la troisième les sprites amis, dans la quatrième les balles des ennemis, dans la cinquième les bonus, etc. (ce n'est sans doute pas le bon ordre mais passons, tu as compris le principe). A chaque mise à jour de l'affichage, les sprites de chaque liste sont affichés, dans l'ordre du tableau, puis, pour chaque liste, dans l'ordre de la liste. Les cellules de chaque liste sont allouées à l'aide d'un memory pool. Les sprites vers lesquelles ces cellules pointent sont allouées à l'aide d'un autre memory pool. J'ai fait des tests qui ont prouvé que le jeu n'était ainsi pas plus rapide qu'avec de simples appels à malloc et à free... mais qu'en revanche la fragmentation de la mémoire était bien plus petite ! (malheureusement ce n'était pas mon objectif premier... je voulais avant tout gagner en vitesse d'exécution).

Tout cela pour te dire que le sujet des structures de données et que celui de la gestion de la mémoire sont très vastes, qu'ils ne sont pas spécifiques au développement de jeux, mais que bien sûr, les programmeurs de jeux doivent se poser ces questions autant que les autres
(et aussi que ce n'est pas parce que c'est relativement bas niveau que c'est inintéressant )

Dans le jeux vidéo est-ce qu'il y a une méthode plus utilisé qu'une autre si quelqu'un sait ?

Je ne pense pas qu'il y ait un consensus sur la question... ça dépend de la culture informatique du programmeur, au sens large (la question n'étant pas du tout spécifique au jeu vidéo), mais aussi du langage choisi, de la base de code qui existe déjà, des habitudes de l'entreprise (si c'est un projet pro).

[hbx360]

Merci pour ton aide et tes explications, je vais me tourner vers un tableau de pointeur.
J'ai mis une boucle de 20 millisecondes pour faire le changement de position des balles, du vaisseau, et le tire + les vérif si il y a eu collision + le blitage.
Effectivement il n'y en aura pas, des masses, des balles. Je mettrais peut être ensuite des vaisseaux aliens à la place des balles comme dans space invader ou sinon me diriger vers une sorte d'arkanoïde.

@CodeurPlusPlus : Oui c'est mieux de commencer simple j'en ai bavé pour les collisions je suis arrivé a quelque chose de pas trop mal pour moi, mais il y a pas mal d'imperfection ; c'est assez chaud quand même si en plus on doit gérer pour les balles qui s'entre chocs le replaçage après collision pour essayer d'avoir un rendu beaucoup plus propre. Je me suis aussi servi de la technique que tu as utilisé dans le jeu de la taupe pour les collisions au pixel près car sur le vaisseau il y a une pente a gauche et a droite et si j'avais fait avec la AABB on vois la balle rebondir dans le vide.

[Matt_Houston]

Pour rebondir sur le propos de CodeurPlusPlus, voici deux variantes que j'utilise assez souvent pour des objets de taille fixe dont la création et la destruction interviennent dans un ordre complètement aléatoire, si ça peut donner des idées :

• tableau de struct non trié, non compacté, avec un curseur de type size_t qui stocke l'index de la première « case libre ». Il faut un champ dans la structure qui permette de déterminer si l'élément est actif (« alloué ») ou inactif (« libre »), ça peut être un enum actortype_t avec une valeur NONE. Si le tableau est très fragmenté, le parcours de la séquence d'éléments peut-être assez inefficace (il faut parcourir les blocs d'éléments libres afin d'atteindre les prochains éléments) mais c'est indétectable dans la plupart des cas (merci la taille actuelle des caches CPU).
• liste chaînée « en place » : en partant du tableau précédent, on ajoute des champs pointeurs next et prev à la struct. Les éléments sont toujours dans un tableau mais le parcours est ainsi réalisé sur cette liste et les éléments s'en trouvent virtuellement compactés.

[Médinoc]

Dans certains cas où l'ordre (et l'adresse mémoire) des objets n'a pas d'importance, on peut aussi utiliser la technique de swapper celui qu'on veut supprimer avec le dernier élément, puis réduire la longueur de 1...

[Matt_Houston]

Très juste, il faut également se demander si le système permet que les pointeurs/itérateurs soient invalidés.

[hbx360]

Merci pour vos commentaires.

on peut aussi utiliser la technique de swapper celui qu'on veut supprimer avec le dernier élément, puis réduire la longueur de 1...

Oui ce serai pas mal je pense que je vais me diriger vers un truc comme ça surtout que c'est assez simple à mettre en oeuvre.

Sinon je voulais faire dans le même principe mais en décalant tout les pointeurs sa prendrais plus de temps pour le faire mais comme dit plus haut pour ce que je veux faire cela ne doit pas poser de problème.