3D-головоломка, яка може вирішитися автоматично на основі функціоналу OpenGL.
.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <malloc.h>
#include <time.h>
#include <math.h>
#include <GL/glut.h>
#include "trackball.h"
#define WIDTH 4
#define HEIGHT 5
#define PIECES 10
#define OFFSETX -2
#define OFFSETY -2.5
#define OFFSETZ -0.5
typedef char Config[HEIGHT][WIDTH];
struct puzzle {
struct puzzle *backptr;
struct puzzle *solnptr;
Config pieces;
struct puzzle *next;
unsigned hashvalue;
};
#define HASHSIZE 10691
struct puzzlelist {
struct puzzle *puzzle;
struct puzzlelist *next;
};
static char convert[PIECES + 1] =
{0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4};
static unsigned char colors[PIECES + 1][3] =
{
{0, 0, 0},
{255, 255, 127},
{255, 255, 127},
{255, 255, 127},
{255, 255, 127},
{255, 127, 255},
{255, 127, 255},
{255, 127, 255},
{255, 127, 255},
{255, 127, 127},
{255, 255, 255},
};
void changeState(void);
static struct puzzle *hashtable[HASHSIZE];
static struct puzzle *startPuzzle;
static struct puzzlelist *puzzles;
static struct puzzlelist *lastentry;
int curX, curY, visible;
#define MOVE_SPEED 0.2
static unsigned char movingPiece;
static float move_x, move_y;
static float curquat[4];
static int doubleBuffer = 1;
static int depth = 1;
static char xsize[PIECES + 1] =
{0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2};
static char ysize[PIECES + 1] =
{0, 1, 1, 1, 1, 2, 2, 2, 2, 1, 2};
static float zsize[PIECES + 1] =
{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0.6};
static Config startConfig =
{
{8, 10, 10, 7},
{8, 10, 10, 7},
{6, 9, 9, 5},
{6, 4, 3, 5},
{2, 0, 0, 1}
};
static Config thePuzzle =
{
{8, 10, 10, 7},
{8, 10, 10, 7},
{6, 9, 9, 5},
{6, 4, 3, 5},
{2, 0, 0, 1}
};
static int xadds[4] =
{-1, 0, 1, 0};
static int yadds[4] =
{0, -1, 0, 1};
static int W = 400, H = 300;
static GLint viewport[4];
#define srandom srand
#define random() (rand() >> 2)
unsigned
hash(Config config)
{
int i, j, value;
value = 0;
for (i = 0; i < HEIGHT; i++) {
for (j = 0; j < WIDTH; j++) {
value = value + convert[config[i][j]];
value *= 6;
}
}
return (value);
}
int
solution(Config config)
{
if (config[4][1] == 10 && config[4][2] == 10)
return (1);
return (0);
}
float boxcoords[][3] =
{
{0.2, 0.2, 0.9},
{0.8, 0.2, 0.9},
{0.8, 0.8, 0.9},
{0.2, 0.8, 0.9},
{0.2, 0.1, 0.8},
{0.8, 0.1, 0.8},
{0.9, 0.2, 0.8},
{0.9, 0.8, 0.8},
{0.8, 0.9, 0.8},
{0.2, 0.9, 0.8},
{0.1, 0.8, 0.8},
{0.1, 0.2, 0.8},
{0.2, 0.1, 0.2},
{0.8, 0.1, 0.2},
{0.9, 0.2, 0.2},
{0.9, 0.8, 0.2},
{0.8, 0.9, 0.2},
{0.2, 0.9, 0.2},
{0.1, 0.8, 0.2},
{0.1, 0.2, 0.2},
{0.2, 0.2, 0.1},
{0.8, 0.2, 0.1},
{0.8, 0.8, 0.1},
{0.2, 0.8, 0.1},
};
float boxnormals[][3] =
{
{0, 0, 1}, /* 0 */
{0, 1, 0},
{1, 0, 0},
{0, 0, -1},
{0, -1, 0},
{-1, 0, 0},
{0.7071, 0.7071, 0.0000}, /* 6 */
{0.7071, -0.7071, 0.0000},
{-0.7071, 0.7071, 0.0000},
{-0.7071, -0.7071, 0.0000},
{0.7071, 0.0000, 0.7071}, /* 10 */
{0.7071, 0.0000, -0.7071},
{-0.7071, 0.0000, 0.7071},
{-0.7071, 0.0000, -0.7071},
{0.0000, 0.7071, 0.7071}, /* 14 */
{0.0000, 0.7071, -0.7071},
{0.0000, -0.7071, 0.7071},
{0.0000, -0.7071, -0.7071},
{0.5774, 0.5774, 0.5774}, /* 18 */
{0.5774, 0.5774, -0.5774},
{0.5774, -0.5774, 0.5774},
{0.5774, -0.5774, -0.5774},
{-0.5774, 0.5774, 0.5774},
{-0.5774, 0.5774, -0.5774},
{-0.5774, -0.5774, 0.5774},
{-0.5774, -0.5774, -0.5774},
};
int boxfaces[][4] =
{
{0, 1, 2, 3}, /* 0 */
{9, 8, 16, 17},
{6, 14, 15, 7},
{20, 23, 22, 21},
{12, 13, 5, 4},
{19, 11, 10, 18},
{7, 15, 16, 8}, /* 6 */
{13, 14, 6, 5},
{18, 10, 9, 17},
{19, 12, 4, 11},
{1, 6, 7, 2}, /* 10 */
{14, 21, 22, 15},
{11, 0, 3, 10},
{20, 19, 18, 23},
{3, 2, 8, 9}, /* 14 */
{17, 16, 22, 23},
{4, 5, 1, 0},
{20, 21, 13, 12},
{2, 7, 8, -1}, /* 18 */
{16, 15, 22, -1},
{5, 6, 1, -1},
{13, 21, 14, -1},
{10, 3, 9, -1},
{18, 17, 23, -1},
{11, 4, 0, -1},
{20, 12, 19, -1},
};
#define NBOXFACES (sizeof(boxfaces)/sizeof(boxfaces[0]))
/* Draw a box. Bevel as desired. */
void
drawBox(int piece, float xoff, float yoff)
{
int xlen, ylen;
int i, k;
float x, y, z;
float zlen;
float *v;
xlen = xsize[piece];
ylen = ysize[piece];
zlen = zsize[piece];
glColor3ubv(colors[piece]);
glBegin(GL_QUADS);
for (i = 0; i < 18; i++) {
glNormal3fv(boxnormals[i]);
for (k = 0; k < 4; k++) {
if (boxfaces[i][k] == -1)
continue;
v = boxcoords[boxfaces[i][k]];
x = v[0] + OFFSETX;
if (v[0] > 0.5)
x += xlen - 1;
y = v[1] + OFFSETY;
if (v[1] > 0.5)
y += ylen - 1;
z = v[2] + OFFSETZ;
if (v[2] > 0.5)
z += zlen - 1;
glVertex3f(xoff + x, yoff + y, z);
}
}
glEnd();
glBegin(GL_TRIANGLES);
for (i = 18; i < NBOXFACES; i++) {
glNormal3fv(boxnormals[i]);
for (k = 0; k < 3; k++) {
if (boxfaces[i][k] == -1)
continue;
v = boxcoords[boxfaces[i][k]];
x = v[0] + OFFSETX;
if (v[0] > 0.5)
x += xlen - 1;
y = v[1] + OFFSETY;
if (v[1] > 0.5)
y += ylen - 1;
z = v[2] + OFFSETZ;
if (v[2] > 0.5)
z += zlen - 1;
glVertex3f(xoff + x, yoff + y, z);
}
}
glEnd();
}
float containercoords[][3] =
{
{-0.1, -0.1, 1.0},
{-0.1, -0.1, -0.1},
{4.1, -0.1, -0.1},
{4.1, -0.1, 1.0},
{1.0, -0.1, 0.6}, /* 4 */
{3.0, -0.1, 0.6},
{1.0, -0.1, 0.0},
{3.0, -0.1, 0.0},
{1.0, 0.0, 0.0}, /* 8 */
{3.0, 0.0, 0.0},
{3.0, 0.0, 0.6},
{1.0, 0.0, 0.6},
{0.0, 0.0, 1.0}, /* 12 */
{4.0, 0.0, 1.0},
{4.0, 0.0, 0.0},
{0.0, 0.0, 0.0},
{0.0, 5.0, 0.0}, /* 16 */
{0.0, 5.0, 1.0},
{4.0, 5.0, 1.0},
{4.0, 5.0, 0.0},
{-0.1, 5.1, -0.1}, /* 20 */
{4.1, 5.1, -0.1},
{4.1, 5.1, 1.0},
{-0.1, 5.1, 1.0},
};
float containernormals[][3] =
{
{0, -1, 0},
{0, -1, 0},
{0, -1, 0},
{0, -1, 0},
{0, -1, 0},
{0, 1, 0},
{0, 1, 0},
{0, 1, 0},
{1, 0, 0},
{1, 0, 0},
{1, 0, 0},
{-1, 0, 0},
{-1, 0, 0},
{-1, 0, 0},
{0, 1, 0},
{0, 0, -1},
{0, 0, -1},
{0, 0, 1},
{0, 0, 1},
{0, 0, 1},
{0, 0, 1},
{0, 0, 1},
{0, 0, 1},
{0, 0, 1},
};
int containerfaces[][4] =
{
{1, 6, 4, 0},
{0, 4, 5, 3},
{1, 2, 7, 6},
{7, 2, 3, 5},
{16, 19, 18, 17},
{23, 22, 21, 20},
{12, 11, 8, 15},
{10, 13, 14, 9},
{15, 16, 17, 12},
{2, 21, 22, 3},
{6, 8, 11, 4},
{1, 0, 23, 20},
{14, 13, 18, 19},
{9, 7, 5, 10},
{12, 13, 10, 11},
{1, 20, 21, 2},
{4, 11, 10, 5},
{15, 8, 19, 16},
{19, 8, 9, 14},
{8, 6, 7, 9},
{0, 3, 13, 12},
{13, 3, 22, 18},
{18, 22, 23, 17},
{17, 23, 0, 12},
};
#define NCONTFACES (sizeof(containerfaces)/sizeof(containerfaces[0]))
/* Draw the container */
void
drawContainer(void)
{
int i, k;
float *v;
/* Y is reversed here because the model has it reversed */
/* Arbitrary bright wood-like color */
glColor3ub(209, 103, 23);
glBegin(GL_QUADS);
for (i = 0; i < NCONTFACES; i++) {
v = containernormals[i];
glNormal3f(v[0], -v[1], v[2]);
for (k = 3; k >= 0; k--) {
v = containercoords[containerfaces[i][k]];
glVertex3f(v[0] + OFFSETX, -(v[1] + OFFSETY), v[2] + OFFSETZ);
}
}
glEnd();
}
void
drawAll(void)
{
int i, j;
int piece;
char done[PIECES + 1];
float m[4][4];
build_rotmatrix(m, curquat);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glTranslatef(0, 0, -10);
glMultMatrixf(&(m[0][0]));
glRotatef(180, 0, 0, 1);
if (depth) {
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
} else {
glClear(GL_COLOR_BUFFER_BIT);
}
for (i = 1; i <= PIECES; i++) {
done[i] = 0;
}
glLoadName(0);
drawContainer();
for (i = 0; i < HEIGHT; i++) {
for (j = 0; j < WIDTH; j++) {
piece = thePuzzle[i][j];
if (piece == 0)
continue;
if (done[piece])
continue;
done[piece] = 1;
glLoadName(piece);
if (piece == movingPiece) {
drawBox(piece, move_x, move_y);
} else {
drawBox(piece, j, i);
}
}
}
}
void
redraw(void)
{
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluPerspective(45, 1.0, 0.1, 100.0);
drawAll();
if (doubleBuffer)
glutSwapBuffers();
else
glFinish();
}
void
solidifyChain(struct puzzle *puzzle)
{
int i;
char buf[256];
i = 0;
while (puzzle->backptr) {
i++;
puzzle->backptr->solnptr = puzzle;
puzzle = puzzle->backptr;
}
sprintf(buf, "%d moves to complete!", i);
glutSetWindowTitle(buf);
}
int
addConfig(Config config, struct puzzle *back)
{
unsigned hashvalue;
struct puzzle *newpiece;
struct puzzlelist *newlistentry;
hashvalue = hash(config);
newpiece = hashtable[hashvalue % HASHSIZE];
while (newpiece != NULL) {
if (newpiece->hashvalue == hashvalue) {
int i, j;
for (i = 0; i < WIDTH; i++) {
for (j = 0; j < HEIGHT; j++) {
if (convert[config[j][i]] !=
convert[newpiece->pieces[j][i]])
goto nomatch;
}
}
return 0;
}
nomatch:
newpiece = newpiece->next;
}
newpiece = (struct puzzle *) malloc(sizeof(struct puzzle));
newpiece->next = hashtable[hashvalue % HASHSIZE];
newpiece->hashvalue = hashvalue;
memcpy(newpiece->pieces, config, HEIGHT * WIDTH);
newpiece->backptr = back;
newpiece->solnptr = NULL;
hashtable[hashvalue % HASHSIZE] = newpiece;
newlistentry = (struct puzzlelist *) malloc(sizeof(struct puzzlelist));
newlistentry->puzzle = newpiece;
newlistentry->next = NULL;
if (lastentry) {
lastentry->next = newlistentry;
} else {
puzzles = newlistentry;
}
lastentry = newlistentry;
if (back == NULL) {
startPuzzle = newpiece;
}
if (solution(config)) {
solidifyChain(newpiece);
return 1;
}
return 0;
}
/* Checks if a space can move */
int
canmove0(Config pieces, int x, int y, int dir, Config newpieces)
{
char piece;
int xadd, yadd;
int l, m;
xadd = xadds[dir];
yadd = yadds[dir];
if (x + xadd < 0 || x + xadd >= WIDTH ||
y + yadd < 0 || y + yadd >= HEIGHT)
return 0;
piece = pieces[y + yadd][x + xadd];
if (piece == 0)
return 0;
memcpy(newpieces, pieces, HEIGHT * WIDTH);
for (l = 0; l < WIDTH; l++) {
for (m = 0; m < HEIGHT; m++) {
if (newpieces[m][l] == piece)
newpieces[m][l] = 0;
}
}
xadd = -xadd;
yadd = -yadd;
for (l = 0; l < WIDTH; l++) {
for (m = 0; m < HEIGHT; m++) {
if (pieces[m][l] == piece) {
int newx, newy;
newx = l + xadd;
newy = m + yadd;
if (newx < 0 || newx >= WIDTH ||
newy < 0 || newy >= HEIGHT)
return 0;
if (newpieces[newy][newx] != 0)
return 0;
newpieces[newy][newx] = piece;
}
}
}
return 1;
}
/* Checks if a piece can move */
int
canmove(Config pieces, int x, int y, int dir, Config newpieces)
{
int xadd, yadd;
xadd = xadds[dir];
yadd = yadds[dir];
if (x + xadd < 0 || x + xadd >= WIDTH ||
y + yadd < 0 || y + yadd >= HEIGHT)
return 0;
if (pieces[y + yadd][x + xadd] == pieces[y][x]) {
return canmove(pieces, x + xadd, y + yadd, dir, newpieces);
}
if (pieces[y + yadd][x + xadd] != 0)
return 0;
return canmove0(pieces, x + xadd, y + yadd, (dir + 2) % 4, newpieces);
}
int
generateNewConfigs(struct puzzle *puzzle)
{
int i, j, k;
Config pieces;
Config newpieces;
memcpy(pieces, puzzle->pieces, HEIGHT * WIDTH);
for (i = 0; i < WIDTH; i++) {
for (j = 0; j < HEIGHT; j++) {
if (pieces[j][i] == 0) {
for (k = 0; k < 4; k++) {
if (canmove0(pieces, i, j, k, newpieces)) {
if (addConfig(newpieces, puzzle))
return 1;
}
}
}
}
}
return 0;
}
void
freeSolutions(void)
{
struct puzzlelist *nextpuz;
struct puzzle *puzzle, *next;
int i;
while (puzzles) {
nextpuz = puzzles->next;
free((char *) puzzles);
puzzles = nextpuz;
}
lastentry = NULL;
for (i = 0; i < HASHSIZE; i++) {
puzzle = hashtable[i];
hashtable[i] = NULL;
while (puzzle) {
next = puzzle->next;
free((char *) puzzle);
puzzle = next;
}
}
startPuzzle = NULL;
}
int
continueSolving(void)
{
struct puzzle *nextpuz;
int i, j;
int movedPiece;
int movedir;
int fromx, fromy;
int tox, toy;
if (startPuzzle == NULL)
return 0;
if (startPuzzle->solnptr == NULL) {
freeSolutions();
return 0;
}
nextpuz = startPuzzle->solnptr;
movedPiece = 0;
movedir = 0;
for (i = 0; i < HEIGHT; i++) {
for (j = 0; j < WIDTH; j++) {
if (startPuzzle->pieces[i][j] != nextpuz->pieces[i][j]) {
if (startPuzzle->pieces[i][j]) {
movedPiece = startPuzzle->pieces[i][j];
fromx = j;
fromy = i;
if (i < HEIGHT - 1 && nextpuz->pieces[i + 1][j] == movedPiece) {
movedir = 3;
} else {
movedir = 2;
}
goto found_piece;
} else {
movedPiece = nextpuz->pieces[i][j];
if (i < HEIGHT - 1 &&
startPuzzle->pieces[i + 1][j] == movedPiece) {
fromx = j;
fromy = i + 1;
movedir = 1;
} else {
fromx = j + 1;
fromy = i;
movedir = 0;
}
goto found_piece;
}
}
}
}
glutSetWindowTitle("What! No change?");
freeSolutions();
return 0;
found_piece:
if (!movingPiece) {
movingPiece = movedPiece;
move_x = fromx;
move_y = fromy;
}
move_x += xadds[movedir] * MOVE_SPEED;
move_y += yadds[movedir] * MOVE_SPEED;
tox = fromx + xadds[movedir];
toy = fromy + yadds[movedir];
if (move_x > tox - MOVE_SPEED / 2 && move_x < tox + MOVE_SPEED / 2 &&
move_y > toy - MOVE_SPEED / 2 && move_y < toy + MOVE_SPEED / 2) {
startPuzzle = nextpuz;
movingPiece = 0;
}
memcpy(thePuzzle, startPuzzle->pieces, HEIGHT * WIDTH);
changeState();
return 1;
}
int
solvePuzzle(void)
{
struct puzzlelist *nextpuz;
char buf[256];
int i;
if (solution(thePuzzle)) {
glutSetWindowTitle("Puzzle already solved!");
return 0;
}
addConfig(thePuzzle, NULL);
i = 0;
while (puzzles) {
i++;
if (generateNewConfigs(puzzles->puzzle))
break;
nextpuz = puzzles->next;
free((char *) puzzles);
puzzles = nextpuz;
}
if (puzzles == NULL) {
freeSolutions();
sprintf(buf, "I can't solve it! (%d positions examined)", i);
glutSetWindowTitle(buf);
return 1;
}
return 1;
}
int
selectPiece(int mousex, int mousey)
{
long hits;
GLuint selectBuf[1024];
GLuint closest;
GLuint dist;
glSelectBuffer(1024, selectBuf);
(void) glRenderMode(GL_SELECT);
glInitNames();
/* Because LoadName() won't work with no names on the stack */
glPushName(-1);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluPickMatrix(mousex, H - mousey, 4, 4, viewport);
gluPerspective(45, 1.0, 0.1, 100.0);
drawAll();
hits = glRenderMode(GL_RENDER);
if (hits <= 0) {
return 0;
}
closest = 0;
dist = 4294967295;
while (hits) {
if (selectBuf[(hits - 1) * 4 + 1] < dist) {
dist = selectBuf[(hits - 1) * 4 + 1];
closest = selectBuf[(hits - 1) * 4 + 3];
}
hits--;
}
return closest;
}
void
nukePiece(int piece)
{
int i, j;
for (i = 0; i < HEIGHT; i++) {
for (j = 0; j < WIDTH; j++) {
if (thePuzzle[i][j] == piece) {
thePuzzle[i][j] = 0;
}
}
}
}
void
multMatrices(const GLfloat a[16], const GLfloat b[16], GLfloat r[16])
{
int i, j;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
r[i * 4 + j] =
a[i * 4 + 0] * b[0 * 4 + j] +
a[i * 4 + 1] * b[1 * 4 + j] +
a[i * 4 + 2] * b[2 * 4 + j] +
a[i * 4 + 3] * b[3 * 4 + j];
}
}
}
void
makeIdentity(GLfloat m[16])
{
m[0 + 4 * 0] = 1;
m[0 + 4 * 1] = 0;
m[0 + 4 * 2] = 0;
m[0 + 4 * 3] = 0;
m[1 + 4 * 0] = 0;
m[1 + 4 * 1] = 1;
m[1 + 4 * 2] = 0;
m[1 + 4 * 3] = 0;
m[2 + 4 * 0] = 0;
m[2 + 4 * 1] = 0;
m[2 + 4 * 2] = 1;
m[2 + 4 * 3] = 0;
m[3 + 4 * 0] = 0;
m[3 + 4 * 1] = 0;
m[3 + 4 * 2] = 0;
m[3 + 4 * 3] = 1;
}
/*
** inverse = invert(src)
*/
int
invertMatrix(const GLfloat src[16], GLfloat inverse[16])
{
int i, j, k, swap;
double t;
GLfloat temp[4][4];
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
temp[i][j] = src[i * 4 + j];
}
}
makeIdentity(inverse);
for (i = 0; i < 4; i++) {
/*
** Look for largest element in column */
swap = i;
for (j = i + 1; j < 4; j++) {
if (fabs(temp[j][i]) > fabs(temp[i][i])) {
swap = j;
}
}
if (swap != i) {
/*
** Swap rows. */
for (k = 0; k < 4; k++) {
t = temp[i][k];
temp[i][k] = temp[swap][k];
temp[swap][k] = t;
t = inverse[i * 4 + k];
inverse[i * 4 + k] = inverse[swap * 4 + k];
inverse[swap * 4 + k] = t;
}
}
if (temp[i][i] == 0) {
/*
** No non-zero pivot. The matrix is singular, which
shouldn't ** happen. This means the user gave us a
bad matrix. */
return 0;
}
t = temp[i][i];
for (k = 0; k < 4; k++) {
temp[i][k] /= t;
inverse[i * 4 + k] /= t;
}
for (j = 0; j < 4; j++) {
if (j != i) {
t = temp[j][i];
for (k = 0; k < 4; k++) {
temp[j][k] -= temp[i][k] * t;
inverse[j * 4 + k] -= inverse[i * 4 + k] * t;
}
}
}
}
return 1;
}
/*
** This is a screwball function. What it does is the following:
** Given screen x and y coordinates, compute the corresponding object space
** x and y coordinates given that the object space z is 0.9 + OFFSETZ.
** Since the tops of (most) pieces are at z = 0.9 + OFFSETZ, we use that
** number.
*/
int
computeCoords(int piece, int mousex, int mousey,
GLfloat * selx, GLfloat * sely)
{
GLfloat modelMatrix[16];
GLfloat projMatrix[16];
GLfloat finalMatrix[16];
GLfloat in[4];
GLfloat a, b, c, d;
GLfloat top, bot;
GLfloat z;
GLfloat w;
GLfloat height;
if (piece == 0)
return 0;
height = zsize[piece] - 0.1 + OFFSETZ;
glGetFloatv(GL_PROJECTION_MATRIX, projMatrix);
glGetFloatv(GL_MODELVIEW_MATRIX, modelMatrix);
multMatrices(modelMatrix, projMatrix, finalMatrix);
if (!invertMatrix(finalMatrix, finalMatrix))
return 0;
in[0] = (2.0 * (mousex - viewport[0]) / viewport[2]) - 1;
in[1] = (2.0 * ((H - mousey) - viewport[1]) / viewport[3]) - 1;
a = in[0] * finalMatrix[0 * 4 + 2] +
in[1] * finalMatrix[1 * 4 + 2] +
finalMatrix[3 * 4 + 2];
b = finalMatrix[2 * 4 + 2];
c = in[0] * finalMatrix[0 * 4 + 3] +
in[1] * finalMatrix[1 * 4 + 3] +
finalMatrix[3 * 4 + 3];
d = finalMatrix[2 * 4 + 3];
/*
** Ok, now we need to solve for z: ** (a + b z) / (c + d
z) = height. ** ("height" is the height in object space we
want to solve z for) ** ** ==> a + b z = height c +
height d z ** bz - height d z = height c - a ** z =
(height c - a) / (b - height d) */
top = height * c - a;
bot = b - height * d;
if (bot == 0.0)
return 0;
z = top / bot;
/*
** Ok, no problem. ** Now we solve for x and y. We know
that w = c + d z, so we compute it. */
w = c + d * z;
/*
** Now for x and y: */
*selx = (in[0] * finalMatrix[0 * 4 + 0] +
in[1] * finalMatrix[1 * 4 + 0] +
z * finalMatrix[2 * 4 + 0] +
finalMatrix[3 * 4 + 0]) / w - OFFSETX;
*sely = (in[0] * finalMatrix[0 * 4 + 1] +
in[1] * finalMatrix[1 * 4 + 1] +
z * finalMatrix[2 * 4 + 1] +
finalMatrix[3 * 4 + 1]) / w - OFFSETY;
return 1;
}
static int selected;
static int selectx, selecty;
static float selstartx, selstarty;
void
grabPiece(int piece, float selx, float sely)
{
int hit;
selectx = selx;
selecty = sely;
if (selectx < 0 || selecty < 0 || selectx >= WIDTH || selecty >= HEIGHT) {
return;
}
hit = thePuzzle[selecty][selectx];
if (hit != piece)
return;
if (hit) {
movingPiece = hit;
while (selectx > 0 && thePuzzle[selecty][selectx - 1] == movingPiece) {
selectx--;
}
while (selecty > 0 && thePuzzle[selecty - 1][selectx] == movingPiece) {
selecty--;
}
move_x = selectx;
move_y = selecty;
selected = 1;
selstartx = selx;
selstarty = sely;
} else {
selected = 0;
}
changeState();
}
void
moveSelection(float selx, float sely)
{
float deltax, deltay;
int dir;
Config newpieces;
if (!selected)
return;
deltax = selx - selstartx;
deltay = sely - selstarty;
if (fabs(deltax) > fabs(deltay)) {
deltay = 0;
if (deltax > 0) {
if (deltax > 1)
deltax = 1;
dir = 2;
} else {
if (deltax < -1)
deltax = -1;
dir = 0;
}
} else {
deltax = 0;
if (deltay > 0) {
if (deltay > 1)
deltay = 1;
dir = 3;
} else {
if (deltay < -1)
deltay = -1;
dir = 1;
}
}
if (canmove(thePuzzle, selectx, selecty, dir, newpieces)) {
move_x = deltax + selectx;
move_y = deltay + selecty;
if (deltax > 0.5) {
memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
selectx++;
selstartx++;
} else if (deltax < -0.5) {
memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
selectx--;
selstartx--;
} else if (deltay > 0.5) {
memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
selecty++;
selstarty++;
} else if (deltay < -0.5) {
memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
selecty--;
selstarty--;
}
} else {
if (deltay > 0 && thePuzzle[selecty][selectx] == 10 &&
selectx == 1 && selecty == 3) {
/* Allow visual movement of solution piece outside of the
box */
move_x = selectx;
move_y = sely - selstarty + selecty;
} else {
move_x = selectx;
move_y = selecty;
}
}
}
void
dropSelection(void)
{
if (!selected)
return;
movingPiece = 0;
selected = 0;
changeState();
}
static int left_mouse, middle_mouse;
static int mousex, mousey;
static int solving;
static int spinning;
static float lastquat[4];
static int sel_piece;
static void
Reshape(int width, int height)
{
W = width;
H = height;
glViewport(0, 0, W, H);
glGetIntegerv(GL_VIEWPORT, viewport);
}
void
toggleSolve(void)
{
if (solving) {
freeSolutions();
solving = 0;
glutChangeToMenuEntry(1, "Solving", 1);
glutSetWindowTitle("glpuzzle");
movingPiece = 0;
} else {
glutChangeToMenuEntry(1, "Stop solving", 1);
glutSetWindowTitle("Solving...");
if (solvePuzzle()) {
solving = 1;
}
}
changeState();
glutPostRedisplay();
}
void reset(void)
{
if (solving) {
freeSolutions();
solving = 0;
glutChangeToMenuEntry(1, "Solving", 1);
glutSetWindowTitle("glpuzzle");
movingPiece = 0;
changeState();
}
memcpy(thePuzzle, startConfig, HEIGHT * WIDTH);
glutPostRedisplay();
}
void
keyboard(unsigned char c, int x, int y)
{
int piece;
switch (c) {
case 27:
exit(0);
break;
case 'D':
case 'd':
if (solving) {
freeSolutions();
solving = 0;
glutChangeToMenuEntry(1, "Solving", 1);
glutSetWindowTitle("glpuzzle");
movingPiece = 0;
changeState();
}
piece = selectPiece(x, y);
if (piece) {
nukePiece(piece);
}
glutPostRedisplay();
break;
case 'R':
case 'r':
reset();
break;
case 'S':
case 's':
toggleSolve();
break;
case 'b':
case 'B':
depth = 1 - depth;
if (depth) {
glEnable(GL_DEPTH_TEST);
} else {
glDisable(GL_DEPTH_TEST);
}
glutPostRedisplay();
break;
default:
break;
}
}
void
motion(int x, int y)
{
float selx, sely;
if (middle_mouse && !left_mouse) {
if (mousex != x || mousey != y) {
trackball(lastquat,
(2.0*mousex - W) / W,
(H - 2.0*mousey) / H,
(2.0*x - W) / W,
(H - 2.0*y) / H);
spinning = 1;
} else {
spinning = 0;
}
changeState();
} else {
computeCoords(sel_piece, x, y, &selx, &sely);
moveSelection(selx, sely);
}
mousex = x;
mousey = y;
glutPostRedisplay();
}
void
mouse(int b, int s, int x, int y)
{
float selx, sely;
mousex = x;
mousey = y;
curX = x;
curY = y;
if (s == GLUT_DOWN) {
switch (b) {
case GLUT_LEFT_BUTTON:
if (solving) {
freeSolutions();
solving = 0;
glutChangeToMenuEntry(1, "Solving", 1);
glutSetWindowTitle("glpuzzle");
movingPiece = 0;
}
left_mouse = GL_TRUE;
sel_piece = selectPiece(mousex, mousey);
if (computeCoords(sel_piece, mousex, mousey, &selx, &sely)) {
grabPiece(sel_piece, selx, sely);
}
glutPostRedisplay();
break;
case GLUT_MIDDLE_BUTTON:
middle_mouse = GL_TRUE;
glutPostRedisplay();
break;
}
} else {
switch (b) {
case GLUT_LEFT_BUTTON:
left_mouse = GL_FALSE;
dropSelection();
glutPostRedisplay();
break;
case GLUT_MIDDLE_BUTTON:
middle_mouse = GL_FALSE;
glutPostRedisplay();
break;
}
}
motion(x, y);
}
void
animate(void)
{
if (spinning) {
add_quats(lastquat, curquat, curquat);
}
glutPostRedisplay();
if (solving) {
if (!continueSolving()) {
solving = 0;
glutChangeToMenuEntry(1, "Solving", 1);
glutSetWindowTitle("glpuzzle");
}
}
if (!solving && !spinning && !visible) {
glutIdleFunc(NULL);
}
}
void
changeState(void)
{
if (visible) {
if (!solving && !spinning) {
glutIdleFunc(NULL);
} else {
glutIdleFunc(animate);
}
} else {
glutIdleFunc(NULL);
}
}
void
init(void)
{
static float lmodel_ambient[] =
{0.0, 0.0, 0.0, 0.0};
static float lmodel_twoside[] =
{GL_FALSE};
static float lmodel_local[] =
{GL_FALSE};
static float light0_ambient[] =
{0.1, 0.1, 0.1, 1.0};
static float light0_diffuse[] =
{1.0, 1.0, 1.0, 0.0};
static float light0_position[] =
{0.8660254, 0.5, 1, 0};
static float light0_specular[] =
{0.0, 0.0, 0.0, 0.0};
static float bevel_mat_ambient[] =
{0.0, 0.0, 0.0, 1.0};
static float bevel_mat_shininess[] =
{40.0};
static float bevel_mat_specular[] =
{0.0, 0.0, 0.0, 0.0};
static float bevel_mat_diffuse[] =
{1.0, 0.0, 0.0, 0.0};
glEnable(GL_CULL_FACE);
glCullFace(GL_BACK);
glEnable(GL_DEPTH_TEST);
glClearDepth(1.0);
glClearColor(0.5, 0.5, 0.5, 0.0);
glLightfv(GL_LIGHT0, GL_AMBIENT, light0_ambient);
glLightfv(GL_LIGHT0, GL_DIFFUSE, light0_diffuse);
glLightfv(GL_LIGHT0, GL_SPECULAR, light0_specular);
glLightfv(GL_LIGHT0, GL_POSITION, light0_position);
glEnable(GL_LIGHT0);
glLightModelfv(GL_LIGHT_MODEL_LOCAL_VIEWER, lmodel_local);
glLightModelfv(GL_LIGHT_MODEL_TWO_SIDE, lmodel_twoside);
glLightModelfv(GL_LIGHT_MODEL_AMBIENT, lmodel_ambient);
glEnable(GL_LIGHTING);
glMaterialfv(GL_FRONT, GL_AMBIENT, bevel_mat_ambient);
glMaterialfv(GL_FRONT, GL_SHININESS, bevel_mat_shininess);
glMaterialfv(GL_FRONT, GL_SPECULAR, bevel_mat_specular);
glMaterialfv(GL_FRONT, GL_DIFFUSE, bevel_mat_diffuse);
glColorMaterial(GL_FRONT_AND_BACK, GL_DIFFUSE);
glEnable(GL_COLOR_MATERIAL);
glShadeModel(GL_FLAT);
trackball(curquat, 0.0, 0.0, 0.0, 0.0);
srandom(time(NULL));
}
static void
Usage(void)
{
printf("Usage: puzzle [-s]\n");
printf(" -s: Run in single buffered mode\n");
exit(-1);
}
void
visibility(int v)
{
if (v == GLUT_VISIBLE) {
visible = 1;
} else {
visible = 0;
}
changeState();
}
void
menu(int choice)
{
switch(choice) {
case 1:
toggleSolve();
break;
case 2:
reset();
break;
case 3:
exit(0);
break;
}
}
int
main(int argc, char **argv)
{
long i;
glutInit(&argc, argv);
for (i = 1; i < argc; i++) {
if (argv[i][0] == '-') {
switch (argv[i][1]) {
case 's':
doubleBuffer = 0;
break;
default:
Usage();
}
} else {
Usage();
}
}
glutInitWindowSize(W, H);
if (doubleBuffer) {
glutInitDisplayMode(GLUT_DEPTH | GLUT_RGB | GLUT_DOUBLE | GLUT_MULTISAMPLE);
} else {
glutInitDisplayMode(GLUT_DEPTH | GLUT_RGB | GLUT_SINGLE | GLUT_MULTISAMPLE);
}
glutCreateWindow("glpuzzle");
init();
glGetIntegerv(GL_VIEWPORT, viewport);
printf("\n");
printf("r Reset puzzle\n");
printf("s Solve puzzle (may take a few seconds to compute)\n");
printf("d Destroy a piece - makes the puzzle easier\n");
printf("b Toggles the depth buffer on and off\n");
printf("\n");
printf("Left mouse moves pieces\n");
printf("Middle mouse spins the puzzle\n");
printf("Right mouse has menu\n");
glutReshapeFunc(Reshape);
glutDisplayFunc(redraw);
glutKeyboardFunc(keyboard);
glutMotionFunc(motion);
glutMouseFunc(mouse);
glutVisibilityFunc(visibility);
glutCreateMenu(menu);
glutAddMenuEntry("Solve", 1);
glutAddMenuEntry("Reset", 2);
glutAddMenuEntry("Quit", 3);
glutAttachMenu(GLUT_RIGHT_BUTTON);
glutMainLoop();
return 0; /* ANSI C requires main to return int. */
}
