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

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

#include <GL/glx.h>

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

#define TX_X 64
#define TX_Y 64

#define MSZ_X 2
#define MSZ_Y 2
#define MSZ_Z 2

#define WINX 400
#define WINY 400

extern const char *__progname;

#define UNUSED __attribute__((__unused__))

typedef unsigned char DIRBITS;
#define DB_PX 0x01
#define DB_PY 0x02
#define DB_PZ 0x04
#define DB_MX 0x08
#define DB_MY 0x10
#define DB_MZ 0x20
#define NDIR 6

typedef struct cell CELL;
typedef struct cbl CBL;
typedef struct mpt MPT;
typedef struct mln MLN;
typedef struct mqd MQD;

struct cell {
  XYZI p;
  DIRBITS links;
  unsigned char f;
#define CF_M  0x01
  } ;

struct cbl {
  CELL *from;
  DIRBITS dir;
  } ;

struct mpt {
  int x;
  int y;
  int z;
  } ;

struct mln {
  int cx;
  int p1;
  int p2;
  } ;

struct mqd {
  int p[4];
  int l[6];
  } ;

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 XColor bgcolour;
static XColor fgcolour;
static GC gc;
static struct timeval starttime;
static struct timeval nexttick;
static double t;
static CELL maze[MSZ_X][MSZ_Y][MSZ_Z];
#define MZ_NPT ((MSZ_X+1)*(MSZ_Y+1)*(MSZ_Z+1))
#define MZ_NLN ( ((MSZ_X+1)*(MSZ_Y+1)*(MSZ_Z))+\
		 ((MSZ_X+1)*(MSZ_Y)*(MSZ_Z+1))+\
		 ((MSZ_X)*(MSZ_Y+1)*(MSZ_Z+1))+\
		 (2*MZ_NQD) )
#define MZ_NQD ( ((MSZ_X+1)*(MSZ_Y)*(MSZ_Z))+\
		 ((MSZ_X)*(MSZ_Y+1)*(MSZ_Z))+\
		 ((MSZ_X)*(MSZ_Y)*(MSZ_Z+1)) )
static MPT mpt[MZ_NPT];
static int mpt_n;
static MLN mln[MZ_NLN];
static int mln_n;
static MQD mqd[MZ_NQD];
static int mqd_n;
static int ncbl;
static int acbl;
static CBL *cbl;
static DIRBITS dirs[NDIR] = { DB_PX, DB_MX, DB_PY, DB_MY, DB_PZ, DB_MZ };
static float walltex_bits[TX_X+2][TX_Y+2][3];
static unsigned int walltex;
/*
 * 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 coorindates is stored in ploc.  Like wx/wy/wz,
 *  this is always valid.
 */
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_L    0x00000001
#define KBS_R    0x00000002
#define KBS_U    0x00000004
#define KBS_D    0x00000008
#define KBS_CW   0x00000010
#define KBS_CCW  0x00000020
#define KBS_LSHF 0x00000040
#define KBS_RSHF 0x00000080
#define KBS_LCTL 0x00000100
#define KBS_RCTL 0x00000200
#define KBS_SHIFT (KBS_LSHF|KBS_RSHF)
#define KBS_CTRL (KBS_LCTL|KBS_RCTL)
static int dbg;
static int swapped;

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 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*2,WINY,0,depth,InputOutput,vi->visual,attrmask,&attr);
 XMapRaised(disp,win);
}

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(.4,.4,.4,0);
 glMatrixMode(GL_PROJECTION);
 glLoadIdentity();
 glFrustum(-.03,.03,-.03,.03,.1,50);
 glMatrixMode(GL_MODELVIEW);
 glEnable(GL_DEPTH_TEST);
 glEnable(GL_POLYGON_OFFSET_FILL);
 glPixelStorei(GL_UNPACK_ALIGNMENT,1);
 glGenTextures(1,&walltex);
 glBindTexture(GL_TEXTURE_2D,walltex);
 glTexEnvi(GL_TEXTURE_ENV,GL_TEXTURE_ENV_MODE,GL_REPLACE);
 glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MIN_FILTER,GL_LINEAR);
 glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_LINEAR);
 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_RGB,TX_X+2,TX_Y+2,1,GL_RGB,GL_FLOAT,&walltex_bits[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]);
 glEnable(GL_POLYGON_OFFSET_FILL);
 kbstate = 0;
}

static int model_pt(int x, int y, int z)
{
 int i;
 MPT *p;

 for (i=mpt_n-1;i>=0;i--)
  { p = &mpt[i];
    if ((p->x == x) && (p->y == y) && (p->z == z)) return(i);
  }
 if (mpt_n >= MZ_NPT) abort();
 p = &mpt[mpt_n];
 p->x = x;
 p->y = y;
 p->z = z;
 return(mpt_n++);
}

static int model_ln(int p1, int p2, int cx)
{
 int i;
 MLN *l;

 if (p1 > p2)
  { i = p1;
    p1 = p2;
    p2 = i;
  }
 for (i=mln_n-1;i>=0;i--)
  { l = &mln[i];
    if ((l->p1 == p1) && (l->p2 == p2))
     { if (l->cx != cx) abort();
       return(i);
     }
  }
 if (mln_n >= MZ_NLN) abort();
 l = &mln[mln_n];
 l->cx = cx;
 l->p1 = p1;
 l->p2 = p2;
 return(mln_n++);
}

static void model_quad(
	int x0, int y0, int z0,
	int dx1, int dy1, int dz1,
	int dx2, int dy2, int dz2 )
{
 MQD *q;

 q = &mqd[mqd_n++];
 q->p[0] = model_pt(x0,y0,z0);
 q->p[1] = model_pt(x0+dx1,y0+dy1,z0+dz1);
 q->p[2] = model_pt(x0+dx1+dx2,y0+dy1+dy2,z0+dz1+dz2);
 q->p[3] = model_pt(x0+dx2,y0+dy2,z0+dz2);
 q->l[0] = model_ln(q->p[0],q->p[1],0);
 q->l[1] = model_ln(q->p[1],q->p[2],0);
 q->l[2] = model_ln(q->p[2],q->p[3],0);
 q->l[3] = model_ln(q->p[3],q->p[0],0);
 q->l[4] = model_ln(q->p[0],q->p[2],1);
 q->l[5] = model_ln(q->p[1],q->p[3],1);
}

static void setup_model(void)
{
 int x;
 int y;
 int z;
 CELL *c;
 int dx;

 mpt_n = 0;
 mln_n = 0;
 mqd_n = 0;
 for (x=MSZ_X-1;x>=0;x--) for (y=MSZ_Y-1;y>=0;y--) for (z=MSZ_Z-1;z>=0;z--)
  { c = &maze[x][y][z];
    for (dx=NDIR-1;dx>=0;dx--)
     { if (! (c->links & DB_PX)) model_quad(x+1,y,z, 0,1,0, 0,0,1);
       if (! (c->links & DB_PY)) model_quad(x,y+1,z, 1,0,0, 0,0,1);
       if (! (c->links & DB_PZ)) model_quad(x,y,z+1, 1,0,0, 0,1,0);
       if (! (c->links & DB_MX)) model_quad(x,y,z, 0,1,0, 0,0,1);
       if (! (c->links & DB_MY)) model_quad(x,y,z, 1,0,0, 0,0,1);
       if (! (c->links & DB_MZ)) model_quad(x,y,z, 1,0,0, 0,1,0);
     }
  }
}

#if 0
static void xyzcall(XYZ p, void (*fn)(double, double, double))
{
 (*fn)(p.x,p.y,p.z);
}
#endif

#if 0
static void xyzvertex(XYZ p)
{
 xyzcall(p,&glVertex3d);
}
#endif

#if 0
static void quad(XYZ c, XYZ d1, XYZ d2)
{
 glTexCoord2d(0,0);
 xyzvertex(c);
 glTexCoord2d(1,0);
 xyzvertex(xyzadd(c,d1));
 glTexCoord2d(1,1);
 xyzvertex(xyzadd(c,xyzadd(d1,d2)));
 glTexCoord2d(0,1);
 xyzvertex(xyzadd(c,d2));
}
#endif

static void rotate_render(void)
{
 GLdouble m[16];

 if (dbg)
  { 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);
  }
 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]);
}

static void drawstuff(void)
{
 int i;

 rotate_render();
 glTranslated(-ploc.x,-ploc.y,-ploc.z);
 glBegin(GL_LINES);
 for (i=mln_n-1;i>=0;i--)
  { if (mln[i].cx)
     { glColor3f(1,0,0);
     }
    else
     { glColor3f(0,1,1);
     }
    glVertex3i(mpt[mln[i].p1].x,mpt[mln[i].p1].y,mpt[mln[i].p1].z);
    glVertex3i(mpt[mln[i].p2].x,mpt[mln[i].p2].y,mpt[mln[i].p2].z);
  }
 glEnd();
}

static void render(void)
{
 glViewport(0,0,WINX*2,WINY);
 glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);
 glLoadIdentity();
 glViewport(swapped?WINX:0,0,WINX,WINY);
 glRotatef(-5,0,1,0);
 glPushMatrix();
 drawstuff();
 glPopMatrix();
 glViewport(swapped?0:WINX,0,WINX,WINY);
 glRotatef(5,0,1,0);
 glPushMatrix();
 drawstuff();
 glPopMatrix();
 glXSwapBuffers(disp,win);
 glXWaitGL();
 XSync(disp,False);
}

static void setup_ticks(void)
{
 gettimeofday(&starttime,0);
 nexttick = starttime;
}

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

static void motion(void)
{
 double f;
 static double lastt = 0;

 if (lastt == 0)
  { lastt = t;
    return;
  }
 if (kbstate & KBS_SHIFT) f = 25; else if (kbstate & KBS_CTRL) f = 1; else f = 5;
 f *= (t - lastt) * 3;
 lastt = t;
 switch (kbstate & (KBS_L|KBS_R))
  { case KBS_L:
       rotate_world(-f,(XYZ){0,1,0});
       break;
    case KBS_R:
       rotate_world(f,(XYZ){0,1,0});
       break;
  }
 switch (kbstate & (KBS_U|KBS_D))
  { case KBS_U:
       rotate_world(-f,(XYZ){1,0,0});
       break;
    case KBS_D:
       rotate_world(f,(XYZ){1,0,0});
       break;
  }
 switch (kbstate & (KBS_CW|KBS_CCW))
  { case KBS_CW:
       rotate_world(-f,(XYZ){0,0,1});
       break;
    case KBS_CCW:
       rotate_world(f,(XYZ){0,0,1});
       break;
  }
 ex=wx;ey=wy;ez=wz;
}

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

 ks = XLookupKeysym(ev,0);
 bit = 0;
 switch (ks)
  { case XK_h: case XK_H:
       bit = KBS_L;
       break;
    case XK_l: case XK_L:
       bit = KBS_R;
       break;
    case XK_k: case XK_K:
       bit = KBS_U;
       break;
    case XK_j: case XK_J:
       bit = KBS_D;
       break;
    case XK_y: case XK_Y:
       bit = KBS_CCW;
       break;
    case XK_u: case XK_U:
       bit = KBS_CW;
       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_d: case XK_D:
       if (updn == 'd') dbg = 1;
       break;
    case XK_q: case XK_Q:
       if ((updn == 'u') && (kbstate & KBS_SHIFT)) exit(0);
       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;
     }
  }
}

static void setcurtime(struct timeval tv)
{
 t = (tv.tv_sec - starttime.tv_sec) + (tv.tv_usec * 1e-6) - (starttime.tv_usec * 1e-6);
}

static void await(void)
{
 struct timeval now;
 int ms;

 nexttick.tv_usec += 100000;
 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) ) )
  { nexttick = now;
    setcurtime(now);
    return;
  }
 while (1)
  { gettimeofday(&now,0);
    if ( (now.tv_sec > nexttick.tv_sec) ||
	 ( (now.tv_sec == nexttick.tv_sec) &&
	   (now.tv_usec >= nexttick.tv_usec) ) )
     { setcurtime(now);
       return;
     }
    ms = ((nexttick.tv_sec - now.tv_sec) * 1000) + 1 +
	 (nexttick.tv_usec / 1000) - (now.tv_usec / 1000);
    if (ms < 1) ms = 1;
    poll(0,0,ms);
  }
}

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

static void setup_random(void)
{
 srandom(time(0));
}

static XYZI move_in_dir(XYZI l, DIRBITS dir)
{
 switch (dir)
  { case DB_PX: return((XYZI){l.x+1,l.y,l.z}); break;
    case DB_MX: return((XYZI){l.x-1,l.y,l.z}); break;
    case DB_PY: return((XYZI){l.x,l.y+1,l.z}); break;
    case DB_MY: return((XYZI){l.x,l.y-1,l.z}); break;
    case DB_PZ: return((XYZI){l.x,l.y,l.z+1}); break;
    case DB_MZ: return((XYZI){l.x,l.y,l.z-1}); break;
  }
 abort();
}

static DIRBITS dirrev(DIRBITS dir)
{
 switch (dir)
  { case DB_PX: return(DB_MX); break;
    case DB_MX: return(DB_PX); break;
    case DB_PY: return(DB_MY); break;
    case DB_MY: return(DB_PY); break;
    case DB_PZ: return(DB_MZ); break;
    case DB_MZ: return(DB_PZ); break;
  }
 abort();
}

static void setup_maze(void)
{
 int x;
 int y;
 int z;
 int i;
 CBL c;
 XYZI n;
 CELL *nc;

 void visit(CELL *c)
  { int j;
    if (c->f & CF_M) abort();
    c->f |= CF_M;
    if (acbl < ncbl+6)
     { acbl = ncbl + 6;
       cbl = realloc(cbl,acbl*sizeof(CBL));
     }
    for (j=NDIR-1;j>=0;j--) cbl[ncbl++] = (CBL){.from=c,.dir=dirs[j]};
  }

 for (x=MSZ_X-1;x>=0;x--) for (y=MSZ_Y-1;y>=0;y--) for (z=MSZ_Z-1;z>=0;z--)
  { maze[x][y][z].p.x = x;
    maze[x][y][z].p.y = y;
    maze[x][y][z].p.z = z;
    maze[x][y][z].links = 0;
    maze[x][y][z].f = 0;
  }
 ncbl = 0;
 acbl = 0;
 cbl = 0;
 visit(&maze[0][0][0]);
 while (ncbl > 0)
  { i = random() % ncbl;
    c = cbl[i];
    ncbl --;
    if (i != ncbl) cbl[i] = cbl[ncbl];
    n = move_in_dir(c.from->p,c.dir);
    if ( (n.x < 0) || (n.x >= MSZ_X) ||
	 (n.y < 0) || (n.y >= MSZ_Y) ||
	 (n.z < 0) || (n.z >= MSZ_Z) ) continue;
    nc = &maze[n.x][n.y][n.z];
    if (nc->f & CF_M) continue;
    c.from->links |= c.dir;
    nc->links |= dirrev(c.dir);
    visit(nc);
  }
}

static void setup_bitmaps(void)
{
 int x;
 int y;
 double dx;
 double dy;
 double d;
 double h;
 double s;
 double r;
 double g;
 double b;
 double junk;

 for (y=TX_Y+1;y>=0;y--)
  { dy = fabs(y-((TX_Y+1)*.5));
    for (x=TX_X+1;x>=0;x--)
     { dx = fabs(x-((TX_X+1)*.5));
       if (dy > dx)
	{ d = dy / ((TX_Y-1)*.5);
	}
       else
	{ d = dx / ((TX_X-1)*.5);
	}
       s = (d < 1) ? (1 - cos(2*M_PI*d)) / 2 : 0;
       h = modf(d*4,&junk) * 3;
       if (h < 1)
	{ r = 1 - h;
	  g = h;
	  b = 0;
	}
       else if (h < 2)
	{ r = 0;
	  g = 2 - h;
	  b = h - 1;
	}
       else
	{ r = h - 2;
	  g = 0;
	  b = 3 - h;
	}
       walltex_bits[y][x][0] = 1 - (s * (1 - r));
       walltex_bits[y][x][1] = 1 - (s * (1 - g));
       walltex_bits[y][x][2] = 1 - (s * (1 - b));
     }
  }
}

static void setup_view(void)
{
 wx = (XYZ){1,0,0};
 wy = (XYZ){0,1,0};
 wz = (XYZ){0,0,1};
 ploc = (XYZ){.25,.5,.75};
 evalid = 0;
 swapped = 0;
}

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

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