////////////////////////HexInfinity Lux Map Generator//Generates maps for Lux like those of the Hex series//Greg McGlynn//////////////////////package org.mcglynns.lux;import com.sillysoft.lux.*;import java.awt.*;import java.awt.geom.*;import java.util.*;import java.io.*;public class HexInfinity implements LuxMapGenerator {  //used in making names  static char[] consonants = new char[]{'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm',                                        'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'z'};  static char[] vowels = new char[]{'a', 'e', 'i', 'o', 'u'};  static int numConsonants = consonants.length;  static int numVowels = vowels.length;  Random rand;  int width, height, numContinents;  Vector[] continents;  Vector connections;  Vector countryPolygons;  Point[] contCenters;  int[] contIndices;  static final double tRad = 30;  static final double tHeight = 3*tRad/2;  static final double tWidth = Math.sqrt(3)*tRad;  PrintWriter out;  public boolean generate(PrintWriter out, String choice, int seed, MapLoader loader) {    rand = new Random(seed);    this.out = out;    int variation;    if(choice == CHOICE_SMALL) {      width = 600;      height = 400;      numContinents = 10;      variation = 1;    } else if(choice == CHOICE_MEDIUM) {      width = 750;      height = 500;      numContinents = 14;      variation = 2;    } else if(choice == CHOICE_LARGE) {      width = 900;      height = 600;      numContinents = 20;      variation = 3;    } else { //(choice == CHOICE_HUGE)      width = 1000;      height = 700;      numContinents = 30;      variation = 4;    }    numContinents += rand.nextInt(2*variation + 1) - variation;    contCenters = new Point[numContinents];    continents = new Vector[numContinents];    loader.setLoadText("Creating map.... (this can take a few seconds)");    out.write("<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n" +              "<luxboard>\n" +              "<version>1.0</version>\n" +              "<width>" + width + "</width>\n" +              "<height>" + height + "</height>\n" +              "<theme>Air</theme>\n" +              "<author>HexInfinity Generator (by Greg McGlynn)</author>\n" +              "<email>greg@mcglynns.org</email>\n" +              "<webpage>www.sillysoft.net</webpage>\n" +              "<title>" + choice + " #" + seed + "</title>\n" +              "<description>This map was made by the HexInfinity LuxMapGenerator. Type: " + choice +                       ",  Number of continents: " + numContinents  + "</description>\n");    loader.setLoadText("Creating map.... (this can take a few seconds)");    debug("making seeds");    makeContinentSeeds();    growContinents();    countryPolygons = new Vector();    connections = new Vector();    contIndices = new int[numContinents+1];    for(int i = 0; i < numContinents; i += 1) {      contIndices[i] = countryPolygons.size();      for(int j = 0; j < continents[i].size(); j += 1) {        countryPolygons.add((Polygon)continents[i].get(j));        connections.add(new Vector());      }      for(int j = contIndices[i]; j < countryPolygons.size(); j += 1) {        for(int k = contIndices[i]; k < countryPolygons.size(); k += 1) {          if(j != k && dist(polygonCenter((Polygon)countryPolygons.get(j)),                            polygonCenter((Polygon)countryPolygons.get(k))) < tRad*1.5) {            ((Vector)connections.get(j)).add(new Integer(k));          }        }      }    }    contIndices[numContinents] = countryPolygons.size();    debug("connecting continents");    Vector lines = makeConnectionsBetweenContinents();    debug("writing...");    for(int i = 0; i < numContinents; i += 1) {      writeContinent(i);    }    for(int i = 0; i < lines.size(); i += 1) {      writeLine((Line2D.Double)lines.get(i));    }    out.write("</luxboard>\n");    return true;  }  //output the xml of a continent  //start and end are indices in the polygon and connection Vectors  private void writeContinent(int cont) {    int start = contIndices[cont];    int end = contIndices[cont+1];    String continentName = makeContinentName();    int countries = end-start;    int numBorders = 0;    for(int i = start; i < end; i += 1) {      Vector theseConns = (Vector)connections.get(i);      boolean isABorder = false;      for(int j = 0; j < theseConns.size(); j += 1) {        int connIndex = ((Integer)theseConns.get(j)).intValue();        if(connIndex < start || connIndex >= end) {          isABorder = true;        }      }      if(isABorder) numBorders += 1;    }    int bonus = (int)Math.round((numBorders + countries/3.0)/2);    out.write("<continent>\n" +	"  <continentname>" + continentName + "</continentname>\n" +	"  <bonus>" + bonus + "</bonus>\n");    for(int i = start; i < end; i += 1) { //write out each country      out.write("  <country>\n" +		"    <id>" + i + "</id>\n" +		"    <name>" + makeCountryName(continentName) + "</name>\n");      writeConnections((Vector)connections.get(i));      writePolygon((Polygon)countryPolygons.get(i));      out.write("  </country>\n");    }    out.write("</continent>\n");  }  private void makeContinentSeeds() {    double minDist = 100;    contCenters = new Point[numContinents];    contplacement:    while(true) {  //loops until we have a valid arrangement      for(int i = 0; i < numContinents; i += 1) { //place the conts one at a time        boolean success = false; //whether we successfully placed this cont        placetry:        for(int k = 0; k < 15; k += 1) { //try to place this cont 15 times          contCenters[i] = new Point(50+rand.nextInt(width-100), 50+rand.nextInt(height-100));          //expandedI creates a buffer between continents          for(int j = 0; j < i; j += 1) {            if(dist(contCenters[j], contCenters[i]) < minDist)  //overlap              continue placetry; //try again...          }          success = true; //no intersections          break; //success in placing this cont        }        if(!success) continue contplacement; //couldn't place this cont, start over      }      break; //made it through all conts: done    }    for(int i = 0; i < numContinents; i += 1) {      continents[i] = new Vector();      continents[i].add(upTriangleAround(contCenters[i]) );    }  }  private void growContinents() {    for(int i = 0; i < 50; i += 1) {      for(int j = 0; j < numContinents; j += 1) {        addOneCountryToContinent(rand.nextInt(numContinents));      }    }  }  private boolean addOneCountryToContinent(int cont) {    trytoplace:    for(int i = 0; i < 40; i += 1) {      int parentIndex = rand.nextInt(continents[cont].size());      Polygon parent = (Polygon)continents[cont].get(parentIndex);      Polygon child = makeAdjoiningTriangle(parent);      for(int j = 0; j < numContinents; j += 1) {        for(int k = 0; k < continents[j].size(); k += 1) {          //debug("child = " + child + ", continents[j] = " + continents[j] + ", continents = " = continents);          if(trianglesIntersect(dilatePolygon(child, (cont == j ? 1.0: 1.2)),                                dilatePolygon((Polygon)continents[j].get(k), (cont==j ? 1.0 : 1.2))) ||             !polygonFitsOnScreen(child) ||             (j != cont && dist(polygonCenter(child), polygonCenter((Polygon)continents[j].get(k))) < tRad*2))            continue trytoplace;        }      }      //valid, add it      continents[cont].add(child);      return true;    }    return false;  }  private Polygon makeAdjoiningTriangle(Polygon p) {    Polygon ret = new Polygon();    if(trianglePointsUp(p)) {      switch(rand.nextInt(3)) {        case 0:          ret.addPoint(p.xpoints[0], (int)(p.ypoints[0]-2*tHeight));          ret.addPoint(p.xpoints[1], p.ypoints[1]);          ret.addPoint(p.xpoints[2], p.ypoints[2]);          ret.translate(0, -5);          return ret;        case 1:          ret.addPoint(p.xpoints[1], p.ypoints[1]);          ret.addPoint(p.xpoints[1]-(int)(tWidth/2), p.ypoints[0]);          ret.addPoint(p.xpoints[0], p.ypoints[0]);          ret.translate(-5, 0);          return ret;        case 2:          ret.addPoint(p.xpoints[2], p.ypoints[2]);          ret.addPoint(p.xpoints[0], p.ypoints[0]);          ret.addPoint(p.xpoints[2]+(int)(tWidth/2), p.ypoints[0]);          ret.translate(5, 0);          return ret;      }    } else {      switch(rand.nextInt(3)) {        case 0:          ret.addPoint(p.xpoints[0], p.ypoints[0]+(int)(2*tHeight));          ret.addPoint(p.xpoints[1], p.ypoints[1]);          ret.addPoint(p.xpoints[2], p.ypoints[2]);          ret.translate(0, 5);          return ret;        case 1:          ret.addPoint(p.xpoints[1], p.ypoints[1]);          ret.addPoint(p.xpoints[1]-(int)(tWidth/2), p.ypoints[0]);          ret.addPoint(p.xpoints[0], p.ypoints[0]);          ret.translate(-5, 0);          return ret;        case 2:          ret.addPoint(p.xpoints[2], p.ypoints[2]);          ret.addPoint(p.xpoints[0], p.ypoints[0]);          ret.addPoint(p.xpoints[2]+(int)(tWidth/2), p.ypoints[0]);          ret.translate(5, 0);          return ret;      }    }    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() {    //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;      }    }    boolean[][] countriesConnected = new boolean[connections.size()][connections.size()];    for(int i = 0; i < connections.size(); i += 1) {      for(int j = 0; j < connections.size(); j += 1) {        countriesConnected[i][j] = false;      }    }    Vector lines = new Vector();    //connect continents until they are all connected    boolean more = true;    while(more && !allContsReachableFrom(0, contsConnected, numContinents)) {//      more = false;      double shortestGap = 10000;      int contA = rand.nextInt(numContinents);//      debug("contIndices[contA+1] - contIndices[contA] = " + (contIndices[contA+1] - contIndices[contA]));      int countryA = contIndices[contA] + rand.nextInt(contIndices[contA+1] - contIndices[contA]);      int contB = -1;      int countryB = -1;      int xxx = 0;      for(int i = 0; i < numContinents; i += 1) {        if(i != contA) {          for(int j = contIndices[i]; j < contIndices[i+1]; j += 1) {            if(!countriesConnected[countryA][j] && countriesConnectable(countryA, j)) {//              debug("xxx = " +  j);              xxx += 1;              double gap = dist(polygonCenter((Polygon)countryPolygons.get(countryA)),                                polygonCenter((Polygon)countryPolygons.get(j)));//              debug("gap = " + gap);              if(gap < shortestGap) {