Question sur les collisions dans les jeux...

[niluge]

Bonjour,

Je me pose actuellement quelques question en ce qui concerne les collisions (pixel perfect ou non, ça n'a pas d'importance pour la suite) dans les jeux, et en particuliers les danmaku etc.

Petite question aux développeurs donc :
Généralement, dans tout ce que j'ai pus voir sur internet, la méthode de détection des collisions proposé, est là suivante :

On calcul le déplacement du vaisseaux et des boulettes puis on calcul les collisions a partir des positions à la fin du déplacement.

Bon dans l'ensemble, ça marche pas mal, mais voila, dans certains cas ça peux poser problème.
Exemple :

On prend un vaisseaux qui se déplace verticalement 15 pixel par frame et qui dispose d'une hitbox réduite sous forme d'une carré de 10 pixels de larges

En face, une boulette avec un diamètre de 10 pixels qui se déplace verticalement de 15 pixels par frame elle aussi

En debut de frame, la boulette qui se déplace purement verticalement se trouve a un pixel de toucher la hitbox du vaisseau qui lui aussi se déplace verticalement (mais pas dans le même sens, bien sur ^^)

Si on fait le calcul, on se rend compte alors qu'en fin de frame, la boulette se trouve derrière la hitbox du vaisseau sans qu'il y ai collision (je vous laisse faire le calcul)

Donc question : Est ce que vous gérez ce genre de cas et si oui comment ? Calcul des vitesses et tailles des hitbox pour que ça n'arrive jamais ? calcul intermédiaire ? vous n'y aviez même pas songé ? vous vous en foutez ^^ ?

Et dans les jeux pro a votre avis, ça se passe comment ? (je pense particulièrement aux danmaku, car ils gèrent des hitbox très réduites)

[Yoshiki]

Question intéressante.
N'étant pas développeur, je n'ai pas la réponse même si je me la suis souvent posée.
J'ai hâte de voir les éventuelles premières réponses explicatives.

[Gunny]

La méthode que tu décris est le test de collision virtuelle si j'ai bien compris.

C'est un problème qui s'avère délicat en fait...

On peut utiliser des "tirs de trajectoires". Dans le cas ou ces lignes se coupent, pas de soucis pour la détection ( j'ai vu une formule matheuse dans un tuto de gamemaker sur un site anglais, c'est relativement complexe ). Ces tirs se compliquent pour des trajectoires paraboliques...

Là où ca se complique vraiment, c'est quand ces lignes ne sont pas coupées de facon nettes et qu'il faille prendre en compte la géométrie de la hitbox.

Gamemaker est très généreux et offre une pléthore de fonctions prêtes à l'emploi ! Mais cela dit, il faut une bonne connaissance de ces mécanismes pour arriver à des résultats concluant meme avec de simples hitbox carrées ( et je suis loin d'être un pro sur la compréhension de ces mécanismes )

Je ne peux pas trop m'étendre sur les autres langages de programmation malheureusement...

[niluge]

virtuelle tu dit ? tiens c'est marrant, j'avais entendu les terme detection statique et dynamique, mais pas virtuelle ^^

Effectivement, on peut se baser sur des equations du mouvement, ce qui est relativement facile pour le rectangle, mais qui me semble très lourd pour du pixel perfect. C'est pour ça que je m'interroge sur les algo utilisé

[Gunny]

Mes connaissances sur le sujet s'arrête ici ^^ Il va falloir demander à quelqu'un d'autre

[Risike]

J'ai déjà eu ce problème plusieurs fois ! Même sur calculette graphique quand j'étais au Lycée !

Je ne l'ai jamais vraiment réglé en fait... La formule mathématique est trop complexe pour moi...

Mais je viens de penser à un truc :

Ton écran se rafraichit x fois pas secondes, ce qui provoque des mouvements saccadés (non visible mais réels pour le calcul des collisions, ce que tu explique quoi).

Je suppose que dans ta boucle principale tu as :

- Scan des contrôles
- Mouvements des sprites
- Attente pour synchro sur x FPS
- Rafraichissement de l'écran

Plutôt que de déplacer ta boulette de 15 pixels par exemple, de tester, d'attendre et de dessiner l'écran. Pourquoi ne pas simplement la déplacer 5 fois de 3 pixels, tester les collisions entre chaque déplacement, attendre la synchro, et dessiner une fois que tout est calculé. C'est des calculs extrêmement rapides à faire, ça ne devrait pas baisser ton framerate.

C'est un peu crade (tiens Firefox ne connait pas crade...) comme technique mais ça peut remplacer des formules de math trop complexes.

[yenshin]

perso moi je le fait pas, meme si j'avais pensé au probleme.

explication: je suis en pixel quasi perfect et ca prend deja beaucoup de resource.
faire un calcul comme ca couplé a du pixel perfect c'est un peu se tirer une balle dans le pied.

Le mieux c'est de rendre cohérent la taille des machins que tu tire et leur vitesse pour éviter cette effet de "teleportation".

par exemple si ta une boulette qui fait 10 px par 10 px il faut eviter qu'elle se déplace à plus de 10 px + la taille de ta hitbox. comme ca tu bloques toi même ce systeme de "teleportation de collision" (je ne sais pas si le terme est bien choisi).

donc ca implique de controlé la direction des objets en déplacement et de connaittre la taille des trucs graphique que tu as ou des zone de collision que tu as toi-même créé en donnéé pur.

voila voila

[Arnofx3d]

Oui le plus simple c'est de faire en sorte que ton objet se deplace de moins de pixel que la taille de la zone de collision... (pas sur d'etre claire là...)

Apres pour ce qui est de detecter les collisions, les consoles et les bornes le font en hardware... Pour ca il leur faut des sprites en noir et blanc. Quand tes masques de collision sont exactement comme le sprite d'origine ca ressemble un peu a des masque d'opacité comme dans photoshope ou dans les logiciels de montage video, mais tu peux leur donner la forme que tu veux!

Sinon, il faut creer une matrice par objet qui enregistre a chaque instant la position de chaque pixel de l'objet. Puis tu fais des comparaisons entre les differentes matrices: Si tu as 2 elements de 2 matrices differentes au meme endroit -> Collision!

J'espere avoir été utile...

[niluge]

t'inquiete, pour la colision pixel perfect, je connais ^^. je m'interroge surtout sur les cas ou les collisions ne sont pas détecté pour la cause que j'ai évoqué dans le premier post . Plus par curiosité d'ailleurs, mon projet en cours étant plutôt une plateformer ou le problème se pose moins vue la taille des sprites. Mais pour plus tard, et par curiosité intellectuelle je me pose la question. Et puis les réponses pourraient intéressé certaines personne ici

[Radigo]

Mon avis rejoins (de loin) celui de Risike parce que calculer du vecteur sur 200 boulettes ça me parait un peu démesuré pour un shmup (sauf si tu as de la dynamique et que tu optimises comme un porc). Du coup, voici ma technique :

1 - Commencer par taper dans un frame rate confortable, genre 60fps (game maker n'a pas cette valeur par défaut il me semble). Déjà à 60fps si tes boulettes se déplacent de 10px/frame elle commencent à fuser...
2 - ensuite se démerder pour que la boulette ne puisse pas traverser le vaisseau sans le toucher, pour ça tu peux :
- limiter la vitesse max de tes boulettes à la plus petite dimension de ton vaisseau (vraisemblablement la largeur dans un shoot vertical).
- ou bien agrandir la taille de tes boulettes pour faire en sorte que même à très grande vitesse l'écart entre 2 affichage soit plus petit que la plus petites dimension de ton vaisseau. Là les techniques sont multiples, si tu détectes par hitboxes tu peux scaler ta boulette, si tu détectes par points tu mets plusieurs hitpoints répartis intelligemment dans ta boulette. Cette solution a aussi l'infini avantage d'améliorer la lisibilité (plus rapide donc moins de temps pour la voir + plus gros = EPIC WIN).

Dans les psikyo par exemple (ou des jeux comme Dangun Feveron), tu remarquera que les boulettes très rapides sont plus grosses que les autres (et moins nombreuses aussi).

[Gunny]

Je confirme le 1 de radigo, gamemaker travaille de base à 30 FPS.

[niluge]

Ah bah voila, c'est interessant tout ça...

Donc certains choix de design sont contraints sur certain points par la technique de collision. Savoir que dans certains jeux (apparemment les Cave déja) La vitesse des boulettes ainsi que leur tailles sont plus ou moins imposé par les algo de collision, je trouve ça interessant pour les designer en herbe.(Je le repete, j'ai créé ce post par curiosité intellectuelle, ce n'est pas encore dans mes projet de creer un shmup).

le fait de definir la vitesse et la taille des hitbox en fonction des collisions faisait partie des idée première a me passer par la tête en songeant a ce problème. Mais je me posais des question quand au contrainte de design que cela impliquait. Mais l'exemple de Radigo semble indiqué que c'est ce qui a été choisi.

L'idée de faire le deplacement en 2 ou trois fois pour une frame me semble interessante si on se limite aux objets proche avec forte possibilité de collision (exemple : Un objet est a 3 pixel d'un autre -> detection de colission precise
plus loin ? -> algo simple)

[Radigo]

L'idée de faire le déplacement en 2 ou trois fois pour une frame me semble intéressante si on se limite aux objets proche avec forte possibilité de collision (exemple : Un objet est a 3 pixel d'un autre -> détection de collision précise
plus loin ? -> algo simple)

Mettre en parallèle 2 algos de collision c'est un peu anti rendement...

Pour optimiser ce genre de truc (proche / éloigné) il existe la méthode des quad tree. Pour simplifier : on découpe l'aire de jeu en cases et on ne détecte les collisions que dans la case où se trouve le perso + les cases adjacentes. Il parait que ça booste bien les perfs et que c'est beaucoup plus rapide que simplement calculer la distance entre le perso et tout ce qui vient puis de lancer la détection de collision.

Exemple en flash

Je ne sais pas faire marche ce genre de truc, l'exemple n'est pas adapté mais le concept peut être étendu à ton idée.

[Y^nO]

Je confirme le 1 de radigo, gamemaker travaille de base à 30 FPS.

...Disons que c'est la valeur entrée par defaut dans le soft...rien ne t'empeche de changer cette valeur pour 60 63 ou 319 si ça te chante.

En parlant de ça GM8 a une toute nouvelle gestion des hitbox 2D, avec possibilité de faire des hitbox rondes, ovales, en prismes ou rectangle pour bien coller au sprites.
Évidemment il gère les collisions tout seul comme un grand, grâce a la fonction(oh ben tiens) 'collision'.
Je ne sais pas trop comment GM calcule ça, mais même a une vitesse débile mes boulettes font mouche sur une hitbox 1X1 pixel.

PS: dsl pour le semi hs.

[Alec]

j'ai fait aussi ce genre d'essai aussi et c'est vrai ça marche avec GM !

ce qui est bien avec game maker c'est qu'on peut dessiner le masque de collision directement depuis le menu d'édition du sprite et ça simplifie beaucoup les choses !

[Gunny]

http://www.siteduzero.com/tutoriel-3-25 ... sions.html

ca devrait apporter quelques réponses

[Yoshiki]

Très intéressant !
Merci pour le lien.

[Radigo]

http://www.siteduzero.com/tutoriel-3-25 ... sions.html

ca devrait apporter quelques réponses

Je balance direct dans l'annuaire.