/*      DETECTION DE COLLISIONS - DETECTER UNE COLLISION AVEC :
			- un rectangle 
			- un cercle
			- un triangle
			- colorer l'intersection de deux rectangles
        
	L'écran est divisé en quatre quarts. Dans chaque quart une 
	forme immobile est affichée haut-gauche=rectangle(0), haut-droite=cercle(1), 
	bas-gauche=triangle(2)	et bas-droite=autre rectangle(3). 

	Une forme est mobile, c'est un rectangle piloté par la souris. Il change de 
	couleur lorsqu'il entre en collision avec une autre forme, sauf pour le 
    rectangle bas-droite où c'est le rectangle de l'intersection qui se colore.
*/

#define ALLEGRO_STATICLINK
#include <allegro.h>
#include <string.h>
#include <stdio.h>

#define ECRAN_X	800
#define ECRAN_Y	600
#define MODE    GFX_AUTODETECT_WINDOWED

#define ERREUR(msg) {\
   set_gfx_mode(GFX_TEXT,0,0,0,0);\
   allegro_message("Error : \n%s\n", msg);\
   allegro_exit();\
   return 1;\
}

#define TAILLE_MOBILE	40 // taille du rect souris

// noms pour chaque forme de 0 à 5. 
// END = taille max pour créer un tableau
enum{RECT1,CERCL,TRIAN,RECT2,MOBILE,INTER,END};

// structure qui rassemble position, taille et couleur d'une forme
typedef struct FORME{
	int x,y;		//position
	int tx,ty;		//taille
	int couleur;    //couleur
}FORME;

// pour simplifier écriture
typedef struct t_pt{
	int x,y;
}POINT;

FORME** init_formes_fixes	 (void);
void	degrade_pas_variable (PALETTE pal);
void	assemble_formes		 (FORME**, BITMAP* bmp);
void	chek_collision		 (FORME**f);
int		collision_rect		 (FORME *f1, FORME *f2);
void	intersection_rect	 (FORME *f1, FORME *f2, FORME *res);
int		collision_cercle	 (FORME *f1, FORME *f2);
int		collision_triangle   (FORME*f1, FORME*f2);
int		gauche				 (POINT p,POINT o, POINT i);
int     point_dans_triangle	 (POINT p,POINT a,POINT b,POINT c);
int		point_dans_rect		 (POINT p,POINT hg,POINT bd);

/******************************************************************************
*******************************************************************************/
int main()
{
FORME **tab; // un tableau de pointeurs et un pointeur de formes 
PALETTE pal;					  
BITMAP*page;
int i;

   allegro_init();
   install_keyboard(); 
   install_mouse();
   srand(time(NULL));
     
   if (set_gfx_mode(MODE, ECRAN_X, ECRAN_Y, 0, 0) != 0) 
      ERREUR("gfx_mode");
   
   // buffer
   page=create_bitmap(ECRAN_X,ECRAN_Y);
   if (!page)
      ERREUR("create_bitmap page");

   // créer une palette et l'activer
   degrade_pas_variable(pal);
   
   // initialisation des formes
   tab=init_formes_fixes();   
   
   while(!key[KEY_ESC]){
   
	  // mouvement souris
      if (tab[MOBILE]->x!=mouse_x || tab[MOBILE]->y !=mouse_y){
		  
         // récup nouvelles coordonnées souris
		 tab[MOBILE]->x=mouse_x;
		 tab[MOBILE]->y=mouse_y;
          
		 // collision ?
		 chek_collision(tab);

		 // dessiner dans le buffer
	     assemble_formes(tab, page);
   
         // affichage à l'écran
         blit(page,screen,0,0,0,0,page->w,page->h);
	  }
	  // changer la taille du carré souris (visible au premier mouvement)
	  // souris départ, petit carré
      if (key[KEY_F1]){
         tab[MOBILE]->tx=TAILLE_MOBILE;
	     tab[MOBILE]->ty=TAILLE_MOBILE;
	  }
	  // souris = une barre verticale
	  if (key[KEY_F2]){
         tab[MOBILE]->tx=TAILLE_MOBILE;
		 tab[MOBILE]->ty=TAILLE_MOBILE+100;
	  }
	  // souris = une barre horizontale
	  if (key[KEY_F3]){
         tab[MOBILE]->tx=TAILLE_MOBILE+100;
		 tab[MOBILE]->ty=TAILLE_MOBILE;
	  }
	  // souris = un gros carré
	  if (key[KEY_F4]){
         tab[MOBILE]->tx=TAILLE_MOBILE+100;
		 tab[MOBILE]->ty=TAILLE_MOBILE+100;
	  }
	  // nouvelle palette
	  if (key[KEY_ENTER])
         degrade_pas_variable(pal);
   }

   // nettoyage sortie
   destroy_bitmap(page);

   for (i=0;i<MOBILE+1;i++)
	   free(tab[i]);
   free(tab);
   
   exit(EXIT_SUCCESS);
}
END_OF_MAIN();
/******************************************************************************
Allocation mémoire du tableau de formes, allocation de chaque forme et 
initialisation des champs de chaque forme. 
La fonction retourne le tableau de FORME* prêt à l'emploi.
*******************************************************************************/
FORME** init_formes_fixes()
{
FORME** f;
int mx=ECRAN_X/2;
int my=ECRAN_Y/2;
int color;
   // socle couleur de départ 
   color=rand()%20+1;

   // allocation du tableau de pointeurs de formes de taille MOBILE + 1
   f=(FORME**)malloc(sizeof(FORME*)*END);
   // rectangle haut gauche
   f[RECT1]=(FORME*)malloc(sizeof(FORME));
   f[RECT1]->tx=100;
   f[RECT1]->ty=100;
   f[RECT1]->x=(mx-f[RECT1]->tx)/2;
   f[RECT1]->y=(my-f[RECT1]->ty)/2;
   f[RECT1]->couleur=color;

   // cercle haut droite
   f[CERCL]=(FORME*)malloc(sizeof(FORME));
   f[CERCL]->tx=100; // rayon
   f[CERCL]->ty=100; // rayon
   f[CERCL]->x=(ECRAN_X-mx)/2 +mx;
   f[CERCL]->y=(ECRAN_Y-my)/2;
   f[CERCL]->couleur=color+20;

   // triangle bas gauche
   f[TRIAN]=(FORME*)malloc(sizeof(FORME));
   f[TRIAN]->tx=100;
   f[TRIAN]->ty=100;
   f[TRIAN]->x=(mx-f[TRIAN]->tx)/2;
   f[TRIAN]->y=(ECRAN_Y-my+f[TRIAN]->ty)/2 +my;
   f[TRIAN]->couleur=color+40;

   // rectangle bas droite
   f[RECT2]=(FORME*)malloc(sizeof(FORME));
   f[RECT2]->tx=140;
   f[RECT2]->ty=140;
   f[RECT2]->x=(ECRAN_X-mx-f[RECT2]->tx)/2 +mx;
   f[RECT2]->y=(ECRAN_Y-my-f[RECT2]->ty)/2 +my;
   f[RECT2]->couleur=color+60;

   //rectangle balladeur
   f[MOBILE]=(FORME*)malloc(sizeof(FORME));
   f[MOBILE]->tx=TAILLE_MOBILE;
   f[MOBILE]->ty=TAILLE_MOBILE;
   f[MOBILE]->x=0;
   f[MOBILE]->y=0;
   f[MOBILE]->couleur=color+80;

   // rectangle d'intersection
   f[INTER]=(FORME*)malloc(sizeof(FORME));
   f[INTER]->tx=-1;
   f[INTER]->ty=-1;
   f[INTER]->x=0;
   f[INTER]->y=0;
   f[INTER]->couleur=255;

   return f;
}
/******************************************************************************
Simple fonction d'affichage, dessine les formes dans le buffer 
en fonction de leur type respectif.
*******************************************************************************/
void assemble_formes(FORME**f, BITMAP* bmp)
{
int i;
   
   clear(bmp);
   for (i=0; i<END;i++)
      switch(i){

	     case RECT1 :
         case RECT2 :
		    rectfill(bmp,f[i]->x, f[i]->y, //pt 1
				         f[i]->x+f[i]->tx, f[i]->y+f[i]->ty, //pt2
						 f[i]->couleur);
            break;
         case MOBILE:
            rectfill(bmp,f[i]->x, f[i]->y, //pt 1
			         f[i]->x+f[i]->tx, f[i]->y+f[i]->ty, //pt2
					 f[i]->couleur);
            break;

		 case INTER:
			// si intersection tx et ty sont positifs
			// dans ce cas dessin du rect
			if (f[i]->tx>0 && f[i]->ty>0) 
               rectfill(bmp,f[i]->x, f[i]->y, //pt 1
				            f[i]->x+f[i]->tx, f[i]->y+f[i]->ty, //pt2
						    f[i]->couleur);
		    break;

         case TRIAN :
		    triangle(bmp,f[i]->x, f[i]->y,                    //pt1
				         f[i]->x+f[i]->tx,  f[i]->y,          //pt2
						 f[i]->x+f[i]->tx/2,f[i]->y-f[i]->ty, //pt3
						 f[i]->couleur);
            break;
         case CERCL :
            circlefill(bmp, f[i]->x,f[i]->y, f[i]->ty, f[i]->couleur);
            break;
	  }
}
/******************************************************************************
Controler les collisions
*******************************************************************************/
void chek_collision(FORME**f)
{ 
int res=0;

   // 1 collision avec RECT1 en haut à gauche ?
   res=collision_rect(f[MOBILE],f[RECT1]);
   
   // 2 collision avec CERCL en haut à droite ? 
   //(ajouter le résultat à res : 0 ne change rien et le résultat 
   // précédent est conservé, et ajouter 1 conserve également le résultat 
   // précédent )
   res+=collision_cercle(f[MOBILE],f[CERCL]);

   // 3 collision avec le triangle en bas à gauche ?
   res+=collision_triangle(f[MOBILE],f[TRIAN]);

   // Si collision : changer de couleur
   if (res)
	   f[MOBILE]->couleur++; 

   // 4 colorer l'intersection de deux rectangles en bas à droite
   intersection_rect(f[MOBILE], f[RECT2], f[INTER]);
	   
}
/******************************************************************************
 1 collision de deux rectangles
*******************************************************************************/
int collision_rect(FORME *f1, FORME *f2)
{
int res=1;

   if ( (f1->x > f2->x + f2->tx -1) ||   // f1 à droite de f2
        (f1->y > f2->y + f2->ty -1) ||   // f1 en dessous
        (f2->x > f1->x + f1->tx -1) ||   // f2 à droite de f1
        (f2->y > f1->y + f1->ty -1)   ){ // f2 en dessous

	     res=0;	 // pas de collision
   }
   return res;
}
/******************************************************************************
 4 colorer l'intersection de deux rectangles. 
Comprarer les points haut gauche et bas droite de chaque rectangle :
le rectangle d'intersection est celui de coordonnées 
- x plus grand à gauche, y plus grand en haut,
- x plus petit à droite, y plus petit en bas 
*******************************************************************************/
void intersection_rect(FORME *f1, FORME *f2, FORME *inter)
{
int gx,px,gy,py;

   // par défaut pas d'intersection
   inter->tx=-1;
   // ccordonnées plus grand à gauche, plus petit à droite
   gx=(f1->x>f2->x)? f1->x : f2->x;
   px=(f1->x+f1->tx<f2->x+f2->tx)? f1->x+f1->tx : f2->x+f2->tx ;
   
   // coordonnées plus grand en haut, plus petit en bas
   gy=(f1->y>f2->y)? f1->y : f2->y;
   py=(f1->y+f1->ty<f2->y+f2->ty)? f1->y+f1->ty : f2->y+f2->ty ;

   // si droite > gauche et bas > haut il y a une intersection
   if(gx-px<=0 && gy-py<=0){
      inter->x=gx;
      inter->y=gy;
      inter->tx=px-gx; 
      inter->ty=py-gy;
   }
}
/******************************************************************************
 2 collision d'un rect et d'un cercle :
en fonction de la position du rect par rapport au cercle, l'idée 
est de tester trois points de contacts :
si le coin le plus près du cercle est dedans, si non
de tester si le point des rayons horizontal et vertical coupe le rect
*******************************************************************************/
int collision_cercle(FORME *f1, FORME *f2)
{
// nord, sud, est, ouest, coin haut-gauche,coin haut-droite, 
//coin bas gauche, coin bas droite
POINT n,s,e,o,chg,chd,cbg,cbd;
int dx,dy,r2;
int dg,hb,res;
   
   //distance du coin haut gauche du rect f1 au centre du cercle en f2
   // pour situer le rect par rapport au centre du cercle
   dx=f1->x-f2->x;
   dy=f1->y-f2->y;
   
   //le rect par rapport au centre du cercle (gauche,droite haut,bas?)
   // 1) à droite
   if (dx>0){
      dg=0;						// pour droite						
      e.x=f2->x+f2->tx;			// necessite le point Est du cercle
	  e.y=f2->y;
	  chd.x=cbd.x=f1->x;		// coordonnées en x des coins du rect à droite
   }
   // 2) à gauche
   else{
	  dg=2;						// pour gauche
      o.x=f2->x-f2->tx;			// necessite le point Ouest du cercle
	  o.y=f2->y;
	  chg.x=cbg.x=f1->x+f1->tx; // coordonnées en x des coins du rect à gauche
   }
   
   // 3) en dessous
   if (dy>0){
      hb=1;						// pour en dessous
      s.x=f2->x;			    // necessite le point Sud du cercle
	  s.y=f2->y+f2->ty;
	  cbg.y=cbd.y=f1->y;		// coordonnées en y des coins en bas
   }
   // 4)  en dessus
   else{
	  hb=2;						// pour en dessus
      n.x=f2->x;				// necessite le point Nord du cercle
	  n.y=f2->y-f2->ty;
	  chg.y=chd.y=f1->y+f1->ty; // coordonnées en y des coins en haut
   }

   
   r2=f2->tx*f2->tx;			// rayon du cercle au carré
   res=0;						// par default il n'y a pas collision, 
								// prouver la collision
								// en fonction de la position du rect,
   switch(dg+hb){				// les points à tester :

      // le rect est à droite et en desous 
      case 1 :
         dx=f2->x-cbd.x;
		 dy=f2->y-cbd.y;
		 if (dx*dx+dy*dy<=r2)	// test 1 le coin est dans le cercle 
			 res=1;
		break;

      // le rect est à droite et en dessus 
      case 2 :
         dx=f2->x-chd.x;
		 dy=f2->y-chd.y;
		 if ( (dx*dx+dy*dy<=r2) || (e.x>=chd.x && e.y>f1->y && e.y<chd.y) )
			 res=1;
						  // test 1 : coin dans cercle ?
			              // test 2 : sinon le rayon à droite coupe t il 
						  //          le rect sur la gauche ?
		 
         break;

	  // le rect est à gauche et en dessous 
      case 3 :
         dx=f2->x-cbg.x;
		 dy=f2->y-cbg.y;
		 if ( (dx*dx+dy*dy<=r2) || (s.x>f1->x && s.x <cbg.x && s.y>=cbg.y) )
			 res=1;
						  // test 1 : coin dans cercle ?
			              // test 2 : sinon le rayon en bas coupe t il 
						  //          le rect sur le haut ?
         break;

	  // le rect est à gauche et en dessus 
      case 4 :
         dx=f2->x-chg.x;
		 dy=f2->y-chg.y;
		 if ( (dx*dx+dy*dy<=r2) || (o.x<=chg.x && o.y>f1->y && o.y <chg.y) 
								|| (n.y<=chg.y && n.x>f1->x && n.x <chg.x) )
			 res=1;
						  // test 1 : coin dans cercle ?
			              // test 2 : sinon le rayon à gauche coupe t il 
						  //          le rect sur la droite ?
						  // test 3 : sinon le rayon en haut coupe t il 
						  //          le rect en bas ?
         break;
   }
   return res;
}
/******************************************************************************
 3 Collision d'un rect et d'un triangle :
le principe est de vérifier 
1) si un des coins du rect est dans le triangle
2) si une des pointes du triangle est dans le rect
*******************************************************************************/
int collision_triangle(FORME*f1, FORME*f2)
{
// les 3 points du triangle
POINT a,b,c;
// les 4 points du rect
POINT hg,hd,bg,bd;
int res=0;

   // triangle
   a.x=f2->x;		     //pt1
   a.y=f2->y;
   b.x=f2->x+f2->tx;	 //pt2
   b.y=f2->y;
   c.x=f2->x+f2->tx/2;   //pt3
   c.y=f2->y-f2->ty;
   // rectangle
   hg.x=f1->x;          // coin haut gauche
   hg.y=f1->y;
   hd.x=f1->x+f1->tx;   // coin haut droite
   hd.y=f1->y;
   bg.x=f1->x;          // coin bas gauche
   bg.y=f1->y+f1->ty;
   bd.x=f1->x+f1->tx;   // coin bas droite
   bd.y=f1->y+f1->ty;

   // un coin du rectangle est-il dans le triangle?
   // coin haut gauche
   res =point_dans_triangle(hg,a,b,c);
   // coin haut-droite
   res+=point_dans_triangle(hd,a,b,c);
   // coin bas gauche
   res+=point_dans_triangle(bg,a,b,c);
   // coin bas droite
   res+=point_dans_triangle(bd,a,b,c);

   // si non voir si une pointe du triangle est dans le rect
   if (!res){
	  
      res =point_dans_rect(a,hg,bd);
	  res+=point_dans_rect(b,hg,bd);
	  res+=point_dans_rect(c,hg,bd);
   }
   return res;
}
/******************************************************************************
Pour connaître si un point est dans un triangle, nous utilisons la règle 
du déterminant. Elle permet de savoir si un point est à gauche ou à 
droite d'un vecteur. Soit le triangle ABC  si le point P est à gauche de AB, 
de BC et de CA alors il est dans le triangle.

le triangle est considéré dans le sens inverse des aiguilles d'une montre
(triangle direct)
*******************************************************************************/
int point_dans_triangle(POINT p,POINT a,POINT b,POINT c)
{
int res=0;
   res =gauche(p, a, b);
   res+=gauche(p, b, c);
   res+=gauche(p, c, a);
   return (res==3)? 1:0;
}
/******************************************************************************
TOOLS "gauche" 
La règle du déterminant est la suivante :
soit 3 points PO,PI,P, P est à gauche de PO-PI si le déterminant 
vxi*vyp-vxp*vyi des vecteurs POPI(vxi,vyi) et POP(vxp,vyp) est positif, 
et à droite dans le cas contraire.
Pour l'observateur c'est inversé. 
*******************************************************************************/
int gauche(POINT p,POINT o, POINT i)
{
int vxi,vyi,vxp,vyp;
int det;
   // les vecteurs POP1 et POP2
   vxi= i.x - o.x;
   vyi= i.y - o.y;
   vxp= p.x - o.x;
   vyp= p.y - o.y;
   // déterminant
   det= vxi*vyp - vxp*vyi;
   // inversion pour le point de vue de l'observateur
   // retourne 0 si positif et à droite pour l'observateur, 1 si négatif
   // et à gauche pour l'observateur
   return (det>0)? 0 : 1;
}
/******************************************************************************
le rect est défini par les coins haut-gauche (hg) et bas-droite(bd)
par défaut il y a collision, le test vérifie qu'il n'y a pas collision
*******************************************************************************/
int point_dans_rect(POINT p,POINT hg,POINT bd)
{
int res=1;
   
   if ( (p.x > bd.x) ||   // p à droite de bd
        (p.x < hg.x) ||   // p en dessous
        (p.y > bd.y) ||   // p à droite de hg
        (p.y < hg.y)   ){ // p en dessus

	     res=0;	 // pas de collision
   }
   return res;  
}
/******************************************************************************
Création d'une palette
*******************************************************************************/
void degrade_pas_variable(PALETTE pal)
{
int i, rouge,pr,vert,pv,bleu,pb;

   pal[0].r=pal[0].g=pal[0].b=0;
   rouge= rand()%54+5;
   vert = rand()%54+5;
   bleu = rand()%54+5; 
   pr= rand()%11-5;
   pv= rand()%11-5;
   pb= rand()%11-5;
   
   for (i=1; i<256; i++){
      // rouge
      rouge+=pr;
      pal[i].r=rouge;
      if ( rouge <= ABS(pr) || rouge>= 63-ABS(pr))
         pr*=-1;
      //vert
      vert+=pv;
      pal[i].g=vert;
      if ( vert <= ABS(pv) || vert>= 63-ABS(pv))
         pv*=-1;
      //bleu
      bleu+=pb;
      pal[i].b=bleu;
      if ( bleu <= ABS(pb) || bleu>= 63-ABS(pb))
         pb*=-1;
   }
   set_palette(pal);
}
/******************************************************************************
RAPPEL LINKAGE lib static :
pour dev :
dans menu : Projet/otpions du projet/paramètres/éditeur de liens , là, 
copier la liste suivante :
  -lalleg_s -lgdi32 -lwinmm -lole32 -ldxguid -ldinput -lddraw -ldsound
et dans la colonne "compilateur" à gauche de l'éditeur de liens copier
  -DALLEGRO_STATICLINK
cliquer "OK"
*******************************************************************************/

