#include <math.h>
#include <time.h>
#include <poll.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#include <X11/Xlib.h>
#include <X11/Xutil.h>
#include <X11/Xatom.h>
#include <X11/keysym.h>

#include <GL/glx.h>

#include "3darith.h"
#include "mathutils.h"

#define WINX 400
#define WINY 400
#define MZX 3
#define MZY 3
#define MZZ 3
#define MZWALLS ((MZX*MZY*MZZ*3)-(MZX*MZY)-(MZY*MZZ)-(MZZ*MZX))
#define TEXSIZE 512
#if MZX*MZY*MZZ < 255
typedef unsigned char CELLNO;
#elif MZX*MZY*MZZ < 65535
typedef unsigned short int CELLNO;
#else
typedef unsigned int CELLNO;
#endif

extern const char *__progname;

static Display *disp;
static XVisualInfo *vi;
static GLXContext ctx;
static Screen *scr;
static int scrwidth;
static int scrheight;
static int depth;
static Window rootwin;
static Colormap cmap;
static Window win;
static Window pwin;
static int peq;
static XColor bgcolour;
static XColor fgcolour;
static GC gc;
static struct timeval nexttick;
static unsigned int frameus;
static struct timeval now;
static unsigned int tex;
static unsigned char texture[TEXSIZE+2][TEXSIZE+2][4];
/*
 * It would be conceptually easier to keep this state as the camera's
 *  unit vectors (eg, forward, up, and right) as measured in world
 *  coordinates.  However, if we do that, we have to invert a
 *  transformation matrix at rendering time.  To make the render-time
 *  operations easy, we have to instead maintain the converse: the
 *  world basis vectors in eye coordinates.  These are wx, wy, and wz:
 *  the world x, y, and z unit vectors, in eye coordinates.  However,
 *  in order to make motion feasibly simple, we also maintain the
 *  converse: the eye x, y, and z unit vectors in world coordinates.
 *
 * We could simply maintain them separately.  But then numerical
 *  roundoff errors would cause the two sets, theoretically inverses of
 *  one another, to drift out of sync.  So, instead, we depend on
 *  another property: rotation and movement are usually well-separated,
 *  meaning it is feasible to maintain only one of them and invert the
 *  matrix when the other is needed.  Since we constantly need wx/wy/wz
 *  for rendering, it is ex/ey/ez that we maintain lazily.  evalid is a
 *  boolean indicating whether ex/ey/ez are valid.
 *
 * wx/wy/wz and ex/ey/ez represent only rotations.  The player's
 *  location in world coordinates is stored in ploc.  Like wx/wy/wz,
 *  this is always valid.
 *
 * "eye coordinates" are a coordinate system whose Z axis points
 *  opposite the view direction, whose X axis points in the camera's
 *  "right" direction, and whose Y axis points in the camera's "up"
 *  direction.  The Z axis is negated from the obvious convention
 *  because that's required by the combination of two other useful
 *  properties: (1) eye X and Y coordinates are "the same as" (parallel
 *  to and same sign as) screen X and Y coordinates and (2) the eye
 *  coordinate system obeys the same right-hand rule as the world
 *  coordinate system.
 */
static XYZ wx;
static XYZ wy;
static XYZ wz;
static XYZ ploc;
static int evalid;
static XYZ ex;
static XYZ ey;
static XYZ ez;
static unsigned int kbstate;
#define KBS_ML   0x00000001
#define KBS_MR   0x00000002
#define KBS_MU   0x00000004
#define KBS_MD   0x00000008
#define KBS_MF   0x00000010
#define KBS_MB   0x00000020
#define KBS_RL   0x00000040
#define KBS_RR   0x00000080
#define KBS_RU   0x00000100
#define KBS_RD   0x00000200
#define KBS_RCW  0x00000400
#define KBS_RCCW 0x00000800
#define KBS_LSHF 0x00001000
#define KBS_RSHF 0x00002000
#define KBS_LCTL 0x00004000
#define KBS_RCTL 0x00008000
#define KBS_SHIFT (KBS_LSHF|KBS_RSHF)
#define KBS_CTRL (KBS_LCTL|KBS_RCTL)
static int dbg;
static int swapped;
typedef unsigned char MZBITS;
static MZBITS maze[MZX][MZY][MZZ];
#define MZ_PX 0x01
#define MZ_MX 0x02
#define MZ_PY 0x04
#define MZ_MY 0x08
#define MZ_PZ 0x10
#define MZ_MZ 0x20
#define MZ_S  0x40
#define MZ_G  0x80
static unsigned int ticks;
static GLuint mazelist;
static XYZI mzs;
static XYZI mzg;

static void open_display(void)
{
 disp = XOpenDisplay(0);
 if (disp == 0)
  { fprintf(stderr,"%s: can't open display\n",__progname);
    exit(1);
  }
}

static void find_visual(void)
{
 XVisualInfo template;
 int nvi;

 template.visualid = 35;
 vi = XGetVisualInfo(disp,VisualIDMask,&template,&nvi);
 if (nvi < 1)
  { fprintf(stderr,"%s: can't find visual\n",__progname);
    exit(1);
  }
 if (nvi > 1)
  { fprintf(stderr,"%s: found multiple visuals\n",__progname);
    exit(1);
  }
}

static void setup_X(void)
{
 Pixmap p;

 scr = XScreenOfDisplay(disp,vi->screen);
 scrwidth = XWidthOfScreen(scr);
 scrheight = XHeightOfScreen(scr);
 depth = vi->depth;
 rootwin = XRootWindowOfScreen(scr);
 cmap = XCreateColormap(disp,rootwin,vi->visual,AllocNone);
 XParseColor(disp,cmap,"#646",&bgcolour);
 XAllocColor(disp,cmap,&bgcolour);
 XParseColor(disp,cmap,"#fff",&fgcolour);
 XAllocColor(disp,cmap,&fgcolour);
 p = XCreatePixmap(disp,rootwin,1,1,depth);
 gc = XCreateGC(disp,p,0,0);
 XFreePixmap(disp,p);
}

static void setup_context(void)
{
 ctx = glXCreateContext(disp,vi,0,True);
 if (! ctx)
  { fprintf(stderr,"%s: can't create GL context\n",__progname);
    exit(1);
  }
}

static int clip(int, int, int)
	__attribute__((__const__));
static int clip(int v, int min, int max)
{
 return((v<min)?min:(v>max)?max:v);
}

static void setup_bitmaps(void)
{
 int x;
 int y;
 double d;

 for (x=TEXSIZE+2-1;x>=0;x--)
  { for (y=TEXSIZE+2-1;y>=0;y--)
     { d = hypot(x-((TEXSIZE+2-1)/2.0),y-((TEXSIZE+2-1)/2.0));
       if (d >= TEXSIZE/2.0)
	{ texture[y][x][0] = 127;
	  texture[y][x][1] = 127;
	  texture[y][x][2] = 127;
	  texture[y][x][3] = 255;
	}
       else
	{ d = (d * 3) / (TEXSIZE/2.0);
	  texture[y][x][0] = clip((d<1)?d*256:0,0,255);
	  texture[y][x][1] = clip(((d>=1)&&(d<2))?(d-1)*256:0,0,255);
	  texture[y][x][2] = clip((d>=2)?(d-2)*256:0,0,255);
	  texture[y][x][3] = 255;
	}
     }
  }
}

static void create_window(void)
{
 XSetWindowAttributes attr;
 unsigned long int attrmask;

 attrmask = 0;
 attr.background_pixel = bgcolour.pixel;
 attrmask |= CWBackPixel;
 attr.event_mask = StructureNotifyMask | VisibilityChangeMask |
	KeyPressMask | KeyReleaseMask;
 attrmask |= CWEventMask;
 attr.colormap = cmap;
 attrmask |= CWColormap;
 win = XCreateWindow(disp,rootwin,0,0,WINX,WINY,0,depth,InputOutput,vi->visual,attrmask,&attr);
 XMapRaised(disp,win);
 attrmask = 0;
 attr.event_mask = PropertyChangeMask;
 attrmask |= CWEventMask;
 pwin = XCreateWindow(disp,win,-1,-1,1,1,0,0,InputOnly,vi->visual,attrmask,&attr);
 peq = 0;
}

static void setup_gl(void)
{
 double ps[4] = { .1, 0, 0, 0 };
 double pt[4] = { 0, .1, 0, 0 };

 if (glXMakeCurrent(disp,(GLXDrawable)win,ctx) != True)
  { fprintf(stderr,"%s: can't make context current\n",__progname);
    exit(1);
  }
 glShadeModel(GL_SMOOTH);
 glClearColor(0,0,0,0);
 glMatrixMode(GL_PROJECTION);
 glLoadIdentity();
 glFrustum(-.25,.25,-.25,.25,.25,(hypot(hypot(MZX,MZY),MZZ)+1)*10);
 glMatrixMode(GL_MODELVIEW);
 glEnable(GL_DEPTH_TEST);
 glEnable(GL_POLYGON_OFFSET_FILL);
 glPixelStorei(GL_UNPACK_ALIGNMENT,1);
 glGenTextures(1,&tex);
 glBindTexture(GL_TEXTURE_2D,tex);
 glTexEnvi(GL_TEXTURE_ENV,GL_TEXTURE_ENV_MODE,GL_DECAL);
 glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MIN_FILTER,GL_NEAREST);
 glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_NEAREST);
 glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_WRAP_S,GL_CLAMP);
 glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_WRAP_T,GL_CLAMP);
 glTexImage2D(GL_TEXTURE_2D,0,GL_RGBA,TEXSIZE+2,TEXSIZE+2,1,GL_RGBA,GL_UNSIGNED_BYTE,&texture[0][0][0]);
 glTexGeni(GL_S,GL_TEXTURE_GEN_MODE,GL_EYE_LINEAR);
 glTexGeni(GL_T,GL_TEXTURE_GEN_MODE,GL_EYE_LINEAR);
 glTexGendv(GL_S,GL_EYE_PLANE,&ps[0]);
 glTexGendv(GL_T,GL_EYE_PLANE,&pt[0]);
 glCullFace(GL_BACK);
 glFrontFace(GL_CW);
 glEnable(GL_CULL_FACE);
 kbstate = 0;
}

static const char *maze_bit_name(MZBITS)
	__attribute__((__unused__));
static const char *maze_bit_name(MZBITS bit)
{
 switch (bit)
  { case MZ_PX: return("PX"); break;
    case MZ_MX: return("MX"); break;
    case MZ_PY: return("PY"); break;
    case MZ_MY: return("MY"); break;
    case MZ_PZ: return("PZ"); break;
    case MZ_MZ: return("MZ"); break;
    case MZ_S: return("S"); break;
    case MZ_G: return("G"); break;
  }
 return("?");
}

static void setup_model(void)
{
 typedef struct {
	   unsigned char x;
	   unsigned char y;
	   unsigned char z;
	   MZBITS bit;
	   } WALL;
 WALL walls[MZWALLS];
 CELLNO cells[MZX][MZY][MZZ];
 int x;
 int y;
 int z;
 int nw;
 int zc;
 int wx;
 WALL w;
 int c;
 int openit;
 MZBITS obit;

 int done(void)
  { int i;
    int j;
    int k;
    if (zc > 0) return(0);
    for (i=MZX-1;i>=0;i--) for (j=MZY-1;j>=0;j--) for (k=MZZ-1;k>=0;k--) if (cells[i][j][k] != 1) return(0);
    return(1);
  }

 void renumber(CELLNO a, CELLNO b)
  { int i;
    int j;
    int k;
    if (b < a)
     { CELLNO t;
       t = a;
       a = b;
       b = t;
     }
    for (i=MZX-1;i>=0;i--) for (j=MZY-1;j>=0;j--) for (k=MZZ-1;k>=0;k--) if (cells[i][j][k] == b) cells[i][j][k] = a;
  }

 srandom(time(0));
 nw = 0;
 for (x=MZX-1;x>=0;x--) for (y=MZY-1;y>=0;y--) for (z=MZZ-1;z>=0;z--)
  { cells[x][y][z] = 0;
    if (x > 0) walls[nw++] = (WALL){.x=x,.y=y,.z=z,.bit=MZ_MX};
    if (y > 0) walls[nw++] = (WALL){.x=x,.y=y,.z=z,.bit=MZ_MY};
    if (z > 0) walls[nw++] = (WALL){.x=x,.y=y,.z=z,.bit=MZ_MZ};
  }
 if (nw != MZWALLS) abort();
 zc = MZX * MZY * MZZ;
 c = 1;
 while (! done())
  { wx = random() % nw;
    w = walls[wx];
    nw --;
    if (wx < nw) walls[wx] = walls[nw];
    switch (w.bit)
     { case MZ_MX: x = w.x - 1; y = w.y; z = w.z; obit = MZ_PX; break;
       case MZ_MY: x = w.x; y = w.y - 1; z = w.z; obit = MZ_PY; break;
       case MZ_MZ: x = w.x; y = w.y; z = w.z - 1; obit = MZ_PZ; break;
       default: abort(); break;
     }
    openit = 1;
    if (cells[w.x][w.y][w.z])
     { if (cells[x][y][z])
	{ if (cells[x][y][z] == cells[w.x][w.y][w.z])
	   { openit = 0;
	   }
	  else
	   { renumber(cells[w.x][w.y][w.z],cells[x][y][z]);
	   }
	}
       else
	{ cells[x][y][z] = cells[w.x][w.y][w.z];
	  zc --;
	}
     }
    else
     { if (cells[x][y][z])
	{ cells[w.x][w.y][w.z] = cells[x][y][z];
	  zc --;
	}
       else
	{ cells[x][y][z] = c;
	  cells[w.x][w.y][w.z] = c;
	  c ++;
	  zc -= 2;
	}
     }
    if (openit)
     { maze[w.x][w.y][w.z] |= w.bit;
       maze[x][y][z] |= obit;
     }
  }
 maze[0][0][0] |= MZ_S;
 maze[MZX-1][MZY-1][MZZ-1] |= MZ_G;
  { int walk(int x, int y, int z)
     { if (! cells[x][y][z])
	{ cells[x][y][z] = 1;
	  if ( (maze[x][y][z] & MZ_G) ||
	       ((maze[x][y][z] & MZ_PX) && walk(x+1,y,z)) ||
	       ((maze[x][y][z] & MZ_MX) && walk(x-1,y,z)) ||
	       ((maze[x][y][z] & MZ_PY) && walk(x,y+1,z)) ||
	       ((maze[x][y][z] & MZ_MY) && walk(x,y-1,z)) ||
	       ((maze[x][y][z] & MZ_PZ) && walk(x,y,z+1)) ||
	       ((maze[x][y][z] & MZ_MZ) && walk(x,y,z-1)) )
	   { cells[x][y][z] = 2;
	     return(1);
	   }
	}
       return(0);
     }
    for (x=MZX-1;x>=0;x--) for (y=MZY-1;y>=0;y--) for (z=MZZ-1;z>=0;z--) cells[x][y][z] = 0;
    walk(0,0,0);
  }
 for (x=MZX-1;x>=0;x--) for (y=MZY-1;y>=0;y--) for (z=MZZ-1;z>=0;z--)
  { if ( ( (x > 0) &&
	   ( ( (maze[x-1][y][z] & MZ_PX) &&
	       !(maze[x][y][z] & MZ_MX) ) ||
	     ( !(maze[x-1][y][z] & MZ_PX) &&
	       (maze[x][y][z] & MZ_MX) ) ) ) ||
	 ( (y > 0) &&
	   ( ( (maze[x][y-1][z] & MZ_PY) &&
	       !(maze[x][y][z] & MZ_MY) ) ||
	     ( !(maze[x][y-1][z] & MZ_PY) &&
	       (maze[x][y][z] & MZ_MY) ) ) ) ||
	 ( (z > 0) &&
	   ( ( (maze[x][y][z-1] & MZ_PZ) &&
	       !(maze[x][y][z] & MZ_MZ) ) ||
	     ( !(maze[x][y][z-1] & MZ_PZ) &&
	       (maze[x][y][z] & MZ_MZ) ) ) ) ) abort();
  }
 for (z=MZZ-1;z>=0;z--)
  { printf("\n");
    for (x=MZX;x>0;x--) printf("+---");
    printf("+\n");
    for (y=MZY-1;y>=0;y--)
     { for (x=0;x<MZX;x++)
	{ putchar( (maze[x][y][z]&MZ_MX) ? ' ' : '|' );
	  putchar( (maze[x][y][z]&MZ_MZ) ? 'v' : ' ' );
	  switch (maze[x][y][z] & (MZ_S|MZ_G))
	   { case 0: putchar((cells[x][y][z]==2)?'*':' '); break;
	     case MZ_S: putchar('s'); break;
	     case MZ_G: putchar('g'); break;
	     case MZ_S|MZ_G: putchar('*'); break;
	   }
	  putchar( (maze[x][y][z]&MZ_PZ) ? '^' : ' ' );
	}
       printf("|\n");
       for (x=0;x<MZX;x++)
	{ printf("+%s",(maze[x][y][z]&MZ_MY)?"   ":"---");
	}
       printf("+\n");
     }
  }
}

static void draw_box(XYZI p0, XYZI p1)
{
 glBegin(GL_QUAD_STRIP);
 glVertex3d(p0.x,p0.y,p0.z);
 glVertex3d(p0.x,p0.y,p1.z);
 glVertex3d(p1.x,p0.y,p0.z);
 glVertex3d(p1.x,p0.y,p1.z);
 glVertex3d(p1.x,p1.y,p0.z);
 glVertex3d(p1.x,p1.y,p1.z);
 glVertex3d(p0.x,p1.y,p0.z);
 glVertex3d(p0.x,p1.y,p1.z);
 glVertex3d(p0.x,p0.y,p0.z);
 glVertex3d(p0.x,p0.y,p1.z);
 glEnd();
 glBegin(GL_QUADS);
 glVertex3d(p0.x,p0.y,p0.z);
 glVertex3d(p1.x,p0.y,p0.z);
 glVertex3d(p1.x,p1.y,p0.z);
 glVertex3d(p0.x,p1.y,p0.z);
 glVertex3d(p0.x,p0.y,p1.z);
 glVertex3d(p0.x,p1.y,p1.z);
 glVertex3d(p1.x,p1.y,p1.z);
 glVertex3d(p1.x,p0.y,p1.z);
 glEnd();
}

/*
 * The way GL transformations work:
 *
 * If the current matrix is C and the coordinates presented to (eg)
 *  glVertex3d are V, then the transformed point P is
 *
 *	P = C V
 *
 *  or
 *
 *	[ P(0) ] = [ C( 0) C( 4) C( 8) C(12) ] [ V(0) ]
 *	[ P(1) ] = [ C( 1) C( 5) C( 9) C(13) ] [ V(1) ]
 *	[ P(2) ] = [ C( 2) C( 6) C(10) C(14) ] [ V(2) ]
 *	[ P(3) ] = [ C( 3) C( 7) C(11) C(15) ] [ V(3) ]
 *
 *  Calling glMultMatrix(M) does C = C M, resulting in
 *
 *	[ P(0) ] = [ C( 0) C( 4) C( 8) C(12) ] [ M( 0) M( 4) M( 8) M(12) ] [ V(0) ]
 *	[ P(1) ] = [ C( 1) C( 5) C( 9) C(13) ] [ M( 1) M( 5) M( 9) M(13) ] [ V(1) ]
 *	[ P(2) ] = [ C( 2) C( 6) C(10) C(14) ] [ M( 2) M( 6) M(10) M(14) ] [ V(2) ]
 *	[ P(3) ] = [ C( 3) C( 7) C(11) C(15) ] [ M( 3) M( 7) M(11) M(15) ] [ V(3) ]
 *
 *  Since we are transorming a world-coordinate V into an
 *  eye-coordinate P, the values we need for M are wx/wy/wz.
 */
static void drawstuff(void)
{
 GLdouble m[16];

 if (dbg)
  { printf("\n");
    printf("wx = (%g,%g,%g)\n",wx.x,wx.y,wx.z);
    printf("wy = (%g,%g,%g)\n",wy.x,wy.y,wy.z);
    printf("wz = (%g,%g,%g)\n",wz.x,wz.y,wz.z);
    printf("ploc = (%g,%g,%g)\n",ploc.x,ploc.y,ploc.z);
    if (evalid)
     { printf("ex = (%g,%g,%g)\n",ex.x,ex.y,ex.z);
       printf("ey = (%g,%g,%g)\n",ey.x,ey.y,ey.z);
       printf("ez = (%g,%g,%g)\n",ez.x,ez.y,ez.z);
     }
    dbg = 0;
  }
 m[0] = wx.x;
 m[1] = wx.y;
 m[2] = wx.z;
 m[3] = 0;
 m[4] = wy.x;
 m[5] = wy.y;
 m[6] = wy.z;
 m[7] = 0;
 m[8] = wz.x;
 m[9] = wz.y;
 m[10] = wz.z;
 m[11] = 0;
 m[12] = 0;
 m[13] = 0;
 m[14] = 0;
 m[15] = 1;
 glMultMatrixd(&m[0]);
 glTranslated(-ploc.x,-ploc.y,-ploc.z);
 glCallList(mazelist);
 /* goal marker */
 if (now.tv_usec >= 500000)
  { glColor3f(.333,0,.333);
  }
 else
  { glColor3f(1,1,.333);
  }
 draw_box( (XYZI){mzg.x+5,mzg.y+5,mzg.z+5},
	   (XYZI){mzg.x+6,mzg.y+6,mzg.z+6} );
}

static void render(void)
{
 glViewport(0,0,WINX,WINY);
 glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);
 glLoadIdentity();
 glViewport(0,0,WINX,WINY);
 drawstuff();
 glXSwapBuffers(disp,win);
 glXWaitGL();
 glXWaitX();
 while (peq > 0)
  { XEvent e;
    XWindowEvent(disp,pwin,PropertyChangeMask,&e);
    peq --;
  }
 XChangeProperty(disp,pwin,XA_STRING,XA_STRING,8,PropModeAppend,"",0);
 peq ++;
}

static void setup_ticks(void)
{
 gettimeofday(&nexttick,0);
 frameus = 10000;
 ticks = 0;
}

static void rotate_world(double a, XYZ axis)
{
 wx = xyzunit(xyzrotate(wx,a,axis));
 wy = xyzunit(subtract_component(xyzrotate(wy,a,axis),wx));
 wz = xyzunit(subtract_component(subtract_component(xyzrotate(wz,a,axis),wx),wy));
 evalid = 0;
}

/*
 * We basically have to invert the matrix
 *
 *	[ rx.x ry.x rz.x ]
 *	[ rx.y ry.y rz.y ]
 *	[ rx.z ry.z rz.z ]
 *
 *  Fortunately, because it's a rotation matrix, it's about as far from
 *  singular as can be; its determinant is theoretically exactly 1.
 *
 * The closed-form inverse of
 *
 *	[ A B C ]
 *	[ D E F ]
 *	[ G H I ]
 *
 *  is
 *
 *	[ EI-FH CH-BI BF-CE ]   /
 *	[ FG-DI AI-CG CD-AF ]  /  AEI+BFG+CDH-AFH-BDI-CEG
 *	[ DH-EG BG-AH AE-BD ] /
 *
 *  We save some multiplications by writing the determinant as
 *  A(EI-FH)+B(FG-DI)+C(DH-EG), for 9 multiplies and 5 adds, versus the
 *  above, which is 12 multiplies and 5 adds.
 */
static void invert_rotations(XYZ rx, XYZ ry, XYZ rz, XYZ *ix, XYZ *iy, XYZ *iz)
{
 double det;

 det = (rx.x * ((ry.y * rz.z) - (rz.y * ry.z))) +
       (ry.x * ((rz.y * rx.z) - (rx.y * rz.z))) +
       (rz.x * ((rx.y * ry.z) - (ry.y * rx.z)));
 *ix = (XYZ) { ((ry.y * rz.z) - (rz.y * ry.z)) / det,
	       ((rz.y * rx.z) - (rx.y * rz.z)) / det,
	       ((rx.y * ry.z) - (ry.y * rx.z)) / det };
 *iy = (XYZ) { ((rz.x * ry.z) - (ry.x * rz.z)) / det,
	       ((rx.x * rz.z) - (rz.x * rx.z)) / det,
	       ((ry.x * rx.z) - (rx.x * ry.z)) / det };
 *iz = (XYZ) { ((ry.x * rz.y) - (rz.x * ry.y)) / det,
	       ((rz.x * rx.y) - (rx.x * rz.y)) / det,
	       ((rx.x * ry.y) - (ry.x * rx.y)) / det };
}

static void ensure_e(void)
{
 if (evalid) return;
 invert_rotations(wx,wy,wz,&ex,&ey,&ez);
 evalid = 1;
}

static void moveby(XYZ dir, double s)
{
 XYZ nploc;
 int x;
 int y;
 int z;
 unsigned char bits;
 double px;
 double py;
 double d;

 nploc = xyzadd(ploc,xyzscale(dir,s*.1));
 x = (nploc.x - .5) / 10;
 y = (nploc.y - .5) / 10;
 z = (nploc.z - .5) / 10;
 if (x < 0) x = 0; else if (x >= MZX) x = MZX - 1;
 if (y < 0) y = 0; else if (y >= MZY) y = MZY - 1;
 if (z < 0) z = 0; else if (z >= MZZ) z = MZZ - 1;
 bits = maze[x][y][z];
 x *= 10;
 y *= 10;
 z *= 10;
 if (!(bits & MZ_PX) && (nploc.x > x+9)) nploc.x = x + 9;
 if (!(bits & MZ_MX) && (nploc.x < x+2)) nploc.x = x + 2;
 if (!(bits & MZ_PY) && (nploc.y > y+9)) nploc.y = y + 9;
 if (!(bits & MZ_MY) && (nploc.y < y+2)) nploc.y = y + 2;
 if (!(bits & MZ_PZ) && (nploc.z > z+9)) nploc.z = z + 9;
 if (!(bits & MZ_MZ) && (nploc.z < z+2)) nploc.z = z + 2;
#if 0
 if (nploc.x < x+5) px = x + .5; else px = x + 10.5;
 if (nploc.y < y+5) py = y + .5; else py = y + 10.5;
 if (nploc.z < z+5) pz = z + .5; else pz = z + 10.5;
 if ((fabs(nploc.x-px) <= 1.5) && (fabs(nploc.y-py) <= 1.5))
  { if (fabs(nploc.x-px) <= .5)
     { if ((nploc.y > py) && (nploc.y < py+1.5)) nploc.y = py + 1.5;
       else if ((nploc.y < py) && (nploc.y > py-1.5)) nploc.y = py - 1.5;
     }
    else if (fabs(nploc.y-py) <= .5)
     { if ((nploc.x > px) && (nploc.x < px+1.5)) nploc.x = px + 1.5;
       else if ((nploc.x < px) && (nploc.x > px-1.5)) nploc.x = px - 1.5;
     }
    else
     { if (nploc.x < px) px -= .5; else px += .5;
       if (nploc.y < py) py -= .5; else py += .5;
       d = hypot(px-nploc.x,py-nploc.y);
       if (d < 1)
	{ nploc.x = px - ((px - nploc.x) / d);
	  nploc.y = py - ((py - nploc.y) / d);
	}
     }
  }
#else
 d=0;px=0;py=0;
#endif
 ploc = nploc;
}

static void motion(void)
{
 double f;

 if (kbstate & KBS_SHIFT) f = 25; else if (kbstate & KBS_CTRL) f = 1; else f = 5;
 f *= .3;
 switch (kbstate & (KBS_ML|KBS_MR))
  { case KBS_ML:
       ensure_e();
       moveby(ex,-f);
       break;
    case KBS_MR:
       ensure_e();
       moveby(ex,f);
       break;
  }
 switch (kbstate & (KBS_MU|KBS_MD))
  { case KBS_MU:
       ensure_e();
       moveby(ey,f);
       break;
    case KBS_MD:
       ensure_e();
       moveby(ey,-f);
       break;
  }
 switch (kbstate & (KBS_MF|KBS_MB))
  { case KBS_MF:
       ensure_e();
       moveby(ez,-f);
       break;
    case KBS_MB:
       ensure_e();
       moveby(ez,f);
       break;
  }
 switch (kbstate & (KBS_RL|KBS_RR))
  { case KBS_RL:
       rotate_world(-f,(XYZ){0,1,0});
       break;
    case KBS_RR:
       rotate_world(f,(XYZ){0,1,0});
       break;
  }
 switch (kbstate & (KBS_RU|KBS_RD))
  { case KBS_RU:
       rotate_world(-f,(XYZ){1,0,0});
       break;
    case KBS_RD:
       rotate_world(f,(XYZ){1,0,0});
       break;
  }
 switch (kbstate & (KBS_RCW|KBS_RCCW))
  { case KBS_RCW:
       rotate_world(-f,(XYZ){0,0,1});
       break;
    case KBS_RCCW:
       rotate_world(f,(XYZ){0,0,1});
       break;
  }
}

static void keystroke(XKeyEvent *ev, char updn)
{
 KeySym ks;
 unsigned int bit;

 ks = XLookupKeysym(ev,0);
 bit = 0;
 switch (ks)
  { case XK_w: case XK_W: bit = KBS_MU;   break;
    case XK_s: case XK_S: bit = KBS_MD;   break;
    case XK_a: case XK_A: bit = KBS_ML;   break;
    case XK_d: case XK_D: bit = KBS_MR;   break;
    case XK_r: case XK_R: bit = KBS_MF;   break;
    case XK_f: case XK_F: bit = KBS_MB;   break;
    case XK_i: case XK_I: bit = KBS_RU;   break;
    case XK_k: case XK_K: bit = KBS_RD;   break;
    case XK_j: case XK_J: bit = KBS_RL;   break;
    case XK_l: case XK_L: bit = KBS_RR;   break;
    case XK_u: case XK_U: bit = KBS_RCCW; break;
    case XK_o: case XK_O: bit = KBS_RCW;  break;
    case XK_Shift_L:
       bit = KBS_LSHF;
       break;
    case XK_Shift_R:
       bit = KBS_RSHF;
       break;
    case XK_Control_L:
       bit = KBS_LCTL;
       break;
    case XK_Control_R:
       bit = KBS_RCTL;
       break;
    case XK_x: case XK_X:
       if (updn == 'd') swapped = ! swapped;
       break;
    case XK_q: case XK_Q:
       if ((updn == 'u') && (kbstate & KBS_SHIFT)) exit(0);
       break;
    case XK_1:
       if (updn == 'd') dbg = 1;
       break;
  }
 switch (updn)
  { case 'u':
       kbstate &= ~bit;
       break;
    case 'd':
       kbstate |= bit;
       break;
    default:
       abort();
       break;
  }
}

static void events(void)
{
 XEvent ev;

 while (XPending(disp))
  { XNextEvent(disp,&ev);
    switch (ev.type)
     { default:
	  /* XXX ignore */
	  break;
       case KeyPress:
	  /* XKeyPressedEvent - XKeyEvent - xkey */
	  keystroke(&ev.xkey,'d');
	  break;
       case KeyRelease:
	  /* XKeyReleasedEvent - XKeyEvent - xkey */
	  keystroke(&ev.xkey,'u');
	  break;
       case MappingNotify:
	  /* XMappingEvent - xmapping */
	  XRefreshKeyboardMapping(&ev.xmapping);
	  break;
       case PropertyNotify:
	  /* XPropertyEvent - xproperty */
	  if (ev.xproperty.window == pwin) peq --;
	  break;
     }
  }
}

static void await(void)
{
 int ms;

 nexttick.tv_usec += frameus;
 if (nexttick.tv_usec >= 1000000)
  { nexttick.tv_usec -= 1000000;
    nexttick.tv_sec ++;
  }
 gettimeofday(&now,0);
 if ( (now.tv_sec > nexttick.tv_sec) ||
      ( (now.tv_sec == nexttick.tv_sec) &&
	(now.tv_usec >= nexttick.tv_usec) ) )
  { frameus += 10000;
    nexttick = now;
    return;
  }
 ms = ((nexttick.tv_sec - now.tv_sec) * 1000) + 1 +
      (nexttick.tv_usec / 1000) - (now.tv_usec / 1000);
 if (ms < 20)
  { frameus += 10000;
  }
 else
  { frameus -= 10;
  }
 if (ms < 1) ms = 1;
 poll(0,0,ms);
 gettimeofday(&now,0);
}

static void tick(void)
{
 motion();
 render();
 events();
 await();
 ticks ++;
}

static void setup_view(void)
{
 ploc = (XYZ){3,3,3};
 ez = xyzunit((XYZ){-1,-1,0});
 ey = xyzunit(subtract_component((XYZ){0,0,1},ez));
 ex = xyzcross(ey,ez);
 invert_rotations(ex,ey,ez,&wx,&wy,&wz);
 evalid = 1;
 swapped = 0;
}

static void setup_input(void)
{
 XGrabKeyboard(disp,win,False,GrabModeAsync,GrabModeAsync,CurrentTime);
}

static void draw_wall(XYZI p0, XYZI u, XYZI r)
{
 glTexCoord2d(0,0);
 glVertex3d(p0.x,p0.y,p0.z);
 glTexCoord2d(0,1);
 glVertex3d(p0.x+u.x,p0.y+u.y,p0.z+u.z);
 glTexCoord2d(1,1);
 glVertex3d(p0.x+u.x+r.x,p0.y+u.y+r.y,p0.z+u.z+r.z);
 glTexCoord2d(1,0);
 glVertex3d(p0.x+r.x,p0.y+r.y,p0.z+r.z);
}

static void setup_lists(void)
{
 int x;
 int y;
 int z;

 mazelist = glGenLists(1);
 glNewList(mazelist,GL_COMPILE);
 glPolygonOffset(0,1);
 mzs.x = -1;
 mzg.x = -1;
 /* walls */
 glEnable(GL_TEXTURE_2D);
 glBindTexture(GL_TEXTURE_2D,tex);
 glBegin(GL_QUADS);
 for (x=MZX-1;x>=0;x--) for (y=MZY-1;y>=0;y--) for (z=MZZ-1;z>=0;z--)
  { if (! (maze[x][y][z] & MZ_PX))
     { draw_wall( (XYZI){(x+1)*10,(y*10)+1,(z*10)+1},
		  (XYZI){0,9,0},
		  (XYZI){0,0,9} );
     }
    if (! (maze[x][y][z] & MZ_MX))
     { draw_wall( (XYZI){(x*10)+1,(y*10)+1,(z*10)+1},
		  (XYZI){0,0,9},
		  (XYZI){0,9,0} );
     }
    if (! (maze[x][y][z] & MZ_PY))
     { draw_wall( (XYZI){(x*10)+1,(y+1)*10,(z*10)+1},
		  (XYZI){0,0,9},
		  (XYZI){9,0,0} );
     }
    if (! (maze[x][y][z] & MZ_MY))
     { draw_wall( (XYZI){(x*10)+1,(y*10)+1,(z*10)+1},
		  (XYZI){9,0,0},
		  (XYZI){0,0,9} );
     }
    if (! (maze[x][y][z] & MZ_PZ))
     { draw_wall( (XYZI){(x*10)+1,(y*10)+1,(z+1)*10},
		  (XYZI){9,0,0},
		  (XYZI){0,9,0} );
     }
    if (! (maze[x][y][z] & MZ_MZ))
     { draw_wall( (XYZI){(x*10)+1,(y*10)+1,(z*10)+1},
		  (XYZI){0,9,0},
		  (XYZI){9,0,0} );
     }
    if (maze[x][y][z] & MZ_S) mzs = (XYZI){x*10,y*10,z*10};
    if (maze[x][y][z] & MZ_G) mzg = (XYZI){x*10,y*10,z*10};
  }
 glEnd();
 glDisable(GL_TEXTURE_2D);
 /* start marker */
 if (mzs.x < 0) abort();
 glColor3f(.333,.333,.667);
 draw_box( (XYZI){mzs.x+5,mzs.y+5,mzs.z+5},
	   (XYZI){mzs.x+6,mzs.y+6,mzs.z+6} );
 /* goal marker is done dynamically, so it can flash */
 if (mzg.x < 0) abort();
 /* "structural" skeleton */
 for (x=MZX;x>=0;x--) for (y=MZY;y>=0;y--) for (z=MZZ;z>=0;z--)
  { glColor3f(.5,.5,.5);
    draw_box( (XYZI){x*10,y*10,z*10},
	      (XYZI){(x*10)+1,(y*10)+1,(z*10)+1} );
    if (x < MZX)
     { glColor3f(.75,.3,.3);
       draw_box( (XYZI){(x*10)+1,y*10,z*10},
		 (XYZI){(x+1)*10,(y*10)+1,(z*10)+1} );
     }
    if (y < MZY)
     { glColor3f(.3,.75,.3);
       draw_box( (XYZI){x*10,(y*10)+1,z*10},
		 (XYZI){(x*10)+1,(y+1)*10,(z*10)+1} );
     }
    if (z < MZZ)
     { glColor3f(.3,.3,.75);
       draw_box( (XYZI){x*10,y*10,(z*10)+1},
		 (XYZI){(x*10)+1,(y*10)+1,(z+1)*10} );
     }
  }
 glEndList();
}

int main(void);
int main(void)
{
 open_display();
 find_visual();
 setup_X();
 setup_context();
 setup_bitmaps();
 create_window();
 setup_gl();
 setup_input();
 setup_model();
 setup_view();
 setup_ticks();
 setup_lists();
 while (1) tick();
}