# Sid Meier's Civilization 4
# Copyright Firaxis Games 2005
from CvPythonExtensions import (CyGlobalContext, CyMap, DirectionTypes,
																CyFractal, PlotTypes, WorldSizeTypes,
																FeatureTypes, plotDirection, plotXY,
																TerrainTypes, NiTextOut)
import CvUtil
# import random
# from math import sqrt
# import sys

"""
NOTES ABOUT THE MAP UTILITIES

generatePlotTypes(), generateTerrainTypes(), and addFeatures() are mandatory functions for all map scripts.

FractalWorld, HintedWorld, and MultilayeredFractal classes are different ways to generatePlotTypes. (Fractal
world is Soren's baby. HintedWorld is Andy's baby. MultilayeredFractal is Bob's baby.) There is no C++ default
for the plot generation process. Each map script must handle the process on its own, typically by calling
one of these three classes (or subclassing them).

TerrainGenerator is the only primary method for generating terrain types. Call, subclass, or replace it to
set terrain types. FeatureGenerator is the primary method for adding Features to the map.

The minor functions at the end are either children of HintedWorld or, in the case of findStartingPlot, an
alternative method to the default process for placing the starting units for each civ.

- Bob Thomas        September 23, 2005
"""


class FractalWorld:

		def __init__(self, fracXExp=CyFractal.FracVals.DEFAULT_FRAC_X_EXP,
								 fracYExp=CyFractal.FracVals.DEFAULT_FRAC_Y_EXP):
				self.gc = CyGlobalContext()
				self.map = self.gc.getMap()
				self.iNumPlotsX = self.map.getGridWidth()
				self.iNumPlotsY = self.map.getGridHeight()
				self.mapRand = self.gc.getGame().getMapRand()
				self.iFlags = self.map.getMapFractalFlags()
				self.plotTypes = [PlotTypes.PLOT_OCEAN] * (self.iNumPlotsX*self.iNumPlotsY)
				self.fracXExp = fracXExp
				self.fracYExp = fracYExp
				self.continentsFrac = CyFractal()
				self.hillsFrac = CyFractal()
				self.peaksFrac = CyFractal()
				# init User Input variances
				self.seaLevelChange = self.gc.getSeaLevelInfo(self.map.getSeaLevel()).getSeaLevelChange()
				self.seaLevelMax = 100
				self.seaLevelMin = 0
				self.hillGroupOneRange = self.gc.getClimateInfo(self.map.getClimate()).getHillRange()
				self.hillGroupOneBase = 25
				self.hillGroupTwoRange = self.gc.getClimateInfo(self.map.getClimate()).getHillRange()
				self.hillGroupTwoBase = 75
				self.peakPercent = self.gc.getClimateInfo(self.map.getClimate()).getPeakPercent()
				self.stripRadius = 15

		def checkForOverrideDefaultUserInputVariances(self):
				# Subclass and override this function to customize/alter/nullify
				# the XML defaults for user selections on Sea Level, Climate, etc.
				return

		def initFractal(self, continent_grain=2, rift_grain=2, has_center_rift=True, invert_heights=False, polar=False):
				"For no rifts, use rift_grain = -1"
				iFlags = self.iFlags
				if invert_heights:
						iFlags += CyFractal.FracVals.FRAC_INVERT_HEIGHTS
				if polar:
						iFlags += CyFractal.FracVals.FRAC_POLAR
				if rift_grain >= 0:
						self.riftsFrac = CyFractal()
						self.riftsFrac.fracInit(self.iNumPlotsX, self.iNumPlotsY, rift_grain, self.mapRand, 0, self.fracXExp, self.fracYExp)
						if has_center_rift:
								iFlags += CyFractal.FracVals.FRAC_CENTER_RIFT
						self.continentsFrac.fracInitRifts(self.iNumPlotsX, self.iNumPlotsY, continent_grain, self.mapRand, iFlags, self.riftsFrac, self.fracXExp, self.fracYExp)
				else:
						self.continentsFrac.fracInit(self.iNumPlotsX, self.iNumPlotsY, continent_grain, self.mapRand, iFlags, self.fracXExp, self.fracYExp)

		def shiftPlotTypes(self):
				stripRadius = self.stripRadius
				best_split_x, best_split_y = 0, 0

				if self.map.isWrapX():
						best_split_x = self.findBestSplitX(stripRadius)
				if self.map.isWrapY():
						best_split_y = self.findBestSplitY(stripRadius)

				self.shiftPlotTypesBy(best_split_x, best_split_y)

		def shiftPlotTypesBy(self, xshift, yshift):
				if xshift > 0 or yshift > 0:
						# iWH = self.iNumPlotsX * self.iNumPlotsY
						buf = self.plotTypes[:]
						for iDestY in range(self.iNumPlotsY):
								for iDestX in range(self.iNumPlotsX):
										iDestI = self.iNumPlotsX*iDestY + iDestX
										iSourceX = iDestX + xshift
										iSourceY = iDestY + yshift
										iSourceX %= self.iNumPlotsX
										iSourceY %= self.iNumPlotsY

										iSourceI = self.iNumPlotsX*iSourceY + iSourceX
										self.plotTypes[iDestI] = buf[iSourceI]

		def findBestSplitY(self, stripRadius):
				stripSize = 2*stripRadius
				if stripSize > self.iNumPlotsX:
						return 0

				numPlots = self.iNumPlotsX * self.iNumPlotsY
				stripCenterIndex = stripRadius
				piLandWeights = self.calcWeights(stripRadius)

				scores = [0]*self.iNumPlotsY
				for y in range(self.iNumPlotsY):
						landScore = 0
						bFoundLand = False
						for x in range(self.iNumPlotsX):
								i = y*self.iNumPlotsX + x
								assert (i >= 0 and i < numPlots)
								if self.plotTypes[i] == PlotTypes.PLOT_LAND:
										landScore += 1
										bFoundLand = True
						if bFoundLand:
								landScore += 30  # the first land is worth about 10 plots of land

						for i in range(stripSize):
								yy = y + i - stripCenterIndex
								yy %= self.iNumPlotsY
								scores[yy] += landScore * piLandWeights[i]

				best_split_y, lowest_score = argmin(scores)
				return best_split_y

		def findBestSplitX(self, stripRadius):
				stripSize = 2*stripRadius
				if stripSize > self.iNumPlotsX:
						return 0

				numPlots = self.iNumPlotsX * self.iNumPlotsY
				stripCenterIndex = stripRadius
				piLandWeights = self.calcWeights(stripRadius)

				scores = [0]*self.iNumPlotsX
				for x in range(self.iNumPlotsX):
						landScore = 0
						bFoundLand = False
						for y in range(self.iNumPlotsY):
								i = y*self.iNumPlotsX + x
								assert (i >= 0 and i < numPlots)
								if self.plotTypes[i] == PlotTypes.PLOT_LAND:
										landScore += 1
										bFoundLand = True
						if bFoundLand:
								landScore += 30  # the first land is worth about 10 plots of land

						for i in range(stripSize):
								xx = x + i - stripCenterIndex
								xx %= self.iNumPlotsX
								scores[xx] += landScore * piLandWeights[i]

				best_split_x, lowest_score = argmin(scores)
				return best_split_x

		def calcWeights(self, stripRadius):
				stripSize = 2*stripRadius
				landWeights = [0]*stripSize
				for i in range(stripSize):
						distFromStart = i+1
						distFromEnd = stripSize-i
						distFromEdge = min(distFromStart, distFromEnd)
						landWeight = distFromEdge
						distFromCenter = stripRadius - distFromEdge
						if distFromCenter <= 1:
								landWeight *= stripRadius
						if distFromCenter == 0:
								landWeight *= 2
						landWeights[i] = landWeight
				return landWeights

		def generatePlotTypes(self, water_percent=78, shift_plot_types=True, grain_amount=3):
				# Check for changes to User Input variances.
				self.checkForOverrideDefaultUserInputVariances()

				self.hillsFrac.fracInit(self.iNumPlotsX, self.iNumPlotsY, grain_amount, self.mapRand, self.iFlags, self.fracXExp, self.fracYExp)
				self.peaksFrac.fracInit(self.iNumPlotsX, self.iNumPlotsY, grain_amount+1, self.mapRand, self.iFlags, self.fracXExp, self.fracYExp)

				water_percent += self.seaLevelChange
				water_percent = min(water_percent, self.seaLevelMax)
				water_percent = max(water_percent, self.seaLevelMin)

				iWaterThreshold = self.continentsFrac.getHeightFromPercent(water_percent)
				iHillsBottom1 = self.hillsFrac.getHeightFromPercent(max((self.hillGroupOneBase - self.hillGroupOneRange), 0))
				iHillsTop1 = self.hillsFrac.getHeightFromPercent(min((self.hillGroupOneBase + self.hillGroupOneRange), 100))
				iHillsBottom2 = self.hillsFrac.getHeightFromPercent(max((self.hillGroupTwoBase - self.hillGroupTwoRange), 0))
				iHillsTop2 = self.hillsFrac.getHeightFromPercent(min((self.hillGroupTwoBase + self.hillGroupTwoRange), 100))
				iPeakThreshold = self.peaksFrac.getHeightFromPercent(self.peakPercent)

				for x in range(self.iNumPlotsX):
						for y in range(self.iNumPlotsY):
								i = y*self.iNumPlotsX + x
								val = self.continentsFrac.getHeight(x, y)
								if val <= iWaterThreshold:
										self.plotTypes[i] = PlotTypes.PLOT_OCEAN
								else:
										hillVal = self.hillsFrac.getHeight(x, y)
										if ((hillVal >= iHillsBottom1 and hillVal <= iHillsTop1) or (hillVal >= iHillsBottom2 and hillVal <= iHillsTop2)):
												peakVal = self.peaksFrac.getHeight(x, y)
												if (peakVal <= iPeakThreshold):
														self.plotTypes[i] = PlotTypes.PLOT_PEAK
												else:
														self.plotTypes[i] = PlotTypes.PLOT_HILLS
										else:
												self.plotTypes[i] = PlotTypes.PLOT_LAND

				if shift_plot_types:
						self.shiftPlotTypes()

				return self.plotTypes


cardinal_directions = (1, 0), (0, 1), (-1, 0), (0, -1)


class HintedWorld(FractalWorld):

		def __init__(self, w=16, h=8, fracXExp=CyFractal.FracVals.DEFAULT_FRAC_X_EXP,
								 fracYExp=CyFractal.FracVals.DEFAULT_FRAC_Y_EXP):
				FractalWorld.__init__(self, fracXExp, fracYExp)

				self.plotsPerBlockX = self.iNumPlotsX/w
				self.plotsPerBlockY = self.iNumPlotsY/h

				if not self.iFlags & CyFractal.FracVals.FRAC_WRAP_X:
						w += 1
				if not self.iFlags & CyFractal.FracVals.FRAC_WRAP_Y:
						h += 1

				self.w, self.h = w, h  # the map is divided into 'w' blocks by 'h' blocks
				self.data = [None]*(w*h)
				self.mapRand = CyGlobalContext().getGame().getMapRand()
				self.continents = []

		def normalizeBlock(self, x, y):
				map = CyMap()
				if map.isWrapX():
						x = x % self.w
				if map.isWrapY():
						y = y % self.h
				return x, y

		def setValue(self, x, y, val):
				x, y = self.normalizeBlock(x, y)

				if self.inBounds(x, y):
						self.data[self.w*y + x] = val
						return True
				else:
						return False

		def getValue(self, x, y):
				x, y = self.normalizeBlock(x, y)
				if self.inBounds(x, y):
						return self.data[self.w*y + x]
				else:
						return None

		def blockToPlot(self, blockx, blocky):
				scalex, scaley = self.plotsPerBlockX, self.plotsPerBlockY
				plotx, ploty = scalex*(blockx), scaley*(blocky)
				return (int(plotx), int(ploty))

		# nested class to describe a continent in the hinted world
		class Continent:

				def __init__(self, world, numBlocks, x, y, maxradius):
						self.world = world
						self.centerx = x
						self.centery = y
						self.targetNumBlocks = numBlocks
						self.maxradius = maxradius
						self.blocks = [(x, y)]  # (x,y) coords of blocks that compose the continent
						self.rects = []  # one (x,y,w,h) rect. of plots for each (x,y) block'

						if numBlocks <= 1:
								self.done = True
						else:
								self.done = False

				def addBlock(self, x, y):
						self.blocks.append((x, y))
						scalex, scaley = self.world.plotsPerBlockX, self.world.plotsPerBlockY
						rect = int(x*scalex), int(y*scaley), int(1*scalex), int(1*scaley)
						self.rects.append(rect)
						if len(self.blocks) >= self.targetNumBlocks:
								self.done = True

				def recalculateRects(self):
						scalex, scaley = self.world.plotsPerBlockX, self.world.plotsPerBlockY
						self.rects = []
						for (x, y) in self.blocks:
								rect = int(x*scalex), int(y*scaley), int(1*scalex), int(1*scaley)
								self.rects.append(rect)

				def containsPlot(self, x, y):  # could add bRemoveParentRect here
						point = (x, y)
						for rect in self.rects:
								if pointInRect(point, rect):
										return True
						return False

				def getCenterPlot(self):
						scalex, scaley = self.world.plotsPerBlockX, self.world.plotsPerBlockY
						x = scalex*(self.centerx+0.5)
						y = scaley*(self.centery+0.5)
						return x, y

				def findStartingPlot(self, playerID):
						validFn = lambda playerID, x, y: self.containsPlot(x, y)
						return findStartingPlot(playerID, validFn)  # call global fn

		def addContinent(self, numBlocks, x=-1, y=-1, maxDist=-1, maxRadius=-1):
				if (x == -1):
						x = self.mapRand.get(self.w, "Add Continent Width PYTHON")
				if (y == -1):
						y = self.mapRand.get(self.h, "Add Continent Height PYTHON")

				foundx, foundy = self.findValid(x, y, maxDist)
				if (foundx == -1 and foundy == -1):
						return None
				else:
						return self.__addContinentAt(numBlocks, foundx, foundy, maxRadius)

		def __addContinentAt(self, numBlocks, x, y, maxradius=-1):
				land_value = 192 + self.mapRand.get(64, "Add Continent At PYTHON")
				self.setValue(x, y, land_value)
				cont = HintedWorld.Continent(self, numBlocks, x, y, maxradius)
				self.continents.append(cont)
				return cont

		def expandContinentBy(self, cont, numBlocks):
				# this plot is not valid; choose an in-bounds plot adjacent to an existing plot and try again:
				# print "expand continent by", numBlocks
				blockOrder = CvUtil.shuffle(len(cont.blocks), self.mapRand)
				for blockIndex in blockOrder:
						x, y = cont.blocks[blockIndex]
						dirOrder = CvUtil.shuffle(len(cardinal_directions), self.mapRand)
						for dirIndex in dirOrder:
								dx, dy = cardinal_directions[dirIndex]
								if self.isValid(x+dx, y+dy, cont):
										cont.addBlock(x+dx, y+dy)
										land_value = 208 + self.mapRand.get(48, "Expand Continent PYTHON")
										self.setValue(x+dx, y+dy, land_value)
										# print "\tadded block", x+dx, y+dy
										if (numBlocks > 1):
												return self.expandContinentBy(cont, numBlocks-1)
										else:
												return True

				print("\tcould not expand continent:")
				printMap(self.data, self.w, self.h, cont.centerx, cont.centery)
				cont.done = True
				return False

		def buildAllContinents(self):
				all_done = False
				while not all_done:
						all_done = True
						for cont in self.continents:
								if not cont.done:
										self.expandContinentBy(cont, 1)  # expand by 1 block
										all_done = False

		def shiftHintsToMap(self):
				map = CyMap()
				wrapX = map.isWrapX()
				wrapY = map.isWrapY()

				splitx, splity = 0, 0
				# self.printHints()
				if (wrapX):
						splitx = self.bestHintsSplitX()
				if (wrapY):
						splity = self.bestHintsSplitY()
				self.shiftHintsBy(splitx, splity)
				# self.printHints()

		def bestHintsSplitX(self):
				scores = [0]*self.w
				for x in range(self.w):
						for y in range(self.h):
								if self.getValue(x, y) >= 192:
										scores[x] += 1
								if self.getValue(x-1, y) >= 192:
										scores[x] += 1
				best_split, best_score = argmin(scores)
				return best_split

		def bestHintsSplitY(self):
				scores = [0]*self.h
				for x in range(self.w):
						for y in range(self.h):
								if self.getValue(x, y) >= 192:
										scores[y] += 1
								if self.getValue(x, y-1) >= 192:
										scores[y] += 1
				best_split, best_score = argmin(scores)
				return best_split

		def shiftHintsBy(self, splitx, splity):
				print("shifting hints by ", splitx, splity)
				if splitx != 0 or splity != 0:
						buf = self.data[:]
						# shift the values in self.data left by best_split
						for x in range(self.w):
								for y in range(self.h):
										i = y*self.w + x
										self.setValue(x-splitx, y-splity, buf[i])

						# shift all continents' blocks left by best_split
						for cont in self.continents:
								cont.blocks = [self.normalizeBlock(x-splitx, y-splity) for (x, y) in cont.blocks]
								cont.recalculateRects()

		# self.data must represent a rect where w = 2*h,
		# and where both w and h are exponents of 2
		def __doInitFractal(self):
				self.shiftHintsToMap()

				# don't call base method, this overrides it.
				size = len(self.data)
				minExp = min(self.fracXExp, self.fracYExp)
				iGrain = None
				for i in range(minExp):
						width = (1 << (self.fracXExp - minExp + i))
						height = (1 << (self.fracYExp - minExp + i))
						if not self.iFlags & CyFractal.FracVals.FRAC_WRAP_X:
								width += 1
						if not self.iFlags & CyFractal.FracVals.FRAC_WRAP_Y:
								height += 1
						if size == width*height:
								iGrain = i
				assert(iGrain is not None)
				iFlags = self.map.getMapFractalFlags()
				self.continentsFrac.fracInitHints(self.iNumPlotsX, self.iNumPlotsY, iGrain, self.mapRand, iFlags, self.data, self.fracXExp, self.fracYExp)

		def isValid(self, x, y, cont=None):
				if not self.inBounds(x, y):
						return False
				if cont and cont.maxradius > 0:
						if abs(x - cont.centerx) + abs(y - cont.centery) > cont.maxradius:
								return False
				val = self.getValue(x, y)
				if val is not None:
						return False
				for dx in range(-1, 2):
						for dy in range(-1, 2):
								val = self.getValue(x+dx, y+dy)
								if val is not None and val >= 192 and ((not cont) or (x+dx, y+dy) not in cont.blocks):
										return False
				return True

		def findValid(self, x, y, dist=-1):
				if (dist == -1):
						dist = max(self.w, self.h)

				if (dist > 0):
						foundx, foundy = self.findValid(x, y, dist-1)
						if (foundx != -1 and foundy != -1):
								return foundx, foundy

				plots = []
				for dx in range(-dist, dist+1):
						for dy in range(-dist, dist+1):
								if max(abs(dx), abs(dy)) == dist:
										plots.append((x+dx, y+dy))

				plotOrder = CvUtil.shuffle(len(plots), self.mapRand)
				for plotIndex in plotOrder:
						tryx, tryy = plots[plotIndex]
						if self.isValid(tryx, tryy):
								return tryx, tryy

				return -1, -1

		def printHints(self, markerx=-1, markery=-1):
				printMap(self.data, self.w, self.h, markerx, markery)

		def inBounds(self, x, y):
				x, y = self.normalizeBlock(x, y)
				return (0 <= x < self.w and 0 <= y < self.h)

		def generatePlotTypes(self, water_percent=-1, shift_plot_types=False):
				for i in range(len(self.data)):
						if self.data[i] == None:
								self.data[i] = self.mapRand.get(48, "Generate Plot Types PYTHON")

				self.__doInitFractal()
				if (water_percent == -1):
						numPlots = len(self.data)
						numWaterPlots = 0
						for val in self.data:
								if val < 192:  # XXX what is this???
										numWaterPlots += 1
						water_percent = int(100*numWaterPlots/numPlots)

				return FractalWorld.generatePlotTypes(self, water_percent, shift_plot_types)  # call superclass


def printMap(data, w, h, markerx=-1, markery=-1):
		print("-"*(w+2))
		hrange = range(h)
		hrange.reverse()
		for y in hrange:
				str = "|"
				for x in range(w):
						val = data[y*w + x]
						if (x, y) == (markerx, markery):
								str += "O"
						elif val != 0:
								str += "X"
						else:
								str += " "
				str += "|"
				print(str)
		print("-"*(w+2))


'''
SIRIAN's "MULTILAYERED FRACTAL" INSTRUCTIONS

Since some map scripting concepts demanded the ability to use more than one
fractal instance to generate plot types, I set out to create a new class that
would use multiple "regional fractals" to assemble a complex map.

MultilayeredFractal duplicates the effects of FractalWorld for each layer
in turn. GeneratePlotsByRegion is the controlling function. You will need to
customize this function for each usage, but the rest of the class will stand
as written unless your needs fall outside the normal intended usage.

I've included an enormous amount of power over the layers, but this does mean
a long list of parameters that you must understand and organize for each layer.

Each layer must be passed this list of arguments:

Regional Variables Key:

iWaterPercent,
iRegionWidth, iRegionHeight,
iRegionWestX, iRegionSouthY,
iRegionGrain, iRegionHillsGrain,
iRegionPlotFlags, iRegionTerrainFlags,
iRegionFracXExp, iRegionFracYExp,
bShift, iStrip,
rift_grain, has_center_rift,
invert_heights

Most of these should be self-explanatory, but I'll discuss the rest.

-------------------------------------------------
Grain is the density of land vs sea. Higher numbers generate more and smaller land masses.

HillsGrain is the density of highlands vs flatlands.
Peaks are included in highlands and work off the same density numbers.

Flags are special variables to pass to the fractal generator.
* FRAC_POLAR will eliminate straight edges along the border of your region.
* FRAC_WRAP_X will "spread out" the fractal horizontally and cancel FRAC_POLAR's vertical component.
* FRAC_WRAP_Y will "spread out" the fractal vertically and cancel FRAC_POLAR's horizontal component.

The Polar flag causes a maximum "height value" to be returned for any coordinates
with a zero component. (0,0 or 0,15 or 71,0 - for instance.) This can cause
problems for terrain and features on maps that put land plots in the zero row
or column. This will also cause a problem for any fractal region you generate.
I've included shortcuts for typical uses, but you may need to customize the flags
for some purposes. PlotFlags and TerrainFlags give you full control.

FracXExp is the width of the source fractal.
FracYExp is the height of the source fractal.
These exponents are raised to powers of two. So a value of FracXExp = 7
means 2^7, which would be 128 units wide. FracXExp = 6 would be only 64
units wide. FracYExp works the same way.

Default values are 7 for FracXExp and 6 for FracYExp, or 128x64 matrix.

I've poked around with the fractals quite a bit. Values lower than 5 seem to
distort the fractal's definition too much, so I don't recommend them even for
use with very small regions. 6x5 proved to be the smallest that I trust. Higher
exponents will generate more defined and refined fractal outputs, but at the
cost of increased calculation times. I would not recommend using exponents
higher than 9. (Larger than 512 even in only one direction is hopeless for Civ4's
True Pathfinding processes, anyway. The game would be unplayably slow!) So I
recommend sticking with 7 as maximum exponent unless your map will be more than
32 (4x4) plot blocks (128 plots) in at least one dimension. Sticking between the
ranges of 6 and 8 for whole maps, and 5 and 7 for regions, is recommended.

Shift is a boolean flag as to whether or not to shift plots in that region.

Strip value has to do with "shifting" the plots to reduce rough edges. This
process overlaps with the Polar flags, though, so if you are using Polar flags,
shifting won't do anything for you along the edges that are Polar-shifted.
The strip size needs to scale appropriately to the size of the region being
shifted. As of this writing, I have not yet determined all the best values to
fit with certain sizes of regions. (And these are a moving target based on map
sizes!) I will try to figure this out and update these notes again before release.

rift_grain has to do with forced strips of water running in a mostly vertical
direction. They simulate the Atlantic and Pacific Oceans separating Earth's
two primary land regions. You can turn off the Atlantic rift by setting
has_center_rift to false. You can turn off all rifts by setting rift_grain
to -1. For most regional fractals, you will probably want to disable rifts.

invert_heights is not a function I have needed, but it seems clear enough. It
has to do with results returned by the fractal generator and could be used
instead of adjusting the height values, in some cases. I always adjust the
height values, though, so it has seemed like a redundant option. It's there
in case somebody wanted to use it, though.
-------------------------------------------------

GeneratePlotsInRegion is a fully automated process. If you want to layer land
plots, all you need to do is call this function over and over from the
controlling function: GeneratePlotsByRegion

Each region needs to be defined by the map scripter, then organized in the
controlling function. Pass in the necessary arguments to generatePlotsInRegion
and get back a region of land, already "layered" on to the global plot array.

The global plot array begins as all water. Each layer of fractalized plots is
applied in turn, overwriting the previous layer. Water plots in each layer are
ignored. Land plots of any type are assigned to the applicable plot. The water
"left over" at the end of the process will be whatever plots went untouched by
any of the regional layers' land plots. If regions overlap, landforms may overlap,
too. This allows both separate-distinct regional use, and layering over a single
area with as many passes as the scripter selects.


For most uses, you can use a new subclass to override GeneratePlotsByRegion
and not have to mess with the rest of the class. GeneratePlotsByRegion is the
controlling function and must be customized for each applicable map script.

- Bob Thomas   July 13, 2005
'''

# This class can be called instead of FractalWorld or HintedWorld.
# MultilayeredFractal enables multiple fractals to be
# layered over a single map, to generate plot types.
# Use GeneratePlotsByRegion to organize your fractal layers.


class MultilayeredFractal:

		def __init__(self, fracXExp=CyFractal.FracVals.DEFAULT_FRAC_X_EXP,
								 fracYExp=CyFractal.FracVals.DEFAULT_FRAC_Y_EXP):
				self.gc = CyGlobalContext()
				self.map = self.gc.getMap()
				self.iW = self.map.getGridWidth()
				self.iH = self.map.getGridHeight()
				self.dice = self.gc.getGame().getMapRand()
				self.iFlags = self.map.getMapFractalFlags()  # Defaults for that map type.
				self.iTerrainFlags = self.map.getMapFractalFlags()  # Defaults for that map type.
				self.iHorzFlags = CyFractal.FracVals.FRAC_WRAP_X + CyFractal.FracVals.FRAC_POLAR  # Use to prevent flat edges to north or south.
				self.iVertFlags = CyFractal.FracVals.FRAC_WRAP_Y + CyFractal.FracVals.FRAC_POLAR  # Use to prevent flat edges to east or west.
				self.iRoundFlags = CyFractal.FracVals.FRAC_POLAR  # Use to prevent flat edges on all sides.
				self.plotTypes = []  # Regional array
				self.wholeworldPlotTypes = [PlotTypes.PLOT_OCEAN] * (self.iW*self.iH)  # Global
				self.fracXExp = fracXExp
				self.fracYExp = fracYExp
				# Note: there is no checkForOverrideDefaultUserInputVariances()
				# function for MultilayeredFractal. You should control any
				# user input variances per region, in your region definitions.

		def shiftRegionPlots(self, iRegionWidth, iRegionHeight, iStrip=15):
				# Minimizes land plots along the region's edges by shifting the coordinates.
				stripRadius = min(15, iStrip)
				stripRadius = max(3, iStrip)
				best_split_x, best_split_y = 0, 0
				best_split_x = self.findBestRegionSplitX(iRegionWidth, iRegionHeight, stripRadius)
				best_split_y = self.findBestRegionSplitY(iRegionWidth, iRegionHeight, stripRadius)
				self.shiftRegionPlotsBy(best_split_x, best_split_y, iRegionWidth, iRegionHeight)

		def shiftRegionPlotsBy(self, xshift, yshift, iRegionWidth, iRegionHeight):
				if xshift > 0 or yshift > 0:
						# iWH = iRegionWidth * iRegionHeight
						buf = self.plotTypes[:]
						for iDestY in range(iRegionHeight):
								for iDestX in range(iRegionWidth):
										iDestI = iRegionWidth*iDestY + iDestX
										iSourceX = iDestX + xshift
										iSourceY = iDestY + yshift
										iSourceX %= iRegionWidth  # normalize
										iSourceY %= iRegionHeight

										iSourceI = iRegionWidth*iSourceY + iSourceX
										self.plotTypes[iDestI] = buf[iSourceI]

		def findBestRegionSplitY(self, iRegionWidth, iRegionHeight, stripRadius):
				stripSize = 2*stripRadius
				if stripSize > iRegionWidth:
						return 0

				numPlots = iRegionWidth * iRegionHeight
				stripCenterIndex = stripRadius
				piLandWeights = self.calcWeights(stripRadius)

				scores = [0]*iRegionHeight
				for y in range(iRegionHeight):
						landScore = 0
						bFoundLand = False
						for x in range(iRegionWidth):
								i = y*iRegionWidth + x
								assert (i >= 0 and i < numPlots)
								if self.plotTypes[i] == PlotTypes.PLOT_LAND:
										landScore += 1
										bFoundLand = True
						if bFoundLand:
								landScore += 30  # the first land is worth about 10 plots of land

						for i in range(stripSize):
								yy = y + i - stripCenterIndex
								yy %= iRegionHeight
								scores[yy] += landScore * piLandWeights[i]

				best_split_y, lowest_score = argmin(scores)
				return best_split_y

		def findBestRegionSplitX(self, iRegionWidth, iRegionHeight, stripRadius):
				stripSize = 2*stripRadius
				if stripSize > iRegionWidth:
						return 0

				numPlots = iRegionWidth * iRegionHeight
				stripCenterIndex = stripRadius
				piLandWeights = self.calcWeights(stripRadius)

				scores = [0]*iRegionWidth
				for x in range(iRegionWidth):
						landScore = 0
						bFoundLand = False
						for y in range(iRegionHeight):
								i = y*iRegionWidth + x
								assert (i >= 0 and i < numPlots)
								if self.plotTypes[i] == PlotTypes.PLOT_LAND:
										landScore += 1
										bFoundLand = True
						if bFoundLand:
								landScore += 30  # the first land is worth about 10 plots of land

						for i in range(stripSize):
								xx = x + i - stripCenterIndex
								xx %= iRegionWidth
								scores[xx] += landScore * piLandWeights[i]

				best_split_x, lowest_score = argmin(scores)
				return best_split_x

		def calcWeights(self, stripRadius):
				stripSize = 2*stripRadius
				landWeights = [0]*stripSize
				for i in range(stripSize):
						distFromStart = i+1
						distFromEnd = stripSize-i
						distFromEdge = min(distFromStart, distFromEnd)
						landWeight = distFromEdge
						distFromCenter = stripRadius - distFromEdge
						if distFromCenter <= 1:
								landWeight *= stripRadius
						if distFromCenter == 0:
								landWeight *= 2
						landWeights[i] = landWeight
				return landWeights

		def generatePlotsInRegion(self, iWaterPercent,
															iRegionWidth, iRegionHeight,
															iRegionWestX, iRegionSouthY,
															iRegionGrain, iRegionHillsGrain,
															iRegionPlotFlags, iRegionTerrainFlags,
															iRegionFracXExp=-1, iRegionFracYExp=-1,
															bShift=True, iStrip=15,
															rift_grain=-1, has_center_rift=False,
															invert_heights=False):
				# This is the code to generate each fractal.
				# Determine and pass in the appropriate arguments from the controlling function.
				#
				# Init local variables
				water = iWaterPercent
				iWestX = iRegionWestX
				# Note: if you pass bad regional dimensions so that iEastX > self.iW, BOOM! So don't do that. I could close out that possibility, but better that I not, so that you get an error to warn you of erroneous regional parameters. - Sirian
				iSouthY = iRegionSouthY

				# Init the plot types array and the regional fractals
				self.plotTypes = []  # reinit the array for each pass
				self.plotTypes = [PlotTypes.PLOT_OCEAN] * (iRegionWidth*iRegionHeight)
				regionContinentsFrac = CyFractal()
				regionHillsFrac = CyFractal()
				regionPeaksFrac = CyFractal()
				regionContinentsFrac.fracInit(iRegionWidth, iRegionHeight, iRegionGrain, self.dice, iRegionPlotFlags, iRegionFracXExp, iRegionFracYExp)
				regionHillsFrac.fracInit(iRegionWidth, iRegionHeight, iRegionHillsGrain, self.dice, iRegionTerrainFlags, iRegionFracXExp, iRegionFracYExp)
				regionPeaksFrac.fracInit(iRegionWidth, iRegionHeight, iRegionHillsGrain+1, self.dice, iRegionTerrainFlags, iRegionFracXExp, iRegionFracYExp)

				iWaterThreshold = regionContinentsFrac.getHeightFromPercent(water)
				iHillsBottom1 = regionHillsFrac.getHeightFromPercent(max((25 - self.gc.getClimateInfo(self.map.getClimate()).getHillRange()), 0))
				iHillsTop1 = regionHillsFrac.getHeightFromPercent(min((25 + self.gc.getClimateInfo(self.map.getClimate()).getHillRange()), 100))
				iHillsBottom2 = regionHillsFrac.getHeightFromPercent(max((75 - self.gc.getClimateInfo(self.map.getClimate()).getHillRange()), 0))
				iHillsTop2 = regionHillsFrac.getHeightFromPercent(min((75 + self.gc.getClimateInfo(self.map.getClimate()).getHillRange()), 100))
				iPeakThreshold = regionPeaksFrac.getHeightFromPercent(self.gc.getClimateInfo(self.map.getClimate()).getPeakPercent())

				# Loop through the region's plots
				for x in range(iRegionWidth):
						for y in range(iRegionHeight):
								i = y*iRegionWidth + x
								val = regionContinentsFrac.getHeight(x, y)
								if val <= iWaterThreshold:
										pass
								else:
										hillVal = regionHillsFrac.getHeight(x, y)
										if ((hillVal >= iHillsBottom1 and hillVal <= iHillsTop1) or (hillVal >= iHillsBottom2 and hillVal <= iHillsTop2)):
												peakVal = regionPeaksFrac.getHeight(x, y)
												if (peakVal <= iPeakThreshold):
														self.plotTypes[i] = PlotTypes.PLOT_PEAK
												else:
														self.plotTypes[i] = PlotTypes.PLOT_HILLS
										else:
												self.plotTypes[i] = PlotTypes.PLOT_LAND

				if bShift:
						# Shift plots to obtain a more natural shape.
						self.shiftRegionPlots(iRegionWidth, iRegionHeight, iStrip)

				# Once the plot types for the region have been generated, they must be
				# applied to the global plot array.
				#
				# Default approach is to ignore water and layer the lands over one another.
				# If you want to layer the water, too, or some other combination, then
				# create a subclass and override this function. Customize in your override.
				#
				# Apply the region's plots to the global plot array.
				for x in range(iRegionWidth):
						wholeworldX = x + iWestX
						for y in range(iRegionHeight):
								i = y*iRegionWidth + x
								if self.plotTypes[i] == PlotTypes.PLOT_OCEAN:
										continue
								wholeworldY = y + iSouthY
								iWorld = wholeworldY*self.iW + wholeworldX
								self.wholeworldPlotTypes[iWorld] = self.plotTypes[i]

				# This region is done.
				return

		def generatePlotsByRegion(self):
				# Sirian's MultilayeredFractal class, controlling function.
				# You -MUST- customize this function for each use of the class.
				#
				# The rest of this function from CvMapGeneratorUtil.py is provided
				# to you as a template. You will have to build your own version for
				# use with your map scripts, according to your designs.
				#
				# The following object indexes custom grain amounts per world size.
				# Add a new column for each desired global or regional grain setting.
				# (Grains are used to control fractal results. Larger grains create
				# smaller patches of similar values. Small grains create large patches.)
				#
				# Here is an example of obtaining grain sizes to fit with map sizes.
				sizekey = self.map.getWorldSize()
				sizevalues = {
						WorldSizeTypes.WORLDSIZE_DUEL:      (3, 2, 1, 2),
						WorldSizeTypes.WORLDSIZE_TINY:      (3, 2, 1, 2),
						WorldSizeTypes.WORLDSIZE_SMALL:     (3, 2, 1, 2),
						WorldSizeTypes.WORLDSIZE_STANDARD:  (4, 2, 1, 2),
						WorldSizeTypes.WORLDSIZE_LARGE:     (4, 2, 1, 2),
						WorldSizeTypes.WORLDSIZE_HUGE:      (5, 2, 1, 2)
				}
				# You can add as many grain entries as you like.
				# Seed them all from the matrix using the following type of line:
				(iGrainOne, iGrainTwo, iGrainThree, iGrainFour) = sizevalues[sizekey]
				# The example is for four grain values. You may not need that many.
				# Check scripts that use MultilayeredFractal for more examples.

				# Define the regions (necessary to any use of generatePlotsByRegion)
				# Start by initializing regional definitions.
				# All regions must be rectangular. (The fractal only feeds on these!)
				# Obtain region width and height by any method you care to design.
				# Obtain WestX and EastX, NorthY and SouthY, to define the boundaries.
				#
				# Note that Lat and Lon as used here are different from the use for
				# the generation of terrain types and features. Sorry for the ambiguity!
				#
				# Latitude and Longitude are values between 0.0 and 1.0
				# Latitude South to North is 0.0 to 1.0
				# Longitude West to East is 0.0 to 1.0
				# Plots are indexed by X,Y with 0,0 in SW corner.
				#
				# Here is an example set of definitions
				regiononeWestLon = 0.05
				regiononeEastLon = 0.35
				regiononeNorthLat = 0.95
				regiononeSouthLat = 0.45
				#regiontwoWestLon = 0.45
				#regiontwoEastLon = 0.95
				subcontinentLargeHorz = 0.2
				subcontinentLargeVert = 0.32
				#subcontinentLargeNorthLat = 0.6
				subcontinentLargeSouthLat = 0.28
				#subcontinentSmallDimension = 0.125
				#subcontinentSmallNorthLat = 0.525
				#subcontinentSmallSouthLat = 0.4
				# You can then use these longitudes and latitudes crossed with grid sizes
				# to enable one definition to fit any map size, map width, map height.

				# Define your first region here.
				NiTextOut("Generating Region One (Python Map_Script_Name) ...")
				# Set dimensions of your region. (Below is an example).
				regiononeWestX = int(self.iW * regiononeWestLon)
				regiononeEastX = int(self.iW * regiononeEastLon)
				regiononeNorthY = int(self.iH * regiononeNorthLat)
				regiononeSouthY = int(self.iH * regiononeSouthLat)
				regiononeWidth = regiononeEastX - regiononeWestX + 1
				regiononeHeight = regiononeNorthY - regiononeSouthY + 1
				regiononeWater = 70

				regiononeGrain = 2  # Ramk, variable was undefined

				# With all of your parameters set, pass them in to the plot generator.
				self.generatePlotsInRegion(regiononeWater,
																	 regiononeWidth, regiononeHeight,
																	 regiononeWestX, regiononeSouthY,
																	 regiononeGrain, iGrainOne,
																	 self.iFlags, self.iTerrainFlags,
																	 -1, -1,
																	 True, 15,
																	 2, False,
																	 False
																	 )

				# Define additional regions.
				# Regions can overlap or add on to other existing regions.
				# Example of a subcontinent region appended to region one from above:
				NiTextOut("Generating subcontinent for Region One (Python Map_Script_Name) ...")
				scLargeWidth = int(subcontinentLargeHorz * self.iW)
				scLargeHeight = int(subcontinentLargeVert * self.iH)
				scRoll = self.dice.get((regiononeWidth - scLargeWidth), "Large Subcontinent Placement - Map_Script_Name PYTHON")
				scWestX = regiononeWestX + scRoll
				#scEastX = scWestX + scLargeWidth
				#scNorthY = int(self.iH * subcontinentLargeNorthLat)
				scSouthY = int(self.iH * subcontinentLargeSouthLat)

				# Clever use of dice rolls can inject some randomization in to definitions.
				scShape = self.dice.get(3, "Large Subcontinent Shape - Map_Script_Name PYTHON")
				if scShape == 2:  # Massive subcontinent!
						scWater = 55
						scGrain = 1
						scRift = 2
				elif scShape == 1:  # Standard subcontinent.
						scWater = 66
						scGrain = 2
						scRift = 2
				else:  # scShape == 0, Archipelago subcontinent.
						archGrain = 2  # Ramk, variable was undefined
						scWater = 77
						scGrain = archGrain
						scRift = -1

				# Each regional fractal needs its own uniquely defined parameters.
				# With proper settings, there's almost no limit to what can be done.
				self.generatePlotsInRegion(scWater,
																	 scLargeWidth, scLargeHeight,
																	 scWestX, scSouthY,
																	 scGrain, iGrainOne,
																	 self.iRoundFlags, self.iTerrainFlags,
																	 6, 6,
																	 False, 9,
																	 scRift, False,
																	 False
																	 )

				# Once all your of your fractal regions (and other regions! You do not have
				# to make every region a fractal-based region) have been processed, and
				# your plot generation is complete, return the global plot array.
				#
				# All regions have been processed. Plot Type generation completed.
				return self.wholeworldPlotTypes


'''
Regional Variables Key:

iWaterPercent,
iRegionWidth, iRegionHeight,
iRegionWestX, iRegionSouthY,
iRegionGrain, iRegionHillsGrain,
iRegionPlotFlags, iRegionTerrainFlags,
iRegionFracXExp, iRegionFracYExp,
bShift, iStrip,
rift_grain, has_center_rift,
invert_heights
'''


class TerrainGenerator:
		"If iDesertPercent=35, then about 35% of all land will be desert. Plains is similar. \
		Note that all percentages are approximate, as values have to be roughened to achieve a natural look."

		def __init__(self, iDesertPercent=32, iPlainsPercent=18,
								 fSnowLatitude=0.7, fTundraLatitude=0.6,
								 fGrassLatitude=0.1, fDesertBottomLatitude=0.2,
								 fDesertTopLatitude=0.5, fracXExp=-1,
								 fracYExp=-1, grain_amount=4):

				self.gc = CyGlobalContext()
				self.map = CyMap()

				grain_amount += self.gc.getWorldInfo(self.map.getWorldSize()).getTerrainGrainChange()

				self.grain_amount = grain_amount

				self.iWidth = self.map.getGridWidth()
				self.iHeight = self.map.getGridHeight()

				self.mapRand = self.gc.getGame().getMapRand()

				self.iFlags = 0  # Disallow FRAC_POLAR flag, to prevent "zero row" problems.
				if self.map.isWrapX():
						self.iFlags += CyFractal.FracVals.FRAC_WRAP_X
				if self.map.isWrapY():
						self.iFlags += CyFractal.FracVals.FRAC_WRAP_Y

				self.deserts = CyFractal()
				self.plains = CyFractal()
				self.variation = CyFractal()

				iDesertPercent += self.gc.getClimateInfo(self.map.getClimate()).getDesertPercentChange()
				iDesertPercent = min(iDesertPercent, 100)
				iDesertPercent = max(iDesertPercent, 0)

				self.iDesertPercent = iDesertPercent
				self.iPlainsPercent = iPlainsPercent

				self.iDesertTopPercent = 100
				self.iDesertBottomPercent = max(0, int(100-iDesertPercent))
				self.iPlainsTopPercent = 100
				self.iPlainsBottomPercent = max(0, int(100-iDesertPercent-iPlainsPercent))
				self.iMountainTopPercent = 75
				self.iMountainBottomPercent = 60

				fSnowLatitude += self.gc.getClimateInfo(self.map.getClimate()).getSnowLatitudeChange()
				fSnowLatitude = min(fSnowLatitude, 1.0)
				fSnowLatitude = max(fSnowLatitude, 0.0)
				self.fSnowLatitude = fSnowLatitude

				fTundraLatitude += self.gc.getClimateInfo(self.map.getClimate()).getTundraLatitudeChange()
				fTundraLatitude = min(fTundraLatitude, 1.0)
				fTundraLatitude = max(fTundraLatitude, 0.0)
				self.fTundraLatitude = fTundraLatitude

				fGrassLatitude += self.gc.getClimateInfo(self.map.getClimate()).getGrassLatitudeChange()
				fGrassLatitude = min(fGrassLatitude, 1.0)
				fGrassLatitude = max(fGrassLatitude, 0.0)
				self.fGrassLatitude = fGrassLatitude

				fDesertBottomLatitude += self.gc.getClimateInfo(self.map.getClimate()).getDesertBottomLatitudeChange()
				fDesertBottomLatitude = min(fDesertBottomLatitude, 1.0)
				fDesertBottomLatitude = max(fDesertBottomLatitude, 0.0)
				self.fDesertBottomLatitude = fDesertBottomLatitude

				fDesertTopLatitude += self.gc.getClimateInfo(self.map.getClimate()).getDesertTopLatitudeChange()
				fDesertTopLatitude = min(fDesertTopLatitude, 1.0)
				fDesertTopLatitude = max(fDesertTopLatitude, 0.0)
				self.fDesertTopLatitude = fDesertTopLatitude

				self.fracXExp = fracXExp
				self.fracYExp = fracYExp

				self.initFractals()

		def initFractals(self):
				self.deserts.fracInit(self.iWidth, self.iHeight, self.grain_amount, self.mapRand, self.iFlags, self.fracXExp, self.fracYExp)
				self.iDesertTop = self.deserts.getHeightFromPercent(self.iDesertTopPercent)
				self.iDesertBottom = self.deserts.getHeightFromPercent(self.iDesertBottomPercent)

				self.plains.fracInit(self.iWidth, self.iHeight, self.grain_amount+1, self.mapRand, self.iFlags, self.fracXExp, self.fracYExp)
				self.iPlainsTop = self.plains.getHeightFromPercent(self.iPlainsTopPercent)
				self.iPlainsBottom = self.plains.getHeightFromPercent(self.iPlainsBottomPercent)

				self.variation.fracInit(self.iWidth, self.iHeight, self.grain_amount, self.mapRand, self.iFlags, self.fracXExp, self.fracYExp)

				self.terrainDesert = self.gc.getInfoTypeForString("TERRAIN_DESERT")
				self.terrainPlains = self.gc.getInfoTypeForString("TERRAIN_PLAINS")
				self.terrainIce = self.gc.getInfoTypeForString("TERRAIN_SNOW")
				self.terrainTundra = self.gc.getInfoTypeForString("TERRAIN_TUNDRA")
				self.terrainGrass = self.gc.getInfoTypeForString("TERRAIN_GRASS")
				# PAE
				self.terrainSwamp = self.gc.getInfoTypeForString("TERRAIN_SWAMP")

		def getLatitudeAtPlot(self, iX, iY):
				"""given a point (iX,iY) such that (0,0) is in the NW,
				returns a value between 0.0 (tropical) and 1.0 (polar).
				This function can be overridden to change the latitudes; for example,
				to make an entire map have temperate terrain, or to make terrain change from east to west
				instead of from north to south"""
				lat = abs((self.iHeight / 2) - iY)/float(self.iHeight/2)  # 0.0 = equator, 1.0 = pole

				# Adjust latitude using self.variation fractal, to mix things up:
				lat += (128 - self.variation.getHeight(iX, iY))/(255.0 * 5.0)

				# Limit to the range [0, 1]:
				if lat < 0:
						lat = 0.0
				if lat > 1:
						lat = 1.0

				return lat

		def generateTerrain(self):
				terrainData = [0]*(self.iWidth*self.iHeight)
				for x in range(self.iWidth):
						for y in range(self.iHeight):
								iI = y*self.iWidth + x
								terrain = self.generateTerrainAtPlot(x, y)
								terrainData[iI] = terrain
				return terrainData

		def generateTerrainAtPlot(self, iX, iY):
				lat = self.getLatitudeAtPlot(iX, iY)

				if (self.map.plot(iX, iY).isWater()):
						return self.map.plot(iX, iY).getTerrainType()

				terrainVal = self.terrainGrass

				if lat >= self.fSnowLatitude:
						terrainVal = self.terrainIce
				elif lat >= self.fTundraLatitude:
						terrainVal = self.terrainTundra
				elif lat < self.fGrassLatitude:
						terrainVal = self.terrainGrass
				else:
						desertVal = self.deserts.getHeight(iX, iY)
						plainsVal = self.plains.getHeight(iX, iY)
						if ((desertVal >= self.iDesertBottom) and (desertVal <= self.iDesertTop) and (lat >= self.fDesertBottomLatitude) and (lat < self.fDesertTopLatitude)):
								terrainVal = self.terrainDesert
						elif ((plainsVal >= self.iPlainsBottom) and (plainsVal <= self.iPlainsTop)):
								terrainVal = self.terrainPlains

				if (terrainVal == TerrainTypes.NO_TERRAIN):
						return self.map.plot(iX, iY).getTerrainType()

				# PAE
				if terrainVal == self.terrainGrass and not self.map.plot(iX, iY).isPeak() and not self.map.plot(iX, iY).isHills():
						if self.mapRand.get(10, "Add Terrain Swamp") == 1:
								return self.terrainSwamp

				return terrainVal


class FeatureGenerator:

		def __init__(self, iJunglePercent=30, iForestPercent=50,
								 jungle_grain=4, forest_grain=6,
								 fracXExp=-1, fracYExp=-1):

				self.gc = CyGlobalContext()
				self.map = CyMap()
				self.mapRand = self.gc.getGame().getMapRand()
				self.jungles = CyFractal()
				self.forests = CyFractal()
				self.denseforests = CyFractal()
				self.savannas = CyFractal()

				self.iFlags = 0  # Disallow FRAC_POLAR flag, to prevent "zero row" problems.
				if self.map.isWrapX():
						self.iFlags += CyFractal.FracVals.FRAC_WRAP_X
				if self.map.isWrapY():
						self.iFlags += CyFractal.FracVals.FRAC_WRAP_Y

				self.iGridW = self.map.getGridWidth()
				self.iGridH = self.map.getGridHeight()

				self.iJunglePercent = iJunglePercent
				self.iSavannaPercent = 60
				self.iForestPercent = iForestPercent
				self.iDenseForestPercent = 60

				jungle_grain += self.gc.getWorldInfo(self.map.getWorldSize()).getFeatureGrainChange()
				savanna_grain = 1 + self.gc.getWorldInfo(self.map.getWorldSize()).getFeatureGrainChange()
				forest_grain += self.gc.getWorldInfo(self.map.getWorldSize()).getFeatureGrainChange()
				denseforest_grain = 2 + self.gc.getWorldInfo(self.map.getWorldSize()).getFeatureGrainChange()

				self.jungle_grain = jungle_grain
				self.savanna_grain = savanna_grain
				self.forest_grain = forest_grain
				self.denseforest_grain = denseforest_grain

				self.fracXExp = fracXExp
				self.fracYExp = fracYExp

				self.__initFractals()
				self.__initFeatureTypes()

		def __initFractals(self):
				self.jungles.fracInit(self.iGridW, self.iGridH, self.jungle_grain, self.mapRand, self.iFlags, self.fracXExp, self.fracYExp)
				self.savannas.fracInit(self.iGridW, self.iGridH, self.savanna_grain, self.mapRand, self.iFlags, self.fracXExp, self.fracYExp)
				self.forests.fracInit(self.iGridW, self.iGridH, self.forest_grain, self.mapRand, self.iFlags, self.fracXExp, self.fracYExp)
				self.denseforests.fracInit(self.iGridW, self.iGridH, self.denseforest_grain, self.mapRand, self.iFlags, self.fracXExp, self.fracYExp)

				self.iJungleTop = self.jungles.getHeightFromPercent((100 + self.iJunglePercent)/2)
				self.iJungleBottom = self.jungles.getHeightFromPercent((100 - self.iJunglePercent)/2)
				self.iSavannaTop = self.savannas.getHeightFromPercent(80)
				self.iSavannaBottom = self.savannas.getHeightFromPercent(20)
				self.iForestLevel = self.forests.getHeightFromPercent(self.iForestPercent)
				self.iDenseForestLevel = self.denseforests.getHeightFromPercent(80)

		def __initFeatureTypes(self):
				self.featureIce = self.gc.getInfoTypeForString("FEATURE_ICE")
				self.featureJungle = self.gc.getInfoTypeForString("FEATURE_JUNGLE")
				self.featureForest = self.gc.getInfoTypeForString("FEATURE_FOREST")
				self.featureDenseForest = self.gc.getInfoTypeForString("FEATURE_DICHTERWALD")
				self.featureOasis = self.gc.getInfoTypeForString("FEATURE_OASIS")
				self.featureSavanna = self.gc.getInfoTypeForString("FEATURE_SAVANNA")
				# for PAE
				self.terrainSwamp = self.gc.getInfoTypeForString("TERRAIN_SWAMP")
				self.terrainGrass = self.gc.getInfoTypeForString("TERRAIN_GRASS")

		def addFeatures(self):

				# for PAE
				self.terrainSwamp = self.gc.getInfoTypeForString("TERRAIN_SWAMP")
				self.terrainGrass = self.gc.getInfoTypeForString("TERRAIN_GRASS")

				"adds features to all plots as appropriate"
				for iX in range(self.iGridW):
						for iY in range(self.iGridH):
								self.addFeaturesAtPlot(iX, iY)

								# PAE: hier, weil die Fluesse bei, TerrainGenerator noch nicht gesetzt sind
								pPlot = self.map.sPlot(iX, iY)
								if not pPlot.isWater() and not pPlot.isPeak() and not pPlot.isHills() and pPlot.isRiver():
										if pPlot.getTerrainType() == self.terrainGrass:
												if self.mapRand.get(5, "Add Terrain Swamp") == 1:
														pPlot.setTerrainType(self.terrainSwamp, 0, 0)

		def getLatitudeAtPlot(self, iX, iY):
				"returns a value in the range of 0.0 (tropical) to 1.0 (polar)"
				return abs((self.iGridH/2) - iY)/float(self.iGridH/2)  # 0.0 = equator, 1.0 = pole

		def addFeaturesAtPlot(self, iX, iY):
				"adds any appropriate features at the plot (iX, iY) where (0,0) is in the SW"
				lat = self.getLatitudeAtPlot(iX, iY)
				pPlot = self.map.sPlot(iX, iY)

				for iI in range(self.gc.getNumFeatureInfos()):
						if pPlot.canHaveFeature(iI):
								if self.mapRand.get(10000, "Add Feature PYTHON") < self.gc.getFeatureInfo(iI).getAppearanceProbability():
										pPlot.setFeatureType(iI, -1)

				if (pPlot.getFeatureType() == FeatureTypes.NO_FEATURE):
						self.addIceAtPlot(pPlot, iX, iY, lat)

				if (pPlot.getFeatureType() == FeatureTypes.NO_FEATURE):
						self.addJunglesAtPlot(pPlot, iX, iY, lat)

				if (pPlot.getFeatureType() == FeatureTypes.NO_FEATURE):
						self.addSavannasAtPlot(pPlot, iX, iY, lat)

				if (pPlot.getFeatureType() == FeatureTypes.NO_FEATURE):
						self.addForestsAtPlot(pPlot, iX, iY, lat)

				if (pPlot.getFeatureType() == FeatureTypes.NO_FEATURE):
						self.addDenseForestsAtPlot(pPlot, iX, iY, lat)

		def addIceAtPlot(self, pPlot, iX, iY, lat):
				if pPlot.canHaveFeature(self.featureIce):
						if (self.map.isWrapX() and not self.map.isWrapY()) and (iY == 0 or iY == self.iGridH - 1):
								pPlot.setFeatureType(self.featureIce, -1)
						elif (self.map.isWrapY() and not self.map.isWrapX()) and (iX == 0 or iX == self.iGridW - 1):
								pPlot.setFeatureType(self.featureIce, -1)
						elif (not self.map.isWrapY()):
								rand = self.mapRand.get(100, "Add Ice PYTHON")/100.0
								if rand < 8 * (lat - (1.0 - (self.gc.getClimateInfo(self.map.getClimate()).getRandIceLatitude() / 2.0))):
										pPlot.setFeatureType(self.featureIce, -1)
								elif rand < 4 * (lat - (1.0 - self.gc.getClimateInfo(self.map.getClimate()).getRandIceLatitude())):
										pPlot.setFeatureType(self.featureIce, -1)

		def addJunglesAtPlot(self, pPlot, iX, iY, lat):
				if pPlot.canHaveFeature(self.featureJungle):
						iHeight = self.jungles.getHeight(iX, iY)
						if self.iJungleTop >= iHeight >= self.iJungleBottom + (self.iJungleTop - self.iJungleBottom)*self.gc.getClimateInfo(self.map.getClimate()).getJungleLatitude()*lat:
								pPlot.setFeatureType(self.featureJungle, -1)

		def addSavannasAtPlot(self, pPlot, iX, iY, lat):
				if pPlot.canHaveFeature(self.featureSavanna):
						iHeight = self.savannas.getHeight(iX, iY)
						if self.iSavannaTop >= iHeight >= self.iSavannaBottom + (self.iSavannaTop - self.iSavannaBottom)*self.gc.getClimateInfo(self.map.getClimate()).getJungleLatitude()*lat:
								pPlot.setFeatureType(self.featureSavanna, -1)

		def addForestsAtPlot(self, pPlot, iX, iY, lat):
				if pPlot.canHaveFeature(self.featureForest):
						if self.forests.getHeight(iX, iY) >= self.iForestLevel:
								pPlot.setFeatureType(self.featureForest, -1)

		def addDenseForestsAtPlot(self, pPlot, iX, iY, lat):
				if pPlot.canHaveFeature(self.featureDenseForest):
						if self.denseforests.getHeight(iX, iY) >= self.iDenseForestLevel:
								pPlot.setFeatureType(self.featureDenseForest, -1)


def getAreas():
		"Returns a list of CyArea objects representing all the areas in the map (land and water)"
		#gc = CyGlobalContext()
		map = CyMap()

		areas = []
		for i in range(map.getIndexAfterLastArea()):
				area = map.getArea(i)
				if not area.isNone():
						areas.append(area)

		return areas


def findStartingPlot(playerID, validFn=None):
		gc = CyGlobalContext()
		map = CyMap()
		player = gc.getPlayer(playerID)

		player.AI_updateFoundValues(True)

		iRange = player.startingPlotRange()
		iPass = 0

		while True:
				iBestValue = 0
				pBestPlot = None

				for iX in range(map.getGridWidth()):
						for iY in range(map.getGridHeight()):
								if validFn is not None and not validFn(playerID, iX, iY):
										continue
								pLoopPlot = map.plot(iX, iY)
								val = pLoopPlot.getFoundValue(playerID)
								if val > iBestValue:
										valid = True
										for iI in range(gc.getMAX_CIV_PLAYERS()):
												if (gc.getPlayer(iI).isAlive()):
														if (iI != playerID):
																if gc.getPlayer(iI).startingPlotWithinRange(pLoopPlot, playerID, iRange, iPass):
																		valid = False
																		break

										if valid:
												iBestValue = val
												pBestPlot = pLoopPlot

				if pBestPlot is not None:
						return map.plotNum(pBestPlot.getX(), pBestPlot.getY())

				print("player", playerID, "pass", iPass, "failed")

				iPass += 1

		return -1


def argmin(list):
		best = None
		best_index = None
		for i in range(len(list)):
				val = list[i]
				if (best is None) or (val < best):
						best_index = i
						best = val
		return (best_index, best)


def pointInRect(point, rect):
		x, y = point
		rectx, recty, rectw, recth = rect
		if rectx <= x < rectx + rectw:
				if recty <= y < recty + recth:
						return True
		return False


class BonusBalancer:

		def __init__(self):
				self.gc = CyGlobalContext()
				self.map = CyMap()

				self.resourcesToBalance = ('BONUS_COAL', 'BONUS_COPPER', 'BONUS_HORSE', 'BONUS_IRON')
				self.resourcesToEliminate = ('BONUS_MARBLE')

		def isSkipBonus(self, iBonusType):
				type_string = self.gc.getBonusInfo(iBonusType).getType()

				return ((type_string in self.resourcesToBalance) or (type_string in self.resourcesToEliminate))

		def isBonusValid(self, eBonus, pPlot, bIgnoreUniqueRange, bIgnoreOneArea, bIgnoreAdjacent):
				"Returns true if we can place a bonus here"

				iX, iY = pPlot.getX(), pPlot.getY()

				if (not bIgnoreOneArea) and self.gc.getBonusInfo(eBonus).isOneArea():
						if self.map.getNumBonuses(eBonus) > 0:
								if self.map.getArea(pPlot.getArea()).getNumBonuses(eBonus) == 0:
										return False

				if not bIgnoreAdjacent:
						for iI in range(DirectionTypes.NUM_DIRECTION_TYPES):
								pLoopPlot = plotDirection(iX, iY, DirectionTypes(iI))
								if not pLoopPlot.isNone():
										if (pLoopPlot.getBonusType(-1) != -1) and (pLoopPlot.getBonusType(-1) != eBonus):
												return False

				if not bIgnoreUniqueRange:
						uniqueRange = self.gc.getBonusInfo(eBonus).getUniqueRange()
						for iDX in range(-uniqueRange, uniqueRange+1):
								for iDY in range(-uniqueRange, uniqueRange+1):
										pLoopPlot = plotXY(iX, iY, iDX, iDY)
										if not pLoopPlot.isNone() and pLoopPlot.getBonusType(-1) == eBonus:
												return False

				return True

		def normalizeAddExtras(self):

				for i in range(self.gc.getMAX_CIV_PLAYERS()):
						if (self.gc.getPlayer(i).isAlive()):
								start_plot = self.gc.getPlayer(i).getStartingPlot()  # returns a CyPlot
								startx, starty = start_plot.getX(), start_plot.getY()

								plots = []  # build a list of the plots near the starting plot
								for dx in range(-5, 6):
										for dy in range(-5, 6):
												x, y = startx+dx, starty+dy
												pLoopPlot = self.map.plot(x, y)
												if not pLoopPlot.isNone():
														plots.append(pLoopPlot)

								resources_placed = []
								for pass_num in range(4):
										bIgnoreUniqueRange = pass_num >= 1
										bIgnoreOneArea = pass_num >= 2
										bIgnoreAdjacent = pass_num >= 3

										for bonus in range(self.gc.getNumBonusInfos()):
												type_string = self.gc.getBonusInfo(bonus).getType()
												if (type_string not in resources_placed) and (type_string in self.resourcesToBalance):
														for (pLoopPlot) in plots:
																if (pLoopPlot.canHaveBonus(bonus, True)):
																		if self.isBonusValid(bonus, pLoopPlot, bIgnoreUniqueRange, bIgnoreOneArea, bIgnoreAdjacent):
																				pLoopPlot.setBonusType(bonus)
																				resources_placed.append(type_string)
																				# print "placed", type_string, "on pass", pass_num
																				break  # go to the next bonus
