Discussion :

[mach1]

Bonjour à tous,

J'essaie de créer un jeu de 2D en c avec la bibliothèque SDL.
Et le problème est que je souhaite à présent gérer les collisions entre ennemis dans mon jeu (pour les interdire d'être les uns sur les autres).
Sachant que les propriétés de mes ennemis sont stockés dans un tableau, j'ai pensé à la procédure suivante :

-Afin de déplacer un ennemi, à chaque pas du déplacement en cours, parcourir le tableau d'ennemis et pour chacun des autres ennemis vérifier qu'il n'est pas en collision avec l'ennemi que l'on est en train de déplacer.

-Pour déplacer l'ensemble des ennemis, répéter cette procédure pour chacun des ennemis.

Le problème est que cette technique me parait trop lourde et couteuse en ressources mais que je ne vois pas comment faire autrement.
J'aurais donc souhaité avoir des suggestions.

Merci par avance.

[pseudocode]

Pour limiter le nombre de tests à faire, on peut quadriller l'espace de jeu.

Chaque ennemi se trouve alors dans une case du quadrillage (il peut y avoir plusieurs ennemi dans une meme case). On peut alors limiter les tests aux ennemi présents dans la meme case, ou dans les 8 cases voisines.

[Mat.M]

Pour limiter le nombre de tests à faire, on peut quadriller l'espace de jeu.

Chaque ennemi se trouve alors dans une case du quadrillage (il peut y avoir plusieurs ennemi dans une meme case). On peut alors limiter les tests aux ennemi présents dans la meme case, ou dans les 8 cases voisines.

salut mais le problème restera le même non ?
Parce que pour diviser l'espace du jeu on va devoir boucler sur toute la liste des personnages joueurs et non joueurs ?
Sinon on m'a parlé d'utiliser des quadtrees comment mettre cela en oeuvre ?
Merci pour les réponses

[Zavonen]

Parce que pour diviser l'espace du jeu on va devoir boucler sur toute la liste des personnages joueurs et non joueurs ?

Cela il faudra de toutes façons le faire mais le quadrillage vise à remplacer cette boucle par une boucle très simple.
On peut en effet considérer la case à laquelle appartient l'objet comme une de ses données membres constamment mise à jour lors des déplacements.
De sorte que pour détecter les collisions on peut éliminer d'entrée les couples d'objets appartenant à des cases trop éloignées pour se concentrer sur ceux pour lesquels une collision est a priori possible.

[Mat.M]

ok merci pour la réponse il faut que je cogite dessus....

[Obsidian]

-Afin de déplacer un ennemi, à chaque pas du déplacement en cours, parcourir le tableau d'ennemis et pour chacun des autres ennemis vérifier qu'il n'est pas en collision avec l'ennemi que l'on est en train de déplacer.

-Pour déplacer l'ensemble des ennemis, répéter cette procédure pour chacun des ennemis.

Le problème est que cette technique me parait trop lourde et couteuse en ressources mais que je ne vois pas comment faire autrement.

Tu peux optimiser sensiblement la chose à peu de frais en triant les positions de tes personnages dans une liste chaînée et en maintenant cette liste triée. L'avantage de la liste chaînée est de rendre faciles les insertions.

Ainsi, les personnages en collision sont forcément consécutifs dans ta liste. Si deux personnages ne coïncident pas, alors tu sais que les suivants ne le feront pas non plus.

[Zavonen]

Tu peux optimiser sensiblement la chose à peu de frais en triant les positions de tes personnages dans une liste chaînée et en maintenant cette liste triée.

Une position dans le plan= un couple de valeurs (x,y). Trier suppose un ordre. Je ne connais aucun ordre canonique sur R^2.
J'appuie par contre fortement la proposition de pseudocode.

[pseudocode]

Une position dans le plan= un couple de valeurs (x,y). Trier suppose un ordre. Je ne connais aucun ordre canonique sur R^2.
J'appuie par contre fortement la proposition de pseudocode.

Pas trop fort quand même, elle n'est pas bien solide.

[Obsidian]

Une position dans le plan= un couple de valeurs (x,y). Trier suppose un ordre. Je ne connais aucun ordre canonique sur R^2.

Je sais : c'est volontairement simplifié. C'est tout-à-fait adapté si la position dans le plan des personnages suit un chemin, par exemple, et sinon, rien n'empêche de maintenir deux listes en parallèle, l'une pour x, l'autre pour y, et ne retenir que les éléments qui sont consécutifs dans les deux listes.

À dire vrai, je pense que ce ne serait pas plus coûteux que la solution de pseudocode car, dans ce cas, il faut quand même passer en revue tous les personnages pour savoir s'ils se trouvent dans une case pour, ensuite, examiner de plus près les colocataires et vérifier s'ils rentrent effectivement en collision.

Je pense qu'au final, la complexité n'est pas beaucoup meilleure que comparer directement leur positions, sauf à numéroter toutes les cases et à classer les personnages dans une liste triée par numéro de case pour retrouver directement les co-occupants, auquel cas on se ramène exactement à ma suggestion initiale : une liste triée sur un ensemble ordonné à une dimension.

[pseudocode]

À dire vrai, je pense que ce ne serait pas plus coûteux que la solution de pseudocode car, dans ce cas, il faut quand même passer en revue tous les personnages pour savoir s'ils se trouvent dans une case pour, ensuite, examiner de plus près les colocataires et vérifier s'ils rentrent effectivement en collision.

Généralement on a une liaison bidirectionnelle entre les personnages et la "Tile Map". On n'a donc pas besoin de passer tous les personnages en revue.

[mach1]

Tout d'abord, merci aux personnes qui ont pris sur leur temps précieux pour me répondre.

D'après ce que j'ai pu lire je pense qu'il peut être une bonne idée de faire un quadrillage de mon niveau comme il me l'a été conseillé.

Pour l'implémentation, je pense créer un tableau à 2 dimensions dont chaque case contiendrait une liste des ennemis qui touchent la zone indexée par la case.
Pour chaque déplacement d'ennemi je mettrais à jour les listes.

Au final, lorsque je déplacerais un ennemi je n'aurais donc qu'à vérifier s'il est en collision avec les ennemis présents dans les zones du quadrillage que l'ennemi à déplacer touche.

Ainsi, j'aimerais savoir si cette idée vous parait valide,
et si elle l'est, si le fait d'ordonner les listes pouvait être utile ou non.