X-Git-Url: http://git.hungrycats.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=hacks%2Fglx%2Fglhanoi.c;h=c86abadafb1f9dd903dc305e58b3b9fda3813e4f;hb=50be9bb40dc60130c99ffa568e6677779904ff70;hp=b0f91cafcc155954c62e57b4e9a2fcd67bd3e0c0;hpb=0d6b320def9180cf907ceaed56b23a972a11b757;p=xscreensaver diff --git a/hacks/glx/glhanoi.c b/hacks/glx/glhanoi.c index b0f91caf..c86abada 100644 --- a/hacks/glx/glhanoi.c +++ b/hacks/glx/glhanoi.c @@ -1,5 +1,7 @@ -/* glhanoi, Copyright (c) 2005 Dave Atkinson +/* -*- Mode: C; tab-width: 4 -*- */ +/* glhanoi, Copyright (c) 2005, 2009 Dave Atkinson * except noise function code Copyright (c) 2002 Ken Perlin + * Modified by Lars Huttar (c) 2010, to generalize to 4 or more poles * * Permission to use, copy, modify, distribute, and sell this software and its * documentation for any purpose is hereby granted without fee, provided that @@ -11,33 +13,27 @@ */ #include -#include -#include +#include "rotator.h" -#define PROGCLASS "glhanoi" -#define HACK_INIT init_glhanoi -#define HACK_DRAW draw_glhanoi -#define HACK_RESHAPE reshape_glhanoi -#define HACK_HANDLE_EVENT glhanoi_handle_event -#define EVENT_MASK PointerMotionMask -#define glh_opts xlockmore_opts - -#define DEF_DELAY "15000" -#define DEF_DISKS "7" -#define DEF_WIRE "False" #define DEF_LIGHT "True" -#define DEF_FPS "False" #define DEF_FOG "False" #define DEF_TEXTURE "True" +#define DEF_POLES "0" /* choose random value */ +#define DEF_SPEED "1" -#define DEFAULTS "*delay: " DEF_DELAY "\n" \ - "*count: " DEF_DISKS "\n" \ - "*showFPS: " DEF_FPS "\n" \ - "*wireframe: " DEF_WIRE "\n" +#define DEFAULTS "*delay: 15000\n" \ + "*count: 0\n" \ + "*showFPS: False\n" \ + "*wireframe: False\n" + +# define refresh_glhanoi 0 +/* polygon resolution of poles and disks */ #define NSLICE 32 #define NLOOPS 1 + +/* How long to wait at start and finish. */ #define START_DURATION 1.0 #define FINISH_DURATION 1.0 #define BASE_LENGTH 30.0 @@ -48,6 +44,10 @@ #define MARBLE_SCALE 1.01 +#undef BELLRAND +/* Return a double precision number in [0...n], with bell curve distribution. */ +#define BELLRAND(n) ((frand((n)) + frand((n)) + frand((n))) / 3) + enum { MARBLE_TEXURE, N_TEXTURES @@ -63,39 +63,16 @@ enum { #ifdef USE_GL /* whole file */ -#include - -#ifdef HAVE_GETTIMEOFDAY -#ifdef GETTIMEOFDAY_TWO_ARGS -# include -# include -typedef struct timeval glhtime; -#else /* GETTIMEOFDAY_TWO_ARGS */ -# include -# include typedef struct timeval glhtime; -#endif -#else /* HAVE_GETTIMEOFDAY */ -#ifdef HAVE_FTIME -# include -typedef struct timeb glhtime; -#endif /* HAVE_FTIME */ -#endif /* HAVE_GETTIMEOFDAY */ - -double getTime(void) + +static double getTime(void) { -#ifdef HAVE_GETTIMEOFDAY struct timeval t; #ifdef GETTIMEOFDAY_TWO_ARGS gettimeofday(&t, NULL); #else /* !GETTIMEOFDAY_TWO_ARGS */ gettimeofday(&t); #endif /* !GETTIMEOFDAY_TWO_ARGS */ -#else /* !HAVE_GETTIMEOFDAY */ -#ifdef HAVE_FTIME - ftime(&t); -#endif /* HAVE_FTIME */ -#endif /* !HAVE_GETTIMEOFDAY */ return t.tv_sec + t.tv_usec / 1000000.0; } @@ -122,13 +99,23 @@ typedef struct { GLfloat t1, t2; GLfloat ucostheta, usintheta; GLdouble rotAngle; + GLfloat speed; + int polys; } Disk; typedef struct { Disk **data; int count; int size; -} Stack; +} Pole; + +/* A SubProblem is a recursive subdivision of the problem, and means + "Move nDisks disks from src pole to dst pole, using the poles indicated in 'available'." */ +typedef struct { + int nDisks; + int src, dst; + unsigned long available; /* a bitmask of poles that have no smaller disks on them */ +} SubProblem; typedef struct { GLXContext *glx_context; @@ -140,18 +127,23 @@ typedef struct { double lastTime; double duration; int numberOfDisks; + int numberOfPoles; int numberOfMoves; int maxDiskIdx; int magicNumber; Disk *currentDisk; int move; + /* src, tmp, dst: index of pole that is source / storage / destination for + current move */ int src; int tmp; int dst; int oldsrc; int oldtmp; int olddst; - Stack pole[3]; + SubProblem *solveStack; + int solveStackSize, solveStackIdx; + Pole *pole; float boardSize; float baseLength; float baseWidth; @@ -162,10 +154,10 @@ typedef struct { float diskHeight; float *diskPos; /* pre-computed disk positions on rods */ Disk *disk; - float speed; GLint floorList; GLint baseList; GLint poleList; + int floorpolys, basepolys, polepolys; GLfloat camera[3]; GLfloat centre[3]; rotator *the_rotator; @@ -174,37 +166,45 @@ typedef struct { GLuint textureNames[N_TEXTURES]; int drag_x; int drag_y; + int noise_initted; + int p[512]; } glhcfg; static glhcfg *glhanoi_cfg = NULL; -static glhcfg *glhanoi = NULL; static Bool fog; static Bool light; static Bool texture; +static int poles; +static double speed; /* coefficient for how fast the disks move */ static XrmOptionDescRec opts[] = { - {"-light", ".glhanoi.light", XrmoptionNoArg, (caddr_t) "true"}, - {"+light", ".glhanoi.light", XrmoptionNoArg, (caddr_t) "false"}, - {"-fog", ".glhanoi.fog", XrmoptionNoArg, (caddr_t) "true"}, - {"+fog", ".glhanoi.fog", XrmoptionNoArg, (caddr_t) "false"}, - {"-texture", ".glhanoi.texture", XrmoptionNoArg, (caddr_t) "true"}, - {"+texture", ".glhanoi.texture", XrmoptionNoArg, (caddr_t) "false"} + {"-light", ".glhanoi.light", XrmoptionNoArg, "true"}, + {"+light", ".glhanoi.light", XrmoptionNoArg, "false"}, + {"-fog", ".glhanoi.fog", XrmoptionNoArg, "true"}, + {"+fog", ".glhanoi.fog", XrmoptionNoArg, "false"}, + {"-texture", ".glhanoi.texture", XrmoptionNoArg, "true"}, + {"+texture", ".glhanoi.texture", XrmoptionNoArg, "false"}, + {"-poles", ".glhanoi.poles", XrmoptionSepArg, 0 }, + {"-speed", ".glhanoi.speed", XrmoptionSepArg, 0 } }; static argtype vars[] = { - {(caddr_t *) (void *)&light, "light", "Light", DEF_LIGHT, t_Bool}, - {(caddr_t *) (void *)&fog, "fog", "Fog", DEF_FOG, t_Bool}, - {(caddr_t *) (void *)&texture, "texture", "Texture", DEF_TEXTURE, - t_Bool} + {&light, "light", "Light", DEF_LIGHT, t_Bool}, + {&fog, "fog", "Fog", DEF_FOG, t_Bool}, + {&texture, "texture", "Texture", DEF_TEXTURE, t_Bool}, + {&poles, "poles", "Poles", DEF_POLES, t_Int}, + {&speed, "speed", "Speed", DEF_SPEED, t_Float} }; static OptionStruct desc[] = { {"+/-light", "whether to light the scene"}, {"+/-fog", "whether to apply fog to the scene"}, - {"+/-texture", "whether to apply texture to the scene"} + {"+/-texture", "whether to apply texture to the scene"}, + {"-poles r", "number of poles to move disks between"}, + {"-speed s", "speed multiplier"} }; -ModeSpecOpt glh_opts = { countof(opts), opts, countof(vars), vars, desc }; +ENTRYPOINT ModeSpecOpt glhanoi_opts = { countof(opts), opts, countof(vars), vars, desc }; #ifdef USE_MODULES @@ -217,45 +217,55 @@ ModStruct glhanoi_description = { #endif -static GLfloat cBlack[] = { 0.0, 0.0, 0.0, 1.0 }; -static GLfloat cWhite[] = { 1.0, 1.0, 1.0, 1.0 }; -static GLfloat poleColor[] = { 0.545, 0.137, 0.137 }; -static GLfloat baseColor[] = { 0.34, 0.34, 0.48 }; -static GLfloat fogcolor[] = { 0.5, 0.5, 0.5 }; - -static float left[] = { 1.0, 0.0, 0.0 }; -static float up[] = { 0.0, 1.0, 0.0 }; -static float front[] = { 0.0, 0.0, 1.0 }; -static float right[] = { -1.0, 0.0, 0.0 }; -static float down[] = { 0.0, -1.0, 0.0 }; -static float back[] = { 0.0, 0.0, -1.0 }; - -GLfloat pos0[4] = { 50.0, 50.0, 50.0, 0.0 }; -GLfloat amb0[4] = { 0.0, 0.0, 0.0, 1.0 }; -GLfloat dif0[4] = { 1.0, 1.0, 1.0, 1.0 }; -GLfloat spc0[4] = { 0.0, 1.0, 1.0, 1.0 }; - -GLfloat pos1[4] = { -50.0, 50.0, -50.0, 0.0 }; -GLfloat amb1[4] = { 0.0, 0.0, 0.0, 1.0 }; -GLfloat dif1[4] = { 1.0, 1.0, 1.0, 1.0 }; -GLfloat spc1[4] = { 1.0, 1.0, 1.0, 1.0 }; - -float g = 3.0 * 9.80665; /* hmm, looks like we need more gravity, Scotty... */ +static const GLfloat cBlack[] = { 0.0, 0.0, 0.0, 1.0 }; +static const GLfloat cWhite[] = { 1.0, 1.0, 1.0, 1.0 }; +static const GLfloat poleColor[] = { 0.545, 0.137, 0.137 }; +static const GLfloat baseColor[] = { 0.34, 0.34, 0.48 }; +static const GLfloat fogcolor[] = { 0.5, 0.5, 0.5 }; + +static const float left[] = { 1.0, 0.0, 0.0 }; +static const float up[] = { 0.0, 1.0, 0.0 }; +static const float front[] = { 0.0, 0.0, 1.0 }; +static const float right[] = { -1.0, 0.0, 0.0 }; +static const float down[] = { 0.0, -1.0, 0.0 }; +static const float back[] = { 0.0, 0.0, -1.0 }; + +static const GLfloat pos0[4] = { 50.0, 50.0, 50.0, 0.0 }; +static const GLfloat amb0[4] = { 0.0, 0.0, 0.0, 1.0 }; +static const GLfloat dif0[4] = { 1.0, 1.0, 1.0, 1.0 }; +static const GLfloat spc0[4] = { 0.0, 1.0, 1.0, 1.0 }; + +static const GLfloat pos1[4] = { -50.0, 50.0, -50.0, 0.0 }; +static const GLfloat amb1[4] = { 0.0, 0.0, 0.0, 1.0 }; +static const GLfloat dif1[4] = { 1.0, 1.0, 1.0, 1.0 }; +static const GLfloat spc1[4] = { 1.0, 1.0, 1.0, 1.0 }; + +static float g = 3.0 * 9.80665; /* hmm, looks like we need more gravity, Scotty... */ + +static void checkAllocAndExit(Bool item, char *descr) { + if (!item) { + fprintf(stderr, "%s: unable to allocate memory for %s\n", + progname, descr); + exit(EXIT_FAILURE); + } +} #define DOPUSH(X, Y) (((X)->count) >= ((X)->size)) ? NULL : ((X)->data[(X)->count++] = (Y)) #define DOPOP(X) (X)->count <= 0 ? NULL : ((X)->data[--((X)->count)]) -Disk *push(int idx, Disk * d) +/* push disk d onto pole idx */ +static Disk *push(glhcfg *glhanoi, int idx, Disk * d) { return DOPUSH(&glhanoi->pole[idx], d); } -Disk *pop(int idx) +/* pop the top disk from pole idx */ +static Disk *pop(glhcfg *glhanoi, int idx) { return DOPOP(&glhanoi->pole[idx]); } -inline void swap(int *x, int *y) +static inline void swap(int *x, int *y) { *x = *x ^ *y; *y = *x ^ *y; @@ -264,8 +274,9 @@ inline void swap(int *x, int *y) /* * magic - it's magic... + * Return 1 if the number of trailing zeroes on i is even, unless i is 1 or 0. */ -int magic(int i) +static int magic(int i) { int count = 0; if(i <= 1) @@ -277,7 +288,8 @@ int magic(int i) return count % 2 == 0; } -float distance(float *p0, float *p1) +#if 0 +static float distance(float *p0, float *p1) { float x, y, z; x = p1[0] - p0[0]; @@ -285,14 +297,15 @@ float distance(float *p0, float *p1) z = p1[2] - p0[2]; return (float)sqrt(x * x + y * y + z * z); } +#endif -GLfloat A(GLfloat a, GLfloat b, GLfloat c) +static GLfloat A(GLfloat a, GLfloat b, GLfloat c) { GLfloat sum = a + b; return c / (a * b - 0.25 * sum * sum); } -void moveSetup(Disk * disk) +static void moveSetup(glhcfg *glhanoi, Disk * disk) { float h, ymax; float u; @@ -300,10 +313,19 @@ void moveSetup(Disk * disk) int dst = glhanoi->dst; GLfloat theta; GLfloat sintheta, costheta; + double absx; + + if(glhanoi->state != FINISHED) { + double xxx = -180.0 * (dst - src >= 0 ? 1.0 : -1.0); + if(random() % 6 == 0) { + disk->rotAngle = xxx * (2 - 2 * random() % 2) * (random() % 3 + 1); + } else { + disk->rotAngle = xxx; + } + if(random() % 4 == 0) { + disk->rotAngle = -disk->rotAngle; + } - if(glhanoi->state != FINISHED && random() % 6 == 0) { - disk->rotAngle = - -180.0 * (2 - 2 * random() % 2) * (random() % 3 + 1); } else { disk->rotAngle = -180.0; } @@ -314,19 +336,15 @@ void moveSetup(Disk * disk) FINISHED ? disk->base0 : glhanoi->diskPos[glhanoi->pole[dst]. count]; - disk->xmin = glhanoi->poleOffset * (src - 1); - disk->xmax = glhanoi->poleOffset * (dst - 1); + disk->xmin = glhanoi->poleOffset * (src - (glhanoi->numberOfPoles - 1.0f) * 0.5); + disk->xmax = glhanoi->poleOffset * (dst - (glhanoi->numberOfPoles - 1.0f) * 0.5); disk->ymin = glhanoi->poleHeight; - ymax = - glhanoi->poleHeight + fabs(disk->xmax - - disk->xmin) * (glhanoi->state == - FINISHED ? 1.0 + - (double)(glhanoi-> - numberOfDisks - - disk->id) / - (double)glhanoi-> - numberOfDisks : 1.0); + absx = fabs(disk->xmax - disk->xmin); + ymax = glhanoi->poleHeight + absx; + if(glhanoi->state == FINISHED) { + ymax += absx * (double)(glhanoi->numberOfDisks - disk->id); + } h = ymax - disk->ymin; theta = atan((disk->xmin - disk->xmax) * A(disk->xmin, disk->xmax, h)); if(theta < 0.0) @@ -346,31 +364,168 @@ void moveSetup(Disk * disk) disk->u2 = disk->usintheta - g * disk->t2; } -void makeMove(void) -{ - int fudge = glhanoi->move + 2; - int magicNumber = magic(fudge); +/* For debugging: show a value as a string of ones and zeroes +static const char *byteToBinary(int x) { + static char b[9]; + int i, z; - glhanoi->currentDisk = pop(glhanoi->src); - moveSetup(glhanoi->currentDisk); - push(glhanoi->dst, glhanoi->currentDisk); - fudge = fudge % 2; + for (z = 128, i = 0; z > 0; z >>= 1, i++) { + b[i] = ((x & z) == z) ? '1' : '0'; + } + b[i] = '\0'; - if(fudge == 1 || magicNumber) { - swap(&glhanoi->src, &glhanoi->tmp); + return b; +} +*/ + +static void pushMove(glhcfg *glhanoi, int n, int src, int dst, int avail) { + SubProblem *sp = &(glhanoi->solveStack[glhanoi->solveStackIdx++]); + + if (glhanoi->solveStackIdx > glhanoi->solveStackSize) { + fprintf(stderr, "solveStack overflow: pushed index %d: %d from %d to %d, using %d\n", + glhanoi->solveStackIdx, n, src, dst, avail); + exit(EXIT_FAILURE); } - if(fudge == 0 || glhanoi->magicNumber) { - swap(&glhanoi->dst, &glhanoi->tmp); + + sp->nDisks = n; + sp->src = src; + sp->dst = dst; + sp->available = avail & ~((unsigned long)(1 << src)) + & ~((unsigned long)(1 << dst)); + /* + fprintf(stderr, "Debug: > pushed solveStack %d: %d from %d to %d, using %s\n", + glhanoi->solveStackIdx - 1, n, src, dst, byteToBinary(sp->available)); + */ +} + + +static Bool solveStackEmpty(glhcfg *glhanoi) { + return (glhanoi->solveStackIdx < 1); +} + +static SubProblem *popMove(glhcfg *glhanoi) { + SubProblem *sp; + if (solveStackEmpty(glhanoi)) return (SubProblem *)NULL; + sp = &(glhanoi->solveStack[--glhanoi->solveStackIdx]); + /* fprintf(stderr, "Debug: < popped solveStack %d: %d from %d to %d, using %s\n", + glhanoi->solveStackIdx, sp->nDisks, sp->src, sp->dst, byteToBinary(sp->available)); */ + return sp; +} + +/* Return number of bits set in b */ +static int numBits(unsigned long b) { + int count = 0; + while (b) { + count += b & 0x1u; + b >>= 1; + } + return count; +} + +/* Return index (power of 2) of least significant 1 bit. */ +static int bitScan(unsigned long b) { + int count; + for (count = 0; b; count++, b >>= 1) { + if (b & 0x1u) return count; } - glhanoi->magicNumber = magicNumber; + return -1; } -double lerp(double alpha, double start, double end) +/* A bit pattern representing all poles */ +#define ALL_POLES ((1 << glhanoi->numberOfPoles) - 1) + +#define REMOVE_BIT(a, b) ((a) & ~(1 << (b))) +#define ADD_BIT(a, b) ((a) | (1 << (b))) + +static void makeMove(glhcfg *glhanoi) +{ + if (glhanoi->numberOfPoles == 3) { + int fudge = glhanoi->move + 2; + int magicNumber = magic(fudge); + + + glhanoi->currentDisk = pop(glhanoi, glhanoi->src); + moveSetup(glhanoi, glhanoi->currentDisk); + push(glhanoi, glhanoi->dst, glhanoi->currentDisk); + + fudge = fudge % 2; + + if(fudge == 1 || magicNumber) { + swap(&glhanoi->src, &glhanoi->tmp); + } + if(fudge == 0 || glhanoi->magicNumber) { + swap(&glhanoi->dst, &glhanoi->tmp); + } + glhanoi->magicNumber = magicNumber; + } else { + SubProblem sp; + int tmp = 0; + + if (glhanoi->move == 0) { + /* Initialize the solution stack. Original problem: + move all disks from pole 0 to furthest pole, + using all other poles. */ + pushMove(glhanoi, glhanoi->numberOfDisks, 0, + glhanoi->numberOfPoles - 1, + REMOVE_BIT(REMOVE_BIT(ALL_POLES, 0), glhanoi->numberOfPoles - 1)); + } + + while (!solveStackEmpty(glhanoi)) { + int k, numAvail; + sp = *popMove(glhanoi); + + if (sp.nDisks == 1) { + /* We have a single, concrete move to do. */ + /* moveSetup uses glhanoi->src, dst. */ + glhanoi->src = sp.src; + glhanoi->dst = sp.dst; + glhanoi->tmp = tmp; /* Probably unnecessary */ + + glhanoi->currentDisk = pop(glhanoi, sp.src); + moveSetup(glhanoi, glhanoi->currentDisk); + push(glhanoi, sp.dst, glhanoi->currentDisk); + + return; + } else { + /* Divide and conquer, using Frame-Stewart algorithm, until we get to base case */ + if (sp.nDisks == 1) break; + + numAvail = numBits(sp.available); + if (numAvail < 2) k = sp.nDisks - 1; + else if(numAvail >= sp.nDisks - 2) k = 1; + /* heuristic for optimal k: sqrt(2n) (see http://www.cs.wm.edu/~pkstoc/boca.pdf) */ + else k = (int)(sqrt(2 * sp.nDisks)); + + if (k >= sp.nDisks) k = sp.nDisks - 1; + else if (k < 1) k = 1; + + tmp = bitScan(sp.available); + /* fprintf(stderr, "Debug: k is %d, tmp is %d\n", k, tmp); */ + if (tmp == -1) { + fprintf(stderr, "Error: n > 1 (%d) and no poles available\n", + sp.nDisks); + } + + /* Push on moves in reverse order, since this is a stack. */ + pushMove(glhanoi, k, tmp, sp.dst, + REMOVE_BIT(ADD_BIT(sp.available, sp.src), tmp)); + pushMove(glhanoi, sp.nDisks - k, sp.src, sp.dst, + REMOVE_BIT(sp.available, tmp)); + pushMove(glhanoi, k, sp.src, tmp, + REMOVE_BIT(ADD_BIT(sp.available, sp.dst), tmp)); + + /* Repeat until we've found a move we can make. */ + } + } + } +} + +static double lerp(double alpha, double start, double end) { return start + alpha * (end - start); } -void upfunc(GLdouble t, Disk * d) +static void upfunc(GLdouble t, Disk * d) { d->position[0] = d->xmin; d->position[1] = d->base0 + (d->u1 - 0.5 * g * t) * t; @@ -378,16 +533,16 @@ void upfunc(GLdouble t, Disk * d) d->rotation[1] = 0.0; } -void parafunc(GLdouble t, Disk * d) +static void parafunc(GLdouble t, Disk * d) { d->position[0] = d->xmin + d->ucostheta * t; d->position[1] = d->ymin + (d->usintheta - 0.5 * g * t) * t; d->rotation[1] = - d->rotAngle * (d->position[0] - d->xmin) / (d->xmax - d->xmin); + d->rotAngle * (d->position[0] - d->xmin) / (d->xmax - d->xmin); } -void downfunc(GLdouble t, Disk * d) +static void downfunc(GLdouble t, Disk * d) { d->position[0] = d->xmax; d->position[1] = d->ymin + (d->u2 - 0.5 * g * t) * t; @@ -395,9 +550,10 @@ void downfunc(GLdouble t, Disk * d) d->rotation[1] = 0.0; } -Bool computePosition(GLfloat t, Disk * d) +/* Return true iff move is finished. */ +static Bool computePosition(GLfloat t, Disk * d) { - Bool finished = FALSE; + Bool finished = False; if(t < d->t1) { upfunc(t, d); @@ -407,13 +563,13 @@ Bool computePosition(GLfloat t, Disk * d) downfunc(t - d->t1 - d->t2, d); if(d->position[1] <= d->base1) { d->position[1] = d->base1; - finished = TRUE; + finished = True; } } return finished; } -void updateView(void) +static void updateView(glhcfg *glhanoi) { double longitude, latitude, radius; double a, b, c, A, B; @@ -451,13 +607,20 @@ void updateView(void) sin(longitude * 2.0 * M_PI)); } -void changeState(State state) +static void changeState(glhcfg *glhanoi, State state) { glhanoi->state = state; glhanoi->startTime = getTime(); } -void update_glhanoi(void) +static Bool finishedHanoi(glhcfg *glhanoi) { + /* use different criteria depending on algorithm */ + return (glhanoi->numberOfPoles == 3 ? + glhanoi->move >= glhanoi->numberOfMoves : + solveStackEmpty(glhanoi)); +} + +static void update_glhanoi(glhcfg *glhanoi) { double t = getTime() - glhanoi->startTime; int i; @@ -473,23 +636,24 @@ void update_glhanoi(void) swap(&glhanoi->tmp, &glhanoi->dst); } glhanoi->magicNumber = 1; - makeMove(); - changeState(MOVE_DISK); + makeMove(glhanoi); + changeState(glhanoi, MOVE_DISK); break; case MOVE_DISK: - if(computePosition(t, glhanoi->currentDisk)) { - changeState(MOVE_FINISHED); + if(computePosition(t * glhanoi->currentDisk->speed, glhanoi->currentDisk)) { + changeState(glhanoi, MOVE_FINISHED); } break; case MOVE_FINISHED: - if(++glhanoi->move < glhanoi->numberOfMoves) { - makeMove(); - changeState(MOVE_DISK); + ++glhanoi->move; + if(!finishedHanoi(glhanoi)) { + makeMove(glhanoi); + changeState(glhanoi, MOVE_DISK); } else { glhanoi->duration = FINISH_DURATION; - changeState(FINISHED); + changeState(glhanoi, FINISHED); } break; @@ -500,14 +664,14 @@ void update_glhanoi(void) glhanoi->src = glhanoi->olddst; glhanoi->dst = glhanoi->oldsrc; for(i = 0; i < glhanoi->numberOfDisks; ++i) { - Disk *disk = pop(glhanoi->src); + Disk *disk = pop(glhanoi, glhanoi->src); assert(disk != NULL); - moveSetup(disk); + moveSetup(glhanoi, disk); } for(i = glhanoi->maxDiskIdx; i >= 0; --i) { - push(glhanoi->dst, &glhanoi->disk[i]); + push(glhanoi, glhanoi->dst, &glhanoi->disk[i]); } - changeState(MONEY_SHOT); + changeState(glhanoi, MONEY_SHOT); break; case MONEY_SHOT: @@ -532,7 +696,7 @@ void update_glhanoi(void) glhanoi->src = glhanoi->oldsrc; glhanoi->tmp = glhanoi->oldtmp; glhanoi->dst = glhanoi->olddst; - changeState(START); + changeState(glhanoi, START); } break; @@ -543,7 +707,7 @@ void update_glhanoi(void) } } -void HSVtoRGBf(GLfloat h, GLfloat s, GLfloat v, +static void HSVtoRGBf(GLfloat h, GLfloat s, GLfloat v, GLfloat * r, GLfloat * g, GLfloat * b) { if(s == 0.0) { @@ -596,12 +760,12 @@ void HSVtoRGBf(GLfloat h, GLfloat s, GLfloat v, } } -void HSVtoRGBv(GLfloat * hsv, GLfloat * rgb) +static void HSVtoRGBv(GLfloat * hsv, GLfloat * rgb) { HSVtoRGBf(hsv[0], hsv[1], hsv[2], &rgb[0], &rgb[1], &rgb[2]); } -void setMaterial(GLfloat color[3], GLfloat hlite[3], int shininess) +static void setMaterial(const GLfloat color[3], const GLfloat hlite[3], int shininess) { glColor3fv(color); glMaterialfv(GL_FRONT, GL_SPECULAR, hlite); @@ -617,10 +781,11 @@ void setMaterial(GLfloat color[3], GLfloat hlite[3], int shininess) * people's hardware supports 3D textures, so I didn't bother (xorg * ATI server doesn't :-( ) */ -void drawTube(GLdouble bottomRadius, GLdouble topRadius, +static int drawTube(GLdouble bottomRadius, GLdouble topRadius, GLdouble bottomThickness, GLdouble topThickness, GLdouble height, GLuint nSlice, GLuint nLoop) { + int polys = 0; GLfloat y; GLfloat *cosCache = malloc(sizeof(GLfloat) * nSlice); GLfloat *sinCache = malloc(sizeof(GLfloat) * nSlice); @@ -629,7 +794,7 @@ void drawTube(GLdouble bottomRadius, GLdouble topRadius, GLint lastSlice = nSlice - 1; GLfloat radius; GLfloat innerRadius; - GLfloat maxRadius; + /*GLfloat maxRadius;*/ if(bottomThickness > bottomRadius) { bottomThickness = bottomRadius; @@ -643,11 +808,11 @@ void drawTube(GLdouble bottomRadius, GLdouble topRadius, if(topThickness < 0.0) { topThickness = 0.0; } - if(topRadius >= bottomRadius) { +/* if(topRadius >= bottomRadius) { maxRadius = topRadius; } else { maxRadius = bottomRadius; - } + }*/ /* bottom */ y = 0.0; @@ -682,6 +847,7 @@ void drawTube(GLdouble bottomRadius, GLdouble topRadius, /* yTexCoord, */ /* midTexCoord + cosCache[slice] * outerTexCoordSize); */ glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]); + polys++; } glEnd(); @@ -707,10 +873,12 @@ void drawTube(GLdouble bottomRadius, GLdouble topRadius, upperRadius * cosCache[slice]); glVertex3f(lowerRadius * sinCache[slice], lowerY, lowerRadius * cosCache[slice]); + polys++; } glNormal3f(0.0, 0.0, 1.0); glVertex3f(0.0, upperY, upperRadius); glVertex3f(0.0, lowerY, lowerRadius); + polys++; glEnd(); /* inside */ @@ -729,6 +897,7 @@ void drawTube(GLdouble bottomRadius, GLdouble topRadius, upperRadius * cosCache[slice]); glVertex3f(lowerRadius * sinCache[slice], lowerY, lowerRadius * cosCache[slice]); + polys++; } glEnd(); } @@ -745,25 +914,27 @@ void drawTube(GLdouble bottomRadius, GLdouble topRadius, innerRadius * cosCache[slice]); glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]); + polys++; } glVertex3f(0.0, y, innerRadius); glVertex3f(0.0, y, radius); glEnd(); + return polys; } -void drawPole(GLfloat radius, GLfloat length) +static int drawPole(GLfloat radius, GLfloat length) { - drawTube(radius, radius, radius, radius, length, NSLICE, NLOOPS); + return drawTube(radius, radius, radius, radius, length, NSLICE, NLOOPS); } -void drawDisk3D(GLdouble inner_radius, GLdouble outer_radius, - GLdouble height) +static int drawDisk3D(GLdouble inner_radius, GLdouble outer_radius, + GLdouble height) { - drawTube(outer_radius, outer_radius, outer_radius - inner_radius, - outer_radius - inner_radius, height, NSLICE, NLOOPS); + return drawTube(outer_radius, outer_radius, outer_radius - inner_radius, + outer_radius - inner_radius, height, NSLICE, NLOOPS); } -void drawCuboid(GLfloat length, GLfloat width, GLfloat height) +static int drawCuboid(GLfloat length, GLfloat width, GLfloat height) { GLfloat xmin = -length / 2.0f; GLfloat xmax = length / 2.0f; @@ -771,6 +942,7 @@ void drawCuboid(GLfloat length, GLfloat width, GLfloat height) GLfloat zmax = width / 2.0f; GLfloat ymin = 0.0f; GLfloat ymax = height; + int polys = 0; glBegin(GL_QUADS); /* front */ @@ -779,42 +951,50 @@ void drawCuboid(GLfloat length, GLfloat width, GLfloat height) glVertex3f(xmax, ymin, zmax); /* 1 */ glVertex3f(xmax, ymax, zmax); /* 2 */ glVertex3f(xmin, ymax, zmax); /* 3 */ + polys++; /* right */ glNormal3fv(right); glVertex3f(xmax, ymin, zmax); /* 1 */ glVertex3f(xmax, ymin, zmin); /* 5 */ glVertex3f(xmax, ymax, zmin); /* 6 */ glVertex3f(xmax, ymax, zmax); /* 2 */ + polys++; /* back */ glNormal3fv(back); glVertex3f(xmax, ymin, zmin); /* 5 */ glVertex3f(xmin, ymin, zmin); /* 4 */ glVertex3f(xmin, ymax, zmin); /* 7 */ glVertex3f(xmax, ymax, zmin); /* 6 */ + polys++; /* left */ glNormal3fv(left); glVertex3f(xmin, ymin, zmin); /* 4 */ glVertex3f(xmin, ymin, zmax); /* 0 */ glVertex3f(xmin, ymax, zmax); /* 3 */ glVertex3f(xmin, ymax, zmin); /* 7 */ + polys++; /* top */ glNormal3fv(up); glVertex3f(xmin, ymax, zmax); /* 3 */ glVertex3f(xmax, ymax, zmax); /* 2 */ glVertex3f(xmax, ymax, zmin); /* 6 */ glVertex3f(xmin, ymax, zmin); /* 7 */ + polys++; /* bottom */ glNormal3fv(down); glVertex3f(xmin, ymin, zmin); /* 4 */ glVertex3f(xmax, ymin, zmin); /* 5 */ glVertex3f(xmax, ymin, zmax); /* 1 */ glVertex3f(xmin, ymin, zmax); /* 0 */ + polys++; glEnd(); + return polys; } -void drawDisks(void) +static int drawDisks(glhcfg *glhanoi) { int i; + int polys = 0; glPushMatrix(); glTranslatef(0.0f, glhanoi->baseHeight, 0.0f); @@ -831,58 +1011,68 @@ void drawDisks(void) glTranslatef(0.0, -glhanoi->diskHeight / 2.0, 0.0); } glCallList(disk->displayList); + polys += disk->polys; glPopMatrix(); } glPopMatrix(); + return polys; } -GLfloat getDiskRadius(int i) +static GLfloat getDiskRadius(glhcfg *glhanoi, int i) { - return ((GLfloat) i + 3.0) * glhanoi->poleRadius; + return ((GLfloat) i + 3.0) * glhanoi->baseLength / + (2 * 0.95 * glhanoi->numberOfPoles * (glhanoi->numberOfDisks + 3.0)); } -void initData(void) +static void initData(glhcfg *glhanoi) { GLfloat maxDiskRadius; int i; glhanoi->baseLength = BASE_LENGTH; - glhanoi->poleRadius = glhanoi->baseLength / - (2.0 * (3 * glhanoi->numberOfDisks + 7.0)); - maxDiskRadius = getDiskRadius(glhanoi->numberOfDisks); + maxDiskRadius = getDiskRadius(glhanoi, glhanoi->numberOfDisks); + glhanoi->poleRadius = maxDiskRadius / (glhanoi->numberOfDisks + 3.0); + /* fprintf(stderr, "Debug: baseL = %f, maxDiskR = %f, poleR = %f\n", + glhanoi->baseLength, maxDiskRadius, glhanoi->poleRadius); */ glhanoi->baseWidth = 2.0 * maxDiskRadius; - glhanoi->poleOffset = 2.0 * getDiskRadius(glhanoi->maxDiskIdx); + glhanoi->poleOffset = 2.0 * getDiskRadius(glhanoi, glhanoi->maxDiskIdx); glhanoi->diskHeight = 2.0 * glhanoi->poleRadius; glhanoi->baseHeight = 2.0 * glhanoi->poleRadius; glhanoi->poleHeight = glhanoi->numberOfDisks * glhanoi->diskHeight + glhanoi->poleRadius; + /* numberOfMoves only applies if numberOfPoles = 3 */ glhanoi->numberOfMoves = (1 << glhanoi->numberOfDisks) - 1; glhanoi->boardSize = glhanoi->baseLength * 0.5 * (1.0 + sqrt(5.0)); - for(i = 0; i < 3; i++) { - if((glhanoi->pole[i].data = - calloc(glhanoi->numberOfDisks, sizeof(Disk *))) == NULL) { - fprintf(stderr, "%s: out of memory creating stack %d\n", - progname, i); - exit(1); - } + glhanoi->pole = (Pole *)calloc(glhanoi->numberOfPoles, sizeof(Pole)); + checkAllocAndExit(!!glhanoi->pole, "poles"); + + for(i = 0; i < glhanoi->numberOfPoles; i++) { + checkAllocAndExit( + !!(glhanoi->pole[i].data = calloc(glhanoi->numberOfDisks, sizeof(Disk *))), + "disk stack"); glhanoi->pole[i].size = glhanoi->numberOfDisks; } - if((glhanoi->diskPos = - calloc(glhanoi->numberOfDisks, sizeof(double))) == NULL) { - fprintf(stderr, "%s: out of memory creating diskPos\n", progname); - exit(1); - } + checkAllocAndExit( + !!(glhanoi->diskPos = calloc(glhanoi->numberOfDisks, sizeof(double))), + "diskPos"); glhanoi->the_rotator = make_rotator(0.1, 0.025, 0, 1, 0.005, False); glhanoi->button_down_p = False; glhanoi->src = glhanoi->oldsrc = 0; glhanoi->tmp = glhanoi->oldtmp = 1; - glhanoi->dst = glhanoi->olddst = 2; + glhanoi->dst = glhanoi->olddst = glhanoi->numberOfPoles - 1; + + if (glhanoi->numberOfPoles > 3) { + glhanoi->solveStackSize = glhanoi->numberOfDisks + 2; + glhanoi->solveStack = (SubProblem *)calloc(glhanoi->solveStackSize, sizeof(SubProblem)); + checkAllocAndExit(!!glhanoi->solveStack, "solving stack"); + glhanoi->solveStackIdx = 0; + } } -void initView(void) +static void initView(glhcfg *glhanoi) { glhanoi->camera[0] = 0.0; glhanoi->camera[1] = 0.0; @@ -909,7 +1099,7 @@ static double grad(int hash, double x, double y, double z) return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v); } -static int p[512], permutation[] = { 151, 160, 137, 91, 90, 15, +static const int permutation[] = { 151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247, 120, 234, 75, 0, 26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 88, 237, @@ -930,40 +1120,43 @@ static int p[512], permutation[] = { 151, 160, 137, 91, 90, 15, 156, 180 }; -static void initNoise(void) +static void initNoise(glhcfg *glhanoi) { int i; for(i = 0; i < 256; i++) - p[256 + i] = p[i] = permutation[i]; + glhanoi->p[256 + i] = glhanoi->p[i] = permutation[i]; } -double improved_noise(double x, double y, double z) +static double improved_noise(glhcfg *glhanoi, double x, double y, double z) { double u, v, w; int A, AA, AB, B, BA, BB; int X = (int)floor(x) & 255, /* FIND UNIT CUBE THAT */ Y = (int)floor(y) & 255, /* CONTAINS POINT. */ Z = (int)floor(z) & 255; - static int start = 0; - if(start == 0) { - initNoise(); - start = 1; + if(!glhanoi->noise_initted) { + initNoise(glhanoi); + glhanoi->noise_initted = 1; } x -= floor(x); /* FIND RELATIVE X,Y,Z */ y -= floor(y); /* OF POINT IN CUBE. */ z -= floor(z); - u = fade(x), /* COMPUTE FADE CURVES */ - v = fade(y), /* FOR EACH OF X,Y,Z. */ - w = fade(z); - A = p[X] + Y, AA = p[A] + Z, AB = p[A + 1] + Z, /* HASH COORDINATES OF */ - B = p[X + 1] + Y, BA = p[B] + Z, BB = p[B + 1] + Z; /* THE 8 CUBE CORNERS, */ - return lerp(w, lerp(v, lerp(u, grad(p[AA], x, y, z), /* AND ADD */ - grad(p[BA], x - 1, y, z)), /* BLENDED */ - lerp(u, grad(p[AB], x, y - 1, z), /* RESULTS */ - grad(p[BB], x - 1, y - 1, z))), /* FROM 8 CORNERS */ - lerp(v, lerp(u, grad(p[AA + 1], x, y, z - 1), grad(p[BA + 1], x - 1, y, z - 1)), /* OF CUBE */ - lerp(u, grad(p[AB + 1], x, y - 1, z - 1), - grad(p[BB + 1], x - 1, y - 1, z - 1)))); + u = fade(x), /* COMPUTE FADE CURVES */ + v = fade(y), /* FOR EACH OF X,Y,Z. */ + w = fade(z); + A = glhanoi->p[X] + Y; + AA = glhanoi->p[A] + Z; + AB = glhanoi->p[A + 1] + Z, /* HASH COORDINATES OF */ + B = glhanoi->p[X + 1] + Y; + BA = glhanoi->p[B] + Z; + BB = glhanoi->p[B + 1] + Z; /* THE 8 CUBE CORNERS, */ + return lerp(w, lerp(v, lerp(u, grad(glhanoi->p[AA], x, y, z),/* AND ADD */ + grad(glhanoi->p[BA], x - 1, y, z)),/* BLENDED */ + lerp(u, grad(glhanoi->p[AB], x, y - 1, z),/* RESULTS */ + grad(glhanoi->p[BB], x - 1, y - 1, z))),/* FROM 8 CORNERS */ + lerp(v, lerp(u, grad(glhanoi->p[AA + 1], x, y, z - 1), grad(glhanoi->p[BA + 1], x - 1, y, z - 1)), /* OF CUBE */ + lerp(u, grad(glhanoi->p[AB + 1], x, y - 1, z - 1), + grad(glhanoi->p[BB + 1], x - 1, y - 1, z - 1)))); } /* @@ -977,8 +1170,8 @@ struct tex_col_t { }; typedef struct tex_col_t tex_col_t; -GLubyte *makeTexture(int x_size, int y_size, int z_size, - GLuint(*texFunc) (double, double, double, +static GLubyte *makeTexture(glhcfg *glhanoi, int x_size, int y_size, int z_size, + GLuint(*texFunc) (glhcfg *, double, double, double, tex_col_t *), tex_col_t * colours) { int i, j, k; @@ -1003,7 +1196,7 @@ GLubyte *makeTexture(int x_size, int y_size, int z_size, for(j = 0; j < y_size; j++, y += yi) { x = 0.0; for(i = 0; i < x_size; i++, x += xi) { - *texturePtr = texFunc(x, y, z, colours); + *texturePtr = texFunc(glhanoi, x, y, z, colours); ++texturePtr; } } @@ -1011,46 +1204,55 @@ GLubyte *makeTexture(int x_size, int y_size, int z_size, return textureData; } -tex_col_t makeMarbleColours(void) +static void freeTexCols(tex_col_t*p) { - tex_col_t marbleColours; + free(p->colours); + free(p); +} + +static tex_col_t *makeMarbleColours(void) +{ + tex_col_t *marbleColours; int ncols = 2; - marbleColours.colours = calloc(sizeof(GLuint), ncols); - marbleColours.ncols = ncols; + marbleColours = malloc(sizeof(tex_col_t)); + if(marbleColours == NULL) return NULL; + marbleColours->colours = calloc(sizeof(GLuint), ncols); + if(marbleColours->colours == NULL) return NULL; + marbleColours->ncols = ncols; - marbleColours.colours[0] = 0x3f3f3f3f; - marbleColours.colours[1] = 0xffffffff; + marbleColours->colours[0] = 0x3f3f3f3f; + marbleColours->colours[1] = 0xffffffff; return marbleColours; } -double turb(double x, double y, double z, int octaves) +static double turb(glhcfg *glhanoi, double x, double y, double z, int octaves) { int oct, freq = 1; double r = 0.0; for(oct = 0; oct < octaves; ++oct) { - r += fabs(improved_noise(freq * x, freq * y, freq * z)) / freq; + r += fabs(improved_noise(glhanoi, freq * x, freq * y, freq * z)) / freq; freq <<= 1; } return r / 2.0; } -void perturb(double *x, double *y, double *z, double scale) +static void perturb(glhcfg *glhanoi, double *x, double *y, double *z, double scale) { - double t = scale * turb(*x, *y, *z, 4); + double t = scale * turb(glhanoi, *x, *y, *z, 4); *x += t; *y += t; *z += t; } -double f_m(double x, double y, double z) +static double f_m(double x, double y, double z) { return sin(3.0 * M_PI * x); } -GLuint C_m(double x, const tex_col_t * tex_cols) +static GLuint C_m(double x, const tex_col_t * tex_cols) { int r = tex_cols->colours[0] & 0xff; int g = tex_cols->colours[0] >> 8 & 0xff; @@ -1073,28 +1275,31 @@ GLuint C_m(double x, const tex_col_t * tex_cols) } -GLuint makeMarbleTexture(double x, double y, double z, tex_col_t * colours) +static GLuint makeMarbleTexture(glhcfg *glhanoi, double x, double y, double z, tex_col_t * colours) { - perturb(&x, &y, &z, MARBLE_SCALE); + perturb(glhanoi, &x, &y, &z, MARBLE_SCALE); return C_m(f_m(x, y, z), colours); } -void setTexture(int n) +static void setTexture(glhcfg *glhanoi, int n) { glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[n]); } -int makeTextures(void) +/* returns 1 on failure, 0 on success */ +static int makeTextures(glhcfg *glhanoi) { GLubyte *marbleTexture; - tex_col_t marbleColours; + tex_col_t *marbleColours; glGenTextures(N_TEXTURES, glhanoi->textureNames); - marbleColours = makeMarbleColours(); + if((marbleColours = makeMarbleColours()) == NULL) { + return 1; + } if((marbleTexture = - makeTexture(MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 1, - makeMarbleTexture, &marbleColours)) == NULL) { + makeTexture(glhanoi, MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 1, + makeMarbleTexture, marbleColours)) == NULL) { return 1; } @@ -1107,28 +1312,27 @@ int makeTextures(void) MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 0, GL_RGBA, GL_UNSIGNED_BYTE, marbleTexture); free(marbleTexture); + freeTexCols(marbleColours); return 0; } -void initFloor(void) +static void initFloor(glhcfg *glhanoi) { int i, j; float tileSize = glhanoi->boardSize / BOARD_SQUARES; float x0, x1, z0, z1; float tx0, tx1, tz0, tz1; - float *col = cWhite; + const float *col = cWhite; float texIncr = 1.0 / BOARD_SQUARES; - if((glhanoi->floorList = glGenLists(1)) == 0) { - fprintf(stderr, "can't allocate memory for floor display list\n"); - exit(EXIT_FAILURE); - } + glhanoi->floorpolys = 0; + checkAllocAndExit(!!(glhanoi->floorList = glGenLists(1)), "floor display list"); glNewList(glhanoi->floorList, GL_COMPILE); x0 = -glhanoi->boardSize / 2.0; tx0 = 0.0f; setMaterial(col, cWhite, 128); - setTexture(0); + setTexture(glhanoi, 0); glNormal3fv(up); for(i = 0; i < BOARD_SQUARES; i++, x0 += tileSize, tx0 += texIncr) { x1 = x0 + tileSize; @@ -1161,51 +1365,49 @@ void initFloor(void) glTexCoord2d(tx1, tz0); glVertex3f(x1, 0.0, z0); + glhanoi->floorpolys++; glEnd(); } } glEndList(); } -void initTowers(void) +static void initTowers(glhcfg *glhanoi) { - if((glhanoi->baseList = glGenLists(1)) == 0) { - fprintf(stderr, "can't allocate memory for towers display list\n"); - exit(EXIT_FAILURE); - } + int i; + + checkAllocAndExit(!!(glhanoi->baseList = glGenLists(1)), "tower bases display list"); + glNewList(glhanoi->baseList, GL_COMPILE); setMaterial(baseColor, cWhite, 50); - drawCuboid(glhanoi->baseLength, glhanoi->baseWidth, - glhanoi->baseHeight); + glhanoi->basepolys = drawCuboid(glhanoi->baseLength, glhanoi->baseWidth, + glhanoi->baseHeight); glEndList(); + checkAllocAndExit(!!(glhanoi->poleList = glGenLists(1)), "poles display list\n"); - if((glhanoi->poleList = glGenLists(1)) == 0) { - fprintf(stderr, "can't allocate memory for towers display list\n"); - exit(EXIT_FAILURE); - } glNewList(glhanoi->poleList, GL_COMPILE); glPushMatrix(); - glTranslatef(0.0f, glhanoi->baseHeight, 0.0f); + glTranslatef(-glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5f, glhanoi->baseHeight, 0.0f); setMaterial(poleColor, cWhite, 50); - drawPole(glhanoi->poleRadius, glhanoi->poleHeight); - glPushMatrix(); - glTranslatef(-glhanoi->poleOffset, 0.0, 0.0); - drawPole(glhanoi->poleRadius, glhanoi->poleHeight); - glPopMatrix(); - glTranslatef(glhanoi->poleOffset, 0.0, 0.0); - drawPole(glhanoi->poleRadius, glhanoi->poleHeight); + for (i = 0; i < glhanoi->numberOfPoles; i++) { + glhanoi->polepolys = drawPole(glhanoi->poleRadius, glhanoi->poleHeight); + /* poleOffset is based on disk radius. */ + glTranslatef(glhanoi->poleOffset, 0.0, 0.0); + } glPopMatrix(); glEndList(); } -double cfunc(double x) +/* Parameterized hue based on input 0.0 - 1.0. */ +static double cfunc(double x) { #define COMP < if(x < 2.0 / 7.0) { return (1.0 / 12.0) / (1.0 / 7.0) * x; } if(x < 3.0 / 7.0) { + /* (7x - 1) / 6 */ return (1.0 + 1.0 / 6.0) * x - 1.0 / 6.0; } if(x < 4.0 / 7.0) { @@ -1217,14 +1419,11 @@ double cfunc(double x) return (1.0 / 12.0) / (1.0 / 7.0) * x + 1.0 / 3.0; } -void initDisks(void) +static void initDisks(glhcfg *glhanoi) { int i; - if((glhanoi->disk = - (Disk *) calloc(glhanoi->numberOfDisks, sizeof(Disk))) == NULL) { - perror("initDisks"); - exit(EXIT_FAILURE); - } + glhanoi->disk = (Disk *) calloc(glhanoi->numberOfDisks, sizeof(Disk)); + checkAllocAndExit(!!glhanoi->disk, "disks"); for(i = glhanoi->maxDiskIdx; i >= 0; i--) { GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i); @@ -1234,38 +1433,43 @@ void initDisks(void) Disk *disk = &glhanoi->disk[i]; disk->id = i; - disk->position[0] = -glhanoi->poleOffset; + disk->position[0] = -glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5; disk->position[1] = glhanoi->diskHeight * height; disk->position[2] = 0.0; disk->rotation[0] = 0.0; disk->rotation[1] = 0.0; disk->rotation[2] = 0.0; + disk->polys = 0; + + /* make smaller disks move faster */ + disk->speed = lerp(((double)glhanoi->numberOfDisks - i) / glhanoi->numberOfDisks, 1.0, speed); + /* fprintf(stderr, "disk id: %d, alpha: %0.2f, speed: %0.2f\n", disk->id, + ((double)(glhanoi->maxDiskIdx - i)) / glhanoi->numberOfDisks, disk->speed); */ color[0] = diskColor; color[1] = 1.0f; color[2] = 1.0f; HSVtoRGBv(color, color); - if((disk->displayList = glGenLists(1)) == 0) { - fprintf(stderr, - "can't allocate memory for disk %d display list\n", i); - exit(EXIT_FAILURE); - } + checkAllocAndExit(!!(disk->displayList = glGenLists(1)), "disk display list"); glNewList(disk->displayList, GL_COMPILE); setMaterial(color, cWhite, 100.0); - drawDisk3D(glhanoi->poleRadius, getDiskRadius(i), - glhanoi->diskHeight); + disk->polys += drawDisk3D(glhanoi->poleRadius, + getDiskRadius(glhanoi, i), + glhanoi->diskHeight); + /*fprintf(stderr, "Debug: disk %d has radius %f\n", i, + getDiskRadius(glhanoi, i)); */ glEndList(); } for(i = glhanoi->maxDiskIdx; i >= 0; --i) { GLfloat height = (GLfloat) (glhanoi->maxDiskIdx - i); int h = glhanoi->maxDiskIdx - i; glhanoi->diskPos[h] = glhanoi->diskHeight * height; - push(glhanoi->src, &glhanoi->disk[i]); + push(glhanoi, glhanoi->src, &glhanoi->disk[i]); } } -void initLights(Bool state) +static void initLights(Bool state) { if(state) { glLightfv(GL_LIGHT0, GL_POSITION, pos0); @@ -1286,20 +1490,22 @@ void initLights(Bool state) } } -void drawFloor(void) +static int drawFloor(glhcfg *glhanoi) { glCallList(glhanoi->floorList); + return glhanoi->floorpolys; } -void drawTowers(void) +static int drawTowers(glhcfg *glhanoi) { glCallList(glhanoi->baseList); glCallList(glhanoi->poleList); + return glhanoi->basepolys + glhanoi->polepolys; } /* Window management, etc */ -void reshape_glhanoi(ModeInfo * mi, int width, int height) +ENTRYPOINT void reshape_glhanoi(ModeInfo * mi, int width, int height) { glViewport(0, 0, (GLint) width, (GLint) height); @@ -1314,23 +1520,40 @@ void reshape_glhanoi(ModeInfo * mi, int width, int height) glClear(GL_COLOR_BUFFER_BIT); } -void init_glhanoi(ModeInfo * mi) +ENTRYPOINT void init_glhanoi(ModeInfo * mi) { + glhcfg *glhanoi; if(!glhanoi_cfg) { glhanoi_cfg = (glhcfg *) calloc(MI_NUM_SCREENS(mi), sizeof(glhcfg)); - if(!glhanoi_cfg) { - fprintf(stderr, "%s: out of memory creating configs\n", - progname); - exit(1); - } - glhanoi = &glhanoi_cfg[MI_SCREEN(mi)]; + checkAllocAndExit(!!glhanoi_cfg, "configuration"); } glhanoi = &glhanoi_cfg[MI_SCREEN(mi)]; glhanoi->glx_context = init_GL(mi); glhanoi->numberOfDisks = MI_BATCHCOUNT(mi); + + if (glhanoi->numberOfDisks <= 1) + glhanoi->numberOfDisks = 3 + (int) BELLRAND(9); + + /* magicnumber is a bitfield, so we can't have more than 31 discs + on a system with 4-byte ints. */ + if (glhanoi->numberOfDisks >= 8 * sizeof(int)) + glhanoi->numberOfDisks = (8 * sizeof(int)) - 1; + glhanoi->maxDiskIdx = glhanoi->numberOfDisks - 1; + + speed = get_float_resource(MI_DISPLAY(mi), "speed", "float"); + /* fprintf(stderr, "speed: %0.2f\n", speed); */ + + glhanoi->numberOfPoles = get_integer_resource(MI_DISPLAY(mi), "poles", "Integer"); + /* Set a number of poles from 3 to numberOfDisks + 1, biased toward lower values, + with probability decreasing linearly. */ + if (glhanoi->numberOfPoles <= 2) + glhanoi->numberOfPoles = 3 + + (int)((1 - sqrt(frand(1.0))) * (glhanoi->numberOfDisks - 1)); + /* fprintf(stderr, "Debug: Num disks: %d; num poles: %d\n", glhanoi->numberOfDisks, glhanoi->numberOfPoles); */ + glhanoi->wire = MI_IS_WIREFRAME(mi); glhanoi->light = light; glhanoi->fog = fog; @@ -1339,22 +1562,19 @@ void init_glhanoi(ModeInfo * mi) reshape_glhanoi(mi, MI_WIDTH(mi), MI_HEIGHT(mi)); if(glhanoi->wire) { - glhanoi->light = FALSE; - glhanoi->fog = FALSE; - glhanoi->texture = FALSE; + glhanoi->light = False; + glhanoi->fog = False; + glhanoi->texture = False; } initLights(!glhanoi->wire && glhanoi->light); - if(makeTextures() != 0) { - fprintf(stderr, "can't allocate memory for marble texture\n"); - exit(EXIT_FAILURE); - } + checkAllocAndExit(!makeTextures(glhanoi), "textures\n"); - initData(); - initView(); - initFloor(); - initTowers(); - initDisks(); + initData(glhanoi); + initView(glhanoi); + initFloor(glhanoi); + initTowers(glhanoi); + initDisks(glhanoi); glEnable(GL_DEPTH_TEST); glEnable(GL_NORMALIZE); @@ -1371,37 +1591,39 @@ void init_glhanoi(ModeInfo * mi) glEnable(GL_FOG); } - glhanoi->duration = START_DURATION; - changeState(START); + changeState(glhanoi, START); } -void draw_glhanoi(ModeInfo * mi) +ENTRYPOINT void draw_glhanoi(ModeInfo * mi) { + glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)]; Display *dpy = MI_DISPLAY(mi); Window window = MI_WINDOW(mi); - glhanoi = &glhanoi_cfg[MI_SCREEN(mi)]; - if(!glhanoi->glx_context) return; + + glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glhanoi->glx_context)); + glPolygonMode(GL_FRONT, glhanoi->wire ? GL_LINE : GL_FILL); glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); + mi->polygon_count = 0; glLoadIdentity(); - update_glhanoi(); - updateView(); + update_glhanoi(glhanoi); + updateView(glhanoi); if(!glhanoi->wire && glhanoi->texture) { glEnable(GL_TEXTURE_2D); } - drawFloor(); + mi->polygon_count += drawFloor(glhanoi); glDisable(GL_TEXTURE_2D); - drawTowers(); - drawDisks(); + mi->polygon_count += drawTowers(glhanoi); + mi->polygon_count += drawDisks(glhanoi); if(mi->fps_p) { do_fps(mi); @@ -1411,7 +1633,7 @@ void draw_glhanoi(ModeInfo * mi) glXSwapBuffers(dpy, window); } -Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event) +ENTRYPOINT Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event) { glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)]; @@ -1454,7 +1676,7 @@ Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event) return False; } -void release_glhanoi(ModeInfo * mi) +ENTRYPOINT void release_glhanoi(ModeInfo * mi) { if(glhanoi_cfg != NULL) { int screen; @@ -1465,11 +1687,12 @@ void release_glhanoi(ModeInfo * mi) glDeleteLists(glh->floorList, 1); glDeleteLists(glh->baseList, 1); glDeleteLists(glh->poleList, 1); + glDeleteLists(glh->textureNames[0], 2); for(j = 0; j < glh->numberOfDisks; ++j) { glDeleteLists(glh->disk[j].displayList, 1); } free(glh->disk); - for(i = 0; i < 3; i++) { + for(i = 0; i < glh->numberOfPoles; i++) { if(glh->pole[i].data != NULL) { free(glh->pole[i].data); } @@ -1478,7 +1701,8 @@ void release_glhanoi(ModeInfo * mi) } free(glhanoi_cfg); glhanoi_cfg = NULL; - glDeleteLists(glhanoi->textureNames[0], 2); } +XSCREENSAVER_MODULE ("GLHanoi", glhanoi) + #endif /* USE_GL */