1

Salut à tous,

Le problème du jour est le suivant:
Il s'agit de faire en C une fonction qui permettrait de détecter lorsque 2 sprites entrent en collision.

Données du problème:
Les sprites entrant en collision ont une largeur 'W' et une hateur 'H'. Ces valeurs peuvent changer. Ainsi, un sprite de HxW peut entrer en collision avec un sprite de HxW.

On aurait ainsi une fonction ayant l' entête suivante:
bool SpriteCollide(SPRITEDESC s1, SPRITEDESC s2);

avec en sortie un booléen qui dit vrai si les sprites entrent en collision, faux sinon.

SPRITEDESC étant une structure simple:
typedef struct _SPRITEDESC
{
	POINT		location;
	DIRECTION		direction;
	SIZE		size;
	unsigned short*	table;
	unsigned short*	masks;
} SPRITEDESC, *PSPRITEDESC;

typedef struct _POINT
{
	int		x, y;
} POINT, *PPOINT;

typedef struct _SIZE
{
	int		cx, cy;
} SIZE, *PSIZE;

typedef enum _DIRECTION
{
	DIRECTION_NONE,
	DIRECTION_UP,
	DIRECTION_DOWN,
	DIRECTION_LEFT,
	DIRECTION_RIGHT,
} DIRECTION;


Certain sprites peuvent bouger (personnages et ennemies) et d'autres sont statiques. Pour les sprites qui peuvent bouger, il faut tenir compte de la directon. Les sprites statiques ont l'attribut DIRECTION_NONE.

Merci d'avance pour le coup de main.

Cordialement.

Fred.

There is no spoon.

2

Voici une méthode : vérifier si le rectangles recouvrant les sprites se recouvrent entre eux, puis ensuite procéder à une détection au pixel près.
avatar
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas. »

3

concrètement, ça donne quoi?
There is no spoon.

4

à quelle condition est-ce que deux segments [a,b[ et [c,d[ se recouvrent ?

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

5

je doute qu'il va voir où tu veux en venir grin

6

(peu importe, on verra le moment venu tongue j'ai aucune envie de balancer une solution direct en tout cas)

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

7

ben je crois que tout est dit dans l'énoncé... je vois pas ce que je peux dire de plus...

j'ai 2 rectangles et j'aimerais savoir s'ils se touchent selon la direction de chacun et ce, au pixel près...

je vois pas bien comment je peux dire/écrire les choses autrement...
There is no spoon.

8

J'ai vraiment du mal à comprendre comment tu peux avoir un aussi bon niveau en codage et etre aussi nul en algorithme :s
Tout ce qui passe pas par le port 80, c'est de la triche.

9

boulifb :
ben je crois que tout est dit dans l'énoncé... je vois pas ce que je peux dire de plus...

j'ai 2 rectangles et j'aimerais savoir s'ils se touchent selon la direction de chacun et ce, au pixel près...

je vois pas bien comment je peux dire/écrire les choses autrement...

Oui, voilà, mais du coup moi pour t'aider je te dis : soit deux segments qui appartiennent tous les deux à une droite. Tu connais leurs extrêmités : le premier a pour extrêmités [a,b[, l'autre a pour extrêmités [c,d[. A quelle condition sur (a,b,c,d) est-ce que [a,b[ et [c,d[ ont une intersection non-vide ?

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

10

soit le rectangle abcd. Il suffit de connaitre le point a (de coordonnées xa,ya) et les autres points tu les a avec H et W.
soit le point f (de coordonnées xf et yf)
image18bw.jpg


à quelle condition f est dans abcd ??


si xf est compris entre (xa et xa+W)...
image24fe.jpg

si yf est compris entre (ya et ya+H)...
image36tz.jpg

et si xf est compris entre (xa et xa+W) ET yf est compris entre (ya et ya+H)...
image45hg.jpg
il est dedans.

et à priori, si f est le point du coin gauche supérieur d'un rectangle fghj, il suffit que le point f, ou le point g ou le point h ou le point j soit dans abcd pour que les deux rectangles se chevauchent.
Tout ce qui passe pas par le port 80, c'est de la triche.

11

c'est une condition suffisante, mais loin d'être nécessaire (et en plus ça fait tout un paquet de tests [16 pour être précis], alors qu'il n'y en a besoin que de 4...) :

par exemple ça ne marche pas avec ça :
   f-----g
   |     |
a--+-----+--b
|  |     |  |
|  |     |  |
|  |     |  |
c--+-----+--d
   |     |
   h-----i

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

12

Onur onur onur... tu me deçois là mourn
Et je crois qu'il n'y a besoin que de 2 tests si on utilise des valeurs absolues.

13

onur: certes, je suis nul en algorithmique concernant les jeux et les maths... et alors? smile et puis ça remonte à la 3ème tout ça... la nuit des temps!! wink

je pense que 4 tests par sprite suffiront. En effent il y a 4 directions, donc il ne faut tester que les 4 extrémités selon la direction mais je sais pas comment faut faire ça wink

pour onur: je pense qu'il me faudrait l'équivalent de l'API PtInRect qui prend en entrée un RECT et un POINT et renvoit un BOOL qui dit vrai si le point est dans le rectangle, faux sinon, regarde dans le msdn wink
There is no spoon.

14

Et ma question ? neutral Si tu ne sais pas résoudre des collisions en 1D, je ne vois pas comment tu pourrais passer ensuite à la 2D ^^


Jyaif>

Par définition tu peux toujours faire en sorte de n'utiliser qu'un seul test pour combiner N tests différents, hein cheeky
(si tu as une expression du style (c1 || c2) && (c3 || c4), alors tu peux en déduire une condition équivalente (k1+k2)*(k3+k4)>0 où les kn sont définis par : si cn = (xn > yn), on pose kn = yn-xn-abs(yn-xn))

En fait par "tests" j'entendais "test simple", par exemple "a >= d" où a et d sont des coordonnées ; de toute façon c'est comme ça que ça sera implémenté, même si tu utilises des valeurs absolues, donc si on veut avoir une idée de la performance c'est la seule mesure raisonnable smile

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

15

euh, là, je suis largué grin
There is no spoon.

16

Je te demande pas de comprendre la deuxième partie de ./14, si ça peut te rassurer grin

Je parle de cette question :
Pollux
:
boulifb :
ben je crois que tout est dit dans l'énoncé... je vois pas ce que je peux dire de plus...

j'ai 2 rectangles et j'aimerais savoir s'ils se touchent selon la direction de chacun et ce, au pixel près...

je vois pas bien comment je peux dire/écrire les choses autrement...

Oui, voilà, mais du coup moi pour t'aider je te dis : soit deux segments qui appartiennent tous les deux à une droite. Tu connais leurs extrêmités : le premier a pour extrêmités [a,b[, l'autre a pour extrêmités [c,d[. A quelle condition sur (a,b,c,d) est-ce que [a,b[ et [c,d[ ont une intersection non-vide ?

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

17

ben... comment dire....
tu as une aire de jeu qui a une taille donnée (un graaaand rectangle)

le gentil joueur qui mesure 16x16 pixels se déplace dans le grand rectangle,
les méchants qui mesurent 16x16 pixels se déplacent aussi dans ce même grand rectangle
si le gentil joueur touche un méchant, ben le gentil il est mort, paf! sad sachant que le gentil va dans une direction et le méchant va dans une autre...

je ne sais pas comment faire pour savoir si le gentil a touché le méchant (ou vice versa)...

il est là mon problème... peut pas être plus simple dans mon énoncé sad

There is no spoon.

18

T'avais pas dit dans ./1 que les dimensions pouvaient changer ? confus Si ta taille est fixe, alors la méthode d'onur marche (même si elle est assez inefficace)

Enfin quoi qu'il arrive ça ne change pas grand-chose à ce que j'ai dit : là c'est un problème en 2D (tu as deux coordonnées), c'est trop compliqué. Donc on peut essayer de voir si déjà on sait résoudre le problème en 1D (i.e. au lieu d'avoir un graaaaaaaaand rectangle, on a juste une graaaaaaaaande droite).

Par exemple on va dire que le gentil est un segment de 16 pixels, dont l'abscisse du point le plus à gauche est a, et dont l'abscisse du point le plus à droite est b :
a--------------b
(ici a=4, b=19)

Et on va dire que le méchant est un segment de 16 pixels, dont l'abscisse du point le plus à gauche est c, et dont l'abscisse du point le plus à droite est d :
c--------------d
(ici c=6, b=21)

A quelle condition sur a, b, c et d est-ce que les deux segments vont être disjoints ? (i.e. le méchant ne touche pas le gentil)

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

19

Pollux :
c'est une condition suffisante, mais loin d'être nécessaire (et en plus ça fait tout un paquet de tests [16 pour être précis], alors qu'il n'y en a besoin que de 4...) :

par exemple ça ne marche pas avec ça :
   f-----g
   |     |
a--+-----+--b
|  |     |  |
|  |     |  |
|  |     |  |
c--+-----+--d
   |     |
   h-----i


C'est pour ca que j'ai dis seulement "suffisant".

boulifb > ca ne sert à rien tes histoire de direction. A moins que tu veuille calculer pour le temps delta T apres, auquel cas tu peux t'en passer aussi en mettant le test au bon endroit dans la boucle de ton jeu.
Tout ce qui passe pas par le port 80, c'est de la triche.

20

onur
:
Pollux :
c'est une condition suffisante, mais loin d'être nécessaire (et en plus ça fait tout un paquet de tests [16 pour être précis], alors qu'il n'y en a besoin que de 4...) :

par exemple ça ne marche pas avec ça :
   f-----g
   |     |
a--+-----+--b
|  |     |  |
|  |     |  |
|  |     |  |
c--+-----+--d
   |     |
   h-----i


C'est pour ca que j'ai dis seulement "suffisant".

J'ai pas dit que t'avais dit que c'était nécessaire, hein tongue Je précisais juste pour pas qu'il y en ait qui croient que ça répondait au pb...

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

21

Pollux :
Jyaif>
Par définition tu peux toujours faire en sorte de n'utiliser qu'un seul test pour combiner N tests différents, hein cheeky


Ah oui effectivement, ma remarque est un peu inutile smile

22

dans le problème, les sprites entrant en collisions peuvent être de taille différente.

si les sprites n'entre pas en collisions, c'est que les rectangles ne se touchent pas.
si le gentil ne touche pas le méchant, il continue son chemin
si le méchant ne touche pas le gentil, il continue son chemin aussi. de toute façon, le méchant il est bête wink
There is no spoon.

23

je crois qu'on a tous compris le "problème" la première fois, pas besoin de te répéter.

24

voui ^^

./22> Et ma question !!!!!! crycrycrycry

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

25

pollux: il s'agit "juste" de tester l'intersection de 2 rectangles... je vois pas comment dire les choses autrement... j'ai tout essayé wink

Si tu ne vois pas, regarde ce lien:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/gdi/rectangl_1mpg.asp
There is no spoon.

26

Réponds d'abord à cette question :
Pollux :
Par exemple on va dire que le gentil est un segment de 16 pixels, dont l'abscisse du point le plus à gauche est a, et dont l'abscisse du point le plus à droite est b :
a--------------b
(ici a=4, b=19)

Et on va dire que le méchant est un segment de 16 pixels, dont l'abscisse du point le plus à gauche est c, et dont l'abscisse du point le plus à droite est d :
c--------------d
(ici c=6, b=21)
A quelle condition sur a, b, c et d est-ce que les deux segments vont être disjoints ? (i.e. le méchant ne touche pas le gentil)

avatar
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas. »

27

laissez-tomber, c'est trouvé...
la fonction fait 5 lignes (return compris et CR/LF compris)
There is no spoon.

28

ah là là ces jeunes...

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

29

à qui le dis-tu... wink
There is no spoon.

30

perso j'hallucine un peu cyborg
Tout ce qui passe pas par le port 80, c'est de la triche.