package com.sillysoft.lux;import com.sillysoft.lux.util.*;import java.util.*;import java.io.PrintWriter;import java.awt.geom.GeneralPath;import java.awt.geom.Point2D;import java.awt.geom.Line2D;import java.awt.geom.Rectangle2D;////  RandomMapGenerator.java//  Lux////  Copyright (c) 2002-2007 Sillysoft Games. //	http://sillysoft.net//	lux@sillysoft.net////	This source code is licensed free for non-profit purposes. //	For other uses please contact lux@sillysoft.net///**  RandomMapGenerator is an implementation of the MapGenerator interface.<br>	It is used to create the built-in random maps in Lux.<br>  <br>	Sometimes described as "potato blob" output. The general strategy is as follows:<br>	<br>		- Pick a width and height to use as the 2D field.<br>		- Pick a random point inside the field. This will serve as a centerpoint of a country.<br>		- Using polar co-ordinates, a randomly changing radius is drawn around the center to select the points that form into a country.<br>		-- Pick a point near outside of the country we just drew.<br>		-- Use this point as a centerpoint of another country. When a newly created point falls inside a previous shape move the point to follow outside the border of that country.<br>		-- Repeat picking nearby points and drawing countries for a while. This will form a continent of countries.<br>		- Then start fresh by picking a brand new point on the field. If inside another country pick again. Start a country around it and more countries near it. Repeat this a few times to grow some continents.<br>		<br>		- After the desired number of countries have been created then countries distance are compared. If they are close enough they connect.<br>		<br>		- More connections (along with lines indicating them) are then made over the board so that all the countries are connected.																								*/public class RandomMapGenerator implements LuxMapGenerator{private MapLoader loader;private Random rand;	// the random number generatorprivate int topx, topy;		// the maximum drawing bounds// These variables control how smooth the random shapes are.private int variance = 3; 					// The maximum distance away nearNumber() will returnprivate double fullCircle = 2*Math.PI;private double thetaStep = fullCircle/20; 	// The step size of the angleprivate int minRadius = 13; 					// the minimum the radius is allowed to be when drawing shapes// To encapsulate the getShpaeAround functions we store the array of shapes:private GeneralPath[] shapes;private Rectangle2D[] shapeBounds; // we keep a cache of the bounds of each shapeprivate int shapeCount;private Vector lines;	// the lines that the LuxView will have to drawprivate boolean[] connected;	// When making connections, we remember what is connected so farprivate int numCountries;private Country[] countries;private int[] contCodes;		// the continent code for each countryprivate int numContinents;private int[] contBonus;	// each continent has a bonus value associated with it// Because there doen't seem to be a way to get the actual points of an GeneralPath in java, we keep a vector of points for each shape. One Vector for each shape. They will be filled with Point2Ds.private Vector[] points;private Hashtable allPoints;	// the points are the keys, thenumber of shapes touching that point is the valueprivate int[][] distanceMemory;	// the closest distance between shapesprivate String boardSize;   // a value from the choices arrayprivate static List choices;public String name()	{	return "Random";	}public float version()	{	return 1.0f;	}public String description()	{	return "RandomMapGenerator is the class that Lux uses to generate the tiny-huge maps.";	}public List getChoices()	{	if (choices == null)		{		choices = new Vector();		choices.add("tiny");		choices.add("small");		choices.add("medium");		choices.add("large");		choices.add("huge");		}	return choices;	}public boolean generate(PrintWriter out, String choice, int seed, MapLoader loader)	{	this.loader = loader;	boardSize = choice;	rand = new Random(seed);	generateBoard();	this.loader = null;	return saveBoard(out, boardSize+" ID#"+seed);	}public boolean canCache()	{	return true;	}/**The main method that controls the generation of a map.Note that rand and boardSize must be set before this is called.		*/public void generateBoard()	{	//debug("Starting generateBoard. boardSize: "+boardSize);	/********************	To create a random board the following things must be done:		-> clear the CreateBoard and initialize vars		-> Determine the number of countries		and For each country:			-> Generate a shape			-> determine the adjoinging list			-> set the continent code		-> choose the bonus values for each continent		-> make any extra lines to connect countries	********************/	// The number of countries depend on the size of the board:	if ( boardSize.equals("tiny") )		{		numCountries = 6 + rand.nextInt(11); // 6 to 16		}	else if ( boardSize.equals("small") )		{		numCountries = 10 + rand.nextInt(11); // 10 to 20		}	else if ( boardSize.equals("large") )		{		numCountries = 20 + rand.nextInt(11); // 20 to 30		}	else if ( boardSize.equals("huge") )		{		numCountries = 30 + rand.nextInt(11); // 30 to 40		}	else		{	// it's medium (or undefined)		numCountries = 15 + rand.nextInt(11); // 15 to 25		}	initialize();	topx = getWidthForSize(boardSize);	topy = getHeightForSize(boardSize);	// Do the shapes now.	// Pick random points and draw shapes around them.	while (shapeCount < numCountries)		{		generateNugget();		}	// so all the shapes are picked. 	loader.setLoadText("adding easy connections");	// add connections between shapes that are very close together	connectShapesAt(5);	// this will cause them to be in the same continent	loader.setLoadText("choosing continent nuggets");	// The shapes have now been completed. Some close connection have been made.	// Here we expand those trees into continents.	// we mark the countries we have assigned to conts	contCodes = new int[numCountries];	connected = new boolean[numCountries];	//used to remember who has been given a continent (markConnectedFrom() and others use this array)	for (int i = 0; i < numCountries; i++) 		{		connected[i] = false;		contCodes[i] = -1;		}	// try and make continents have about this number of countries	int averageContinentCountries = 5;	numContinents = (int)Math.ceil((double)numCountries/(double)averageContinentCountries);	// NOTE: numContinents may become smaller, if we don't find that many nuggets	// the method: cycle through the countries and find the biggest tree without a cont code	// give that tree a continent code	// repeat till all countries have a cont code or we have chosen the desired number of conts	for (int nextContCode = 0; nextContCode < numContinents; nextContCode++)		{		int biggestTreeSize = 0;		int inBiggestTree = -1;		for (int i = 0; i < numCountries; i++) 			{			if (contCodes[i] == -1)				{				Vector tree = getTouching(i);				if (tree.size() > biggestTreeSize)					{					biggestTreeSize = tree.size();					inBiggestTree = i;					}				}			}		if (inBiggestTree != -1)			{// xxxx this would be the place to break up big continents into smaller ones...			// so mark the tree as the nugget to start this cont:			markConnectedFrom(inBiggestTree);			markContinentCodeFrom(inBiggestTree, nextContCode);			}		else			{			// then everything has been given a continent.			numContinents = nextContCode;	// this will break us out of thr for loop			}		}// Now numContinents is garanteed to be its final value.String currentLoadText = new String ("building up nuggets");loader.setLoadText(currentLoadText);// So now we have numContinents nuggets to build on.// cycle through the countries, making connections from unassigned countries, until everything has a continent.while ( ! isFullyConnected() ) // NOTE: the isFullyConnected() function just tests that everything has been marked as connected. the graph will not be fully connected when the while loop exits.	{	// pick a random country that still has no continent.	int from = rand.nextInt(numCountries);	while (contCodes[from] != -1)		from = (from+1) % numCountries;	// now connect it to the closest possible country.	int closestShape = -1;	int closestDistance = 1000000;	for (int j = 0; j < countries.length; j++)		{		if (from != j && ! countries[from].canGoto(j))			{			int distance = distanceBetween(from, j);			if (distance < closestDistance && lineCanExistBetween(from,j) )				{				closestDistance = distance;				closestShape = j;				}			}		}	if (closestShape != -1)		{		// then connect the unassigned country to it's closest neighbor		makeCountriesTouch(from, closestShape);		addLineBetweenShapes(from, closestShape);		// if we connected it to a shape with a contCode then we get that contCode too.		if (contCodes[closestShape] != -1)			{			markConnectedFrom(from);			markContinentCodeFrom(from, contCodes[closestShape]);			}		}	else		{		System.out.println("ERROR in RandomMapGenerator.generateBoard() -> (closestShape == -1) while building up nuggets");		System.out.println("	-> from = "+from);		// HACK: create a new continent with this shape...		markConnectedFrom(from);		markContinentCodeFrom(from, numContinents);		numContinents++;		}	currentLoadText = currentLoadText+".";	loader.setLoadText(currentLoadText);	}// good. the world is now fully divided into continents.// since the continents are now finalized we can create bonus values for them all// for now the bonus is just the # of countries in the cont.contBonus = new int[numContinents];for (int i = 0; i < numContinents; i++)	{	int size = BoardHelper.getContinentSize( i, countries );	contBonus[i] = size;	}currentLoadText = new String("fully connecting");loader.setLoadText(currentLoadText);// now the only thing left to do is ensure that the graph is fully connected.// we want to do it using the smallest possible connections.// first add all the tiny edges possible:connectShapesAt(12);// now the harder part:// we must clear the connected memoryfor (int i = 0; i < numCountries; i++)	connected[i] = false;markConnectedFrom(0);// first connect continents that are closeconnectContinentsAt(50);// Now we must fullt connect the graph.// Start by getting the connected graph from shape 0.Vector tree = getTouching(0);// And add non-reachable nodes until everything is connected...while (tree.size() < numCountries)	{	// In each iteration we should connect the closest shape that is not in <tree> to a shape in <tree>	int closestShapeFrom = -1, closestShapeTo = -1;	int closestDistance = 1000000;	for (int i = 0; i < tree.size(); i++)		{		int in = ((Country)tree.get(i)).getCode();		for (int out = 0; out < numCountries; out++)			{			if ( ! tree.contains( countries[out] ) )				{				// then consider connecting <out> to <in>				int dist = distanceBetween(in,out);				if (dist < closestDistance && lineCanExistBetween(in,out) )					{					closestDistance = dist;					closestShapeFrom = in;					closestShapeTo = out;					}				}			}		}	if (closestShapeFrom == -1)		{		// this should never happen...		System.out.println("ERROR in RandomMapGenerator.generateBoard() -> (closestShapeFrom == -1) while fully connecting");		break;	// the board won't be fully connected, but what else can we do?		}	else		{		makeCountriesTouch(closestShapeFrom, closestShapeTo);		addLineBetweenShapes(closestShapeFrom, closestShapeTo);		tree = getTouching(0);		// some user feedback		currentLoadText = currentLoadText+".";		loader.setLoadText(currentLoadText);		}	}	// now our graph is fully connected	// whew	// in order to make a more globe-like world we would also like to make a 	// connection crossing over the edges of the board	// (like the alaska-russia connection in Risk).	double lowWrapDistance = 1000000;	int lowShape = -1, highShape = -1;	for (int i = 0; i < numCountries; i++)		{		for (int j = 0; j < numCountries; j++)			{			double dist = wrappedDistance(i,j);			if (dist < lowWrapDistance)				{				lowWrapDistance = dist;				if (shapeBounds[i].getX() < shapeBounds[j].getX())					{					lowShape = i;					highShape = j;					}				else					{					lowShape = j;					highShape = i;					}				}			}		}	// Now we have the shapes to connect	makeCountriesTouch(lowShape, highShape);	// now we just have to find the shortest wrapped line and add it...	Point2D lowPoint = null, highPoint = null;	double smallestDist = 1000000;	for (int i = 0; i < points[lowShape].size(); i++)		for (int j = 0; j < points[highShape].size(); j++)			{			// pretend the low-shape is actually really high			Point2D mapHigherPoint = new Point2D.Double(((Point2D)points[lowShape].get(i)).getX()+topx, ((Point2D)points[lowShape].get(i)).getY());			double dist = mapHigherPoint.distance((Point2D)points[highShape].get(j));			if (dist < smallestDist)				{				smallestDist = dist;				lowPoint = (Point2D)points[lowShape].get(i);				highPoint = (Point2D)points[highShape].get(j);				}			}	// so we have the points, map them and add the lines...	Point2D mapHigherPoint = new Point2D.Double(lowPoint.getX()+topx, lowPoint.getY());	Point2D mapLowerPoint = new Point2D.Double(highPoint.getX()-topx, highPoint.getY());	lines.add( new Line2D.Float(highPoint, mapHigherPoint) );	lines.add( new Line2D.Float(mapLowerPoint, lowPoint) );	//report for testing purposes	//debug("GenReport -> size: "+boardSize+", numShapes: "+numCountries+", conts: "+numContinents);	}public static int getWidthForSize(String boardSize)	{	if ("tiny".equals(boardSize))		{		return 600;		}	else if ("small".equals(boardSize))		{