/* jeu-laby-g.c : un jeu de labyrinthe
 *
 * Edouard.Thiel@lif.univ-mrs.fr - 23/03/2010 - version 0.9
 *
 * Compilation sous Unix :
 *     gcc -Wall jeu-laby-g.c ez-gtk.c -o jeu-laby-g `pkg-config gtk+-2.0 --cflags --libs`
 *
 * This program is free software under the terms of the
 * GNU Lesser General Public License (LGPL) version 2.1.
*/

#include "ez-gtk.h"
#include <math.h>


/*------------------------- D E F I N I T I O N S ---------------------------*/

/* Taille du labyrinthe */
#define LABY_XM 15
#define LABY_YM 12

/* Taille en pixels */
#define W_X0  25
#define W_Y0  40
#define W_TA  22
#define P_RA  8

/* Taille fenetres */
#define WIN1_W (W_X0+W_TA*LABY_XM+W_X0)
#define WIN1_H (W_Y0+W_TA*LABY_YM+30)
#define WIN2_W 400
#define WIN2_H 400

/* Delai de l'animation a la creation, au deplacement */
#define DELAY1 20
#define DELAY2 20

/* Parametres 3D */
#define HOMO_RAP    0.5
#define PROJ_DISTD  4

/* Codage du labyrinthe pour une case x,y: 
 *   laby[2*y+1][2*x+1] : centre de la case
 *   laby[2*y  ][2*x+1] : mur horizontal
 *   laby[2*y+1][2*x  ] : mur verical
 *   laby[2*y  ][2*x  ] : angle, inutilise'
*/
typedef int Laby[LABY_YM*2+1][LABY_XM*2+1];

/* Utilise' lors de la cre'ation du labyrinthe */
typedef struct {
    struct { int cx, cy; } l[LABY_YM*LABY_XM];
    int n;
} Voisi;

/* Pion courant et sortie */
typedef struct {
    int px, py;  /* Coordonnees du pion */
    int pa;      /* Angle du pion */
    int sx, sy;  /* Coordonnees sortie */
} Pion;

/* Un deplacement en plusieurs etapes */
typedef struct {
    enum { D_AVANCE, D_TOURNE, D_COGNE1, D_COGNE2 } lequel;
    double x, y, a, x1, x2, y1, y2, a1, a2;
    int k, nb;  /* etape k : 0 .. nb */
} Depla;

/* Donnees de l'appli */
typedef struct {
    enum { E_DEBUT, E_CREER, E_JOUER, E_DEPLA, E_GAGNE } etat;
    Laby laby;                /* Le labyrinthe et les murs */
    Voisi voisi;              /* liste des voisins pendant creation */
    Pion pion;                /* Coordonnees courantes */
    Depla depla;              /* Deplacement en cours */
    int kb_flch;              /* code de la touche fleche courante */
    int kb_ctrl;              /* une touche control enfoncee */
    double distD;             /* Distance de l'observateur au plan focal */
    GtkWidget *win1, *win2,   /* Fenetre du plan, de la vue 3D */
              *area1, *area2; /* Drawing area du plan, de la vue 3D*/
    int timer1_id, timer2_id; /* Timers */
} Appli;


/*--------------------------------- A P P L I -------------------------------*/

Appli app;  /* Globale */

void init_appli ()
{
    app.etat = E_DEBUT;
    app.kb_flch = 0;
    app.kb_ctrl = 0;
    app.distD = PROJ_DISTD;
    app.timer1_id = app.timer2_id = -1;
}

void send_2expose ()
{
    ezg_area_expose (app.win1);
    ezg_area_expose (app.win2);
}

/* Cette fonction est definie plus loin */
gboolean area2_onTimeout (gpointer data);


/*---------------- C R E A T I O N   D U   L A B Y R I N T H E --------------*/


void init_laby (Laby laby)
{
    int x, y;

    for (y = 0; y < LABY_YM*2+1; y++)
    for (x = 0; x < LABY_XM*2+1; x++)
        laby[y][x] = 1;
}

void push_voisin (Laby laby, Voisi *voisi, int x, int y)
{
    if (x < 0 || x >= LABY_XM || y < 0 || y >= LABY_YM) return;
    if (laby[2*y+1][2*x+1] != 1) return;
    laby[2*y+1][2*x+1] = 2;  /* Pour ne pas l'empiler plusieurs fois */
    voisi->l[voisi->n].cx = x;
    voisi->l[voisi->n].cy = y;
    voisi->n++;   
}

void init_voisi (Laby laby, Voisi *voisi)
{
    int x, y;

    x = ezg_random(LABY_XM);
    y = ezg_random(LABY_YM);
    laby[2*y+1][2*x+1] = 0;
    voisi->n = 0;
    push_voisin (laby, voisi, x+1,y);
    push_voisin (laby, voisi, x-1,y);
    push_voisin (laby, voisi, x,y+1);
    push_voisin (laby, voisi, x,y-1);
}

void mange_mur (Laby laby, int x, int y)
{
    int dx[] = { 1, 0, -1, 0},
        dy[] = { 0, 1, 0, -1},
        xx, yy, i, j, n = 0, t[4];

    /* Memorise les voisins a 0 dans t[] et le nombre dans n */
    for (i = 0; i < 4; i++) {
        xx = x+dx[i]; yy = y+dy[i];
        if (0 <= xx && xx < LABY_XM && 0 <= yy && yy < LABY_YM &&
            laby[2*yy+1][2*xx+1] == 0)
            t[n++] = i;
    }

    /* On tire l'un d'eux au hasard et on mange le mur */
    i = ezg_random (n); j = t[i];
    laby[2*y+dy[j]+1][2*x+dx[j]+1] = 0;
}

int etape_laby (Laby laby, Voisi *voisi)
{
    int n, x, y;

    if (voisi->n == 0) return 0;  /* Le labyrinthe est fini */

    /* On titre un voisin au hasard et on le met a 0 */
    n = ezg_random (voisi->n);
    x = voisi->l[n].cx; y = voisi->l[n].cy; 
    laby[2*y+1][2*x+1] = 0;

    /* On mange un des murs voisin d'un 0 */
    mange_mur (laby, x,y);

    /* Enleve (x,y) de la liste des voisins et empile les 4-voisins */
    voisi->n--;
    voisi->l[n] = voisi->l[voisi->n];
    push_voisin (laby, voisi, x+1,y);
    push_voisin (laby, voisi, x-1,y);
    push_voisin (laby, voisi, x,y+1);
    push_voisin (laby, voisi, x,y-1);

    return 1;
}

void murs_invisibles (Laby laby, int a, int b)
{
    int x, y;
    for (y = 1; y < LABY_YM*2; y++)
    for (x = 1; x < LABY_XM*2; x++)
        if (laby[y][x] == a) laby[y][x] = b;
}

void mur_visible (Laby laby, int mx, int my)
{
    if (laby[my][mx] == 2) laby[my][mx] = 1;
}

void murs_visibles (Laby laby, int x, int y)
{
    mur_visible (laby, 2*x  , 2*y+1);
    mur_visible (laby, 2*x+1, 2*y  );
    mur_visible (laby, 2*x+2, 2*y+1);
    mur_visible (laby, 2*x+1, 2*y+2);
}


/*-------------------- D E P L A C E M E N T   D U   P I O N ----------------*/

void init_pion (Pion *pion)
{
    pion->px = pion->py = pion->pa = 0;
    pion->sx = LABY_XM-1; pion->sy = LABY_YM-1;
}

void bouge_pion (Laby laby, Pion *pion, Depla *depla, int dx, int dy)
{
    int xx = pion->px + dx, yy = pion->py + dy;

    if (0 <= xx && xx < LABY_XM && 0 <= yy && yy < LABY_YM &&
        laby[2*pion->py+dy+1][2*pion->px+dx+1] == 0) 
    {
        depla->lequel = D_AVANCE;
        depla->x = depla->x1 = pion->px; depla->x2 = xx;
        depla->y = depla->y1 = pion->py; depla->y2 = yy;
        depla->a = depla->a1 = depla->a2 = pion->pa;
        depla->k = 0; depla->nb = 20;
    } else {
        depla->lequel = D_COGNE1;
        depla->x = depla->x1 = pion->px; depla->x2 = pion->px + 0.1*dx;
        depla->y = depla->y1 = pion->py; depla->y2 = pion->py + 0.1*dy;
        depla->a = depla->a1 = depla->a2 = pion->pa;
        depla->k = 0; depla->nb = 6;
    }
}

void avance_pion (Laby laby, Pion *pion, Depla *depla, int sens)
{
    int dx = (pion->pa ==  0) ? sens : (pion->pa == 180) ? -sens : 0,
        dy = (pion->pa == 90) ? sens : (pion->pa == 270) ? -sens : 0;
    bouge_pion (laby, pion, depla, dx, dy);
 }

void lateral_pion (Laby laby, Pion *pion, Depla *depla, int sens)
{
    int dx = (pion->pa == 270) ? sens : (pion->pa ==  90) ? -sens : 0,
        dy = (pion->pa ==   0) ? sens : (pion->pa == 180) ? -sens : 0;
    bouge_pion (laby, pion, depla, dx, dy);
}

void tourne_pion (Pion *pion, Depla *depla, int sens)
{
    int a = pion->pa + sens*90;

    depla->lequel = D_TOURNE;
    depla->x = depla->x1 = depla->x2 = pion->px;
    depla->y = depla->y1 = depla->y2 = pion->py;
    depla->a = depla->a1 = pion->pa; depla->a2 = a;
    depla->k = 0; depla->nb = 20 ;
}

void fleche_action ()
{
    switch (app.kb_flch) {
        case GDK_Left     : 
        case GDK_KP_Left  : 
            if (app.kb_ctrl) 
                 lateral_pion (app.laby, &app.pion, &app.depla, -1); 
            else tourne_pion (&app.pion, &app.depla, -1); 
            break;

        case GDK_Right    : 
        case GDK_KP_Right : 
            if (app.kb_ctrl) 
                 lateral_pion (app.laby, &app.pion, &app.depla, 1); 
            else tourne_pion (&app.pion, &app.depla, 1); 
            break;

        case GDK_Up       : 
        case GDK_KP_Up    : 
            avance_pion (app.laby, &app.pion, &app.depla, 1); 
            break;

        case GDK_Down     : 
        case GDK_KP_Down  : 
            avance_pion (app.laby, &app.pion, &app.depla, -1); 
            break;

        default : return;
    }

    app.etat = E_DEPLA;
    if (app.timer2_id != -1) g_source_remove (app.timer2_id);
    app.timer2_id = g_timeout_add (DELAY2, area2_onTimeout, NULL);
}

void deplace_pion ()
{
    double u; 

    app.depla.k++;
    u = (double) app.depla.k / app.depla.nb;
    app.depla.x = app.depla.x1 * (1-u) + app.depla.x2 * u;
    app.depla.y = app.depla.y1 * (1-u) + app.depla.y2 * u;
    app.depla.a = app.depla.a1 * (1-u) + app.depla.a2 * u;

    if (app.depla.k == app.depla.nb && app.depla.lequel == D_COGNE1) {
        double tmp;
        app.depla.lequel = D_COGNE2;
        tmp = app.depla.x1; app.depla.x1 = app.depla.x2; app.depla.x2 = tmp;
        tmp = app.depla.y1; app.depla.y1 = app.depla.y2; app.depla.y2 = tmp;
        app.depla.k = 0;
    } 

    if (app.depla.k == app.depla.nb) {
        app.etat = E_JOUER;
        if (app.depla.lequel == D_AVANCE) {
            app.pion.px = app.depla.x2; app.pion.py = app.depla.y2;
            murs_visibles (app.laby, app.pion.px, app.pion.py);
            if (app.pion.px == app.pion.sx && app.pion.py == app.pion.sy) { 
                /* On a atteint la sortie ! */
                app.etat = E_GAGNE; murs_invisibles (app.laby, 2, 1); 
            } else if (app.kb_flch != 0) {
                /* si une fleche est enfoncee, on relance */
                fleche_action ();
            }
        } else if (app.depla.lequel == D_TOURNE) {
            app.pion.pa = (int) (app.depla.a2 + 360) % 360;
            if (app.kb_flch != 0) {
                fleche_action ();
            }
        }
    } else {
        app.timer2_id = g_timeout_add (DELAY2, area2_onTimeout, NULL);
    }

    send_2expose ();
}

/*------------------------------ D E S S I N S ------------------------------*/

void dessin_murh (GtkWidget *widget, GdkGC *gc, int x, int y)
{
    gdk_draw_line (widget->window, gc,
        W_X0+ x   *W_TA, W_Y0+y*W_TA, 
        W_X0+(x+1)*W_TA, W_Y0+y*W_TA);
}

void dessin_murv (GtkWidget *widget, GdkGC *gc, int x, int y)
{
    gdk_draw_line (widget->window, gc,
        W_X0+x*W_TA, W_Y0+ y   *W_TA, 
        W_X0+x*W_TA, W_Y0+(y+1)*W_TA);
}

void dessin_case (GtkWidget *widget, GdkGC *gc, int x, int y)
{
    gdk_draw_rectangle (widget->window, gc, TRUE, 
        W_X0+ x*W_TA+1, W_Y0+ y*W_TA+1, 
        W_TA-1, W_TA-1);
}

void dessin_pion (GtkWidget *widget, GdkGC *gc, double x, double y, double a)
{
    double b = a * M_PI / 180, c = cos (b), s = sin (b);
    int x1 = W_X0+(x+0.5)*W_TA + 0.5, y1 = W_Y0+(y+0.5)*W_TA + 0.5;
             
    gdk_draw_arc (widget->window, gc, FALSE, 
        x1 - P_RA, y1 - P_RA, P_RA*2, P_RA*2, 0, 360*64);

    gdk_draw_line (widget->window, gc, 
        x1, y1, x1 + c*P_RA + 0.5, y1 + s*P_RA + 0.5);
}

void dessin_sortie (GtkWidget *widget, GdkGC *gc, int x, int y)
{
    gdk_draw_line (widget->window, gc, 
        W_X0+ x   *W_TA+3, W_Y0+ y   *W_TA+3, 
        W_X0+(x+1)*W_TA-3, W_Y0+(y+1)*W_TA-3);
    gdk_draw_line (widget->window, gc, 
        W_X0+(x+1)*W_TA-3, W_Y0+ y   *W_TA+3, 
        W_X0+ x   *W_TA+3, W_Y0+(y+1)*W_TA-3);
}

void area1_redessiner (GtkWidget *widget)
{
    int x, y;
    char *s;

    /* On recupere le contexte graphique associe' au widget */
    GdkGC *gc = ezg_get_gc (widget);

    /* On cree un layout pour dessiner du texte */
    PangoLayout *layout = gtk_widget_create_pango_layout (widget, NULL);

    /* On dessine le fond en blanc */
    ezg_area_clear (widget);

    switch (app.etat) {
        case E_DEBUT : s = "\n** Labyrinthe **"; break;
        case E_CREER : s = "Creation en cours ..."; break;
        case E_JOUER :
        case E_DEPLA : s = "Trouvez la sortie !"; break;
        case E_GAGNE : s = "Bravo !!"; break;
        default : s = "";
    }
    ezg_set_color (gc, EZG_BLUE); ezg_set_nfont (layout, 2);
    ezg_draw_text (widget, gc, layout, EZG_TC, WIN1_W/2, 10, s);

    ezg_set_color (gc, EZG_BLACK); ezg_set_nfont (layout, 0);
    ezg_draw_text (widget, gc, layout, EZG_BL, 10, WIN1_H-5, 
        "n : nouvelle partie  i : devoiler  q : quitter");

    if (app.etat == E_DEBUT) {

        ezg_set_color (gc, EZG_MAGENTA); ezg_set_nfont (layout, 1);
        ezg_draw_text (widget, gc, layout, EZG_TC, WIN1_W/2, WIN1_H*2/7,
            "Utilisez les fleches\npour vous deplacer.\n\n"
            "Tapez 'n' pour commencer ...");
        ezg_set_color (gc, EZG_RED); ezg_set_nfont (layout, 0);
        ezg_draw_text (widget, gc, layout, EZG_TC, WIN1_W/2, WIN1_H*9/14,
            "Le programme jeu-laby-g.c\nfait partie de EZ-Draw-GTK :\n\n"
            "http://pageperso.lif.univ-mrs.fr/\n~edouard.thiel/ez-draw-gtk");

    } else {

        ezg_set_color (gc, EZG_BLUE);
        for (y = 0; y <= LABY_YM; y++)
        for (x = 0; x <  LABY_XM; x++)
        if (app.laby[y*2][x*2+1] == 1) 
            dessin_murh (widget, gc, x, y);

        for (y = 0; y <  LABY_YM; y++)
        for (x = 0; x <= LABY_XM; x++)
        if (app.laby[y*2+1][x*2] == 1) 
            dessin_murv (widget, gc, x, y);

        if (app.etat == E_CREER) {
            ezg_set_color (gc, EZG_GREY);
            for (y = 0; y <  LABY_YM; y++)
            for (x = 0; x <  LABY_XM; x++)
            if (app.laby[y*2+1][x*2+1] == 1)
                dessin_case (widget, gc, x, y);

            ezg_set_color (gc, EZG_YELLOW);
            for (y = 0; y <  LABY_YM; y++)
            for (x = 0; x <  LABY_XM; x++)
            if (app.laby[y*2+1][x*2+1] == 2)
                dessin_case (widget, gc, x, y);
        } else {
            ezg_set_color (gc, EZG_RED);
            if (app.etat == E_DEPLA)
                 dessin_pion (widget, gc, app.depla.x, app.depla.y, app.depla.a);
            else dessin_pion (widget, gc, app.pion.px, app.pion.py, app.pion.pa);
            dessin_sortie (widget, gc, app.pion.sx, app.pion.sy);
        }
    }

    /* Libere la memoire */
    g_object_unref (G_OBJECT (layout));
}


/*----------------------- E V E N E M E N T S   W I N 1 ---------------------*/

gint area1_onExpose (GtkWidget *widget, GdkEventExpose *ev)
{
    area1_redessiner (widget);

    return TRUE;  /* L'evenement a ete traite' */
}

gboolean area1_onTimeout (gpointer data)
{
    if (app.etat == E_CREER) {
        /* On fait une etape supplementaire de la creation du laby */
        int k = etape_laby (app.laby, &app.voisi);

        if (k == 1) {  /* Le laby n'est pas fini, on relance le timer */
            send_2expose ();
            return TRUE;
        }

        /* Le laby est fini, on va pouvoir jouer */
        app.etat = E_JOUER; 
        murs_invisibles (app.laby, 1, 2); 
        init_pion (&app.pion); 
        murs_visibles (app.laby, app.pion.px, app.pion.py);
        send_2expose ();
    }

    return FALSE;  /* Supprime le timer */
}

gint area1_onMotionNotify (GtkWidget *widget, GdkEventMotion *ev)
{
    return TRUE;  /* L'evenement a ete traite' */
}

gint area1_onButtonPress (GtkWidget *widget, GdkEventButton *ev)
{
    return TRUE;  /* L'evenement a ete traite' */
}

gint area1_onButtonRelease (GtkWidget *widget, GdkEventButton *ev)
{
    return TRUE;  /* L'evenement a ete traite' */
}

gint area1_onKeyPress (GtkWidget *widget, GdkEventKey *ev)
{
    switch (ev->keyval) {
        case GDK_q : 
            gtk_main_quit (); 
            break;
        case GDK_Left :
        case GDK_Right :
        case GDK_Up :
        case GDK_Down :
        case GDK_KP_Left :
        case GDK_KP_Right :
        case GDK_KP_Up :
        case GDK_KP_Down :
            app.kb_flch = ev->keyval;
            if (app.etat == E_JOUER) fleche_action ();
            break;
        case GDK_Control_L :
        case GDK_Control_R :
            app.kb_ctrl = 1;
            break;
        case GDK_i :
            if (app.etat == E_JOUER) { 
                murs_invisibles (app.laby, 2, 1); 
                ezg_area_expose (widget);  
            }
            break;
        case GDK_d :
            app.distD /= 1.05; 
            if (app.distD < 2) app.distD = 2;
            ezg_area_expose (app.area2);
            break;
        case GDK_D :
            app.distD *= 1.05; 
            if (app.distD > 10) app.distD = 10;
            ezg_area_expose (app.area2);
            break;
        case GDK_n :
            app.etat = E_CREER;
            init_laby (app.laby);
            init_voisi (app.laby, &app.voisi);
            if (app.timer1_id != -1) g_source_remove (app.timer1_id);
            app.timer1_id = g_timeout_add (DELAY1, area1_onTimeout, NULL);
            break;
    }

    return TRUE;  /* L'evenement a ete traite' */
}

gint area1_onKeyRelease (GtkWidget *widget, GdkEventKey *ev)
{
    switch (ev->keyval) {
        case GDK_Left :
        case GDK_Right :
        case GDK_Up :
        case GDK_Down :
        case GDK_KP_Left :
        case GDK_KP_Right :
        case GDK_KP_Up :
        case GDK_KP_Down :
            app.kb_flch = 0;
            break;
        case GDK_Control_L :
        case GDK_Control_R :
            app.kb_ctrl = 0;
            break;
    }

    return TRUE;  /* L'evenement a ete traite' */
}


/*-------------------- T R A N S F O R M A T I O N S   3 D ------------------*/

#define ZEDIM 4
typedef double Matr[ZEDIM][ZEDIM];  /* [ligne][colonne] */
typedef double Vec[ZEDIM];


/*
 * Affiche la matrice pour la mise au point du programme
*/

void affi_matr (Matr m)
{
    int i, j;
    
    for (i = 0; i < ZEDIM; i++) {
        for (j = 0; j < ZEDIM; j++) printf ("%2.3f ", m[i][j]);
        printf ("\n");
    }
}


/*
 * Initialise la matrice m a la matrice unite
*/

void matr_unite (Matr m)
{
    int i, j;

    for (i = 0; i < ZEDIM; i++)
    for (j = 0; j < ZEDIM; j++)
        m[i][j] = 0;

    for (i = 0; i < ZEDIM; i++)
        m[i][i] = 1;
}


/*
 * Recopie la matrice m dans la matrice res
*/

void copie_matr (Matr m, Matr res)
{
    int i, j;

    for (i = 0; i < ZEDIM; i++)
    for (j = 0; j < ZEDIM; j++)
        res[i][j] = m[i][j];
}


/*
 * Multiplie la matrice m1 par la matrice m2 et place le resultat dans res
*/

void mult_matr_matr (Matr m1, Matr m2, Matr res)
{
    int i, j, k;
    double d;

    for (i = 0; i < ZEDIM; i++)
    for (j = 0; j < ZEDIM; j++)
    {
        d = 0;
        for (k = 0; k < ZEDIM; k++)
            d += m1[i][k] * m2[k][j];
        res[i][j] = d;
    }
}


/*
 * Multiplie la matrice m1 par le vecteur v2 et place le resultat dans res
*/

void mult_matr_vec (Matr m1, Vec v2, Vec res)
{
    int i, k;
    double d;

    for (i = 0; i < ZEDIM; i++)
    {
        d = 0;
        for (k = 0; k < ZEDIM; k++)
            d += m1[i][k] * v2[k];
        res[i] = d;
    }
}


/*
 * Fait l'operation : m = T*m
 * ou T est la matrice de la projection conique sur le plan XY 
 * et de centre (0,0,-D)
*/

void mult_projection (Matr m, double d)
{
    Matr res, tmp = { { d, 0, 0, 0 },
                      { 0, d, 0, 0 },
                      { 0, 0, d, 0 },
                      { 0, 0, 1, d } };
    mult_matr_matr (tmp, m, res);
    copie_matr (res, m);
}


/*
 * Fait l'operation : m = T*m
 * ou T est la matrice de rotation sur l'axe des X et d'angle r (en degres)
*/

void mult_rot_X (Matr m, double r)
{
    double a = r * M_PI / 180, c = cos(a), s = sin(a);
    Matr res, tmp = { { 1, 0, 0, 0 },
                      { 0, c, s, 0 },
                      { 0,-s, c, 0 },
                      { 0, 0, 0, 1 } };
    mult_matr_matr (tmp, m, res);
    copie_matr (res, m);
}


/*
 * Fait l'operation : m = T*m
 * ou T est la matrice de rotation sur l'axe des Y et d'angle r (en degres)
*/

void mult_rot_Y (Matr m, double r)
{
    double a = r * M_PI / 180, c = cos(a), s = sin(a);
    Matr res, tmp = { { c, 0, s, 0 },
                      { 0, 1, 0, 0 },
                      {-s, 0, c, 0 },
                      { 0, 0, 0, 1 } };
    mult_matr_matr (tmp, m, res);
    copie_matr (res, m);
}


/*
 * Fait l'operation : m = T*m
 * ou T est la matrice de rotation sur l'axe des Z et d'angle r (en degres)
*/

void mult_rot_Z (Matr m, double r)
{
    double a = r * M_PI / 180, c = cos(a), s = sin(a);
    Matr res, tmp = { { c, s, 0, 0 },
                      {-s, c, 0, 0 },
                      { 0, 0, 1, 0 },
                      { 0, 0, 0, 1 } };
    mult_matr_matr (tmp, m, res);
    copie_matr (res, m);
}


/*
 * Fait l'operation : m = T*m
 * ou T est la matrice de la translation (dx,dy,dz)
*/

void mult_translation (Matr m, double dx, double dy, double dz)
{
    Matr res, tmp = { { 1, 0, 0, dx },
                      { 0, 1, 0, dy },
                      { 0, 0, 1, dz },
                      { 0, 0, 0,  1 } };
    mult_matr_matr (tmp, m, res);
    copie_matr (res, m);
}


/*
 * Fait l'operation : m = T*m
 * ou T est la matrice d'homothetie de centre 0 et de rapport (rx, ry, rz)
*/

void mult_homothetie (Matr m, double rx, double ry, double rz)
{
    Matr res, tmp = { { rx,  0,  0, 0 },
                      {  0, ry,  0, 0 },
                      {  0,  0, rz, 0 },
                      {  0,  0,  0, 1 } };
    mult_matr_matr (tmp, m, res);
    copie_matr (res, m);
}


/*
 * Transformation geometrique d'un sommet en coordonnees homogenes :
 *  - on applique la matrice de transformation m au vecteur (x1, y1, z1, 1).
 *  - on obtient un vecteur (x', y', z', t').
 *  - si t' != 0, le resultat est *x2=x'/t', *y2=y'/t', *z2 = z'/fabs(t').
*/

void transformation_3D (Matr m, double  x1, double  y1, double  z1, 
                                double *x2, double *y2, double *z2)
{
    Vec v1, v2;
    
    v1[0] = x1; v1[1] = y1; v1[2] = z1; v1[3] = 1;
    mult_matr_vec (m, v1, v2);

    /* Point a l'infini */
    if (v2[3] == 0) { *x2 = *y2 = 0; *z2 = -1; }

    /* On utilise fabs() pour que les objets situe's derriere l'observateur
       aient un z < 0 */
    *x2 = v2[0]/v2[3]; *y2 = v2[1]/v2[3]; *z2 = v2[2]/fabs(v2[3]); 
}


/* (Actuellement inutilisee dans ce programme)
 *
 * Coupe le segment en tz = 0 avec par hypothese tz1 < 0 <= tz2.
 * Une interpolation lineaire en tz=0 ne suffisant pas, on fait
 * une recherche dichotomique du point de coupe. Usage :
 *   if (tz1 < 0)
 *       coupe_segment (m, x1, y1, 1, x2, y2, 1, tx1, tx2, &tx1, &ty1, &tz1);
 *   else if (tz2 < 0)
 *       coupe_segment (m, x2, y2, 1, x1, y1, 1, tx2, tx1, &tx2, &ty2, &tz2);
*/

void coupe_segment (Matr m, double   x1, double   y1, double   z1, 
                            double   x2, double   y2, double   z2, 
                            double  tx1, double  tx2, 
                            double *ox3, double *oy3, double *oz3)
{
    double x3, y3, z3;

    while ( fabs(tx2 - tx1) >= 1 ) {
        x3 = (x1+x2)/2; y3 = (y1+y2)/2; z3 = (z1+z2)/2;
        transformation_3D (m, x3, y3, z3, ox3, oy3, oz3);
        if (*oz3 < 0) { x1 = x3; y1 = y3; z1 = z3; tx1 = *ox3; }
        else          { x2 = x3; y2 = y3; z2 = z3; tx2 = *ox3; }
    }
}


/*------------------------------- Z - B U F F E R ---------------------------*/

#define ZBUF_MAX 2048
typedef struct {
    double y[ZBUF_MAX], z[ZBUF_MAX];
    int    e[ZBUF_MAX], larg;
} Zbuffer;


/* 
 * Initialise le Z-buffer sur une ligne 
*/

void zbuf_init (Zbuffer *buf, int larg)
{
    int x;

    buf->larg = (larg < ZBUF_MAX) ? larg : ZBUF_MAX;

    for (x = 0; x < buf->larg; x++) {
        buf->y[x] = -1;
        buf->z[x] = -1;
        buf->e[x] = 0;
    }
}


/*
 * Incruste les points visibles d'un segment dans le Z-buffer
*/

void zbuf_segment (Zbuffer *buf, Matr m, int x1, int y1, int x2, int y2)
{
    double tx1, ty1, tz1, tx2, ty2, tz2, tmp, z;
    int x, ix1, ix2;

    transformation_3D (m, x1, y1, 1, &tx1, &ty1, &tz1);
    transformation_3D (m, x2, y2, 1, &tx2, &ty2, &tz2);

    /* Si les deux extremites sont hors fenetre alors retour */
    if ((tx1 < 0 && tx2 < 0) || (tx1 >= buf->larg && tx2 >= buf->larg)) return;

    /* Si les deux extremites sont derriere l'observateur alors retour */
    if (tz1 < 0 && tz2 < 0) return; 

    /* Si l'une des extremites est derriere et que l'autre est hors fenetre,
       c'est un mur qu'on ne doit pas voir */
    if ( (tz1 < 0 && (tx2 < 0 || tx2 >= buf->larg)) ||
         (tz2 < 0 && (tx1 < 0 || tx1 >= buf->larg)) ) return;

    /* On met les x dans l'ordre croissant */
    if (tx1 > tx2) {
        tmp = tx1; tx1 = tx2; tx2 = tmp;
        tmp = ty1; ty1 = ty2; ty2 = tmp;
        tmp = tz1; tz1 = tz2; tz2 = tmp;
    }

    /* Calcul des bornes dans la fenetre */
    ix1 = (tx1 >= 0) ? tx1 : 0;
    ix2 = (tx2 < buf->larg) ? tx2 : buf->larg-1;

    /* Pour chaque point du segment on verifie si le point sera visible */
    for (x = ix1; x <= ix2; x++) {

        /* On interpole lineairement en z : c'est faux mais suffisant */
        z = tz1 + (x-tx1)*(tz2-tz1)/(tx2-tx1) + 0.5;  /* arrondi */

        /* Ce point est derriere, on passe au suivant. */
        if (buf->z[x] != -1 && z >= buf->z[x]) continue;

        /* Ce point est visible, on le memorise dans le Z-buffer */
        buf->z[x] = z;
        buf->y[x] = ty1 + (x-tx1)*(ty2-ty1)/(tx2-tx1) + 0.5;  /* arrondi */
        /* e[x] =  0 interieur, 1 extremite, 2 coupe' */
        buf->e[x] = (x != ix1 && x != ix2) ? 0 :  
                    (fabs(x-tx1) > 1 && fabs(x-tx2) > 1) ? 2 : 1;
    }
}


/*
 * Dessine la scene a partir du Z-buffer
*/

void zbuf_render (GtkWidget *widget, GdkGC *gc, Zbuffer *buf, int haut)
{
    int x, lx = -1;

    ezg_set_color (gc, EZG_BLUE);

    for (x = 0; x < buf->larg; x++) {
        if (buf->e[x] >= 1 || x == buf->larg-1) {
            if (lx+1 < x-1) {
                /* Dessine le haut et le bas du mur */
                gdk_draw_line (widget->window, gc, 
                    lx+1, buf->y[lx+1], x-1, buf->y[x-1]);
                gdk_draw_line (widget->window, gc, 
                    lx+1, haut-buf->y[lx+1], x-1, haut-buf->y[x-1]);
            }
            if (buf->e[x] == 1) {
                /* Dessine un cote vertical du mur */
                gdk_draw_line (widget->window, gc, 
                    x, haut - buf->y[x], x, buf->y[x]);
            }
            lx = x;
        } 
    }
}


/*-------------------------- A F F I C H A G E   3 D ------------------------*/

/*
 * Calcule la matrice m du produit des transformations simples.
*/

void calcul_transfo3D (Matr m, double angle, 
	double distD, int larg, int haut, double rap, double cx, double cy)
{
    matr_unite (m);
    mult_translation (m, -cx, -cy, 0);
    mult_rot_Z (m, angle+90);
    mult_rot_X (m, 90);
    mult_projection (m, distD);
    mult_homothetie (m, rap*larg, rap*haut, 1);
    mult_translation (m, larg/2, haut/2, 0);
}


/*
 * Dessin en projection perspective :
 *  - calcule la matrice m du produit des transformations simples
 *  - applique m aux sommets 3D --> sommets 2D
 *  - adapte les coordonnees des sommets 2D a la taille de la fenetre
 *  - calcule les parties visibles avec un Z-buffer sur une ligne
 *  - affiche les parties visibles.
*/

void dessin_perspective (Laby laby, GtkWidget *widget, GdkGC *gc, 
    int larg, int haut, double rap,
    double angle, double distD, double px, double py)
{
    int x, y;
    Matr m;
    Zbuffer buf;
    
    /* Calcule la matrice m du produit des transformations simples */
    calcul_transfo3D (m, angle, distD, larg, haut, rap, px*2+1, py*2+1);
    
    /* Utile un Z-buffer en x pour calculer les parties visibles */
    zbuf_init (&buf, larg);

    for (y = 0; y <= LABY_YM; y++)
    for (x = 0; x <  LABY_XM; x++)
    if (laby[y*2][x*2+1] >= 1) 
        zbuf_segment (&buf, m, 2*x, 2*y, 2*x+2, 2*y);

    for (y = 0; y <  LABY_YM; y++)
    for (x = 0; x <= LABY_XM; x++)
    if (laby[y*2+1][x*2] >= 1) 
        zbuf_segment (&buf, m, 2*x, 2*y, 2*x, 2*y+2);

    /* Dessine les parties visibles */
    zbuf_render (widget, gc, &buf, haut);
}


/*----------------------- E V E N E M E N T S   W I N 2 ---------------------*/

gint area2_onExpose (GtkWidget *widget, GdkEventExpose *ev)
{
    int w = widget->allocation.width, 
        h = widget->allocation.height;

    /* On recupere le contexte graphique associe' au widget */
    GdkGC *gc = ezg_get_gc (widget);

    /* On cree un layout pour dessiner du texte */
    PangoLayout *layout = gtk_widget_create_pango_layout (widget, NULL);

    /* On dessine le fond en blanc */
    ezg_area_clear (widget);

    if (app.etat == E_DEPLA)
         dessin_perspective (app.laby, widget, gc, w, h, HOMO_RAP, 
            app.depla.a, app.distD, app.depla.x, app.depla.y);
    else dessin_perspective (app.laby, widget, gc, w, h, HOMO_RAP, 
            app.pion.pa, app.distD, app.pion.px, app.pion.py);

    ezg_set_color (gc, EZG_BLACK); ezg_set_nfont (layout, 0);
    ezg_draw_text (widget, gc, layout, EZG_BC, w/2, h-5, 
        "fleches : deplacer   control+fleches : lateral");
    ezg_draw_text (widget, gc, layout, EZG_TC, w/2, 5, 
        "d,D : dist focale %.2f", app.distD);

    /* Libere la memoire */
    g_object_unref (G_OBJECT (layout));

    return TRUE;  /* L'evenement a ete traite' */
}

gboolean area2_onTimeout (gpointer data)
{
    if (app.etat == E_DEPLA) deplace_pion ();
    return FALSE;  /* Supprime le timer */
}

gint area2_onMotionNotify (GtkWidget *widget, GdkEventMotion *ev)
{
    return TRUE;  /* L'evenement a ete traite' */
}

gint area2_onButtonPress (GtkWidget *widget, GdkEventButton *ev)
{
    return TRUE;  /* L'evenement a ete traite' */
}

gint area2_onButtonRelease (GtkWidget *widget, GdkEventButton *ev)
{
    return TRUE;  /* L'evenement a ete traite' */
}

gint area2_onKeyPress (GtkWidget *widget, GdkEventKey *ev)
{
    return area1_onKeyPress (app.area1, ev);
}

gint area2_onKeyRelease (GtkWidget *widget, GdkEventKey *ev)
{
    return area1_onKeyRelease (app.area1, ev);
}


/*------------------ P R O G R A M M E   P R I N C I P A L ------------------*/

int main (int argc, char *argv[])
{
    /* Initialise gtk et analyse la ligne de commande */
    gtk_init (&argc, &argv);

    init_appli ();
    init_laby (app.laby);

    app.win1 = ezg_window_create (WIN1_W, WIN1_H, "Jeu de labyrinthe");
    app.area1 = ezg_area_create (app.win1);

    /* On autorise certains evenements */
    GTK_WIDGET_SET_FLAGS  (app.area1, GTK_CAN_FOCUS);
    gtk_widget_set_events (app.area1, 
        GDK_EXPOSURE_MASK |
        GDK_KEY_PRESS_MASK | GDK_KEY_RELEASE_MASK |
        GDK_BUTTON_PRESS_MASK | GDK_BUTTON_RELEASE_MASK |
        GDK_POINTER_MOTION_MASK);

    /* On attache des callbacks pour gerer certains evenements */
    g_signal_connect (G_OBJECT (app.area1), "expose_event"        , G_CALLBACK (area1_onExpose)  , NULL);
    g_signal_connect (G_OBJECT (app.area1), "key_press_event"     , G_CALLBACK (area1_onKeyPress)     , NULL);
    g_signal_connect (G_OBJECT (app.area1), "key_release_event"   , G_CALLBACK (area1_onKeyRelease)   , NULL);
    g_signal_connect (G_OBJECT (app.area1), "button_press_event"  , G_CALLBACK (area1_onButtonPress)  , NULL);
    g_signal_connect (G_OBJECT (app.area1), "button_release_event", G_CALLBACK (area1_onButtonRelease), NULL);
    g_signal_connect (G_OBJECT (app.area1), "motion_notify_event" , G_CALLBACK (area1_onMotionNotify) , NULL);
    g_signal_connect (G_OBJECT (app.win1) , "destroy"             , G_CALLBACK (gtk_main_quit)   , NULL);


    app.win2 = ezg_window_create (WIN2_W, WIN2_H, "Vue 3D");
    app.area2 = ezg_area_create (app.win2);

    /* On autorise certains evenements */
    GTK_WIDGET_SET_FLAGS  (app.area2, GTK_CAN_FOCUS);
    gtk_widget_set_events (app.area2,
        GDK_EXPOSURE_MASK |
        GDK_KEY_PRESS_MASK | GDK_KEY_RELEASE_MASK |
        GDK_BUTTON_PRESS_MASK | GDK_BUTTON_RELEASE_MASK |
        GDK_POINTER_MOTION_MASK);

    /* On attache des callbacks pour gerer certains evenements */
    g_signal_connect (G_OBJECT (app.area2), "expose_event"        , G_CALLBACK (area2_onExpose)  , NULL);
    g_signal_connect (G_OBJECT (app.area2), "key_press_event"     , G_CALLBACK (area2_onKeyPress)     , NULL);
    g_signal_connect (G_OBJECT (app.area2), "key_release_event"   , G_CALLBACK (area2_onKeyRelease)   , NULL);
    g_signal_connect (G_OBJECT (app.area2), "button_press_event"  , G_CALLBACK (area2_onButtonPress)  , NULL);
    g_signal_connect (G_OBJECT (app.area2), "button_release_event", G_CALLBACK (area2_onButtonRelease), NULL);
    g_signal_connect (G_OBJECT (app.area2), "motion_notify_event" , G_CALLBACK (area2_onMotionNotify) , NULL);
    g_signal_connect (G_OBJECT (app.win2) , "destroy"             , G_CALLBACK (gtk_main_quit)   , NULL);


    /* Rend visibles les fenetres et leur contenu */
    gtk_widget_show_all (app.win2);
    gtk_widget_show_all (app.win1); 


    /* Boucle d'evenements qui fait "vivre" la fenetre */
    gtk_main ();

    exit (0);
}