appletframe.java

魔方问题是算法设计中一个难点

import java.awt.*;
import java.applet.Applet;

/*** nur fuer die Application-Version:

////////////////////////////////////////////////////////////////////
// AppletFrame
//
class AppletFrame extends Frame {

  public static void startApplet (String className,
                                  String title) {
    Applet a;
    try {
      a = (Applet) Class.forName(className).newInstance();
    }
    catch (ClassNotFoundException e) {return;}
    catch (InstantiationException e) {return;}
    catch (IllegalAccessException e) {return;}

    a.init();
    a.start();

    AppletFrame f = new AppletFrame (title);
    f.add ("Center", a);
    f.pack(); // passt die Groesse an preferredSize() der Komponenten an
    f.show();
  }

  public AppletFrame (String name) {
    super (name); // java.awt.Frame(String) constructor
  }

  public boolean handleEvent (Event e) {
    if (e.id == Event.WINDOW_DESTROY) {
      System.exit (0);
      return true;
    }
    return super.handleEvent(e);
  }
}

***/

////////////////////////////////////////////////////////////////////
// Projektion
//

class Point3 {
  public Point3 () {
    X = new float[3];
    X[0] = 0.0f; X[1] = 0.0f; X[2] = 0.0f;
  }

  public Point3 (float x, float y, float z) {
    X = new float[3];
    X[0] = x; X[1] = y; X[2] = z;
  }

  // Zur Einsparung von Modulo-Arithmetik
  public float get (int n)              {return X[n%3];}
  public void  set (int n, float value) {X[n%3] = value;}
  public void  inc (int n, float value) {X[n%3] += value;}

  private float[] X;
}

class Prj {
  // <APPLET code="RubikSimul.class" width=456 height=457>
  private static final int border = 8;
  private static final int a  = 23;  // halbe Laenge der projizierten Wuerfelkanten
  private static final int a2 = 2*a;
  private static final int b  = 40;  // a * sqrt(3)
/* kleinere Variante
  // <APPLET code="RubikSimul.class" width=298 height=305>
  private static final int border = 6;
  private static final int a  = 15;  // halbe Laenge der projizierten Wuerfelkanten
  private static final int a2 = 2*a;
  private static final int b  = 26;  // a * sqrt(3)
*/
  private static final int x0 = border + (int)(5.5*b);
  private static final int y0 = border + (int)(8.5*a);

  //            / \                In Wirklichkeit
  // y        /     \        z     alle Winkel
  //  \     /         \     /      im 30?Raster
  //    \ /             \ /
  //     |\             /|
  //     |  \         /  |
  //     |    \     /    |
  //     |      \ /      |
  //     |       |       |
  //     |.......|..b....|
  //      \      |      /
  //        \   a|    /a2
  //          \  |  /
  //            \|/
  //             |
  //             |
  //             x

  public static Point P2D (Point3 p) {
    return new Point ((int)(x0               - b*p.get(1) + b*p.get(2)),
                      (int)(y0 + a2*p.get(0) - a*p.get(1) - a*p.get(2)));
  }

  public static Dimension preferredSize () {
    return new Dimension (11 * b + 2*border,
                          (int)(19.5 * a) + 2 * border);
  }
}

////////////////////////////////////////////////////////////////////
// Elementarwuerfel
//

class Cube {
  private static Color[] color;
  static {
    color = new Color[6];
    color[0] = new Color (255,   0,   0); // hellrot
    color[1] = new Color (  0,   0, 255); // blau
    color[2] = new Color (255, 255, 255); // weiss
    color[3] = new Color (255, 255,   0); // gelb
    color[4] = new Color (  0, 128,   0); // gruen
    color[5] = new Color (128,   0,   0); // dunkelrot
  }

  public Cube () {
    face = new int[6];
    reset ();
  }

  void reset () {
    for (int i=0; i<6; i++) face[i] = i;
  }

  void rotate (int nAxis) {
    int h               = face[  (nAxis+2)%3];
    face[  (nAxis+2)%3] = face[3+(nAxis+1)%3];
    face[3+(nAxis+1)%3] = face[3+(nAxis+2)%3];
    face[3+(nAxis+2)%3] = face[  (nAxis+1)%3];
    face[  (nAxis+1)%3] = h;
  }

  void paint (Graphics g, Point3 X, boolean back) { // Lage im Gesamtwuerfel
    // zeigt den Einzelwuerfel als Teil eines n*n*n-Wuerfels
    // nur die aussenliegenden Flaechen werden gemalt
    for (int n=0; n<3; n++) {
      if (X.get(n) == (back ? 2 : 0)) { // Ebene n ? (0=y-z, 1=z-y, 2=x-y)
        Point P;
        if (back) X.inc (n, 3.5f);
        Polygon p = new Polygon();
        P = Prj.P2D (X); p.addPoint (P.x, P.y); X.inc(n+1, 1);
        P = Prj.P2D (X); p.addPoint (P.x, P.y); X.inc(n+2, 1);
        P = Prj.P2D (X); p.addPoint (P.x, P.y); X.inc(n+1,-1);
        P = Prj.P2D (X); p.addPoint (P.x, P.y); X.inc(n+2,-1);
        P = Prj.P2D (X); p.addPoint (P.x, P.y); // Polygon schliessen
        if (back) X.inc (n, -3.5f);
        g.setColor (color[face[(n + (back ? 3 : 0)) % 6]]);
        g.fillPolygon (p);
        g.setColor (Color.black);
        g.drawPolygon (p);
      }
    }
  }

  int[] face;  // Farbnummern der Seiten,
}              // Reihenfolge: x=0, y=0, z=0, x=1, y=1, z=1

////////////////////////////////////////////////////////////////////
// Rubik-Wuerfel
//

class RubikCube {

  RubikCube () {
    cube = new Cube[N][N][N];
    for (int x=0; x<N; x++)
      for (int y=0; y<N; y++)
        for (int z=0; z<N; z++)
          cube[x][y][z] = new Cube();
    bPreview = false;
  }

  void reset () {
    for (int x=0; x<N; x++)
      for (int y=0; y<N; y++)
        for (int z=0; z<N; z++)
          cube[x][y][z].reset ();
  }

  void rotate (int n,          // Achse (0=x, 1=y, 2=z)
               int x,          // Ebene (0..N-1)
               int nQuarters) {
    Point3 P = new Point3();
    for (int r=0; r<nQuarters; r++) { // Vierteldrehungen
      for (int y=0; y<N; y++) {       // Elementarwuerfel in sich drehen
        for (int z=0; z<N; z++) {
          P.set (n,   x);
          P.set (n+1, y);
          P.set (n+2, z);
          getCube(P).rotate (n);
        }
      }
      for (int y=0; y<(N+1)/2; y++) { // Elementarwuerfel zyklisch austauschen
        for (int z=0; z<N/2; z++) {
          P.set (n,   x);             // Wuerfel aus einem Quadranten der Schicht
          P.set (n+1, y);
          P.set (n+2, z);
          float t;
          int[] X = new int[4];
          int[] Y = new int[4];
          int[] Z = new int[4];

          for (int i=0; i<4; i++) {   // Vierergruppe ermitteln
            X[i] = (int)P.get(0);
            Y[i] = (int)P.get(1);
            Z[i] = (int)P.get(2);
            t = P.get(n+1);  P.set(n+1, P.get(n+2));  P.set (n+2, N-1-t);
          }
          Cube h = cube[X[3]][Y[3]][Z[3]]; // zyklisch austauschen
          for (int i=3; i>0; i--)
            cube[X[i]][Y[i]][Z[i]] = cube[X[i-1]][Y[i-1]][Z[i-1]];
          cube[X[0]][Y[0]][Z[0]] = h;
        }
      }
    }
  }

  private boolean bPreview; // Richtungspfeil zeigen
  private int  nAxis;    // \.
  private int  nLevel;   //  > Daten f黵 Richtungspfeil
  private int  nRot;     // /

  boolean getMouseInfo (int xM, int yM) {
    Point[] P = new Point[4];
    for (int n=0; n<3; n++) {        // Mausklick in Ebene n ?
      Point3 X = new Point3 (0,0,0); // (0=y-z, 1=z-y, 2=x-y)
      //X[n] = 0;
      for (int i=0; i<N; i++) {
        X.set (n+1, i);
        for (int j=0; j<N; j++) {
          X.set (n+2, j);
          P[0] = Prj.P2D (X);  X.inc (n+1, 1);
          P[1] = Prj.P2D (X);  X.inc (n+2, 1);
          P[2] = Prj.P2D (X);  X.inc (n+1,-1);
          P[3] = Prj.P2D (X);
          Polygon p = new Polygon();
          p.addPoint (P[0].x, P[0].y);
          p.addPoint (P[1].x, P[1].y);
          p.addPoint (P[2].x, P[2].y);
          p.addPoint (P[3].x, P[3].y);
          p.addPoint (P[0].x, P[0].y);
          if (p.inside (xM, yM)
            && 2*j+1 != N) { // nicht mittlere Felder
            nAxis  = (n+1)%3;
            nLevel = i;
            nRot   = (j<N/2) ? 1 : 3;
            return true;
          }
        }
      }
    }
    return false;
  }

  void onMouseClick (int xM, int yM) {
    bPreview = getMouseInfo (xM, yM);
    if (! bPreview) return;
      rotate (nAxis, nLevel, nRot);
  }

  void onMouseMove (Graphics g, int xM, int yM) {
    int oldAxis  = nAxis;
    int oldLevel = nLevel;
    int oldRot   = nRot;
    boolean bNewPreview = getMouseInfo (xM, yM);
    int newAxis  = nAxis;
    int newLevel = nLevel;
    int newRot   = nRot;

    if (! bPreview && ! bNewPreview) return; // weiter au遝rhalb
    if (bPreview && bNewPreview && nAxis == oldAxis
      && nLevel == oldLevel && nRot == oldRot)
      return;                                // gleiche Situation

    nAxis  = oldAxis;
    nLevel = oldLevel;
    nRot   = oldRot;

    if (bPreview) previewRotation (g, false); // alter Pfeil
    bPreview = bNewPreview;
    nAxis  = newAxis;
    nLevel = newLevel;
    nRot   = newRot;
    if (bPreview) previewRotation (g, true);  // neuer Pfeil
  }

  static Point interpolation (int w1, Point p1, int w2, Point p2) {
    int s = w1 + w2;
    return new Point ((w1 * p1.x + w2 * p2.x) / s,
                      (w1 * p1.y + w2 * p2.y) / s);
  }

  Polygon makeArrow (Polygon p, boolean bReverse) {
    // Erzeugt ein pfeilf鰎miges Polygon Q[9]
    // im Innern des abgeknickten Doppelparallelogramms P[6]
    //
    // P[0]--------5-----------4   P[6]: Au遝nkontur
    //   |            6\       |   in Wirklichkeit zwei
    //   |  Q[0]---8--7  \     |   Parallelogramme:
    //   |    |            5   |   0125 und 5234
    //   |    1----2--3  /     |
    //   |            4/       |   Q[9]: Pfeil
    //   1---------2-----------3
    //
    Point P1 = new Point(0,0);
    Point P2 = new Point(0,0);
    Point[] P = new Point[6];
    Point[] Q = new Point[9];
    for (int i=0; i<6; i++)
      P[i] = new Point (p.xpoints[i], p.ypoints[i]);
    for (int i=0; i<9; i++)
      Q[i] = new Point(0,0);

    if (bReverse) { // Pfeil in umgekehter Richtung
      Point t = P[0]; P[0] = P[4]; P[4] = t;
            t = P[1]; P[1] = P[3]; P[3] = t;
    }
    P1   = interpolation (1, P[0], 1, P[5]);
    P2   = interpolation (1, P[1], 1, P[2]);
    Q[0] = interpolation (5, P1,   3, P2);
    Q[1] = interpolation (3, P1,   5, P2);
    Q[2] = interpolation (3, P[5], 5, P[2]);
    Q[8] = interpolation (5, P[5], 3, P[2]);
    P1   = interpolation (1, P[4], 1, P[5]);
    P2   = interpolation (1, P[3], 1, P[2]);
    Q[5] = interpolation (1, P1,   1, P2);
    P1   = interpolation (1, P1,   1, P[5]);
    P2   = interpolation (1, P2,   1, P[2]);
    Q[6] = interpolation (3, P1,   1, P2);
    Q[7] = interpolation (5, P1,   3, P2);
    Q[3] = interpolation (3, P1,   5, P2);
    Q[4] = interpolation (1, P1,   3, P2);

    Polygon q = new Polygon();
    for (int i=0; i<9; i++)
      q.addPoint (Q[i].x, Q[i].y);
    q.addPoint (Q[0].x, Q[0].y); // Polygon schliessen
    return q;
  }

  void previewRotation (Graphics g, boolean bShow) {
    Point[] P = new Point[6];
    Point[] Q = new Point[9];
    if (bShow) {
      Point3 X = new Point3(0,0,0);
      int n = nAxis;
      X.set(n, nLevel);
      X.set(n+1, 1);
      X.set(n+2, 0);
      P[0] = Prj.P2D (X);  X.inc(n+0, 1);
      P[1] = Prj.P2D (X);  X.inc(n+1,-1);
      P[2] = Prj.P2D (X);  X.inc(n+2, 1);
      P[3] = Prj.P2D (X);  X.inc(n+0,-1);
      P[4] = Prj.P2D (X);  X.inc(n+2,-1);
      P[5] = Prj.P2D (X);
      Polygon p = new Polygon();
      for (int i=0; i<6; i++)
        p.addPoint (P[i].x, P[i].y);
      Polygon q = makeArrow (p, nRot == 3);
      g.setColor (Color.lightGray);
      g.fillPolygon (q);
      g.setColor (Color.black);
      g.drawPolygon (q);
    }
    else {
      Point3 X = new Point3();
      X.set (nAxis, nLevel);
      getCube(X).paint (g, X, false);
    }
  }

  void paint (Graphics g) {
    // Ansicht von vorn
    for (int x=0; x<N; x++) {
      for (int y=0; y<N; y++) {
        for (int z=0; z<N; z++)
          cube[x][y][z].paint (g, new Point3 (x,y,z), true);
      }
    }
    // Einzelne Rueckseiten
    for (int x=0; x<N; x++) {
      for (int y=0; y<N; y++) {
        for (int z=0; z<N; z++)
          cube[x][y][z].paint (g, new Point3 (x,y,z), false);
      }
    }
    // ggf. Richtungspfeil
    if (bPreview)
      previewRotation (g, true);
  }

  protected static final int N = 3;

  Cube getCube (Point3 P) {
    return cube[(int)P.get(0)][(int)P.get(1)][(int)P.get(2)];
  }

  Cube cube[][][];
}

////////////////////////////////////////////////////////////////////