glpuzzle.cxx

PIXIL is a small footprint operating environment, complete with PDA PIM applications, a browser and

    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(0);

  glMatrixMode(GL_PROJECTION);
  glLoadIdentity();
  gluPickMatrix(mousex, H - mousey, 4, 4, viewport);
  gluPerspective(45, viewport[2]*1.0/viewport[3], 0.1, 100.0);

  drawAll();

  hits = glRenderMode(GL_RENDER);
  if (hits <= 0) {
    return 0;
  }
  closest = 0;
  dist = 0xFFFFFFFFU; //2147483647;
  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;

  /*