/* jeu-laby.c : un jeu de labyrinthe
 *
 * Edouard.Thiel@lif.univ-mrs.fr - 08/04/2009 - version 1.2
 *
 * Compilation sous Unix :
 *   gcc -Wall jeu-laby.c ez-draw.c -o jeu-laby -lX11 -lXext -lm -L/usr/X11R6/lib
 * Compilation sous Windows :
 *   gcc -Wall jeu-laby.c ez-draw.c -o jeu-laby.exe -lgdi32 -lm
 *
 * This program is free software under the terms of the
 * GNU Lesser General Public License (LGPL) version 2.1.
*/

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

#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif

/*------------------------- 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_shift;          /* une touche control enfoncee */
    double distD;          /* Distance de l'observateur au plan focal */
    Ez_window win1, win2;  /* Fenetre du plan, de la vue 3D */
} Appli;


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

Appli app;  /* Globale */

void init_appli ()
{
    app.etat = E_DEBUT;
    app.kb_flch = 0;
    app.kb_shift = 0;
    app.distD = PROJ_DISTD;
}

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


/*---------------- 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 = ez_random(LABY_XM);
    y = ez_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 = ez_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 = ez_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 XK_Left     : 
        case XK_KP_Left  : 
            if (app.kb_shift) 
                 lateral_pion (app.laby, &app.pion, &app.depla, -1); 
            else tourne_pion (&app.pion, &app.depla, -1); 
            break;

        case XK_Right    : 
        case XK_KP_Right : 
            if (app.kb_shift) 
                 lateral_pion (app.laby, &app.pion, &app.depla, 1); 
            else tourne_pion (&app.pion, &app.depla, 1); 
            break;

        case XK_Up       : 
        case XK_KP_Up    : 
            avance_pion (app.laby, &app.pion, &app.depla, 1); 
            break;

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

        default : return;
    }

    app.etat = E_DEPLA;
    ez_start_timer (app.win2, DELAY2);
}

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 ez_start_timer (app.win2, DELAY2);

    send_2expose ();
}

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

void dessin_murh (Ez_window win, int x, int y)
{
    ez_draw_line (win, W_X0+ x   *W_TA, W_Y0+y*W_TA, 
                       W_X0+(x+1)*W_TA, W_Y0+y*W_TA);
}

void dessin_murv (Ez_window win, int x, int y)
{
    ez_draw_line (win, W_X0+x*W_TA, W_Y0+ y   *W_TA, 
                       W_X0+x*W_TA, W_Y0+(y+1)*W_TA);
}

void dessin_case (Ez_window win, int x, int y)
{
    ez_fill_rectangle (win, W_X0+ x   *W_TA+1, W_Y0+ y   *W_TA+1, 
                            W_X0+(x+1)*W_TA-1, W_Y0+(y+1)*W_TA-1);
}

void dessin_pion (Ez_window win, 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;
             
    ez_draw_circle (win, x1 - P_RA, y1 - P_RA, x1 + P_RA, y1 + P_RA);

    ez_draw_line (win, x1, y1, x1 + c*P_RA + 0.5, y1 + s*P_RA + 0.5);
}

void dessin_sortie (Ez_window win, int x, int y)
{
    ez_draw_line (win, 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);
    ez_draw_line (win, 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 win1_redessiner (Ez_window win)
{
    int x, y;
    char *s;

    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 = "";
    }
    ez_set_color (ez_blue); ez_set_nfont (2);
    ez_draw_text (win, EZ_TC, WIN1_W/2, 10, s);

    ez_set_color (ez_black); ez_set_nfont (0);
    ez_draw_text (win, EZ_BL, 10, WIN1_H-5, 
        "n : nouvelle partie  i : devoiler  q : quitter");

    if (app.etat == E_DEBUT) {

        ez_set_color (ez_magenta); ez_set_nfont (1);
        ez_draw_text (win, EZ_TC, WIN1_W/2, WIN1_H*2/7,
            "Utilisez les fleches\npour vous deplacer.\n\n"
            "Tapez 'n' pour commencer ...");
        ez_set_color (ez_red); ez_set_nfont (0);
        ez_draw_text (win, EZ_TC, WIN1_W/2, WIN1_H*5/7,
            "Le programme jeu-laby.c fait partie de EZ-Draw :\n"
            "http://pageperso.lif.univ-mrs.fr/~edouard.thiel/ez-draw");

    } else {

        ez_set_color (ez_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 (win, 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 (win, x, y);

        if (app.etat == E_CREER) {
            ez_set_color (ez_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 (win, x, y);

            ez_set_color (ez_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 (win, x, y);
        } else {
            ez_set_color (ez_red);
            if (app.etat == E_DEPLA)
                 dessin_pion (win, app.depla.x, app.depla.y, app.depla.a);
            else dessin_pion (win, app.pion.px, app.pion.py, app.pion.pa);
            dessin_sortie (win, app.pion.sx, app.pion.sy);
        }
    }
}


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

void win1_onExpose (Ez_event *ev)
{
    win1_redessiner (ev->win);
}

void win1_onMotionNotify (Ez_event *ev)
{
    (void) ev;  /* Parametre inutilise' */
}

void win1_onButtonPress (Ez_event *ev)
{
    (void) ev;  /* Parametre inutilise' */
}

void win1_onButtonRelease (Ez_event *ev)
{
    (void) ev;  /* Parametre inutilise' */
}

void win1_onKeyPress (Ez_event *ev)
{
    switch (ev->key_sym) {
        case XK_q : 
            ez_quit (); 
            break;
        case XK_Left :
        case XK_Right :
        case XK_Up :
        case XK_Down :
        case XK_KP_Left :
        case XK_KP_Right :
        case XK_KP_Up :
        case XK_KP_Down :
            app.kb_flch = ev->key_sym;
            if (app.etat == E_JOUER) fleche_action ();
            break;
        case XK_Shift_L :
        case XK_Shift_R :
            app.kb_shift = 1;
            break;
        case XK_i :
            if (app.etat == E_JOUER) { 
                murs_invisibles (app.laby, 2, 1); 
                ez_send_expose (ev->win); 
            }
            break;
        case XK_d :
            app.distD /= 1.05; 
            if (app.distD < 2) app.distD = 2;
            ez_send_expose (app.win2);
            break;
        case XK_D :
            app.distD *= 1.05; 
            if (app.distD > 10) app.distD = 10;
            ez_send_expose (app.win2);
            break;
        case XK_n :
            app.etat = E_CREER;
            init_laby (app.laby);
            init_voisi (app.laby, &app.voisi);
            ez_start_timer (ev->win, DELAY1);
            break;
    }
}

void win1_onKeyRelease (Ez_event *ev)
{
    switch (ev->key_sym) {
        case XK_Left :
        case XK_Right :
        case XK_Up :
        case XK_Down :
        case XK_KP_Left :
        case XK_KP_Right :
        case XK_KP_Up :
        case XK_KP_Down :
            app.kb_flch = 0;
            break;
        case XK_Shift_L :
        case XK_Shift_R :
            app.kb_shift = 0;
            break;
    }
}

void win1_onTimerNotify (Ez_event *ev)
{
    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 */
            ez_start_timer (ev->win, DELAY1);
        } else { 
            /* 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 ();
    }
}

void win1_event (Ez_event *ev)        /* Appele'e a chaque evenement sur win1 */
{
    switch (ev->type) {
        case Expose        : win1_onExpose (ev); break;
        case MotionNotify  : win1_onMotionNotify (ev); break;
        case ButtonPress   : win1_onButtonPress (ev); break;
        case ButtonRelease : win1_onButtonRelease (ev); break;
        case KeyPress      : win1_onKeyPress (ev); break;
        case KeyRelease    : win1_onKeyRelease (ev); break;
        case TimerNotify   : win1_onTimerNotify (ev); break;
    }
}


/*-------------------- 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;

    tmp[0][0] =  d; tmp[0][1] =  0; tmp[0][2] =  0; tmp[0][3] =  0;
    tmp[1][0] =  0; tmp[1][1] =  d; tmp[1][2] =  0; tmp[1][3] =  0;
    tmp[2][0] =  0; tmp[2][1] =  0; tmp[2][2] =  d; tmp[2][3] =  0;
    tmp[3][0] =  0; tmp[3][1] =  0; tmp[3][2] =  1; tmp[3][3] =  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)
{
    Matr res, tmp;
    double a, c, s;

    a = r * M_PI / 180; c = cos(a); s = sin(a);

    tmp[0][0] =  1; tmp[0][1] =  0; tmp[0][2] =  0; tmp[0][3] =  0;
    tmp[1][0] =  0; tmp[1][1] =  c; tmp[1][2] =  s; tmp[1][3] =  0;
    tmp[2][0] =  0; tmp[2][1] = -s; tmp[2][2] =  c; tmp[2][3] =  0;
    tmp[3][0] =  0; tmp[3][1] =  0; tmp[3][2] =  0; tmp[3][3] =  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)
{
    Matr res, tmp;
    double a, c, s;

    a = r * M_PI / 180; c = cos(a); s = sin(a);

    tmp[0][0] =  c; tmp[0][1] =  0; tmp[0][2] =  s; tmp[0][3] =  0;
    tmp[1][0] =  0; tmp[1][1] =  1; tmp[1][2] =  0; tmp[1][3] =  0;
    tmp[2][0] = -s; tmp[2][1] =  0; tmp[2][2] =  c; tmp[2][3] =  0;
    tmp[3][0] =  0; tmp[3][1] =  0; tmp[3][2] =  0; tmp[3][3] =  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)
{
    Matr res, tmp;
    double a, c, s;

    a = r * M_PI / 180; c = cos(a); s = sin(a);

    tmp[0][0] =  c; tmp[0][1] =  s; tmp[0][2] =  0; tmp[0][3] =  0;
    tmp[1][0] = -s; tmp[1][1] =  c; tmp[1][2] =  0; tmp[1][3] =  0;
    tmp[2][0] =  0; tmp[2][1] =  0; tmp[2][2] =  1; tmp[2][3] =  0;
    tmp[3][0] =  0; tmp[3][1] =  0; tmp[3][2] =  0; tmp[3][3] =  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;

    tmp[0][0] =  1; tmp[0][1] =  0; tmp[0][2] =  0; tmp[0][3] = dx;
    tmp[1][0] =  0; tmp[1][1] =  1; tmp[1][2] =  0; tmp[1][3] = dy;
    tmp[2][0] =  0; tmp[2][1] =  0; tmp[2][2] =  1; tmp[2][3] = dz;
    tmp[3][0] =  0; tmp[3][1] =  0; tmp[3][2] =  0; tmp[3][3] =  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;

    tmp[0][0] = rx; tmp[0][1] =  0; tmp[0][2] =  0; tmp[0][3] =  0;
    tmp[1][0] =  0; tmp[1][1] = ry; tmp[1][2] =  0; tmp[1][3] =  0;
    tmp[2][0] =  0; tmp[2][1] =  0; tmp[2][2] = rz; tmp[2][3] =  0;
    tmp[3][0] =  0; tmp[3][1] =  0; tmp[3][2] =  0; tmp[3][3] =  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; return; }

    /* 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 (Ez_window win, Zbuffer *buf, int haut)
{
    int x, lx = -1;

    ez_set_color (ez_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 */
                ez_draw_line (win, lx+1, buf->y[lx+1], x-1, buf->y[x-1]);
                ez_draw_line (win, 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 */
                ez_draw_line (win, 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, Ez_window win, 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 (win, &buf, haut);
}


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

void win2_onExpose (Ez_event *ev)
{
    int w, h;

    ez_window_get_size (ev->win, &w, &h);
    if (app.etat == E_DEPLA)
         dessin_perspective (app.laby, ev->win, w, h, HOMO_RAP, 
            app.depla.a, app.distD, app.depla.x, app.depla.y);
    else dessin_perspective (app.laby, ev->win, w, h, HOMO_RAP, 
            app.pion.pa, app.distD, app.pion.px, app.pion.py);

    ez_set_color (ez_black); ez_set_nfont (0);
    ez_draw_text (ev->win, EZ_BC, w/2, h-5, 
        "fleches : deplacer   shift+fleches : lateral");
    ez_draw_text (ev->win, EZ_TC, w/2, 5, 
        "d,D : dist focale %.2f", app.distD);
}

void win2_onMotionNotify (Ez_event *ev)
{
    (void) ev;  /* Parametre inutilise' */
}

void win2_onButtonPress (Ez_event *ev)
{
    (void) ev;  /* Parametre inutilise' */
}

void win2_onButtonRelease (Ez_event *ev)
{
    (void) ev;  /* Parametre inutilise' */
}

void win2_onKeyPress (Ez_event *ev)
{
    Ez_event ev2 = *ev;
    ev2.win = app.win1;
    win1_onKeyPress (&ev2);
}

void win2_onKeyRelease (Ez_event *ev)
{
    Ez_event ev2 = *ev;
    ev2.win = app.win1;
    win1_onKeyRelease (&ev2);
}

void win2_onTimerNotify (Ez_event *ev)
{
    (void) ev;  /* Parametre inutilise' */
    if (app.etat == E_DEPLA) deplace_pion ();
}

void win2_event (Ez_event *ev)        /* Appele'e a chaque evenement sur win2 */
{
    switch (ev->type) {
        case Expose        : win2_onExpose (ev); break;
        case MotionNotify  : win2_onMotionNotify (ev); break;
        case ButtonPress   : win2_onButtonPress (ev); break;
        case ButtonRelease : win2_onButtonRelease (ev); break;
        case KeyPress      : win2_onKeyPress (ev); break;
        case KeyRelease    : win2_onKeyRelease (ev); break;
        case TimerNotify   : win2_onTimerNotify (ev); break;
    }
}


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

int main ()
{
    if (ez_init() < 0) exit(1);

    init_appli ();
    init_laby (app.laby);

    app.win1 = ez_window_create (WIN1_W, WIN1_H, "Jeu de labyrinthe", win1_event);
    app.win2 = ez_window_create (WIN2_W, WIN2_H, "Vue 3D", win2_event);

    /* On associe un double-buffer d'affichage pour eviter tout clignotement */
    ez_window_dbuf (app.win1, 1);
    ez_window_dbuf (app.win2, 1);

    ez_main_loop ();
    exit(0);
}