#include #include #include #include #include #include #include #include #include #include #include #include "3darith.h" #include "findvis.h" #include "mathutils.h" #define WINX 400 #define WINY 400 #define TEXSIZE 512 #define PLAYER_SIDES 10 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 coordinates is stored in ploc, the camera's in * cloc. Like wx/wy/wz, these are 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 XYZ cloc; 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 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 /* open in the plus x direction */ #define MZ_MX 0x02 /* open in the minus x direction */ #define MZ_PY 0x04 /* open in the plus y direction */ #define MZ_MY 0x08 /* open in the minus y direction */ #define MZ_S 0x10 /* is start */ #define MZ_G 0x20 /* is goal */ #define MZ_P 0x40 /* is on shortest start-goal path */ static unsigned int ticks; static GLuint mazelist; static GLuint pathlist; static GLuint playerlist; static int showpath; static int sx; static int sy; static int gx; static int gy; static unsigned long int seed; static void open_display(void) { disp = XOpenDisplay(0); if (disp == 0) { fprintf(stderr,"%s: can't open display\n",__progname); exit(1); } } static void setup_visual(void) { vi = find_visual(disp); } 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((vmax)?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); } static void draw_compass(void) { XYZ gvf; double gvl; XYZ gvr; XYZ p1; XYZ p2; XYZ p3; XYZ p4; gvf = xyzsub((XYZ){((mzx-1)*10)+5.5,((mzy-1)*10)+5.5,0},ploc); gvl = xyzlength(gvf); if (gvl < 5) return; gvf = xyzscale(gvf,1/gvl); gvr = xyzcross(gvf,(XYZ){0,0,1}); p1 = xyzadd(ploc,xyzadd(xyzscale(gvf,3),xyzscale(gvr,-.05))); p2 = xyzadd(ploc,xyzadd(xyzscale(gvf,3),xyzscale(gvr,.05))); p3 = xyzadd(ploc,xyzscale(gvr,.05)); p4 = xyzadd(ploc,xyzscale(gvr,-.05)); glBegin(GL_QUADS); glColor3f(1,0,0); glVertex3d(p1.x,p1.y,-.75); glVertex3d(p2.x,p2.y,-.75); glVertex3d(p3.x,p3.y,-.75); glVertex3d(p4.x,p4.y,-.75); 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 transforming 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); printf("cloc = (%g,%g,%g)\n",cloc.x,cloc.y,cloc.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); } else { printf("ex/ey/ez not valid\n"); } printf("frameus = %d (fps = %g)\n",frameus,1e6/frameus); 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(-cloc.x,-cloc.y,-cloc.z); glCallList(mazelist); if (showpath) glCallList(pathlist); /* player avatar */ glPushMatrix(); glTranslated(ploc.x,ploc.y,ploc.z); glCallList(playerlist); glPopMatrix(); /* goal-seeking compass */ draw_compass(); /* 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; } /* * 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 - and 6 of those 9 * multiplies can be saved by noticing that three of the terms are * equal to the first column of the matrix dividend. */ static void invert_rotations(XYZ rx, XYZ ry, XYZ rz, XYZ *ix, XYZ *iy, XYZ *iz) { double det; double xx; double xy; double xz; xx = (ry.y * rz.z) - (rz.y * ry.z); xy = (rz.y * rx.z) - (rx.y * rz.z); xz = (rx.y * ry.z) - (ry.y * rx.z); det = (rx.x * xx) + (ry.x * xy) + (rz.x * xz); *ix = (XYZ) { xx / det, xy / det, xz / 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 XYZ limit_location(XYZ l, double size) { int x; int y; unsigned char bits; double px; double py; double d; /* find the relevant maze cell */ x = (l.x - .5) / 10; y = (l.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; /* don't go through walls */ if (!(bits & MZ_PX) && (l.x > x+10-size)) l.x = x + 10 - size; if (!(bits & MZ_MX) && (l.x < x+1+size)) l.x = x + 1 + size; if (!(bits & MZ_PY) && (l.y > y+10-size)) l.y = y + 10 - size; if (!(bits & MZ_MY) && (l.y < y+1+size)) l.y = y + 1 + size; /* find the closest grid pillar */ if (l.x < x+5) px = x + .5; else px = x + 10.5; if (l.y < y+5) py = y + .5; else py = y + 10.5; /* don't go into it */ if ((fabs(l.x-px) <= 1+size) && (fabs(l.y-py) <= 1+size)) /* cheap check */ { if (fabs(l.x-px) <= .5) { /* within pillar's X band; push away in Y */ if ((l.y > py) && (l.y < py+.5+size)) l.y = py + .5 + size; else if ((l.y < py) && (l.y > py-.5-size)) l.y = py - .5 - size; } else if (fabs(l.y-py) <= .5) { /* within pillar's Y band; push away in X */ if ((l.x > px) && (l.x < px+.5+size)) l.x = px + .5 + size; else if ((l.x < px) && (l.x > px-.5-size)) l.x = px - .5 - size; } else { /* closest corner of pillar */ if (l.x < px) px -= .5; else px += .5; if (l.y < py) py -= .5; else py += .5; d = hypot(px-l.x,py-l.y); /* push away if too close to it */ if (d < size) { l.x = px - ((px - l.x) * size / d); l.y = py - ((py - l.y) * size / d); } } } return(l); } static void movepby(XYZ dir, double s) { ploc = limit_location(xyzadd(ploc,xyzscale(dir,s*.1)),.1); } static void drag_camera(void) { double ed; XYZ epd; cloc.z = 0; epd = xyzsub(cloc,ploc); ez = xyzunit(epd); ey = (XYZ){0,0,1}; ex = xyzcross(ey,ez); invert_rotations(ex,ey,ez,&wx,&wy,&wz); evalid = 1; ed = hypot(ploc.x-cloc.x,ploc.y-cloc.y); if (ed < 3) cloc = limit_location(xyzadd(ploc,xyzscale(ez,3)),.01); else if (ed > 4) cloc = limit_location(xyzadd(ploc,xyzscale(ez,4)),.01); cloc.z = .5; } static void movecby(XYZ dir, double s) { cloc = limit_location(xyzadd(cloc,xyzscale(dir,s*.1)),.1); } static void motion(void) { double f; if (kbstate & KBS_SHIFT) f = 12.5; else if (kbstate & KBS_CTRL) f = 2; else f = 5; f *= .3; switch (kbstate & (KBS_ML|KBS_MR)) { case KBS_ML: ensure_e(); movepby(ex,-f); movecby(ex,-f); break; case KBS_MR: ensure_e(); movepby(ex,f); movecby(ex,f); break; } switch (kbstate & (KBS_MF|KBS_MB)) { case KBS_MF: ensure_e(); movepby(ez,-f); break; case KBS_MB: ensure_e(); movepby(ez,f); break; } if (kbstate & (KBS_ML|KBS_MR|KBS_MF|KBS_MB)) { drag_camera(); } switch (kbstate & (KBS_RL|KBS_RR)) { case KBS_RL: movecby(ex,f); drag_camera(); break; case KBS_RR: movecby(ex,-f); drag_camera(); 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_c: case XK_C: if (updn == 'd') showpath = ! showpath; 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 -= 17; } 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){5.5,5.5,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; cloc = (XYZ){0,0,0}; drag_camera(); } static void setup_input(void) { XGrabKeyboard(disp,win,False,GrabModeAsync,GrabModeAsync,CurrentTime); } static void setup_maze_list(void) { int x; int y; mazelist = glGenLists(1); glNewList(mazelist,GL_COMPILE); 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); /* 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(); /* start marker */ glPolygonOffset(0,-20); if (sx < 0) abort(); glBegin(GL_QUADS); glColor3f(.333,.333,.667); glVertex3d(sx+1,sy+1,-1); glVertex3d(sx+1,sy+10,-1); glVertex3d(sx+10,sy+10,-1); glVertex3d(sx+10,sy+1,-1); glEnd(); glPolygonOffset(0,0); /* "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 void setup_path_list(void) { int x; int y; pathlist = glGenLists(1); glNewList(pathlist,GL_COMPILE); glPolygonOffset(0,-10); glBegin(GL_QUADS); glColor3f(.333,.667,.333); for (x=mzx-1;x>=0;x--) for (y=mzy-1;y>=0;y--) { if (Maze(x,y) & MZ_P) { sx = x * 10; sy = y * 10; if ((x > 0) && ((Maze(x-1,y) & (MZ_P|MZ_PX)) == (MZ_P|MZ_PX))) { glVertex3d(sx-5,sy+5,-1); glVertex3d(sx-5,sy+6,-1); glVertex3d(sx+6,sy+6,-1); glVertex3d(sx+6,sy+5,-1); } if ((y > 0) && ((Maze(x,y-1) & (MZ_P|MZ_PY)) == (MZ_P|MZ_PY))) { glVertex3d(sx+5,sy-5,-1); glVertex3d(sx+5,sy+6,-1); glVertex3d(sx+6,sy+6,-1); glVertex3d(sx+6,sy-5,-1); } } } glEnd(); glPolygonOffset(0,0); glEndList(); } static void setup_player_list(void) { int i; double s[PLAYER_SIDES+1]; double c[PLAYER_SIDES+1]; for (i=0;i<=PLAYER_SIDES;i++) { s[i] = sindeg(i*360.0/PLAYER_SIDES) * .1; c[i] = cosdeg(i*360.0/PLAYER_SIDES) * .1; } playerlist = glGenLists(1); glNewList(playerlist,GL_COMPILE); glColor3f(1,1,1); glBegin(GL_QUAD_STRIP); for (i=0;i<=PLAYER_SIDES;i++) { glVertex3d(c[i],s[i],-1); glVertex3d(c[i],s[i],-.75); } glEnd(); glBegin(GL_TRIANGLE_FAN); glVertex3d(0,0,-.7); for (i=PLAYER_SIDES;i>=0;i--) { glVertex3d(c[i],s[i],-.75); } glEnd(); glEndList(); } static void setup_lists(void) { setup_maze_list(); setup_path_list(); setup_player_list(); } 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; } if (!strcmp(*av,"-seed")) { WANTARG(); seed = strtoul(av[skip],0,0); 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; } int mark_solution(int x, int y) { if (Maze(x,y) & MZ_P) return(0); Maze(x,y) |= MZ_P; if (Maze(x,y) & MZ_G) return(1); if ( ((x > 0) && (Maze(x,y) & MZ_MX) && mark_solution(x-1,y)) || ((y > 0) && (Maze(x,y) & MZ_MY) && mark_solution(x,y-1)) || ((x < mzx-1) && (Maze(x,y) & MZ_PX) && mark_solution(x+1,y)) || ((y < mzy-1) && (Maze(x,y) & MZ_PY) && mark_solution(x,y+1)) ) return(1); Maze(x,y) &= ~MZ_P; return(0); } mzwalls = (mzx * mzy * 2) - mzx - mzy; mzcells = mzx * mzy; maze = malloc(mzcells*sizeof(*maze)); bzero(maze,mzcells*sizeof(*maze)); if (seed == 0) { seed = time(0); seed = ((seed >> 16) & 0xffff) | ((seed & 0xffff) << 16); seed = ((seed >> 8) & 0xff00ff) | ((seed & 0xff00ff) << 8); seed = ((seed >> 4) & 0xf0f0f0f) | ((seed & 0xf0f0f0f) << 4); seed = ((seed >> 2) & 0x33333333) | ((seed & 0x33333333) << 2); seed = ((seed >> 1) & 0x55555555) | ((seed & 0x55555555) << 1); } printf("seed = %lu\n",seed); srandom(seed); 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; mark_solution(0,0); 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