Je sais pas, j´ai pas verifié. J´ai t´ai deja donné la formule qui tue (les 4 comparaisons, qui marche dans tous les cas)

==> Posté le 29 octobre 2005 à 12:01:54

Mais la c´est plus collision, c´est inclusion ^^

L´algo qe tu proposes, fil, est le meilleur a priori (qui semble etre le meme que celui proposé par Lapintade ! (j´ai lu vite fait) )
(les if avec les inégalités)

C´est connu, c´est un algorithme utilisé dans un cas AABB (tres connu)
--> Axes Aligned Bounding Box

Et jusqu´a preuve du contraire, il n´y a pas plus rapide
Meme le calcul de distance au préalable ne gagnerait pas :
en effet, le calcul de distance te rejette si la distance est trop grande. Meme si tu consideres une distance carrée, tu as plusieurs multiplications et plusieurs additions a faire.
Alors que les if avec les inégalités, c´est immédiat, et si tu en as un seul qui ne répond pas, tu return tout de suite (du coup, le plus "lent" est le cas ou ça touche, car il faut vérifier 4 if)

Dans les algos en zone critique comme cela, il faut tout optimiser

Merci beaucoup JYY

"Dans les algos en zone critique comme cela, il faut tout optimiser "
Vu le frame rate sur petites configs (et moyennes) y´a encore du boulot ^^

il faut savoir que les compilateurs optimisent également (on m´a dit que c´était valable pour tous les compilateurs)

Quand tu fais :

if (a && b && c && d)

la norme veut que la machine commence par a, touours, ensuite, si jamais (dans ce cas ou c´est que des &&) une condition est égale à 0, alors le reste n´est pas traité du tout !

ça parait bete, mais ça permet d´optimiser :
toujours mettre les conditions les plus simples (ou alors celles qui éliminent le + de tests) AVANT si il y a des && ou des || (le || sort si une condition est égale à 0)

Ainsi, cela permet d´écrire, sans risque de plantage :

if (tab!=NULL && tab[0]==3){}

Alors que l´inverse pourrait cracher :

if (tab[0]==3 && tab!=NULL){}

fil_razorback > "Vu le frame rate sur petites configs (et moyennes) y´a encore du boulot "

--> tout d´abord, je ne sais pas si tu es toujours sous SDL, mais SDL est lent quand tu te sens d´attaque, passe, par exemple, a OpenGL.

Ensuite, les tests de collisions, meme optimisés, il faut, bien sur, essayer de les limiter :

Imagine que tu aies 200 balles qui rebondissent sur ton écran (en 2D par exemple)
et que tu veux tester les collisions :

La méthode bourrine est de faire un double for : 200*200 = 40000 tests par frame !! !
Meme si l´algo de collision est optimisé : ouch !!

Dans ce cas la, il faut optimiser encore en amont. Dans un tel cas, une méthode, par exemple, est le QuadTree :

tu sépares ton écran en 4, puis chaque sous zones en 4, et récursivement : tu fais un arbre a 4 fils a chaque fois.
Le but est de ranger une balle dans la bonne "case" : si elle en chevauche 2, la ranger dans le pere commun aux cases.
Ainsi, pour les tests de collisions, tu n´as besoin de tester, pour une balle, que celles de la liste de la meme case, ou alors des cases adjascentes : inutile de tester la collision avec une balle située dans une case de l´autre coté de l´écran : de toute façon, ça ne touche pas !! !

Apres bien sur, il y a des calculs supplémentaires : a chaque mouvement, il faut replacer les balles dans leurs nouveaux carreaux... Mais tu peux profiter du fait que les balles ne peuvent pas se "téléporter" donc de toute façon, si la balle change de carreau, ce sera un voisin, etc....

Ce sont des optimisations pour des cas comme ça
(évidemment, si tu as 4 balles sur ton écran, il est ridicule de faire un quadtree...)

Le meme algo en 3D s´appelle Octree.

Tres interessant, je connaissais pas ce principe
Merci beaucoup ^^

Ah oui, je bosse en flash

J´ai jamais bossé sous SDL ni Open GL d´ailleurs, enfin bon c´est dur de se souvenir de tout le monde

tu sais qu´il existe en flash un fonction qui gere les collision (hitTest)

J´ai pas tres envie de m´embarquer dans des collisions avec des movie clips vides et ce genre de choses
D´autant plus que je n´ai jamais été convaincu par la rapidité de cette fonction

Ben justement flash fonctionnant en vectoriel c´est tres simple pour le log de savoir si deux droites se coupent.
Je l´ai utilisé pour mon jeux et ca fonctionne tres bien.
Je sais pas trop comment tu compte faire ton jeu, mais les movieClip sont un peut la base de tout en flash.
Ensuite la fonction duplicateMovieClip te permet de creer dynamiquement des clip sur ta scene.

"Mais la c´est plus collision, c´est inclusion"

Oops

Oui, pour les inclusion je connais pas de fonction de flash. Mais bon je lui disais juste que c´est pas utile de refaire des outils deja creer et surement plus optimisé que ce qu´il pourrait faire.

"Ben justement flash fonctionnant en vectoriel c´est tres simple pour le log de savoir si deux droites se coupent."
Mon jeu a des graphismes tout en bitmap ^^

"Je l´ai utilisé pour mon jeux et ca fonctionne tres bien.
Je sais pas trop comment tu compte faire ton jeu, mais les movieClip sont un peut la base de tout en flash.
Ensuite la fonction duplicateMovieClip te permet de creer dynamiquement des clip sur ta scene."
Je suis plus un noob quand même

Ah pardon je croyais

Sinon, y en a qui connaissent un algo de détection de collision de sprite sans rectangle ? J´y ai réfléchi un peu, mais je vois pas...

C´est du suicide de ne pas encadrer ton sprite.
Ce que tu peux faire, c´est te dire :
"si la boite englobante de 2 sprites ne se touche pas, jamais les sprites se touchent"
Donc de ce fait : détection en 2 passes :
- d´abord tu detecte si les boites se touchent
- ensuite, pour précision, tu peux considérer l´algorithme du pixel perfect, ou alors des sous boites englbantes...

JeanYvesYves, t´es génial ! Je vais déjà tenter le système des sous boîtes englobantes, à défaut de connaître l´algo du pixel perfect...

Mais merci!

(à titre indicatif, c´est pour gérer la collision entre mon perso et la pente dans un petit jeu de plateforme 2D genre sonic (en version moins rapide, évidemment !) écrit en C++ que je suis entrain de faire... grâce à ton tuto !)

au passage, on a laisse tombe le pixel perfect depuis longtemps pour certaines raisons ; on peut encore s´en servir pour du picking, et encore. Le fait que selon les machines et les config, les pixels en question, peuvent changer (haute/basse resolution, filtres/pas filtres, etc.) : ce qui peut se reveler inequitable pour des joueurs car on a alors des situations non deterministes qui dependent de la machine ; en se basant sur les concepts sous-jacents qu´on associe aux objets (bouding boxes, etc.) 1) c´est plus rapide 2) c´est consistant

Ah ! Mais ton cas est très précis
Il ne nécessite pas un algo de collision "quelconque"
Je vais te dire comment ils font dans Mario et Sonic (et tous les jeux du genre)

Déja, considere un monde simple sans pente (juste des tiles droits)
Dans ce cas, facile de calculer les collisions (avec des boites englobantes simples)

Pour les pentes, c´est la meme chose :
consideres juste des tiles qui ont cette allure (comme cette piece de légo)

http://www.ultradark.com/images/Lego-005-DoubleSlope.jpg

Une partie ciel, une partie terre.
Pour tester la collision avec ça, tu le fais en 2 passes :
1) collision tile normale (boite englobante du tile de pente)
2) si ça touche, alors il faut détecter si le sprite est sur la partie pente, ou la partie "air"
pour cela, dans la mesure ou on simplifie toujours par une pente droite *, en fonction de la position X du sprite par rapport au tile, tu sais immédiatement ou est le Y.
Je te conseille dans ce cas de considérer un seul point : celui en bas au milieu de la boite englobante de Sonic.
Si ce point est SOUS la ligne de la pente, il y a collision, sinon, non.
(* quand dans les mario ou Sonic, tu vois une pente qui devient de plus en plus pentue, c´est simplement des tiles plus ou moins pentus posés les uns a coté des autres, mais chaque tile a une pente constante. )

A la sortie, pour la machine, ça revient exactement comme un cas de tilemapping simple. Pour faire l´effet pente, tu donnes une force a ton bonhomme quand il touche le tile pente, force qui fera glisser le gars

toute une histoire d´astuces !
Dis toi que les programmeurs de jeu recherchent la rapidité, donc ils évitent tant qu´ils peuvent les cas généraux calculatoires, et utilisent des tas d´astuces comme celle la !

Les sous boites englobantes sont davantages utilisées pour les Street fighter. (quoiqu´on combine ça avec des techniques de points d´action dans ce cas)