// qotw17_puzzle
// Kevin Pfeiffer
//#html work-in-progress
//#html Use the 'x' key to flip and the 'z' or 'c' keys to rotate a tile.

// Based on the Perl 'Expert' Quiz-of-the-Week #17
// http://perl.plover.com/qotw/e/017
// Code based on an approach developed by Mark Jason Dominus


// TODO
// auto-solve puzzle method!
// work on color pallette
// change rotate() to use BB centerpoint instead of vertex
// add selection marquee & "moveAllSelect" for repositioning placed pieces!
// improve snap method (use angle of sides!)
// prevent overlapping tiles
// suitable shuffle-tiles method
// instructions? (or on web page)?
// displayProperties method (angle, lengths, area)
// animated_moving routine

/*
An "S" in the "Sides" column represents a side with length
sqrt(3).  The areas in the "Area" column are measured in multiples
of tile A, which actually has an area of sqrt(3)/4 square units.

Piece "E" is rather irregular.  It is formed by taking a copy of tile
C and gluing a copy of tile A to its short side.

Tiles C and D are identical.

It is permissible to flip the tiles over.  And, of course, to rotate
them or slide them around on the table.  But it is not permitted to
overlap them.
*/

int sc;
int unit;
Puzzle puzzle;
final float S = sqrt(3);                                // sqrt of 3 * unit  

void setup()
{
  size(700,500);
  sc = width/5;                                         // scale tiles to window
  unit = sc * 1;                                        // unit size of tiles
  puzzle = new Puzzle(unit);
  smooth();
  noStroke();
}

void loop()
{
  background(45, 55, 50);
  puzzle.run();
}

void mousePressed() { puzzle.mousePressed(); }
void mouseReleased() { puzzle.mouseReleased(); }
void keyPressed() { puzzle.keyPressed(); }

class Puzzle
{
  // fields
  Stack stack = new Stack();                            // puzzle tiles
  int unit;                                             // scalar for sizes
  Tile selected;                                        // currently selected tile
  boolean tileSelected;                                 // true if tile selected
  final color selColor = color(40, 40, 40, 200);        // selection stroke
  final static int snapTolerance = 10;                  // for placing adjoining tiles
  final static int X = 0;                               // easier vector array handling
  final static int Y = 1;  
  
  Puzzle(int unitSize)
  {
    unit = unitSize;
    /*
    A       Equilateral triangle    60 60 60        1 1 1           1
    B       Isosceles triangle      30 30 120       1 1 S           1
    C       Right triangle          30 60 90        1 S 2           2
    D       Right triangle          30 60 90        1 S 2           2
    E       Quadrilateral           60 150 30 120   1 S 2 1         3
    F       Trapezoid               120 60 60 120   1 1 2 1         3
    G       Rectangle               90 90 90 90     S 1 S 1         4
    */
    //NOTE: All drawn counterclockwise (CCW)!
    int[][] vtx = new int[7][];                            // vertices
    float[][] sides = new float[7][];                      // lengths
    int[] colors = new int[7];
    
    vtx[0] = new int[] { 0, 240, 120 };                    // A -- equilateral triangle
    sides[0]    = new float[] { 1, 1, 1 };
    colors[0] = color(200, 100, 20);
  
    vtx[1] = new int[] { 0, 210, 150 };                    // B -- isoceles triangle
    sides[1]    = new float[] { S, 1, 1 };
    colors[1] = color(100, 100, 20);
  
    vtx[2] = new int[] { 0, 240, 90 };                     // C -- right triangle
    sides[2]    = new float[] { 1, 2, S };
    colors[2] = color(80, 130, 80);
  
    vtx[3] = new int[] { 0, 270, 120 };                    // D -- right triangle
    sides[3]    = new float[] { 1, S, 2 };
    colors[3] = color(80, 80, 170);
  
    vtx[4] = new int[] { 120, 90, 300, 240 };               // E -- quadrilateral
    sides[4]    = new float[] { 1, S, 2, 1 };
    colors[4] = color(150, 150, 40);
  
    vtx[5] = new int[] { 0, 240, 180, 120 };                // F -- trapezoid
    sides[5]    = new float[] { 2, 1, 1, 1 };
    colors[5] = color(130, 110, 40);
  
    vtx[6] = new int[] { 0, 270, 180, 90 };                 // G -- rectangle
    sides[6]    = new float[] { S, 1, S, 1 };
    colors[6] = color(100, 80, 140);
   
    for(int i = 0; i < vtx.length; i++) {
      stack.push(new Tile(unit, 0, vtx[i], sides[i], int( random(width/2) + 50 ), int( random(height/2) + 100 ), colors[i]));
    }
    
  } // end puzzle constructor


  void run()
  { 
      if(mousePressed && tileSelected) {          // move selected tile
        selected.updatePos(mouseX, mouseY);
      }
      for(int i = 0; i < stack.size(); i++) {     // display tiles
        ((Tile) stack.get(i)).display();      
      }
  }
  
  
  void mousePressed()
  {
    if(tileSelected) selected.isOver = false;     // clear old tile
    tileSelected = false;
    
    for(int i = stack.size()-1; i >= 0; i--) {    // from top of stack down (we want upper-most tile)
      boolean newSelect = false;
      Tile tile = (Tile) stack.get(i);
      newSelect = tile.isInside(mouseX, mouseY);

      if(newSelect == true) {                     // tile found under curser; move to top of stack and break out of loop
        selected = tile;
        tileSelected = true;
        stack.removeElementAt(i);                 // remove from current index in stack
        stack.push(tile);                         // push to top of stack
        selected.isOver = true;                   // flag tile that it is selected
        selected.calcOffset();                    // offset mouse to tile
        break;
      }
    }
  }
  
  
  void mouseReleased()
  {
    if(tileSelected) {
      for(int i = stack.size()-2; i >= 0; i--) {        // skip 1st tile (selected) in stack
        Tile tile = (Tile) stack.get(i);
        for(int j = 0; j < 2; j++) {
          for(int k = 2; k < 4; k++) {
            if( tile.isInsideBB(selected.bb[j], selected.bb[k]) ) {
              snapTo(tile);                             // try to snap two tiles together
            }
          }
        }
      }
    }
  } // end mouseReleased
  

  void keyPressed()
  {      
    if(key == 'x' && tileSelected) {
      selected.flip();
    }    
    
    // DEBUG - turn on box for tile
    if(key == 'b' && tileSelected) {
      if(selected.showBB == false) {
        selected.showBB = true;
      } else {
        selected.showBB = true;
      }
    }

    // To rotate selected tile
    else if(key == LEFT || key == RIGHT || 
            key == 'z' || key == 'c') {
      int sign = 1;
      if(key == LEFT || key == 'z') sign = -1;
      selected.rotate(sign);
    }
    
    // DEBUG dump vertices  
    else if(key == 'p') {
      for(int i = 0; i < selected.ang.length; i++) {
        println(i + ": " + selected.ang[i] + "   " + selected.sides[i]);
      }
    }
        
  } // end keyPressed()


  // *** Sides matching will have the same length and differ in angle by PI
  boolean sidesMatch()
  {
    // TODO
    // compare two sides
    return false;
  }

  
  boolean snapTo(Tile tile)
  { 
    // look for two pairs of close vertices
    int match = 0;
    int a = 0;
    int b = 0;
    for(int i = 0; i < tile.vtx.length; i++) {
      for(int j = 0; j < selected.vtx.length; j++) { 
        if(abs(tile.vtx[i][X] - selected.vtx[j][X]) < snapTolerance &&
           abs(tile.vtx[i][Y] - selected.vtx[j][Y]) < snapTolerance) {
          a = i;
          b = j;
          match++;
          //println(match);
         }         
       }
     }
     if(match > 0) {
       selected.moveTo(b, tile.vtx[a][X], tile.vtx[a][Y]);
       return true;
     } else {
       return false;
     }  
  }

} // end of Puzzle class


class Tile
{
  // fields
  int unit;                          // size in pixels of 1 unit;
  float[] ang;                       // angles for each vertex
  float[] sides;                     // length of each side
  int[][] vtx;                       // actual x,y vtx of current position
  int[] bb = new int[4];             // bounding box
  boolean isOver;                    // is mousePressed over tile?
  // int area;                        // area in terms of tile A (info only)
  int xPos, yPos;                    // current position of first vertex (lowerleft)
  int offsetX, offsetY;              // from mousePressed
  float rot;                         // rotation - radians
  boolean flipped;                   // tile is flipped over
  boolean showBB;                    // debug - display bounding box
  color c;                           // fill color
  final static float rotInc = PI/6;  // 30 degree increment
  final static int X = 0;            // for vector array handling
  final static int Y = 1;  

  Tile(int _unit, float _rot, int[] _angles, float[] _sides, float _xPos, float _yPos, color clr)
  {
    unit = _unit;
    rot = _rot;

    // NOTE: For finding solution, probably should work with degrees (int)!! - another array?
    // convert angles to radians
    ang = new float[_angles.length];
    for(int i = 0; i < _angles.length; i++) {
      ang[i] = radians(_angles[i]);
    }
    sides = _sides;
    xPos = (int) _xPos;
    yPos = (int) _yPos;
    c = clr;
    
    vtx = new int[sides.length][2];
    calcVtx();
     
  } // end constructor
  
  
  void calcBoundingBox()
  {
    bb[0] = vtx[0][X];
    bb[1] = vtx[0][X];
    bb[2] = vtx[0][Y];
    bb[3] = vtx[0][Y];
    
    // get dimensions
    for(int i = 0; i < vtx.length; i++) {
      bb[0] = min(bb[0], vtx[i][X]);  // min x -- right
      bb[1] = max(bb[1], vtx[i][X]);  // + puzzle.snapTolerance;  // max x -- left
      bb[2] = min(bb[2], vtx[i][Y]);  // min y -- top
      bb[3] = max(bb[3], vtx[i][Y]);  // + 8;  // max y -- bottom
    }
    // loosen
    bb[0] -= puzzle.snapTolerance;
    bb[1] += puzzle.snapTolerance;
    bb[2] -= puzzle.snapTolerance;
    bb[3] += puzzle.snapTolerance;
  }
  
  
  // calculcate offset between mousePressed and xPos/yPos of tile
  void calcOffset()
  { 
    offsetX = mouseX - xPos;
    offsetY = mouseY - yPos;
  }
  
  
  boolean isInsideBB(int _x, int _y)
  {
    // check bounding box
    if(_x > bb[0] && _x < bb[1] && _y > bb[2] && _y < bb[3]) {
      return true;
    } else {
      return false;
    }
  }
  
  // is coord. inside polygon?
  boolean isInside(int _x, int _y)
  {  
    if( isInsideBB(_x, _y) ) {
      float b0, b1, b2, b3;
      int n = vtx.length;
        
      for(int i = 0; i < n; i++) {
        int result = (_y - vtx[i][Y]) * (vtx[(i+1) % n][X] - vtx[i][X]) - (_x - vtx[i][X]) * (vtx[(i+1) % n][Y] - vtx[i][Y]);
        if(result > 0) {
          return false;  // outside
        }
      }
      return true;  // must be inside or on line
    } else {
      return false; // outside bounding box
    }
  }  
  
  
  // move to new position using coords for vertex given
  void moveTo(int index, int _x, int _y)
  {
    int moveX = _x - vtx[index][X];
    int moveY = _y - vtx[index][Y];
    xPos += moveX;
    yPos += moveY;
    calcOffset();  // offset to mouse position has changed!
    calcVtx();
  }
    

  // new position; recalculate vtx
  void updatePos(int _x, int _y)
  {
    if(isOver) {
      xPos = _x - offsetX;
      yPos = _y - offsetY;
    } else {
      xPos = _x;
      yPos = _y;
    }
    calcVtx();
  }

  
  // calculate vertices for current position
  void calcVtx()
  {
    float x = 0;
    float y = 0;
    for(int i = 0; i < ang.length; i++) {
      x += unit * sides[i] * cos(ang[i]);
      vtx[i][X] = int(x + xPos + 0.5);  // add 0.5 for rounding
      y += unit * sides[i] * sin(ang[i]);
      vtx[i][Y] = int(y + yPos + 0.5);
    }
    calcBoundingBox();
  }


  void rotate(int direction)
  {
    // direction: -1 is CCW; 1 is CW
    for(int i = 0; i < ang.length; i++) {
      ang[i] += rotInc * direction;
      if(ang[i] <= 0) ang[i] = TWO_PI + ang[i];
      else if(ang[i] > TWO_PI) ang[i] = ang[i] - TWO_PI; 
    }
    calcVtx();
  }


  void flip()
  {
    // To flip a tile over, reverse the order of the numbers and subtract
    // each one from TWO_PI. (Also reverse order of sides!)
    if(flipped) flipped = false;
    else { flipped = true; };
  
    // flip ang array (Fred Swartz) and subtract from PI; flip sides array
    int left  = 0;              // index of leftmost element
    int right = ang.length-1;   // index of rightmost element
  
    while (left < right) {
      // exchange the left and right elements
      float tempAng = ang[left]; 
      float tempSide = sides[left];
      ang[left]  = TWO_PI - ang[right];
      ang[right] = TWO_PI - tempAng;
      sides[left] = sides[right];
      sides[right] = tempSide;
     
      // move the bounds toward the center
      left++;
      right--;
    } 
    // need to also do subtraction for center index!!!
    if(ang.length % 2 != 0) ang[left] = TWO_PI - ang[left];

    // recenter
    xPos = bb[0] + bb[1] - xPos;
    calcVtx();
  }


  void display()
  {
    if(puzzle.tileSelected && puzzle.selected == this) {
      if(showBB) drawBoundingBox();  // DEBUG
      stroke(puzzle.selColor);
    }
    
    fill(c);
    beginShape(POLYGON);
    {
      for(int i = 0; i < vtx.length; i++) {
        vertex( vtx[i][X], vtx[i][Y] );
      }
    }
    endShape();
    noStroke();
  }  
  
  void drawBoundingBox()
  {
     stroke(100, 100, 100);
      beginShape(LINE_LOOP);
      {
        vertex( bb[0], bb[3] );
        vertex( bb[1], bb[3] );
        vertex( bb[1], bb[2] );
        vertex( bb[0], bb[2] );
        vertex( bb[0], bb[3] );                   
      }
      endShape();
      noStroke();
  }  
  
}  // end Tile class