Détection de collision

Bonjour,

Je dois faire un jeu vidéo (space shooter a la rtype) avec la librairie Allegro 4, et je me pose une question. Ce jeu implique des collisions entre entités, et je suis parti sur un principe de map de collision (hitbox). Chaque entité a deux donc deux images, celle que j'affiche à l'écran, et une autre image où je reprends uniquement les contours de l'entité d'une couleur bien spéciale.

Le rose/violet c'est la transparence dans Allegro.

Ainsi je parcours toute l'image, et dès que je suis sur une bordure je regarde les 4 pixels adjaçents et s'ils ne sont pas transparents, c'est qu'il y a collision.

Seulement voilà, quand il n'y a pas de collision, le programme parcourt tout le sprite, et fais donc beaucoup de getpixel() (fonction qui récupère la couleur d'un pixel). Cela marche très bien avec des petits sprites, mais quand ils sont plus gros, le programme lag.

Alors voilà, après vous avoir présenté ma méthode, est-ce que certains d'entre vous auraient des conseils ou d'autres idées d'algorithmes aussi efficaces (détection au pixel près) mais plus rapide?

Pourquoi ne pas comparé la position des sprites ?

Bonsoir,

La collision au pixel près est rarement une bonne idée(gourmand et rarement utile). En utilisant des bounding box plus petites, tu dois pouvoir obtenir un résultat satisfaisant.

Sinon, pour diminuer le cout d'une collision au pixel, tu peux commencer par tester si il y a collision entre 2 bounding box. De là, tu ne testes les pixels que dans la zone commune aux 2 rectangles. La zone à tester sera souvent bien plus restreinte. Aussi, peut être ne pas tester les pixels sur tes images directement, mais générer des masques pour tes images(0 transparent, 1 visible). Ce sera plus rapide que de tester les pixels de tes images, surtout si tes images sont en mémoire video.

Je me suis toujours demandé si ce qui suit est une bonne idee.

Serait il possible qu'un pixel (ou une forme quelconque en fait) qui avance dans une direction donnee sache au bout de combien de pixels (comprendre nombre de deplacement) il lui reste avant d'entrer en collision. Une fois cela calculer il suffit de decrementer la variable a chaque deplacement. Une fois a 0, pouf c'est mort. Bien sûr c'est un truc galere si l'entite change souvent de sens ou que l'obstacle est mouvant

Cirdo > Tu veux dire sans détection par pixel? Nan j'ai passé trop de temps sur ce système pour ne pas l'inclure

GurneyH > Intérresant, j'y réfléchis aujourd'hui j'en reparle ce soir

Ricocotam > Dans mon programme ce serait encore plus gourmand, mais c'est possible oui.

C'est quoi l’intérêt réelle d'aller au pixel près plutôt que de faire une bête bounding box ?

Admettons que l'on parte sur un déplacement horizontal (pour faire un shooter horizontal) de 1280 pixels (résolution 720p) parcouru en 10 secondes (un truc dynamique mais pas trop). Ca veut dire qu'un pixel est parcouru en 8ms. Si je prend ton dessin, dans le coin supérieur droit je compte 10 ou 12 pixels entre le "devant" du vaisseau et la partie en haut. 10 pixels c'est parcouru en 80ms. Le joueur a t-il le temps de faire une quelconque décision finale en si peu de temps ? (indice, d’après mes recherches les pilots de formule 1 ont des temps de réaction dans les 250ms).

Hum, ça m'ennuie de voir proposer Box2d pour un shooter 2d. J'aime bien me souvenir ce sur quoi ces jeux tournaient à l'origine (snes, pcengine, megadrive, etc…): Très peu de ressources, donc beaucoup de ruse de la part de programmeurs. Une collision bounding box, c'est rien à gérer et c'est ce qui était utilisé à l'époque. Pas besoin de sortir le bazooka à mon avis.

Bon alors j'ai pas mal lu ce que vous avez tous dis et j'ai décidé de modifier mon algo. Le principe de base reste le même, à la différence près qu'il ne s’exécute que quand deux entités sont assez proches l'une de l'autre pour qu'il y ait collision.

Stranger > C'est un sujet d'école, je ne peux pas utiliser autre chose que Allegro et du C. Peux tu développer ton idée du calcul offline s'il te plaît je ne pense pas l'avoir bien compris?

Eskimon > Je suis d'accord que pour l'interaction utilisateur ca ne change rien j'en ai conscience depuis le début. C'est uniquement pour ne pas avoir un missile qui se détruit 15-20 pixels avant le vaisseau (et oui ça se voit quand c'est le cas).

Ok j'ai compris ton idée merci de ton explication La solution que j'ai mise en place pour l'instant me convient plutot pas mal niveau performance et fiabilité, mais si besoin est j'essayerai de développer la tienne merci