#import <Alpaca/Model/ALMap_TerrainGeneration.h>

@implementation ALMap (TerrainGeneration)

- (void)equalizeHeightmap:(double **)aHeightmap
{
	// Calculate total weight
	double weight = 0.0;
	for(int x = 0; x < width; ++x)
		for(int y = 0; y < height; ++y)
			weight += aHeightmap[x][y];

	// Calculate shift
	double shift = weight/(width*height);

	// Shift map
	for(int x = 0; x < width; ++x)
		for(int y = 0; y < height; ++y)
			aHeightmap[x][y] -= shift;
}

- (void)smoothHeightmap:(double **)aHeightmap
{
	// Create blurred heightmap
	double **smoothedHeightmap = malloc(width*sizeof(double *));
	for(int x = 0; x < width; ++x)
		smoothedHeightmap[x] = malloc(height*sizeof(double));

	// Blur
	for(int x = 0; x < width; ++x)
	{
		for(int y = 0; y < height; ++y)
		{
			UInt8	count = 0;
			double	sum = 0;

			// TL
			if(x > 0 && y > 0)
			{
				++count;
				sum += aHeightmap[x-1][y-1];
			}

			// TC
			if(y > 0)
			{
				++count;
				sum += aHeightmap[x][y-1];
			}

			// TR
			if(x < width-1 && y > 0)
			{
				++count;
				sum += aHeightmap[x+1][y-1];
			}

			// ML
			if(x > 0)
			{
				++count;
				sum += aHeightmap[x-1][y];
			}

			// MC
			if(1)
			{
				++count;
				sum += aHeightmap[x][y];
			}

			// MR
			if(x < width-1)
			{
				++count;
				sum += aHeightmap[x+1][y];
			}

			// BL
			if(x > 0 && y < height-1)
			{
				++count;
				sum += aHeightmap[x-1][y+1];
			}

			// BC
			if(y < height-1)
			{
				++count;
				sum += aHeightmap[x][y+1];
			}

			// BR
			if(x < width-1 && y < height-1)
			{
				++count;
				sum += aHeightmap[x+1][y+1];
			}

			// Calculate average
			smoothedHeightmap[x][y] = sum/(double)count;
		}
	}

	// Copy heightmap
	for(int x = 0; x < width; ++x)
		for(int y = 0; y < height; ++y)
			aHeightmap[x][y] = smoothedHeightmap[x][y];
}

- (double)randomNumberWithWeight:(double)aWeight
{
	return ((((double)random()) / (double)INT_MAX) - 0.5l) * aWeight;
}

- (void)randomizeHeightmapUsingSquares:(double **)aHeightmap
{
	UInt16	iterations = 1000;
	UInt8	maxSize = 100;
	double	weightModifier = 0.01;

	// Clear
	for(int x = 0; x < width; ++x)
		for(int y = 0; y < height; ++y)
			aHeightmap[x][y] = 0.0;

	for(int i = 0; i < iterations; ++i)
	{
		int randomX			= (int)((((double)random()) / (double)INT_MAX) * width);
		int randomY			= (int)((((double)random()) / (double)INT_MAX) * height);
		int randomSize		= (int)((((double)random()) / (double)INT_MAX) * maxSize);
		double randomWeight	= weightModifier * (((((double)random()) / (double)INT_MAX) - 0.5l) * maxSize);

		for(int x = randomX - randomSize; x < randomX + randomSize; ++x)
		{
			if(x < 0)		continue;
			if(x >= width)	continue;

			for(int y = randomY - randomSize; y < randomY + randomSize; ++y)
			{
				if(y < 0)		continue;
				if(y >= height)	continue;

				aHeightmap[x][y] += randomWeight * ((randomX + randomY) - (x + y));
			}
		}
	}
}

- (void)randomizeHeightmapUsingMPD:(double **)aHeightmap
{
	// Clear
	for(int x = 0; x < width; ++x)
		for(int y = 0; y < height; ++y)
			aHeightmap[x][y] = 0.0;

	// Set corner heights
	aHeightmap[0][0]				= ((((double)random()) / (double)INT_MAX) - 0.5l) * 300.0;
	aHeightmap[0][height-1]			= ((((double)random()) / (double)INT_MAX) - 0.5l) * 300.0;
	aHeightmap[width-1][0]			= ((((double)random()) / (double)INT_MAX) - 0.5l) * 300.0;
	aHeightmap[width-1][height-1]	= ((((double)random()) / (double)INT_MAX) - 0.5l) * 300.0;

	// Randomize
	[self randomizeHeightmapUsingMPD:aHeightmap from:MOMakePoint(0, 0) to:MOMakePoint(width-1, height-1)];
}

- (void)randomizeHeightmapUsingMPD:(double **)aHeightmap from:(MOPoint)aSrc to:(MOPoint)aDst
{
	[self randomizeHeightmapUsingMPD:aHeightmap from:aSrc to:aDst depth:0];
}

- (void)randomizeHeightmapUsingMPD:(double **)aHeightmap from:(MOPoint)aSrc to:(MOPoint)aDst depth:(UInt8)aDepth
{
	// Get relevant X coords
	UInt16 lX = aSrc.x;
	UInt16 mX = (aSrc.x + aDst.x)/2;
	UInt16 rX = aDst.x;

	// Get relevant Y coords
	UInt16 tY = aSrc.y;
	UInt16 mY = (aSrc.y + aDst.y)/2;
	UInt16 bY = aDst.y;

	// Get width/height
	UInt16 w = aDst.x - aSrc.x + 1;
	UInt16 h = aDst.y - aSrc.y + 1;

	// Configuration
	double weight = 300.0;

	// Get shortcut
	double **hm = aHeightmap;

	// Calculate center
	if(w >= 3 && h >= 3)
	{
		hm[mX][mY] = (hm[lX][tY] + hm[rX][tY] + hm[rX][bY] + hm[lX][bY])/4;
		hm[mX][mY] += [self randomNumberWithWeight:weight / (double)(1 + aDepth*aDepth)];
	}

	// Calculate edges
	if(w >= 3)
	{
		// top
		hm[mX][tY] = (hm[lX][tY] + hm[rX][tY])/2;
		hm[mX][tY] += ((((double)random()) / (double)INT_MAX) - 0.5l) * weight / (double)(1 + aDepth*aDepth);

		// bottom
		hm[mX][bY] = (hm[lX][bY] + hm[rX][bY])/2;
		hm[mX][bY] += ((((double)random()) / (double)INT_MAX) - 0.5l) * weight / (double)(1 + aDepth*aDepth);
	}
	if(h >= 3)
	{
		// right
		hm[rX][mY] = (hm[rX][tY] + hm[rX][bY])/2;
		hm[rX][mY] += ((((double)random()) / (double)INT_MAX) - 0.5l) * weight / (double)(1 + aDepth*aDepth);

		// left
		hm[lX][mY] = (hm[lX][tY] + hm[lX][bY])/2;
		hm[lX][mY] += ((((double)random()) / (double)INT_MAX) - 0.5l) * weight / (double)(1 + aDepth*aDepth);
	}

	// Divide and conquer
	if(w > 3 && h <= 3)
	{
		// Divide vertically
		[self randomizeHeightmapUsingMPD:hm from:MOMakePoint(lX, tY) to:MOMakePoint(mX, bY) depth:aDepth+1];
		[self randomizeHeightmapUsingMPD:hm from:MOMakePoint(mX, tY) to:MOMakePoint(rX, bY) depth:aDepth+1];
	}
	else if(w <= 3 && h > 3)
	{
		// Divide horizontally
		[self randomizeHeightmapUsingMPD:hm from:MOMakePoint(lX, tY) to:MOMakePoint(rX, mY) depth:aDepth+1];
		[self randomizeHeightmapUsingMPD:hm from:MOMakePoint(lX, mY) to:MOMakePoint(rX, bY) depth:aDepth+1];
	}
	else if(w > 3 && h > 3)
	{
		// Divide in four
		[self randomizeHeightmapUsingMPD:hm from:MOMakePoint(lX, tY) to:MOMakePoint(mX, mY) depth:aDepth+1];
		[self randomizeHeightmapUsingMPD:hm from:MOMakePoint(mX, tY) to:MOMakePoint(rX, mY) depth:aDepth+1];
		[self randomizeHeightmapUsingMPD:hm from:MOMakePoint(lX, mY) to:MOMakePoint(mX, bY) depth:aDepth+1];
		[self randomizeHeightmapUsingMPD:hm from:MOMakePoint(mX, mY) to:MOMakePoint(rX, bY) depth:aDepth+1];
	}
}

@end