islandinfinity.java

good project for programmer,,

        Point ret = new Point(bounds.x + rand.nextInt(bounds.width),
                              bounds.y + rand.nextInt(bounds.height));
        if(new Ellipse2D.Double(bounds.x, bounds.y, bounds.width, bounds.height).contains(ret)) return ret;
      }
    }

    debug("UNKNOWN CONT TYPE");
    return null;
  }

  //find the point on the continent border with the given angle to center.
  //we do this by a binary search for the border
  private Point getPointOnContinentBorder(Point center, double theta, Rectangle border, int contType) {

    if(!border.contains(center)) debug("border doesn't contain center!");

    if(contType == CONT_RECT || contType == CONT_ELLIPSE) {
      RectangularShape rs = null;
      if(contType == CONT_RECT) {
        rs = border;
      } else if(contType == CONT_ELLIPSE) {
        rs = new Ellipse2D.Double(border.x, border.y, border.width, border.height);
      }

      int radius = 1000;
      Point ret = null;
      int movement = 500;
      for(int i = 0; i < 20; i += 1) {
        ret = new Point((int)(center.x + radius*Math.cos(theta)), (int)(center.y + radius*Math.sin(theta)));

        if(rs.contains(ret)) {
          radius += movement;
        } else {
          radius -= movement;
        }
        movement /= 2;
      }

      return ret;
    }

    debug("GPOCB: unkown cont type");
    return null;

  }

  //connect up the continents so that any country can reach any other country.
  //the algorithm is to make the shortest valid connection at each step until
  //all continents are reacheable. we return a Vector of lines that should be
  //drawn representing the connections we made
  private Vector makeConnectionsBetweenContinents(
              int[] contIndices, Point[] contCenters, Rectangle[] contBounds, int numContinents) {
    //an array saying whether there is a direct connection between any two continents
    boolean[][] contsConnected = new boolean[numContinents][numContinents];
    for(int i = 0; i < numContinents; i += 1) {
      for(int j = 0; j < numContinents; j += 1) {
        contsConnected[i][j] = false;
      }
    }

    Vector lines = new Vector();

    //connect continents until they are all connected
    while(!allContsReachableFrom(0, contsConnected, numContinents)) {
      double shortestGap = 10000;
      int contA = -1;
      int contB = -1;
      for(int i = 0; i < numContinents; i += 1) {
        for(int j = 0; j < numContinents; j += 1) {
          if(!contsConnected[i][j] && contsConnectable(i, j, contBounds, contCenters, numContinents)) {
            double gap = dist(contCenters[i], contCenters[j]);
            if(gap < shortestGap) {
              shortestGap = gap;
              contA = i;
              contB = j;
            }
          }
        }
      }
      contsConnected[contA][contB] = true;
      contsConnected[contB][contA] = true;
      lines.add(connectContinents(contA, contB, contIndices));
    }

    for(int i = 0; i < numContinents; i += 1) {
      int connectedConts = 0;
      for(int j = 0; j < numContinents; j += 1) {
        if(contsConnected[i][j]) connectedConts += 1;
      }

      debug("connectedConts[" + i + "] = " + connectedConts);

      if(connectedConts == 2) { //dead end
        double shortestGap = 10000;
        int contB = -1;
        for(int j = 0; j < numContinents; j += 1) {
          if(!contsConnected[i][j] && contsConnectable(i, j, contBounds, contCenters, numContinents)) {
            double gap = dist(contCenters[i], contCenters[j]);
            if(gap < shortestGap) {
              shortestGap = gap;
              contB = j;
            }
          }
        }

        debug("XXXXXXXXXXXX");
        if(contB != -1) {
          lines.add(connectContinents(i, contB, contIndices));
          contsConnected[i][contB] = true;
          contsConnected[contB][i] = true;
        }
      }
    }

    return lines;
  }

  //can we connect contA and contB? no if the resulting line would cross another continent
  private boolean contsConnectable(int contA , int contB, Rectangle[] contBounds, Point[] contCenters, int numContinents) {
    Line2D.Double l = new Line2D.Double(contCenters[contA], contCenters[contB]);
    for(int i = 0; i < numContinents; i += 1) {
      if(i != contA && i != contB) {
        if(l.intersects(contBounds[i])) return false;
      }
    }
    return true;
  }

  //can all continents be reached from start?
  private boolean allContsReachableFrom(int start, boolean[][] contsConnected, int numContinents) {
    boolean[] reachedAlready = new boolean[numContinents];
    for(int i = 0; i < numContinents; i += 1) {
      reachedAlready[i] = false;
    }
    reachedAlready[start] = true;

    int numReached = 1;
    for(int i = 0; i < numContinents; i += 1) {
      if(contsConnected[start][i] && i != start) {
        reachedAlready = whichContsReachableFrom(i, contsConnected, reachedAlready, numContinents);
      }
    }
    for(int i = 0; i < numContinents; i += 1) {
      if(!reachedAlready[i]) return false;
    }
    return true;
  }

  //which continents can be reached from start?
  private boolean[] whichContsReachableFrom(
               int start, boolean[][] contsConnected, boolean[] reachedAlready, int numContinents) {
    int numReached = 1;
    reachedAlready[start] = true;
    for(int i = 0; i < numContinents; i += 1) {
      if(contsConnected[start][i] && !reachedAlready[i]) {
        reachedAlready = whichContsReachableFrom(i, contsConnected, reachedAlready, numContinents);
      }
    }
    return reachedAlready;
  }

  //connect cont1 and cont2, adding the connection to the connections Vector
  //and returning the line to draw on the board
  private Line2D.Double connectContinents(int cont1, int cont2, int[] contIndices) {
    int bestPolygon1 = -1;
    int bestPolygon2 = -1;
    double bestLength = 10000;
    for(int j = contIndices[cont1]; j < contIndices[cont1+1]; j += 1) {
      for(int k = contIndices[cont2]; k < contIndices[cont2+1]; k += 1) {
        Point a = polygonCenter((Polygon)countryPolygons.get(j));
        Point b = polygonCenter((Polygon)countryPolygons.get(k));
        double dist = dist(a, b);
        if(dist < bestLength) {
          bestLength = dist;
          bestPolygon1 = j;
          bestPolygon2 = k;
        }
      }
    }

    ((Vector)connections.get(bestPolygon1)).add(new Integer(bestPolygon2));
    ((Vector)connections.get(bestPolygon2)).add(new Integer(bestPolygon1));

    return drawLineBetween((Polygon)countryPolygons.get(bestPolygon1),
                           (Polygon)countryPolygons.get(bestPolygon2));
  }

  //write the xml representation of a country polygon
  private void writePolygon(PrintWriter out, Polygon p) {
    out.write("<polygon>");
    for(int i = 0; i < p.npoints; i += 1) {
      out.write("" + p.xpoints[i] + "," + p.ypoints[i] + " ");
    }
    out.write("</polygon>\n");

  }

  //write the xml representation of a country's adjoining list
  private void writeConnections(PrintWriter out, Vector conns) {
    out.write("<adjoining>");
    for(int i = 0; i < conns.size()-1; i += 1) {
      out.write("" + (Integer)conns.get(i) + ",");
    }
    if(conns.size() > 0) out.write("" + (Integer)conns.get(conns.size()-1));
    out.write("</adjoining>\n");
  }

  //write the xml representation of a line
  private void writeLine(PrintWriter out, Line2D.Double l) {
    out.write("<line><position>" + (int)l.x1 + "," + (int)l.y1 + " " +
                                   (int)l.x2 + "," + (int)l.y2 + "</position></line>\n");
  }

  //distance between two points
  private double dist(Point a, Point b) {
    return Math.sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
  }

  //find the center of gravity of a polygon
  private Point polygonCenter(Polygon p) {
    double x = 0;
    double y = 0;
    for(int i = 0; i < p.npoints; i += 1) {
      x += p.xpoints[i];
      y += p.ypoints[i];
    }
    x /= p.npoints;
    y /= p.npoints;
    return new Point((int)x, (int)y);
  }

  //draw a line between the polygons with endpoints on their perimeters
  //we do this through a binary search for their boundaries
  private Line2D.Double drawLineBetween(Polygon a, Polygon b) {
    Point ca = polygonCenter(a);
    Point cb = polygonCenter(b);

    double theta = Math.atan2(ca.y - cb.y, ca.x - cb.x);

    double radius = dist(ca, cb);
    double movement = radius/2;
    for(int i = 0; i < 20; i += 1) {
      ca = new Point((int)(cb.x + radius*Math.cos(theta)), (int)(cb.y + radius*Math.sin(theta)));
      if(a.contains(ca)) {
        radius -= movement;
      } else {
        radius += movement;
      }
      movement /= 2;
    }
    radius += 5; //make sure the line isn't detached
    ca = new Point((int)(cb.x + radius*Math.cos(theta)), (int)(cb.y + radius*Math.sin(theta)));

    theta += Math.PI;

    radius = dist(ca, cb);
    movement = radius/2;
    for(int i = 0; i < 20; i += 1) {
      cb = new Point((int)(ca.x + radius*Math.cos(theta)), (int)(ca.y + radius*Math.sin(theta)));
      if(b.contains(cb)) {
        radius -= movement;
      } else {
        radius += movement;
      }
      movement /= 2;
    }
    radius += 5; //make sure the line isn't detached
    cb = new Point((int)(ca.x + radius*Math.cos(theta)), (int)(ca.y + radius*Math.sin(theta)));

    return new Line2D.Double(ca, cb);
  }

  //interface function. should be true on release
  public boolean canCache() {
    return true;
  }

  public String description() {
    return "Makes maps consisting of island continents.";
  }

  //user size choices
  static final String CHOICE_NORMAL = "IslandInfinity - Hawaii";
  static final String CHOICE_BIG = "IslandInfinity - normal";
  static final String CHOICE_HUGE = "IslandInfinity - big";
  static final String CHOICE_REALLYHUGE = "IslandInfinity - huge";

  public java.util.List getChoices() {
    Vector v = new Vector();
    v.add(CHOICE_NORMAL);
    v.add(CHOICE_BIG);
    v.add(CHOICE_HUGE);
    v.add(CHOICE_REALLYHUGE);
    return v;
  }

  //interface function; unused
  public String message(String message, Object data) {
    return "";
  }

  public String name() {
    return "IslandInfinity";
  }

  public float version() {
    return 1.0f;
  }

  private void debug(String s) {
//    System.out.println(":" + s);
  }
}