X-Git-Url: http://git.hungrycats.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=hacks%2Fglx%2Fglhanoi.c;h=6f52b3a1014e9f768dfb3cfaed5a24c4610e0c84;hb=aa75c7476aeaa84cf3abc192b376a8b03c325213;hp=df62a37151bf6e763fce15c006e20eb44bd2183f;hpb=6b1c86cf395f59389e4ece4ea8f4bea2c332745b;p=xscreensaver diff --git a/hacks/glx/glhanoi.c b/hacks/glx/glhanoi.c index df62a371..6f52b3a1 100644 --- a/hacks/glx/glhanoi.c +++ b/hacks/glx/glhanoi.c @@ -1,6 +1,7 @@ /* -*- Mode: C; tab-width: 4 -*- */ -/* glhanoi, Copyright (c) 2005 Dave Atkinson +/* 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 @@ -15,34 +16,41 @@ #include "rotator.h" -#define DEF_DELAY "15000" -#define DEF_DISKS "0" /* < 2 means 3-12 */ -#define DEF_WIRE "False" #define DEF_LIGHT "True" -#define DEF_FPS "False" #define DEF_FOG "False" #define DEF_TEXTURE "True" - -#define DEFAULTS "*delay: " DEF_DELAY "\n" \ - "*count: " DEF_DISKS "\n" \ - "*showFPS: " DEF_FPS "\n" \ - "*wireframe: " DEF_WIRE "\n" - +#define DEF_POLES "0" /* choose random value */ +#define DEF_SPEED "1" +#define DEF_TRAILS "2" + +#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 (seconds). */ #define START_DURATION 1.0 #define FINISH_DURATION 1.0 #define BASE_LENGTH 30.0 #define BOARD_SQUARES 8 +/* Don't draw trail lines till they're this old (sec). + Helps trails not be "attached" to the disks. */ +#define TRAIL_START_DELAY 0.1 + #define MAX_CAMERA_RADIUS 250.0 #define MIN_CAMERA_RADIUS 75.0 #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 { @@ -91,18 +99,37 @@ typedef struct { GLfloat base0; GLfloat base1; GLfloat height; - GLfloat xmin, xmax, ymin; + GLfloat xmin, xmax, ymin, zmin, zmax; GLfloat u1, u2; GLfloat t1, t2; GLfloat ucostheta, usintheta; - GLdouble rotAngle; + GLfloat dx, dz; + GLdouble rotAngle; /* degree of "flipping" so far, during travel */ + GLdouble phi; /* angle of motion in xz plane */ + GLfloat speed; + int polys; } Disk; typedef struct { Disk **data; int count; int size; -} Stack; + GLfloat position[3]; +} 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 { + GLfloat position[3]; + double startTime, endTime; + Bool isEnd; +} TrailPoint; typedef struct { GLXContext *glx_context; @@ -110,22 +137,30 @@ typedef struct { Bool wire; Bool fog; Bool light; + Bool layoutLinear; + GLfloat trailDuration; double startTime; 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]; + GLfloat speed; /* coefficient for how fast the disks move */ + SubProblem *solveStack; + int solveStackSize, solveStackIdx; + Pole *pole; float boardSize; float baseLength; float baseWidth; @@ -133,12 +168,18 @@ typedef struct { float poleRadius; float poleHeight; float poleOffset; + float poleDist; /* distance of poles from center, for round layout */ float diskHeight; + float maxDiskRadius; float *diskPos; /* pre-computed disk positions on rods */ Disk *disk; GLint floorList; GLint baseList; GLint poleList; + int floorpolys, basepolys, polepolys; + int trailQSize; + TrailPoint *trailQ; + int trailQFront, trailQBack; GLfloat camera[3]; GLfloat centre[3]; rotator *the_rotator; @@ -148,15 +189,16 @@ typedef struct { int drag_x; int drag_y; int noise_initted; - - int p[512]; - + int p[512]; } glhcfg; static glhcfg *glhanoi_cfg = NULL; static Bool fog; static Bool light; static Bool texture; +static GLfloat trails; +static int poles; +static GLfloat speed; static XrmOptionDescRec opts[] = { {"-light", ".glhanoi.light", XrmoptionNoArg, "true"}, @@ -164,19 +206,28 @@ static XrmOptionDescRec opts[] = { {"-fog", ".glhanoi.fog", XrmoptionNoArg, "true"}, {"+fog", ".glhanoi.fog", XrmoptionNoArg, "false"}, {"-texture", ".glhanoi.texture", XrmoptionNoArg, "true"}, - {"+texture", ".glhanoi.texture", XrmoptionNoArg, "false"} + {"+texture", ".glhanoi.texture", XrmoptionNoArg, "false"}, + {"-trails", ".glhanoi.trails", XrmoptionSepArg, 0}, + {"-poles", ".glhanoi.poles", XrmoptionSepArg, 0 }, + {"-speed", ".glhanoi.speed", XrmoptionSepArg, 0 } }; static argtype vars[] = { {&light, "light", "Light", DEF_LIGHT, t_Bool}, {&fog, "fog", "Fog", DEF_FOG, t_Bool}, - {&texture, "texture", "Texture", DEF_TEXTURE, t_Bool} + {&texture, "texture", "Texture", DEF_TEXTURE, t_Bool}, + {&trails, "trails", "Trails", DEF_TRAILS, t_Float}, + {&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"}, + {"-trails t", "how long of disk trails to show (sec.)"}, + {"-poles r", "number of poles to move disks between"}, + {"-speed s", "speed multiplier"} }; ENTRYPOINT ModeSpecOpt glhanoi_opts = { countof(opts), opts, countof(vars), vars, desc }; @@ -196,7 +247,9 @@ 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 baseColor[] = { 0.545, 0.137, 0.137 }; */ static const GLfloat fogcolor[] = { 0.5, 0.5, 0.5 }; +static GLfloat trailColor[] = { 1.0, 1.0, 1.0, 0.5 }; static const float left[] = { 1.0, 0.0, 0.0 }; static const float up[] = { 0.0, 1.0, 0.0 }; @@ -217,14 +270,24 @@ 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)]) +/* push disk d onto pole idx */ static Disk *push(glhcfg *glhanoi, int idx, Disk * d) { return DOPUSH(&glhanoi->pole[idx], d); } +/* pop the top disk from pole idx */ static Disk *pop(glhcfg *glhanoi, int idx) { return DOPOP(&glhanoi->pole[idx]); @@ -239,6 +302,7 @@ static 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. */ static int magic(int i) { @@ -252,7 +316,6 @@ static int magic(int i) return count % 2 == 0; } -#if 0 static float distance(float *p0, float *p1) { float x, y, z; @@ -261,13 +324,18 @@ static float distance(float *p0, float *p1) z = p1[2] - p0[2]; return (float)sqrt(x * x + y * y + z * z); } -#endif +/* What is this for? + = c / (a b - 0.25 (a^2 + 2 a b + b^2) ) + = c / (-0.25 (a^2 - 2 a b + b^2) ) + = c / (-0.25 ((a - b)(a - b))) + = -4 c / (a - b)^2 static GLfloat A(GLfloat a, GLfloat b, GLfloat c) { GLfloat sum = a + b; return c / (a * b - 0.25 * sum * sum); } +*/ static void moveSetup(glhcfg *glhanoi, Disk * disk) { @@ -277,35 +345,55 @@ static void moveSetup(glhcfg *glhanoi, Disk * disk) int dst = glhanoi->dst; GLfloat theta; GLfloat sintheta, costheta; + double dh; + double dx, dz; /* total x and z distances from src to dst */ + Pole *poleSrc, *poleDst; + + poleSrc = &(glhanoi->pole[src]); + poleDst = &(glhanoi->pole[dst]); - if(glhanoi->state != FINISHED && random() % 6 == 0) { - disk->rotAngle = - -180.0 * (2 - 2 * random() % 2) * (random() % 3 + 1); + disk->xmin = poleSrc->position[0]; + /* glhanoi->poleOffset * (src - (glhanoi->numberOfPoles - 1.0f) * 0.5); */ + disk->xmax = poleDst->position[0]; + /* disk->xmax = glhanoi->poleOffset * (dst - (glhanoi->numberOfPoles - 1.0f) * 0.5); */ + disk->ymin = glhanoi->poleHeight; + disk->zmin = poleSrc->position[2]; + disk->zmax = poleDst->position[2]; + + dx = disk->xmax - disk->xmin; + dz = disk->zmax - disk->zmin; + + if(glhanoi->state != FINISHED) { + double xxx = ((dx < 0) ? 180.0 : -180.0); + if(random() % 6 == 0) { + disk->rotAngle = xxx * (2 - 2 * random() % 2) * (random() % 3 + 1); + } else { + disk->rotAngle = xxx; + } + if(random() % 4 == 0) { + /* Backflip */ + disk->rotAngle = -disk->rotAngle; + } } else { disk->rotAngle = -180.0; } - disk->base0 = glhanoi->diskPos[glhanoi->pole[src].count]; - disk->base1 = - glhanoi->state == - FINISHED ? disk->base0 : glhanoi->diskPos[glhanoi->pole[dst]. - count]; - - disk->xmin = glhanoi->poleOffset * (src - 1); - disk->xmax = glhanoi->poleOffset * (dst - 1); - 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); - + disk->base0 = glhanoi->diskPos[poleSrc->count]; + disk->base1 = (glhanoi->state == FINISHED) ? + disk->base0 : glhanoi->diskPos[poleDst->count]; + + /* horizontal distance to travel? */ + /* was: absx = sqrt(disk->xmax - disk->xmin); */ + dh = distance(poleSrc->position, poleDst->position); + /* absx = sqrt(dh); */ + ymax = glhanoi->poleHeight + dh; + if(glhanoi->state == FINISHED) { + ymax += dh * (double)(glhanoi->numberOfDisks - disk->id); + } h = ymax - disk->ymin; - theta = atan((disk->xmin - disk->xmax) * A(disk->xmin, disk->xmax, h)); + /* A(a, b, c) = -4 c / (a - b)^2 */ + /* theta = atan(4 h / (b - a)) */ + theta = atan(4 * h / dh); if(theta < 0.0) theta += M_PI; costheta = cos(theta); @@ -313,33 +401,177 @@ static void moveSetup(glhcfg *glhanoi, Disk * disk) u = (float) sqrt(fabs (-g / - (2.0 * A(disk->xmin, disk->xmax, h) * costheta * costheta))); + /* (2.0 * A(disk->xmin, disk->xmax, h) * costheta * costheta))); */ + (2.0 * -4 * h / (dh * dh) * costheta * costheta))); disk->usintheta = u * sintheta; disk->ucostheta = u * costheta; + /* Not to be confused: disk->dx is the per-time-unit portion of dx */ + disk->dx = disk->ucostheta * dx / dh; + disk->dz = disk->ucostheta * dz / dh; disk->t1 = (-u + sqrt(u * u + 2.0 * g * fabs(disk->ymin - disk->base0))) / g; disk->u1 = u + g * disk->t1; disk->t2 = 2.0 * disk->usintheta / g; disk->u2 = disk->usintheta - g * disk->t2; + + /* Compute direction of travel, in the XZ plane. */ + disk->phi = atan(dz / dx); + disk->phi *= 180.0 / M_PI; /* convert radians to degrees */ +} + +/* 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; + + for (z = 128, i = 0; z > 0; z >>= 1, i++) { + b[i] = ((x & z) == z) ? '1' : '0'; + } + b[i] = '\0'; + + 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); + } + + 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; + } + return -1; +} + +/* 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) { - int fudge = glhanoi->move + 2; - int magicNumber = magic(fudge); + 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->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. */ + } + } } - glhanoi->magicNumber = magicNumber; } static double lerp(double alpha, double start, double end) @@ -351,28 +583,67 @@ static void upfunc(GLdouble t, Disk * d) { d->position[0] = d->xmin; d->position[1] = d->base0 + (d->u1 - 0.5 * g * t) * t; + d->position[2] = d->zmin; d->rotation[1] = 0.0; } static void parafunc(GLdouble t, Disk * d) { - d->position[0] = d->xmin + d->ucostheta * t; + /* ##was: d->position[0] = d->xmin + d->ucostheta * t; */ + d->position[0] = d->xmin + d->dx * t; + d->position[2] = d->zmin + d->dz * 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->rotation[1] = d->rotAngle * t / d->t2; + /* d->rotAngle * (d->position[0] - d->xmin) / (d->xmax - d->xmin); */ } static void downfunc(GLdouble t, Disk * d) { d->position[0] = d->xmax; d->position[1] = d->ymin + (d->u2 - 0.5 * g * t) * t; - + d->position[2] = d->zmax; + d->rotation[1] = 0.0; } -static Bool computePosition(GLfloat t, Disk * d) +#define normalizeQ(i) ((i) >= glhanoi->trailQSize ? (i) - glhanoi->trailQSize : (i)) +#define normalizeQNeg(i) ((i) < 0 ? (i) + glhanoi->trailQSize : (i)) + +/* Add trail point at position posn at time t onto back of trail queue. + Removes old trails if necessary to make room. */ +static void enQTrail(glhcfg *glhanoi, GLfloat *posn) +{ + if (glhanoi->trailQSize && glhanoi->state != MONEY_SHOT) { + TrailPoint *tp = &(glhanoi->trailQ[glhanoi->trailQBack]); + double t = getTime(); + + tp->position[0] = posn[0]; + tp->position[1] = posn[1] + glhanoi->diskHeight; + /* Slight jitter to prevent clashing with other trails */ + tp->position[2] = posn[2] + (glhanoi->move % 23) * 0.01; + tp->startTime = t + TRAIL_START_DELAY; + tp->endTime = t + TRAIL_START_DELAY + glhanoi->trailDuration; + tp->isEnd = False; + + /* Update queue back/front indices */ + glhanoi->trailQBack = normalizeQ(glhanoi->trailQBack + 1); + if (glhanoi->trailQBack == glhanoi->trailQFront) + glhanoi->trailQFront = normalizeQ(glhanoi->trailQFront + 1); + } +} + +/* Mark last trailpoint in queue as the end of a trail. */ +/* was: #define endTrail(glh) ((glh)->trailQ[(glh)->trailQBack].isEnd = True) */ +static void endTrail(glhcfg *glhanoi) { + if (glhanoi->trailQSize) + glhanoi->trailQ[normalizeQNeg(glhanoi->trailQBack - 1)].isEnd = True; +} + +/* Update disk d's position and rotation based on time t. + Returns true iff move is finished. */ +static Bool computePosition(glhcfg *glhanoi, GLfloat t, Disk * d) { Bool finished = False; @@ -380,11 +651,13 @@ static Bool computePosition(GLfloat t, Disk * d) upfunc(t, d); } else if(t < d->t1 + d->t2) { parafunc(t - d->t1, d); + enQTrail(glhanoi, d->position); } else { downfunc(t - d->t1 - d->t2, d); if(d->position[1] <= d->base1) { d->position[1] = d->base1; finished = True; + endTrail(glhanoi); } } return finished; @@ -402,6 +675,7 @@ static void updateView(glhcfg *glhanoi) longitude += glhanoi->camera[0]; latitude += glhanoi->camera[1]; radius += glhanoi->camera[2]; + /* FUTURE: tweak this to be smooth: */ longitude = longitude - floor(longitude); latitude = latitude - floor(latitude); radius = radius - floor(radius); @@ -411,7 +685,7 @@ static void updateView(glhcfg *glhanoi) if(radius > 0.5) { radius = 1.0 - radius; } - + b = glhanoi->centre[1]; c = (MIN_CAMERA_RADIUS + radius * (MAX_CAMERA_RADIUS - MIN_CAMERA_RADIUS)); @@ -434,6 +708,13 @@ static void changeState(glhcfg *glhanoi, State state) glhanoi->startTime = getTime(); } +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; @@ -455,13 +736,14 @@ static void update_glhanoi(glhcfg *glhanoi) break; case MOVE_DISK: - if(computePosition(t, glhanoi->currentDisk)) { + if(computePosition(glhanoi, t * glhanoi->currentDisk->speed, glhanoi->currentDisk)) { changeState(glhanoi, MOVE_FINISHED); } break; case MOVE_FINISHED: - if(++glhanoi->move < glhanoi->numberOfMoves) { + ++glhanoi->move; + if(!finishedHanoi(glhanoi)) { makeMove(glhanoi); changeState(glhanoi, MOVE_DISK); } else { @@ -471,9 +753,8 @@ static void update_glhanoi(glhcfg *glhanoi) break; case FINISHED: - while(t < glhanoi->duration) { + if (t < glhanoi->duration) break; - } glhanoi->src = glhanoi->olddst; glhanoi->dst = glhanoi->oldsrc; for(i = 0; i < glhanoi->numberOfDisks; ++i) { @@ -498,7 +779,7 @@ static void update_glhanoi(glhcfg *glhanoi) continue; } - finished = computePosition(t - delay, &glhanoi->disk[i]); + finished = computePosition(glhanoi, t - delay, &glhanoi->disk[i]); glhanoi->disk[i].rotation[1] = 0.0; if(!finished) { @@ -594,10 +875,11 @@ static void setMaterial(const GLfloat color[3], const GLfloat hlite[3], int shin * people's hardware supports 3D textures, so I didn't bother (xorg * ATI server doesn't :-( ) */ -static 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); @@ -606,7 +888,6 @@ static void drawTube(GLdouble bottomRadius, GLdouble topRadius, GLint lastSlice = nSlice - 1; GLfloat radius; GLfloat innerRadius; - GLfloat maxRadius; if(bottomThickness > bottomRadius) { bottomThickness = bottomRadius; @@ -620,11 +901,11 @@ static 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; @@ -659,6 +940,7 @@ static void drawTube(GLdouble bottomRadius, GLdouble topRadius, /* yTexCoord, */ /* midTexCoord + cosCache[slice] * outerTexCoordSize); */ glVertex3f(radius * sinCache[slice], y, radius * cosCache[slice]); + polys++; } glEnd(); @@ -684,10 +966,12 @@ static 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 */ @@ -706,6 +990,7 @@ static void drawTube(GLdouble bottomRadius, GLdouble topRadius, upperRadius * cosCache[slice]); glVertex3f(lowerRadius * sinCache[slice], lowerY, lowerRadius * cosCache[slice]); + polys++; } glEnd(); } @@ -722,25 +1007,28 @@ static 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; } -static 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); } -static 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); } -static void drawCuboid(GLfloat length, GLfloat width, GLfloat height) +/* used for drawing base */ +static int drawCuboid(GLfloat length, GLfloat width, GLfloat height) { GLfloat xmin = -length / 2.0f; GLfloat xmax = length / 2.0f; @@ -748,6 +1036,7 @@ static 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 */ @@ -756,42 +1045,181 @@ static 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; +} + +/* Set normal vector in xz plane, based on rotation around center. */ +static void setNormalV(glhcfg *glhanoi, GLfloat theta, int y1, int y2, int r1) { + if (y1 == y2) /* up/down */ + glNormal3f(0.0, y1 ? 1.0 : -1.0, 0.0); + else if (!r1) /* inward */ + glNormal3f(-cos(theta), 0.0, -sin(theta)); + else /* outward */ + glNormal3f(cos(theta), 0.0, sin(theta)); +} + +/* y1, r1, y2, r2 are indices into y, r, beg, end */ +static int drawBaseStrip(glhcfg *glhanoi, int y1, int r1, int y2, int r2, + GLfloat y[2], GLfloat r[2], GLfloat beg[2][2], GLfloat end[2][2]) { + int i; + GLfloat theta, costh, sinth, x[2], z[2]; + GLfloat theta1 = (M_PI * 2) / (glhanoi->numberOfPoles + 1); + + glBegin(GL_QUAD_STRIP); + + /* beginning edge */ + glVertex3f(beg[r1][0], y[y1], beg[r1][1]); + glVertex3f(beg[r2][0], y[y2], beg[r2][1]); + setNormalV(glhanoi, theta1, y1, y2, r1); + + for (i = 1; i < glhanoi->numberOfPoles; i++) { + theta = theta1 * (i + 0.5); + costh = cos(theta); + sinth = sin(theta); + x[0] = costh * r[0]; + x[1] = costh * r[1]; + z[0] = sinth * r[0]; + z[1] = sinth * r[1]; + + glVertex3f(x[r1], y[y1], z[r1]); + glVertex3f(x[r2], y[y2], z[r2]); + + setNormalV(glhanoi, theta1 * (i + 1), y1, y2, r1); + } + + /* end edge */ + glVertex3f(end[r1][0], y[y1], end[r1][1]); + glVertex3f(end[r2][0], y[y2], end[r2][1]); + setNormalV(glhanoi, glhanoi->numberOfPoles, y1, y2, r1); + glEnd(); + return glhanoi->numberOfPoles; } -static void drawDisks(glhcfg *glhanoi) +/* Draw base such that poles are distributed around a regular polygon. */ +static int drawRoundBase(glhcfg *glhanoi) { + int polys = 0; + GLfloat theta, sinth, costh; + + /* + r[0] = (minimum) inner radius of base at vertices + r[1] = (minimum) outer radius of base at vertices + y[0] = bottom of base + y[1] = top of base */ + GLfloat r[2], y[2]; + /* positions of end points: beginning, end. + beg[0] is inner corner of beginning of base, beg[1] is outer corner. + beg[i][0] is x, [i][1] is z. */ + GLfloat beg[2][2], end[2][2], begNorm, endNorm; + /* ratio of radius at base vertices to ratio at poles */ + GLfloat longer = 1.0 / cos(M_PI / (glhanoi->numberOfPoles + 1)); + + r[0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * longer; + r[1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * longer; + y[0] = 0; + y[1] = glhanoi->baseHeight; + + /* compute beg, end. Make the ends square. */ + theta = M_PI * 2 / (glhanoi->numberOfPoles + 1); + + costh = cos(theta); + sinth = sin(theta); + beg[0][0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * costh + + glhanoi->maxDiskRadius * sinth; + beg[1][0] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * costh + + glhanoi->maxDiskRadius * sinth; + beg[0][1] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * sinth - + glhanoi->maxDiskRadius * costh; + beg[1][1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * sinth - + glhanoi->maxDiskRadius * costh; + begNorm = theta - M_PI * 0.5; + + theta = M_PI * 2 * glhanoi->numberOfPoles / (glhanoi->numberOfPoles + 1); + + costh = cos(theta); + sinth = sin(theta); + end[0][0] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * costh - + glhanoi->maxDiskRadius * sinth; + end[1][0] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * costh - + glhanoi->maxDiskRadius * sinth; + end[0][1] = (glhanoi->poleDist - glhanoi->maxDiskRadius) * sinth + + glhanoi->maxDiskRadius * costh; + end[1][1] = (glhanoi->poleDist + glhanoi->maxDiskRadius) * sinth + + glhanoi->maxDiskRadius * costh; + endNorm = theta + M_PI * 0.5; + + /* bottom: never seen + polys = drawBaseStrip(glhanoi, 0, 0, 0, 1, y, r, beg, end); */ + /* outside edge */ + polys += drawBaseStrip(glhanoi, 0, 1, 1, 1, y, r, beg, end); + /* top */ + polys += drawBaseStrip(glhanoi, 1, 1, 1, 0, y, r, beg, end); + /* inside edge */ + polys += drawBaseStrip(glhanoi, 1, 0, 0, 0, y, r, beg, end); + + /* Draw ends */ + glBegin(GL_QUADS); + + glVertex3f(beg[0][0], y[1], beg[0][1]); + glVertex3f(beg[1][0], y[1], beg[1][1]); + glVertex3f(beg[1][0], y[0], beg[1][1]); + glVertex3f(beg[0][0], y[0], beg[0][1]); + glNormal3f(cos(begNorm), 0, sin(begNorm)); + + glVertex3f(end[0][0], y[0], end[0][1]); + glVertex3f(end[1][0], y[0], end[1][1]); + glVertex3f(end[1][0], y[1], end[1][1]); + glVertex3f(end[0][0], y[1], end[0][1]); + glNormal3f(cos(endNorm), 0, sin(endNorm)); + + polys += 2; + + glEnd(); + + return polys; +} + +static int drawDisks(glhcfg *glhanoi) { int i; + int polys = 0; glPushMatrix(); glTranslatef(0.0f, glhanoi->baseHeight, 0.0f); @@ -804,59 +1232,91 @@ static void drawDisks(glhcfg *glhanoi) glTranslatef(pos[0], pos[1], pos[2]); if(rot[1] != 0.0) { glTranslatef(0.0, glhanoi->diskHeight / 2.0, 0.0); + /* rotate around different axis depending on phi */ + if (disk->phi != 0.0) + glRotatef(-disk->phi, 0.0, 1.0, 0.0); glRotatef(rot[1], 0.0, 0.0, 1.0); + if (disk->phi != 0.0) + glRotatef(disk->phi, 0.0, 1.0, 0.0); glTranslatef(0.0, -glhanoi->diskHeight / 2.0, 0.0); } glCallList(disk->displayList); + polys += disk->polys; glPopMatrix(); } glPopMatrix(); + return polys; } static GLfloat getDiskRadius(glhcfg *glhanoi, int i) { - return ((GLfloat) i + 3.0) * glhanoi->poleRadius; + GLfloat retVal = glhanoi->maxDiskRadius * + ((GLfloat) i + 3.0) / (glhanoi->numberOfDisks + 3.0); + return retVal; } static void initData(glhcfg *glhanoi) { - GLfloat maxDiskRadius; int i; + GLfloat sinPiOverNP; glhanoi->baseLength = BASE_LENGTH; - glhanoi->poleRadius = glhanoi->baseLength / - (2.0 * (3 * glhanoi->numberOfDisks + 7.0)); - maxDiskRadius = getDiskRadius(glhanoi, glhanoi->numberOfDisks); - glhanoi->baseWidth = 2.0 * maxDiskRadius; + if (glhanoi->layoutLinear) { + glhanoi->maxDiskRadius = glhanoi->baseLength / + (2 * 0.95 * glhanoi->numberOfPoles); + } else { + sinPiOverNP = sin(M_PI / (glhanoi->numberOfPoles + 1)); + glhanoi->maxDiskRadius = (sinPiOverNP * glhanoi->baseLength * 0.5 * 0.95) / (1 + sinPiOverNP); + } + + glhanoi->poleDist = glhanoi->baseLength * 0.5 - glhanoi->maxDiskRadius; + glhanoi->poleRadius = glhanoi->maxDiskRadius / (glhanoi->numberOfDisks + 3.0); + /* fprintf(stderr, "Debug: baseL = %f, maxDiskR = %f, poleR = %f\n", + glhanoi->baseLength, glhanoi->maxDiskRadius, glhanoi->poleRadius); */ + glhanoi->baseWidth = 2.0 * glhanoi->maxDiskRadius; 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; + /* use golden ratio */ 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"); + + if (glhanoi->trailQSize) { + glhanoi->trailQ = (TrailPoint *)calloc(glhanoi->trailQSize, sizeof(TrailPoint)); + checkAllocAndExit(!!glhanoi->trailQ, "trail queue"); + } else glhanoi->trailQ = (TrailPoint *)NULL; + glhanoi->trailQFront = glhanoi->trailQBack = 0; + glhanoi->the_rotator = make_rotator(0.1, 0.025, 0, 1, 0.005, False); + /* or glhanoi->the_rotator = make_rotator(0.025, 0.025, 0.025, 0.5, 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; + } } static void initView(glhcfg *glhanoi) @@ -928,15 +1388,19 @@ static double improved_noise(glhcfg *glhanoi, double x, double y, double z) 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 = 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 */ + 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)))); @@ -987,16 +1451,25 @@ static GLubyte *makeTexture(glhcfg *glhanoi, int x_size, int y_size, int z_size, return textureData; } -static 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; } @@ -1060,17 +1533,20 @@ static void setTexture(glhcfg *glhanoi, int n) glBindTexture(GL_TEXTURE_2D, glhanoi->textureNames[n]); } +/* 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(glhanoi, MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 1, - makeMarbleTexture, &marbleColours)) == NULL) { + makeMarbleTexture, marbleColours)) == NULL) { return 1; } @@ -1083,6 +1559,7 @@ static int makeTextures(glhcfg *glhanoi) MARBLE_TEXTURE_SIZE, MARBLE_TEXTURE_SIZE, 0, GL_RGBA, GL_UNSIGNED_BYTE, marbleTexture); free(marbleTexture); + freeTexCols(marbleColours); return 0; } @@ -1096,10 +1573,8 @@ static void initFloor(glhcfg *glhanoi) 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; @@ -1137,44 +1612,63 @@ static void initFloor(glhcfg *glhanoi) glTexCoord2d(tx1, tz0); glVertex3f(x1, 0.0, z0); + glhanoi->floorpolys++; glEnd(); } } glEndList(); } -static void initTowers(glhcfg *glhanoi) +static void initBase(glhcfg *glhanoi) { - if((glhanoi->baseList = glGenLists(1)) == 0) { - fprintf(stderr, "can't allocate memory for towers display list\n"); - exit(EXIT_FAILURE); - } + 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); + if (glhanoi->layoutLinear) { + glhanoi->basepolys = drawCuboid(glhanoi->baseLength, glhanoi->baseWidth, + glhanoi->baseHeight); + } else { + glhanoi->basepolys = drawRoundBase(glhanoi); + } glEndList(); +} +static void initTowers(glhcfg *glhanoi) +{ + int i; + + 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); - glPopMatrix(); + for (i = 0; i < glhanoi->numberOfPoles; i++) { + GLfloat *p = glhanoi->pole[i].position; + GLfloat rad = (M_PI * 2.0 * (i + 1)) / (glhanoi->numberOfPoles + 1); + + p[1] = glhanoi->baseHeight; + + if (glhanoi->layoutLinear) { + /* Linear: */ + p[0] = -glhanoi->poleOffset * ((glhanoi->numberOfPoles - 1) * 0.5f - i); + p[2] = 0.0f; + } else { + /* Circular layout: */ + p[0] = cos(rad) * glhanoi->poleDist; + p[2] = sin(rad) * glhanoi->poleDist; + } + + glPushMatrix(); + glTranslatef(p[0], p[1], p[2]); + glhanoi->polepolys = drawPole(glhanoi->poleRadius, glhanoi->poleHeight); + glPopMatrix(); + + } glEndList(); } +/* Parameterized hue based on input 0.0 - 1.0. */ static double cfunc(double x) { #define COMP < @@ -1182,6 +1676,7 @@ static double cfunc(double x) 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) { @@ -1196,11 +1691,8 @@ static double cfunc(double x) 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); @@ -1210,28 +1702,33 @@ static void initDisks(glhcfg *glhanoi) Disk *disk = &glhanoi->disk[i]; disk->id = i; - disk->position[0] = -glhanoi->poleOffset; + disk->position[0] = glhanoi->pole[0].position[0]; /* -glhanoi->poleOffset * (glhanoi->numberOfPoles - 1.0f) * 0.5; */ disk->position[1] = glhanoi->diskHeight * height; - disk->position[2] = 0.0; + disk->position[2] = glhanoi->pole[0].position[2]; 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, glhanoi->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(glhanoi, 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) { @@ -1263,15 +1760,85 @@ static void initLights(Bool state) } } -static void drawFloor(glhcfg *glhanoi) +static int drawFloor(glhcfg *glhanoi) { glCallList(glhanoi->floorList); + return glhanoi->floorpolys; } -static void drawTowers(glhcfg *glhanoi) +static int drawTowers(glhcfg *glhanoi) { glCallList(glhanoi->baseList); glCallList(glhanoi->poleList); + return glhanoi->basepolys + glhanoi->polepolys; +} + +static int drawTrails1(glhcfg *glhanoi, double t, double thickness, double alpha) { + int i, prev = -1, lines = 0; + Bool fresh = False; + GLfloat trailDurInv = 1.0f / glhanoi->trailDuration; + + glLineWidth(thickness); + + glBegin(GL_LINES); + + for (i = glhanoi->trailQFront; + i != glhanoi->trailQBack; + i = normalizeQ(i + 1)) { + TrailPoint *tqi = &(glhanoi->trailQ[i]); + + if (!fresh && t > tqi->endTime) { + glhanoi->trailQFront = normalizeQ(i + 1); + } else { + if (tqi->startTime > t) break; + /* Found trails that haven't timed out. */ + if (!fresh) fresh = True; + if (prev > -1) { + /* Fade to invisible with age */ + trailColor[3] = alpha * (tqi->endTime - t) * trailDurInv; + /* Can't use setMaterial(trailColor, cBlack, 0) because our color needs an alpha value. */ + glColor4fv(trailColor); + glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, trailColor); + /* FUTURE: to really do this right, trails should be drawn in back-to-front + order, so that blending is done correctly. + Currently it looks poor when a faded trail is in front of, or coincident with, + a bright trail but is drawn first. + I think for now it's good enough to recommend shorter trails so they + never/rarely overlap. + A jitter per trail arc would also mitigate this problem, to a lesser degree. */ + glVertex3fv(glhanoi->trailQ[prev].position); + glVertex3fv(glhanoi->trailQ[i].position); + lines++; + } + if (glhanoi->trailQ[i].isEnd) + prev = -1; + else + prev = i; + } + } + + glEnd(); + + return lines; +} + +static int drawTrails(glhcfg *glhanoi) { + int lines = 0; + double t = getTime(); + + glEnable (GL_BLEND); + glBlendFunc (GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); + glMaterialfv(GL_FRONT, GL_SPECULAR, cBlack); + glMateriali(GL_FRONT, GL_SHININESS, 0); + + /* Draw them twice, with different widths and opacities, to make them smoother. */ + lines = drawTrails1(glhanoi, t, 1.0, 0.75); + lines += drawTrails1(glhanoi, t, 2.5, 0.5); + + glDisable (GL_BLEND); + + /* fprintf(stderr, "Drew trails: %d lines\n", lines); */ + return lines; } /* Window management, etc @@ -1297,31 +1864,47 @@ ENTRYPOINT void init_glhanoi(ModeInfo * mi) 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); - } + 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; + /* 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; + + 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)); + glhanoi->wire = MI_IS_WIREFRAME(mi); + +# ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */ + glhanoi->wire = 0; +# endif + glhanoi->light = light; glhanoi->fog = fog; glhanoi->texture = texture; - + glhanoi->speed = speed; + glhanoi->trailDuration = trails; + /* set trailQSize based on 60 fps (a maximum, more or less) */ + /* FUTURE: Should clamp framerate to 60 fps? See flurry.c's draw_flurry(). + The only bad effect if we don't is that trail-ends could + show "unnatural" pauses at high fps. */ + glhanoi->trailQSize = (int)(trails * 60.0); + reshape_glhanoi(mi, MI_WIDTH(mi), MI_HEIGHT(mi)); if(glhanoi->wire) { @@ -1331,14 +1914,15 @@ ENTRYPOINT void init_glhanoi(ModeInfo * mi) } initLights(!glhanoi->wire && glhanoi->light); - if(makeTextures(glhanoi) != 0) { - fprintf(stderr, "can't allocate memory for marble texture\n"); - exit(EXIT_FAILURE); - } + checkAllocAndExit(!makeTextures(glhanoi), "textures\n"); + /* Choose linear or circular layout. Could make this a user option. */ + glhanoi->layoutLinear = (glhanoi->numberOfPoles == 3); + initData(glhanoi); initView(glhanoi); initFloor(glhanoi); + initBase(glhanoi); initTowers(glhanoi); initDisks(glhanoi); @@ -1357,40 +1941,55 @@ ENTRYPOINT void init_glhanoi(ModeInfo * mi) glEnable(GL_FOG); } - glhanoi->duration = START_DURATION; changeState(glhanoi, START); } ENTRYPOINT void draw_glhanoi(ModeInfo * mi) { - glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)]; + glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)]; Display *dpy = MI_DISPLAY(mi); Window window = MI_WINDOW(mi); if(!glhanoi->glx_context) return; - glXMakeCurrent(MI_DISPLAY(mi), MI_WINDOW(mi), *(glhanoi->glx_context)); + 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(); + glRotatef(current_device_rotation(), 0, 0, 1); update_glhanoi(glhanoi); updateView(glhanoi); +# ifdef HAVE_MOBILE /* Keep it the same relative size when rotated. */ + { + GLfloat h = MI_HEIGHT(mi) / (GLfloat) MI_WIDTH(mi); + int o = (int) current_device_rotation(); + if (o != 0 && o != 180 && o != -180) + glScalef (1/h, 1/h, 1/h); + } +# endif + if(!glhanoi->wire && glhanoi->texture) { glEnable(GL_TEXTURE_2D); } - drawFloor(glhanoi); + mi->polygon_count += drawFloor(glhanoi); glDisable(GL_TEXTURE_2D); - drawTowers(glhanoi); - drawDisks(glhanoi); + mi->polygon_count += drawTowers(glhanoi); + mi->polygon_count += drawDisks(glhanoi); + if (glhanoi->trailQSize) { + /* No polygons, just lines. So ignore the return count. */ + (void)drawTrails(glhanoi); + } + if(mi->fps_p) { do_fps(mi); } @@ -1403,6 +2002,8 @@ ENTRYPOINT Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event) { glhcfg *glhanoi = &glhanoi_cfg[MI_SCREEN(mi)]; + /* #### this is all wrong on iOS -- should be using gltrackball. */ + if(event->xany.type == ButtonPress && event->xbutton.button == Button1) { glhanoi->button_down_p = True; glhanoi->drag_x = event->xbutton.x; @@ -1439,6 +2040,13 @@ ENTRYPOINT Bool glhanoi_handle_event(ModeInfo * mi, XEvent * event) return True; } +#if 0 /* #### doesn't work */ + else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event)) + { + changeState(glhanoi, START); + return True; + } +#endif return False; } @@ -1458,7 +2066,7 @@ ENTRYPOINT void release_glhanoi(ModeInfo * mi) 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); }