hexinfinity.java

good project for programmer,,

                shortestGap = gap;
                contB = i;
                countryB = j;
              }
            }
          }
        }
      }

      if(countryB != -1) {
        lines.add(connectCountries(countryA, countryB));
        countriesConnected[countryA][countryB] = true;
        countriesConnected[countryB][countryA] = true;
        contsConnected[contA][contB] = true;
        contsConnected[contB][contA] = true;
      }
    }

    //kill dead ends
    for(int a = 0; a < numContinents; a += 1) {
      int connectedConts = 0;
      for(int i = 0; i < numContinents; i += 1) {
        if(i != a && contsConnected[i][a]) {
          connectedConts += 1;
        }
      }

      if(connectedConts == 1) {
        newconnection:
        for(int t = 0; t < 10; t += 1) {
          double shortestGap = 10000;
          int contA = a;
          int countryA = contIndices[contA] + rand.nextInt(contIndices[contA+1] - contIndices[contA]);
          int contB = -1;
          int countryB = -1;

          for(int i = 0; i < numContinents; i += 1) {
            if(i != contA) {
              for(int j = contIndices[i]; j < contIndices[i+1]; j += 1) {
                if(!contsConnected[contA][i] && !countriesConnected[countryA][j] && countriesConnectable(countryA, j)) {
                  double gap = dist(polygonCenter((Polygon)countryPolygons.get(countryA)),
                                    polygonCenter((Polygon)countryPolygons.get(j)));
                  if(gap < shortestGap) {
                    shortestGap = gap;
                    contB = i;
                    countryB = j;
                  }
                }
              }
            }
          }
          if(countryB != -1) {
            lines.add(connectCountries(countryA, countryB));
            countriesConnected[countryA][countryB] = true;
            countriesConnected[countryB][countryA] = true;
            contsConnected[contA][contB] = true;
            contsConnected[contB][contA] = true;
            break newconnection;
          }
        }
      }
    }

    return lines;
  }

  //can we connect contA and contB? no if the resulting line would cross another continent
  private boolean countriesConnectable(int countryA, int countryB) {
    Line2D.Double l = new Line2D.Double(polygonCenter((Polygon)countryPolygons.get(countryA)),
                                        polygonCenter((Polygon)countryPolygons.get(countryB)));
    for(int i = 0; i < countryPolygons.size(); i += 1) {
      if(i != countryA && i != countryB) {
        Polygon p = (Polygon)countryPolygons.get(i);
        p = dilatePolygon(p, 1.2);
        Line2D.Double l1 = new Line2D.Double(p.xpoints[0], p.ypoints[0], p.xpoints[1], p.ypoints[1]);
        Line2D.Double l2 = new Line2D.Double(p.xpoints[1], p.ypoints[1], p.xpoints[2], p.ypoints[2]);
        Line2D.Double l3 = new Line2D.Double(p.xpoints[2], p.ypoints[2], p.xpoints[0], p.ypoints[0]);
        if(l.intersectsLine(l1) || l.intersectsLine(l2) || l.intersectsLine(l3)) return false;
      }
    }
    return true;
  }

  private Polygon dilatePolygon(Polygon p, double ratio) {
    Point c = polygonCenter(p);
    int[] xpoints = new int[p.npoints];
    int[] ypoints = new int[p.npoints];
    for(int i = 0; i < p.npoints; i += 1) {
       xpoints[i] = (int)(c.x + ratio*(p.xpoints[i] - c.x));
       ypoints[i] = (int)(c.y + ratio*(p.ypoints[i] - c.y));
    }
    return new Polygon(xpoints, ypoints, p.npoints);
  }

  //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 connectCountries(int country1, int country2) {
    ((Vector)connections.get(country1)).add(new Integer(country2));
    ((Vector)connections.get(country2)).add(new Integer(country1));

    return drawLineBetween((Polygon)countryPolygons.get(country1),
                           (Polygon)countryPolygons.get(country2));
  }


  private boolean trianglesIntersect(Polygon a, Polygon b) {
    if(a.contains(polygonCenter(b))) return true;
    if(b.contains(polygonCenter(a))) return true;
    if(b.contains(a.xpoints[0], a.ypoints[0])) return true;
    if(b.contains(a.xpoints[1], a.ypoints[1])) return true;
    if(b.contains(a.xpoints[2], a.ypoints[2])) return true;
    if(a.contains(b.xpoints[0], b.ypoints[0])) return true;
    if(a.contains(b.xpoints[1], b.ypoints[1])) return true;
    if(a.contains(b.xpoints[2], b.ypoints[2])) return true;

    return false;
  }

  //write the xml representation of a country polygon
  private void writePolygon(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(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(Line2D.Double l) {
    out.write("<line><position>" + (int)l.x1 + "," + (int)l.y1 + " " +
                                   (int)l.x2 + "," + (int)l.y2 + "</position></line>\n");
  }

  //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);
  }


  private Polygon upTriangleAround(Point p) {
    int[] xpoints = new int[3];
    int[] ypoints = new int[3];
    xpoints[0] = p.x;
    ypoints[0] = p.y + (int)tRad;
    xpoints[1] = p.x - (int)(tRad*Math.sqrt(3)/2);
    ypoints[1] = p.y - (int)(tRad/2);
    xpoints[2] = p.x + (int)(tRad*Math.sqrt(3)/2);
    ypoints[2] = p.y - (int)(tRad/2);

    return new Polygon(xpoints, ypoints, 3);
  }

  private Polygon downTriangleAround(Point p) {
    int[] xpoints = new int[3];
    int[] ypoints = new int[3];
    xpoints[0] = p.x;
    ypoints[0] = p.y - (int)tRad;
    xpoints[1] = p.x - (int)(tRad*Math.sqrt(3)/2);
    ypoints[1] = p.y + (int)(tRad/2);
    xpoints[2] = p.x + (int)(tRad*Math.sqrt(3)/2);
    ypoints[2] = p.y + (int)(tRad/2);

    return new Polygon (xpoints, ypoints, 3);
  }

  private boolean trianglePointsUp(Polygon p) {
    Point c = polygonCenter(p);
    int pointsAbove = 0;
    for(int i = 0; i < 3; i += 1) {
      if(p.ypoints[i] > c.y) pointsAbove += 1;
    }
    if(pointsAbove == 1) return true;
    return false;
  }

  private boolean polygonFitsOnScreen(Polygon p) {
    for(int i = 0; i < p.npoints; i += 1) {
      if(p.xpoints[i] < 0 || p.xpoints[i] > width || 
         p.ypoints[i] < 0 || p.ypoints[i] > height) {
           return false;
      }
    }
    return true;
  }

  //pick a name for a continent (consonant - vowel - consonant)
  private String makeContinentName() {
    return new String(new char[]{Character.toUpperCase(consonants[rand.nextInt(numConsonants)]),
                                  vowels[rand.nextInt(numVowels)],
                                  consonants[rand.nextInt(numConsonants)]});
  }

  //pick a name for a country (contName - vowel - consonant)
  private String makeCountryName(String continentName) {
    return continentName + new String(new char[]{vowels[rand.nextInt(numVowels)],
                                                 consonants[rand.nextInt(numConsonants)]});
  }

  //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);
  }

  public boolean canCache() {
    return false;
  }

  public String description() {
    return "Generates maps like those of the Hex series.";
  }

  private static final String CHOICE_SMALL = "HexInfinity - small";
  private static final String CHOICE_MEDIUM = "HexInfinity - medium";
  private static final String CHOICE_LARGE = "HexInfinity - large";
  private static final String CHOICE_HUGE = "HexInfinity - huge";

  public java.util.List getChoices() {
    Vector v = new Vector();
    v.add(CHOICE_SMALL);
    v.add(CHOICE_MEDIUM);
    v.add(CHOICE_LARGE);
    v.add(CHOICE_HUGE);
    return v;
  }


  public float version() {
    return 1.0f;
  }

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

  public String message(String message, Object data) {
    return "";
  }

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