package pl.vgtworld.tools;

import java.util.Random;

/**
 * Generator heightmap wg algorytmu Diamond-Square.
 * 
 * Klasa udostepniana na licencji BSD.
 * 
 * @author Tomek Gubala / tomek@vgtworld.pl / http://vgtworld.pl
 */
public class DiamondSquare
	{
	private int size = 0;
	private int rangeMin = 0;
	private int rangeMax = 255;
	private float randomHeightChange = 0;
	private float roughness = 0.8f;
	private float[][] area = null;
	private Random generator = new Random();
	/**
	 * Konstruktor domyslny.
	 */
	public DiamondSquare()
		{}
	/**
	 * Konstruktor pozwalajacy zdefiniowac rozmiar tworzonej heightmap'y.
	 * 
	 * @param size Dlugosc boku tworzonej heightmap'y.
	 */
	public DiamondSquare(int size)
		{
		setSize(size);
		}
	/**
	 * Ustawia rozmiar tworzonej heightmap'y.
	 * 
	 * @param size Dlugosc boku tworzonej heightmap'y.
	 */
	public void setSize(int size)
		{
		this.size = size;
		}
	/**
	 * Ustawia zakres wartosci dla tworzonej heightmap'y.
	 * 
	 * Domyslna wartosc range: <0, 255>.
	 * 
	 * @param rangeMin Minimalna wartosc zakresu.
	 * @param rangeMax Maksymalna wartosc zakresu.
	 */
	public void setRange(int rangeMin, int rangeMax)
		{
		if (rangeMin >= rangeMax)
			throw new IllegalArgumentException("Illegal range");
		this.rangeMin = rangeMin;
		this.rangeMax = rangeMax;
		}
	/**
	 * Okesla "szorstkosc" generowanej hightmap'y.
	 * 
	 * Im mniejsza wartosc, tym lagodniejsza jest wygenerowana heightmap'a.
	 * 
	 * Domyslna wartosc: 0.8
	 * 
	 * @param roughness "Szorstkosc" generowanej heightmap'y.
	 */
	public void setRoughness(float roughness)
		{
		this.roughness = roughness;
		}
	/**
	 * Metoda generujaca tablice zawierajaca wartosci stworzonej heightmap'y.
	 * 
	 * @return Tablica z wartosciami wygenerowanej heightmap'y.
	 */
	public float[][] generate()
		{
		if (size <= 1)
			throw new IllegalStateException("size undefined");
		//ustalenie rozmiaru tworzonej heightmap (wymog, aby do obliczen rozmiar tablicy wynosil pow(2, n) + 1 )
		int areaSize;
		int baseSize = 1;
		int iterations = 0;
		while (baseSize + 1 < size)
			{
			baseSize*= 2;
			++iterations;
			}
		areaSize = baseSize + 1;
		//utworzenie mapy
		area = new float[areaSize][areaSize];
		generateSeeds();
		randomHeightChange = area.length;
		for (int i = 1; i <= iterations; ++i)
			calculateIteration(i);
		trimArea();
		return area;
		}
	/**
	 * Wykonuje komplet obliczen (etapy diamond i square) dla podanej iteracji.
	 * 
	 * @param iteration Numer iteracji obliczen.
	 */
	private void calculateIteration(int iteration)
		{
		int baseSize = area.length - 1;
		int step = baseSize;
		for (int i = 1; i < iteration; ++i)
			step = step / 2;
		int x, y;
		for (x = step / 2; x <= baseSize; x += step)
			for (y = step / 2; y <= baseSize; y+= step)
				calculateDiamond(x, y, step / 2);
		for (x = step / 2; x <= baseSize; x += step)
			for (y = step / 2; y <= baseSize; y+= step)
				calculateSquares(x, y, step / 2);
		randomHeightChange = randomHeightChange / 2;
		}
	/**
	 * Wykonuje obliczenia dla 4 punktow (etap square) otaczajacych punkt o podanych wspolrzednych.
	 * 
	 * @param x Wspolrzedna X punktu centralnego.
	 * @param y Wspolrzedna Y punktu centralnego.
	 * @param radius Odleglosc, w ktorej znajduja sie 4 punkty wymagajace obliczen od punktu centralnego.
	 */
	private void calculateSquares(int x, int y, int radius)
		{
		int leftX, rightX, topY, bottomY;
		leftX = x - radius;
		rightX = x + radius;
		topY = y - radius;
		bottomY = y + radius;
		if (topY == 0)
			calculateSquare(x, topY, radius);
		calculateSquare(rightX, y, radius);
		calculateSquare(x, bottomY, radius);
		if (leftX == 0)
			calculateSquare(leftX, y, radius);
		}
	/**
	 * Oblicza wartosc punktu o podanych wspolrzednych (etap square).
	 * 
	 * @param x Wspolrzedna X punktu, dla ktorego maja byc wykonane obliczenia.
	 * @param y Wspolrzedna Y punktu, dla ktorego maja byc wykonane obliczenia.
	 * @param radius Odleglosc, w ktorej znajduja sie punkty, ktorych wartosci nalezy pobrac do obliczen.
	 */
	private void calculateSquare(int x, int y, int radius)
		{
		float value = 0;
		int leftX, rightX, topY, bottomY;
		int size = area.length;
		int count = 0;
		
		leftX = x - radius;
		rightX = x + radius;
		topY = y - radius;
		bottomY = y + radius;
		
		if (topY >= 0)
			{
			++ count;
			value+= area[x][topY];
			}
		if (bottomY < size)
			{
			++count;
			value+= area[x][bottomY];
			}
		if (leftX >= 0)
			{
			++count;
			value+= area[leftX][y];
			}
		if (rightX < size)
			{
			++count;
			value+= area[rightX][y];
			}
		value = value / count;
		
		if (value > rangeMax)
			value = rangeMax;
		if (value < rangeMin)
			value = rangeMin;
		
		area[x][y] = value;
		}
	/**
	 * Oblicza wartosc punktu o podanych wspolrzednych (etap diamond).
	 * 
	 * @param x Wspolrzedna X punktu, dla ktorego maja byc wykonane obliczenia.
	 * @param y Wspolrzedna Y punktu, dla ktorego maja byc wykonane obliczenia.
	 * @param radius Odleglosc, w ktorej znajduja sie punkty, ktorych wartosci nalezy pobrac do obliczen.
	 */
	private void calculateDiamond(int x, int y, int radius)
		{
		float value = 0;
		int leftX, rightX, topY, bottomY;
		
		leftX = x - radius;
		rightX = x + radius;
		topY = y - radius;
		bottomY = y + radius;
		
		value+= area[leftX][topY];
		value+= area[rightX][topY];
		value+= area[leftX][bottomY];
		value+= area[rightX][bottomY];
		value = value / 4;
		
		//random change
		float change = randomHeightChange * ( generator.nextFloat() * 2 - 1 ) * roughness;
		value = value + change;
		
		if (value > rangeMax)
			value = rangeMax;
		if (value < rangeMin)
			value = rangeMin;
		
		area[x][y] = value;
		}
	/**
	 * Generuje losowo startowe wartosci w 4 rogach generowanej heightmap'y.
	 */
	private void generateSeeds()
		{
		int size = area.length;
		area[0][0] = randomHeight();
		area[0][size - 1] = randomHeight();
		area[size - 1][0] = randomHeight();
		area[size - 1][size - 1] = randomHeight();
		}
	/**
	 * Generuje losowa wartosc wysokosci znajdujaca sie w zakresie zdefiniowanym przez rangeMin i rangeMax.
	 * 
	 * @return Zwraca wygenerowana wartosc wysokosci.
	 */
	private float randomHeight()
		{
		int amplitude = rangeMax - rangeMin;
		double rand = generator.nextDouble() * amplitude;
		rand+= rangeMin;
		return (float)rand;
		}
	/**
	 * Przycina stworzona tablice do oczekiwanego rozmiaru.
	 */
	private void trimArea()
		{
		if (area.length > size)
			{
			float[][] newArea = new float[size][size];
			for (int i = 0; i < size; ++i)
				for (int j = 0; j < size; ++j)
					newArea[i][j] = area[i][j];
			area = newArea;
			}
		}
	}