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

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

#include <GL/glx.h>

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

#define WINX 400
#define WINY 400
#define TEXSIZE 512

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 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 coorindates 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_RL   0x00000004
#define KBS_RR   0x00000008
#define KBS_MF   0x00000010
#define KBS_MB   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 int mzx = 8;
static int mzy = 8;
static int mzwalls;
static int mzcells;
typedef unsigned char MZBITS;
static MZBITS *maze;
#define Maze(x,y) maze[(x)+((y)*mzx)]
#define MZ_PX 0x01
#define MZ_MX 0x02
#define MZ_PY 0x04
#define MZ_MY 0x08
#define MZ_S  0x10
#define MZ_G  0x20
static unsigned int ticks;
static GLuint mazelist;
static int sx;
static int sy;
static int gx;
static int gy;

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 double blend(double, double, double)
	__attribute__((__const__));
static double blend(double v1, double a, double v2)
{
 return((a*v2)+((1-a)*v1));
}

static void setup_bitmaps(void)
{
 int x;
 int y;
 double fx;
 double fy;

 for (y=TEXSIZE+2-1;y>=0;y--)
  { fy = (y - 1) / (double)TEXSIZE;
    for (x=TEXSIZE+2-1;x>=0;x--)
     { fx = ((x - 1) * 3) / (double)TEXSIZE;
       if ((x == 0) || (x == TEXSIZE+2-1) || (y == 0) || (y == TEXSIZE+2-1))
	{ texture[y][x][0] = 127;
	  texture[y][x][1] = 127;
	  texture[y][x][2] = 127;
	  texture[y][x][3] = 255;
	}
       else
	{ texture[y][x][0] = clip(blend(127.5,fy,(fx<1)?fx*256:0),0,255);
	  texture[y][x][1] = clip(blend(127.5,fy,((fx>=1)&&(fx<2))?(fx-1)*256:0),0,255);
	  texture[y][x][2] = clip(blend(127.5,fy,(fx>=2)?(fx-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*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(0,0,0,0);
 glMatrixMode(GL_PROJECTION);
 glLoadIdentity();
 glFrustum(-.25,.25,-.125,.125,.25,(hypot(mzx,mzy)+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 void draw_wall(int x0, int y0, int dx, int dy)
{
 glTexCoord2d(1,0);
 glVertex3d(x0,y0,-1);
 glTexCoord2d(0,0);
 glVertex3d(x0+dx,y0+dy,-1);
 glTexCoord2d(0,1);
 glVertex3d(x0+dx,y0+dy,1);
 glTexCoord2d(1,1);
 glVertex3d(x0,y0,1);
}

/*
 * 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, sides */
 glBegin(GL_QUAD_STRIP);
 if (now.tv_usec >= 500000)
  { glColor3f(.333,0,.333);
  }
 else
  { glColor3f(1,1,.333);
  }
 glVertex3d(gx+4,gy+4,-1);
 glVertex3d(gx+4,gy+4,-.5);
 glVertex3d(gx+7,gy+4,-1);
 glVertex3d(gx+7,gy+4,-.5);
 glVertex3d(gx+7,gy+7,-1);
 glVertex3d(gx+7,gy+7,-.5);
 glVertex3d(gx+4,gy+7,-1);
 glVertex3d(gx+4,gy+7,-.5);
 glVertex3d(gx+4,gy+4,-1);
 glVertex3d(gx+4,gy+4,-.5);
 glEnd();
}

static void render(void)
{
 glViewport(0,0,WINX*2,WINY);
 glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);
 glLoadIdentity();
 glViewport(0,0,2*WINX,WINY);
 drawstuff();
 glXSwapBuffers(disp,win);
 glXWaitGL();
 glXWaitX();
}

static void setup_ticks(void)
{
 gettimeofday(&nexttick,0);
 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;
 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;
 if (x < 0) x = 0; else if (x >= mzx) x = mzx - 1;
 if (y < 0) y = 0; else if (y >= mzy) y = mzy - 1;
 bits = Maze(x,y);
 x *= 10;
 y *= 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 (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 ((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);
	}
     }
  }
 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_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;
  }
}

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_MF;
       break;
    case XK_s: case XK_S:
       bit = KBS_MB;
       break;
    case XK_a: case XK_A:
       bit = KBS_ML;
       break;
    case XK_d: case XK_D:
       bit = KBS_MR;
       break;
    case XK_u: case XK_U:
       bit = KBS_RL;
       break;
    case XK_i: case XK_I:
       bit = KBS_RR;
       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_p: case XK_P:
       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;
     }
  }
}

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){2,2,0};
 ey = (XYZ){0,0,1};
 ez = xyzunit((XYZ){-1,-1,0});
 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 setup_lists(void)
{
 int x;
 int y;

 mazelist = glGenLists(1);
 glNewList(mazelist,GL_COMPILE);
 glPolygonOffset(0,1);
 sx = -1;
 gx = -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--)
  { MZBITS b;
    b = Maze(x,y);
    if (! (b & MZ_PX)) draw_wall((x+1)*10,(y*10)+1,0,9);
    if (! (b & MZ_MX)) draw_wall((x*10)+1,(y+1)*10,0,-9);
    if (! (b & MZ_PY)) draw_wall((x+1)*10,(y+1)*10,-9,0);
    if (! (b & MZ_MY)) draw_wall((x*10)+1,(y*10)+1,9,0);
    if (b & MZ_S)
     { sx = x * 10;
       sy = y * 10;
     }
    if (b & MZ_G)
     { gx = x * 10;
       gy = y * 10;
     }
  }
 glEnd();
 glDisable(GL_TEXTURE_2D);
 glBegin(GL_QUADS);
 /* floor */
 glColor3f(.333,.333,.333);
 glVertex3d(0,0,-1);
 glVertex3d(0,(mzy*10)+1,-1);
 glVertex3d((mzx*10)+1,(mzy*10)+1,-1);
 glVertex3d((mzx*10)+1,0,-1);
 /* ceiling */
 glColor3f(.667,.667,.667);
 glVertex3d(0,0,1);
 glVertex3d((mzx*10)+1,0,1);
 glVertex3d((mzx*10)+1,(mzy*10)+1,1);
 glVertex3d(0,(mzy*10)+1,1);
 /* start marker */
 if (sx < 0) abort();
 glColor3f(.333,.333,.667);
 glVertex3d(sx+1,sy+1,-.99);
 glVertex3d(sx+1,sy+10,-.99);
 glVertex3d(sx+10,sy+10,-.99);
 glVertex3d(sx+10,sy+1,-.99);
 /* goal marker, top cover (sides are done dynamically - they flash) */
 if (gx < 0) abort();
 glColor3f(.333,1,.333);
 glVertex3d(gx+4,gy+4,-.5);
 glVertex3d(gx+4,gy+7,-.5);
 glVertex3d(gx+7,gy+7,-.5);
 glVertex3d(gx+7,gy+4,-.5);
 glEnd();
 /* "structural" posts */
 glColor3f(.5,.5,.5);
 for (x=mzx;x>=0;x--) for (y=mzy;y>=0;y--)
  { glBegin(GL_QUAD_STRIP);
    glVertex3d(x*10,y*10,-1);
    glVertex3d(x*10,y*10,1);
    glVertex3d((x*10)+1,y*10,-1);
    glVertex3d((x*10)+1,y*10,1);
    glVertex3d((x*10)+1,(y*10)+1,-1);
    glVertex3d((x*10)+1,(y*10)+1,1);
    glVertex3d(x*10,(y*10)+1,-1);
    glVertex3d(x*10,(y*10)+1,1);
    glVertex3d(x*10,y*10,-1);
    glVertex3d(x*10,y*10,1);
    glEnd();
  }
 glEndList();
}

static int set_sizes_from_string(const char *s0)
{
 const char *s;
 char *e;
 long int x;
 long int y;

 x = strtol(s0,&e,10);
 if ((e == s0) || (*e != 'x')) return(1);
 s = e + 1;
 y = strtol(s,&e,10);
 if ((e == s) || *e) return(1);
 if ((x < 2) || (y < 2) || (x > 100) || (y > 100)) return(1);
 mzx = x;
 mzy = y;
 return(0);
}

static void handleargs(int ac, char **av)
{
 int skip;
 int errs;

 skip = 0;
 errs = 0;
 for (ac--,av++;ac;ac--,av++)
  { if (skip > 0)
     { skip --;
       continue;
     }
    if (**av != '-')
     { fprintf(stderr,"%s: extra argument `%s'\n",__progname,*av);
       errs = 1;
       continue;
     }
    if (0)
     {
needarg:;
       fprintf(stderr,"%s: %s needs a following argument\n",__progname,*av);
       errs = 1;
       continue;
     }
#define WANTARG() do { if (++skip >= ac) goto needarg; } while (0)
    if (!strcmp(*av,"-size"))
     { WANTARG();
       if (set_sizes_from_string(av[skip]))
	{ fprintf(stderr,"%s: bad size string `%s'\n",__progname,av[skip]);
	  errs = 1;
	}
       continue;
     }
#undef WANTARG
    fprintf(stderr,"%s: unrecognized option `%s'\n",__progname,*av);
    errs = 1;
  }
 if (errs) exit(1);
}

static void setup_maze(void)
{
 typedef struct {
	   unsigned char x;
	   unsigned char y;
	   MZBITS bit;
	   } WALL;
 WALL *walls;
 int *cells;
 int x;
 int y;
 int i;
 int nw;
 int zc;
 int wi;
 WALL w;
 int c;
 int openit;
 MZBITS obit;

 int done(void)
  { int i;
    if (zc > 0) return(0);
    for (i=mzcells-1;i>=0;i--) if (cells[i] != 1) return(0);
    return(1);
  }

 void renumber(int a, int b)
  { int i;
    if (b < a)
     { int t;
       t = a;
       a = b;
       b = t;
     }
    for (i=mzcells-1;i>=0;i--) if (cells[i] == b) cells[i] = a;
  }

 mzwalls = (mzx * mzy * 2) - mzx - mzy;
 mzcells = mzx * mzy;
 maze = malloc(mzcells*sizeof(*maze));
 bzero(maze,mzcells*sizeof(*maze));
 srandom(time(0));
 nw = 0;
 cells = malloc(mzcells*sizeof(*cells));
 walls = malloc(mzwalls*sizeof(*walls));
 i = 0;
 for (x=mzx-1;x>=0;x--) for (y=mzy-1;y>=0;y--)
  { cells[i++] = 0;
    if (x > 0) walls[nw++] = (WALL){.x=x,.y=y,.bit=MZ_MX};
    if (y > 0) walls[nw++] = (WALL){.x=x,.y=y,.bit=MZ_MY};
  }
 if (nw != mzwalls) abort();
 zc = mzcells;
 c = 1;
 while (! done())
  { wi = random() % nw;
    w = walls[wi];
    nw --;
    if (wi < nw) walls[wi] = walls[nw];
    wi = w.x + (w.y * mzx);
    i = wi;
    switch (w.bit)
     { case MZ_MX: x = w.x - 1; y = w.y; obit = MZ_PX; i --;     break;
       case MZ_MY: x = w.x; y = w.y - 1; obit = MZ_PY; i -= mzx; break;
       default: abort(); break;
     }
    openit = 1;
    if (cells[wi])
     { if (cells[i])
	{ if (cells[i] == cells[wi])
	   { openit = 0;
	   }
	  else
	   { renumber(cells[wi],cells[i]);
	   }
	}
       else
	{ cells[i] = cells[wi];
	  zc --;
	}
     }
    else
     { if (cells[i])
	{ cells[wi] = cells[i];
	  zc --;
	}
       else
	{ cells[i] = c;
	  cells[wi] = c;
	  c ++;
	  zc -= 2;
	}
     }
    if (openit)
     { maze[wi] |= w.bit;
       maze[i] |= obit;
     }
  }
 maze[0] |= MZ_S;
 maze[mzcells-1] |= MZ_G;
 for (x=mzx-1;x>=0;x--) for (y=mzy-1;y>=0;y--)
  { if ( ( (x > 0) &&
	   ( ( (Maze(x-1,y) & MZ_PX) &&
	       !(Maze(x,y) & MZ_MX) ) ||
	     ( !(Maze(x-1,y) & MZ_PX) &&
	       (Maze(x,y) & MZ_MX) ) ) ) ||
	 ( (y > 0) &&
	   ( ( (Maze(x,y-1) & MZ_PY) &&
	       !(Maze(x,y) & MZ_MY) ) ||
	     ( !(Maze(x,y-1) & MZ_PY) &&
	       (Maze(x,y) & MZ_MY) ) ) ) ) abort();
  }
 for (x=mzx;x>0;x--) printf("+---");
 printf("+\n");
 for (y=mzy-1;y>=0;y--)
  { for (x=0;x<mzx;x++)
     { char c;
       switch (Maze(x,y) & (MZ_S|MZ_G))
	{ case 0: c = ' '; break;
	  case MZ_S: c = 's'; break;
	  case MZ_G: c = 'g'; break;
	  case MZ_S|MZ_G: c = '*'; break;
	}
       printf("%c %c ",(Maze(x,y)&MZ_MX)?' ':'|',c);
     }
    printf("|\n");
    for (x=0;x<mzx;x++)
     { printf("+%s",(Maze(x,y)&MZ_MY)?"   ":"---");
     }
    printf("+\n");
  }
 free(cells);
 free(walls);
}

int main(int, char **);
int main(int ac, char **av)
{
 handleargs(ac,av);
 setup_maze();
 open_display();
 find_visual();
 setup_X();
 setup_context();
 setup_bitmaps();
 create_window();
 setup_gl();
 setup_input();
 setup_view();
 setup_ticks();
 setup_lists();
 while (1) tick();
}