randommapgenerator.java

good project for programmer,,

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
//	[e-mail]
//
//	This source code is licensed free for non-profit purposes. 
//	For other uses please contact [e-mail]
//

/**
  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 generator


private 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 return
private double fullCircle = 2*Math.PI;
private double thetaStep = fullCircle/20; 	// The step size of the angle
private 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 shape
private int shapeCount;
private Vector lines;	// the lines that the LuxView will have to draw

private boolean[] connected;	// When making connections, we remember what is connected so far

private int numCountries;
private Country[] countries;
private int[] contCodes;		// the continent code for each country

private 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 value

private int[][] distanceMemory;	// the closest distance between shapes

private String boardSize;   // a value from the choices array

private 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 memory
for (int i = 0; i < numCountries; i++)
	connected[i] = false;
markConnectedFrom(0);


// first connect continents that are close
connectContinentsAt(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))
		{