ArabianTotestra.py

##############################################################################
## Arabian Totestra
## Version: 2022-01-01 (Happy New Year!)
## This is a fork of Totestra designed for Legends of Ancient Arabia.
## Hence, the map will use one of about 180 possible fixed seeds to 
## generate the world.  It's possible to select one of the seeds 
## below randomly, or to specify one of three fixed seeds.
## The worlds have been selected because they generate maps which are 
## suitable for an Arabian adventure (main land in middle latitudes, has no
## snow and little tundra)

"""
# About
ArabianTotestra.py is a map script for Civilization IV.  It is derived 
from Rich Marinaccio's map script Perfect World.  While Rich Marinaccio
never provided a license for Perfect World, he has given me permission 
to make derivatives of it and I believe he is OK with any and all
non-commercial use of the script.

In this variant of Perfect World, I have made a version of Perfect World
which generates the same maps Perfect World generates, but only (by default)
selects maps which are suitable for the Warlords Mod "Legends of Ancient
Arabia".

This is a map script: It is a Python2 program run by Civilization IV to
generate a map for that game.

This map script is designed to model a natural world like Earth:  The 
scipt simulates plate tectonics, rainfall, meteor hits, and other factors
which created the continents on Earth.

This script limits the number of worlds that can be generated.  A script
was run for several weeks to find Perfect World random number generator
seeds which generate simulated planets suitable for creating an Arabian
adventure:  The main continent needs to be near the equator, and there
needs to be very little cold areas in that continent.  This script, by
default, will only randomly select one of the larger possible Arabian
adventures found by this script.

Unlike other Civilization IV map generators, all of the players will 
start on the same continent, changing the map size won't change the
size of the generated map (all maps are 144 tiles wide and 96 tiles 
tall), climate can not be selected (the climate is arid), and the
sea level can not be adjusted.

# Installation

Place this in one's PublicMaps folder, such as 
"/Sid Meier's Civilization 4 Complete/Warlords/PublicMaps/".  When
starting a game, select "Custom Game", and make sure "ArabianTotestra"
is visible when selecting "Map".

# Options

## Size

This should be set to Huge.  While it can be set to a smaller size, the
map generator *always* generates an 144x96 map; smaller sizes reduce the
default number of players and make war weariness happen more quickly
while not affecting the actual map generated.

## Era

Set this to the desired era to start with.  With the "Legends of Ancient
Arabia" mod, this should be "Ancient".

## Speed

How fast the game develops.  For a quick game, choose "Quick" or "Normal",
and choose "Smaller start continents" for the seed below.

## Resources

Perfect World had its own unique resource placement code which better
simulates resources in the real world.  For Civilization games, this is
less than ideal.  "Full of resources" simply randomly places a large
number of resources everywhere on the map; "Resources evenly spread"
does not place resources on their own continents, but acts like "Full
of resources", except the resource count is lower.  "Like Perfect World"
uses Perfect World's resource placement code.

## Map seed

This determines the seed given to the pseudo random number generator
to generate a map.  Running a script on a Raspberry Pi server found a
large number of maps which appear to be suitable for Arabian adventures.

Selecting "larger start continents" will select one of those seeds which 
generates a continent with a size of 1400 or higher.  This is suitable
for a game at "epic" or "marathon" speeds.

"Smaller start continents" will select a seed which makes a continent 
smaller than 1400 in size.  This is for a game at "quick" or "normal"
speeds.

"Random" will select any known seed suitable for generating an Arabian
adventure.

"Free form (not Arabian)" will select a completely random Pefect World seed; 
most maps will not be optimized for an Arabian adventure.

"Amira map" is a fixed seed I found in 2018 which looks to be a very
enjoyable Arabian adventure.  Selecting this will always generate the
same map.

"Caulixtla map" is a fixed seed I found in 2012 which is my usual go
to Arabian adventure map.  If nine players are selected, this is the 
Hijazi start in the Arabian Caulixtla map included with my fork of 
"Legends of Ancient Arabia".  Note that this map will be upside down
compared to the map included with "Legends of Ancient Arabia"; the
LOAA version of the map was flipped over 180 degrees back in 2012.

"Fixed seed (Jungle start)" is a fixed seed making a larger continent
where the player starts in a jungle.

"Caulixtla map (Jungle start)" is the Caulixtla map again, but with
a start in a Jungle, as long as precisely nine players are selected (the
number of tribes in "Legends of Ancient Arabia").  If the map does not
have nine players, the player may not start in a jungle.  This start
is the Omani start in the 2012 version of the Arabian Caulixtla map,
and the Hijazi start in the 2021 second revision of the Arabian Caulixtla
map.

"Fixed seed (Grassland start)" is a different map than the "Fixed seed
(Jungle start)" map above, and places the player on a medium sized map.
Like the Caulixtla map and other Fixed seed, this seed will always 
generate the same map.

None of the fixed seed maps will be generated if selecting "Large start
continents", "Small start continents", "Random", or free form maps.
In addition, the free form maps will never generate a map from the "Large
start continents", "Small start continents", and "Random" list of maps.

## Player bonus resources

If playing at a harder difficulty, or if simply wanting to play an easier
game, it may be desirable to have more resources at one's starting
location. There are a large number of levels of bouns resources placed
in the player's start.

This allows one to have more starting resources without having to 
regenerate the map until one has the desired quantity of starting 
resources.

## Hut placement

This determines how goody huts are placed on the map.  "Civ4 default" 
just uses Civ4's default hut placement code; note that a given map seed
will have different hut placements every time a map is generated.  In
other words, if using "Civ4 default" and one of the fixed seeds, the 
huts will still vary their location every time the map is generated.

"No huts" simply does not put any goody huts on the map.  This is the
behavior the original "Legends of Ancient Arabia" has with its default
map.

"Fixed huts per seed" places a reasonable number of huts on the map.
A given map seed will always have the same locations for goody huts.

"Huts are rare" makes huts very uncommon.  A given map seed will always
have the same locations for huts.

"Many desert huts" places a large number of goody huts in deserts.  A 
given map seed will have the same hut locations.

"Many huts everywhere" has many goody huts all over the map.  A given map
seed will have the same hut locations.

# Running stand alone
The script can also be run stand alone.  This will not generate maps;
if map generation in standalone mode is desired, use old/TotestraRG32.py
instead.  Instead, standalone mode tests the random number generator to
ensure it is generating correct RadioGatun[32] sums.

To run it standalone:

```
python2 ArabianTotestra.py --test foo
```

Replace foo above with the desired string to generate a RadioGatun[32]
sum of.
"""

# Here is a list of seeds for a possible Arabian adventure.  Each seed is
# in (size, seed) format.
# Batch #1: 39000-52999
seedList = [(822, 52805),
(905, 51274),
(920, 49666),
(941, 39432),
(1009, 42645),
(1046, 49344),
(1047, 42527),
(1170, 46736),
(1185, 40509),
(1189, 47305),
(1214, 48855),
(1247, 41934),
(1291, 51302),
(1296, 48054),
(1305, 45083),
(1305, 51471),
(1315, 44103),
(1331, 52939),
(1366, 41848),
(1379, 46296),
(1382, 47419),
(1387, 47362),
(1410, 44380),
(1412, 47479),
(1460, 41126),
(1510, 44859),
(1519, 42362),
(1527, 41446),
(1554, 40780),
(1593, 50570),
(1605, 40170),
(1613, 48732),
(1746, 52226),
(1752, 43333),
(1823, 49499),
(1841, 47902),
(1851, 46824),
(1906, 46453),
(1912, 48126),
(2006, 50950),
(2173, 43216),
(2292, 42086),
(2323, 42609),
# Batch #2 70000+
(1544,70343),
(849,70810),
(1015,70843),
(1784,71015),
(1254,71467),
(1827,71484),
(1152,71499),
(1384,71566),
(2032,71855),
(709,71995),
(1161,72253),
(1035,72270),
(1640,72540),
(1271,72588),
(1959,72607),
(1534,72687),
(1644,72779),
(2013,73569),
(1034,73747),
(2113,73824),
(2022,73916),
(1674,74715),
(1164,75189),
(907,75214),
(2037,75280),
(1634,75374),
(1767,75409),
(795,75484),
(1710,75720),
(1812,75842),
(1916,76097),
(2348,76403),
(1393,76612),
(1612,77251),
(1412,77457),
(1021,77515),
(1409,77794),
(1923,77833),
(1822,78143),
(1167,78241),
(1781,78911),
(1053,79207),
(798,79391),
(1560,79494),
(2381,79534),
(1395,79661),
(1702,79861),
(1203,80387),
(989,80746),
(1454,80839),
(1208,81580),
(1431,81666),
(1839,82569),
(969,83077),
(912,83129),
(1804,83693),
(919,83897),
(1778,83960),
(1153,85024),
(1886,85846),
(1300,86356),
(1250,86631),
(1489,86846),
(1033,87400),
(1479,87402),
(1100,87512),
(1023,87925),
(1574,88522),
(1594,88823),
(1242,89101),
(946,89352),
(626,89650),
(1026,89777),
(1229,89816),
(1193,90116),
(868,90397),
(1105,90713),
(1177,90728),
(1481,90739),
(1032,90839),
(1794,91108),
(1543,91157),
(1294,91451),
(1315,91704),
(1417,92058),
(1070,92084),
(792,92102),
(1817,92156),
(1152,92794),
(1028,93379),
(1539,94166),
(1162,94324),
(1523,94751),
(2530,95000),
(1545,95113),
(1432,95305),
(1469,95600),
(1026,95813),
(1473,96034),
(1106,96942),
(1390,97173),
(1327,97610),
(1074,97755),
(791,97824),
(1612,98289),
(820,98419),
(1615,98603),
(1858,98677),
(1398,98881),
(1666,99421),
(2128,99613),
(1192,100109),
(1663,100321),
(1523,100799),
(1630,100870),
(2464,100891),
(1477,100980),
(1498,101145),
(1276,102074),
(1220,102806),
(1324,103244),
(984,103349),
(1503,103366),
(2256,103771),
(2103,104060),
(1112,104419),
(1453,104499),
(1349,104741),
(1805,104767),
(1189,104779),
(1614,104813),
(1356,105228),
(1068,105415),
(1338,105767),
(1503,105977),
(965,106312),
(1171,106559),
(1939,106617),
(989,107147),
(985,107856),
(1310,108193)
]

## Changes from PerfectWorld 2.06 (*not* 2.06f)
## 1) Ability to select climate
## 2) Ability to use fixed random seed
## 3) Remove mountains next to coast (fix coastside mountain ring bug)
## 4) Allow everyone to start on same landmass (biggest or 2nd biggest)
## 5) Have options for changing resource distribution
## 6) Note random seed on sign placed in the arctic
## 7) Ability to have bigger (192x128) or smaller (96x64) maps
## 8) Use RadioGatun[32] for random number generation
## File: PerfectWorld.py version 2.06
## Author: Rich Marinaccio
## Copyright 2007 Rich Marinaccio
##
## This map script for Civ4 generates a random, earth-like map, usually with a
## 'New World' with no starting locations that can only be reached with
## ocean going technology. Though great pains are taken to accurately simulate
## landforms and climate, the goal must be to make unpredictible, beautiful
## looking maps that are fun to play on.
## 
## -- Summary of creation process: --
## First, a random heightfield is created using midpoint displacement. The
## resulting altitudes are then modified by a plate tectonics scheme that
## grows random plates and raises the altitudes near the plate borders to
## create mountain ranges and island chains.
##
## In generating the plot types from a heightmap, I had found that using
## peaks for high altitude and land for less altitude created large clusters
## of peaks, surrounded by a donut of hills, surrounded again by a donut of
## land. This looked absolutely terrible for Civ, so I made it such that
## peaks and hills are determined by altitude *differences* rather than by
## absolute altitude. This approach looks much better and more natural.
##
## The terrain generator gives the other needed visual cues to communicate
## altitude. Since air temperature gets colder with altitude, the peaks will
## be plots of ice and tundra, even near the equator, if the altitude
## is high enough. Prevailing winds, temperature and rainfall are all simulated
## in the terrain generator. You will notice that the deserts and rainforests
## are where they should be, as well as rain shadows behind mountain ranges.
##
## Rivers and lakes are also generated from the heightmap and follow accurate
## drainage paths, although with such a small heightmap some randomness needs
## to be thrown in to prevent rivers from being merely straight lines.
##
## Map bonuses are placed following the XML Rules but slightly differently than
## the default implimentation to better accomodate this map script.
##
## I've always felt that the most satisfying civ games are the ones that
## provide a use for those explorers and caravels. Though the map generator
## does not explicitly create a 'New World', it will take advantage of any
## continents that can serve that purpose. No starting locations will be placed
## on these continents. Therefore, the likelyhood of a significant new world
## is very high, but not guaranteed. It might also come in the form of multiple
## smaller 'New Worlds' rather than a large continent.
##
##############################################################################
## Version History
## 2.06 - Fixed a few bugs from my minimum hill/maximum bad feature function.
##
## 2.05 - Made maps of standard size and below a bit smaller. Changed the way I
## remove jungle to prevent excessive health problems. Tiles in FC on different
## continents have zero value. Tiles on different continents will not be boosted
## with resources or hills. Water tiles have zero value for non-coastal cities.
## Water tiles will not be boosted with resources for non-coastal cities, land
## tiles will be boosted instead. (lookout Sid's Sushi!)
##
## 2.04 - Changed many percent values to be a percent of land tiles rather than
## total map tiles for easier, more predictable adjustment. Ensured a minimum
## number of hills in a starting fat cross. Disabled the normalizeRemovePeaks
## function a replaced it with a maximum peaks in FC function. Added bonus
## resources to FC depending on player handicap. Added a value bonus for cities
## placed on river sides.
##
## 2.03 - Fixed an initialization problem related to Blue Marble. Added some
## enhanced error handling to help me track down some of the intermittant bugs
## that still remain.
##
## 2.02 - Fixed some problems with monsoons that were creating strange artifacts
## near the tropics. Added an exponential curve to heat loss due to altitude, so
## that jungles can appear more readily without crawling to inappropriate
## latitudes.
##
## 2.01 - Changed the way I handled a vanilla version difference. Added toroidal
## and flat map options. Made tree amount more easily adjustable. Added a variable to
## tune the level of resource bonuses. Changed the rules for fixing tundra/ice next
## to desert. Added altitude noise to the plate map to improve island chains. Added
## a variable to control heat loss due to high altitude. Implimented a new interleaved
## bonus placement scheme so that bonuses are placed individually in random order,
## rather than all of each bonus type at once. Brought back the meteor code from
## PerfectWorld 1 and eliminated the east/west continent divide.
##
## 2.0 - Rebuilt the landmass and climate model using the FaireWeather.py for
## Colonization map script engine. Improved the river system. Fixed some
## old bugs.
##
## 1.13 - Fixed a bug where starting on a goody hut would crash the game.
## Prevented start plots from being on mountain peaks. Changed an internal
## distance calculation from a straight line to a path distance, improving
## start locations somewhat. Created a new tuning variable called
## DesertLowTemp. Since deserts in civ are intended to be hot deserts, this
## variable will prevent deserts from appearing near the poles where the
## desert texture clashes horribly with the tundra texture.
##
## 1.12 - Found a small bug in the bonus placer that gave bonuses a minimum
## of zero, this is why duel size maps were having so much trouble.
##
## 1.11 - limited the features mixing with bonuses to forests only. This
## eliminates certain undesireable effects like floodplains being erased by
## or coinciding with oil or incense, or corn appearing in jungle.
##
## 1.10 - Wrapped all map constants into a class to avoid all those
## variables being loaded up when PW is not used. Also this makes it a
## little easier to change them programatically. Added two in-game options,
## New World Rules and Pangaea Rules. Added a tuning variable that allows
## bonuses with a tech requirement to co-exist with features, so that the
## absence of those features does not give away their location.
##
## 1.09 - Fixed a starting placement bug introduced in 1.07. Added a tuning
## variable to turn off 'New world' placement.
##
## 1.08 - Removed the hemispheres logic and replaced it with a simulated meteor
## shower to break up pangeas. Added a tuning variable to allow pangeas.
##
## 1.07 - Placing lakes and harbors after river placement was not updating river
## crossings. Resetting rivers after lake placement should solve this. Fixed a
## small discrepancy between Python randint and mapRand to make them behave the
## same way. Bonuses of the same bonus class, when forced to appear on the
## same continent, were sometimes crowding each other off the map. This was
## especially problematic on the smaller maps. I added some additional, less
## restrictive, passes to ensure that every resource has at least one placement
## unless the random factors decide that none should be placed. Starting plot
## normalization now will place food if a different bonus can not be used due
## to lack of food. Changed heightmap generation to more likely create a
## new world.
##
## 1.06 - Overhauled starting positions and resource placement to better
## suit the peculiarities of PerfectWorld
##
## 1.05 - Fixed the Mac bug and the multi-player bug.
##
## 1.04a - I had unfairly slandered getMapRand in my comments. I had stated
## that the period was shortened unnecessarily, which is not the case.
##
## 1.04 - Added and option to use the superior Python random number generator
## or the getMapRand that civ uses. Made the number of rivers generated tunable.
## Fixed a bug that prevented floodplains on river corners. Made floodplains
## in desert tunable.
##
## 1.03a - very minor change in hope of finding the source of a multi-player
## glitch.
##
## 1.03 - Improved lake generation. Added tuning variables to control some
## new features. Fixed some minor bugs involving the Areamap filler
## and fixed the issue with oasis appearing on lakes. Maps will now report
## the random seed value that was used to create them, so they can be easily
## re-created for debugging purposes.
##
## 1.02 - Fixed a bug that miscalculated the random placing of deserts. This
## also necessitated a readjustment of the default settings.
##
## 1.01 - Added global tuning variables for easier customization. Fixed a few
## bugs that caused deserts to get out of control.
##

# Class RadioGatun32 is under different copyright:
# Copyright (c) 2012-2017 Sam Trenholme
#
# TERMS
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
#
# This software is provided 'as is' with no guarantees of correctness or
# fitness for purpose.

# This is a Python implementation of RadioGatun32.  It takes about 10
# seconds to set up the RNG, then it can output approximately
# 30,000 16-bit random numbers per second on a Core i5-2430M

# There is another open-source Python RadioGatun implementation here:
# https://github.com/doegox/python-cryptoplus

# I would like to thank Lorenzo for his suggestion to use xrange to speed up
# the program

# Since range is too slow in Python2, we do this to make the code run in
# Python2 and Python3
try:
    xrange
except:
    xrange = range

class RadioGatun32:
        def __init__(self, m):
                self.wordsize = int(32)
                self.millsize = int(19)
                self.beltrows = 3
                self.beltcol = 13
                self.beltfeed = 12
                self.mask = 0xffffffff # 32-bit
                self.index = 0
                (self.a, self.b) = self.seed(str(m))
        def mill(self,a):
                aa = []
                for g in xrange(self.millsize):
                        aa.append(0)
                x = 0
                i = 0
                y = 0
                r = 0
                z = 0
                for i in xrange(self.millsize):
                        y = (i * 7) % self.millsize
                        r = int(((i * (i + 1)) / 2)) % self.wordsize
                        x = a[y] ^ (a[ ((y + 1) % self.millsize) ] |
                            (a[ ((y + 2) % self.millsize) ] ^ self.mask))
                        aa[i] = ((x >> r) | (x <<(self.wordsize - r))
                                 & self.mask)
                for i in xrange(self.millsize):
                        y = i
                        r = (i + 1) % self.millsize
                        z = (i + 4) % self.millsize
                        a[i] = aa[y] ^ aa[r] ^ aa[z]
                a[0] ^= 1
                return a
        def belt(self,a,b):
                q = []
                for g in xrange(self.beltrows):
                        q.append(0)
                s = 0
                i = 0
                v = 0
                for s in xrange(self.beltrows):
                        q[s] = b[((s * self.beltcol) + self.beltcol - 1)]
                i = self.beltcol - 1
                while i > 0:
                        for s in xrange(self.beltrows):
                                v = i - 1
                                if v < 0:
                                        v = self.beltcol - 1
                                b[((s * self.beltcol) + i)] = (
                                        b[((s * self.beltcol) + v)])
                        i -= 1
                for s in xrange(self.beltrows):
                        b[(s * self.beltcol)] = q[s]
                for i in xrange(self.beltfeed):
                        s = (i + 1) + ((i % self.beltrows) * self.beltcol)
                        b[s] ^= a[(i + 1)]
                a = self.mill(a)
                for i in xrange(self.beltrows):
                        a[(i + self.beltcol)] ^= q[i]
                return (a, b)
        def seed(self,m):
                p = []
                for g in xrange(3):
                        p.append(0)
                q = 0
                c = 0
                r = 0
                done = 0
                index = 0
                counter = 0
                a = []
                b = []
                for g in xrange(self.millsize):
                        a.append(0)
                for g in xrange(self.beltrows * self.beltcol):
                        b.append(0)
                for counter in xrange(16777218): # Infinite loop protection
                        p[0] = p[1] = p[2] = 0
                        for r in xrange(3):
                                q = 0
                                while q < self.wordsize:
                                        x = 0
                                        try:
                                                x = ord(m[index])
                                        except:
                                                x = 1
                                        index += 1
                                        if(index > len(m)):
                                                done = 1
                                                x = 1
                                        p[r] |= x << q
                                        if done == 1:
                                                for c in xrange(3):
                                                        b[c * 13] ^= p[c]
                                                        a[16 + c] ^= p[c]
                                                (a,b) = self.belt(a,b)
                                                for c in xrange(16):
                                                        (a,b) = self.belt(a,b)
                                                return (a,b)
                                        q += 8
                        for c in xrange(3):
                                b[c * 13] ^= p[c]
                                a[16 + c] ^= p[c]
                        (a,b) = self.belt(a,b)
                return (a,b) # We should never get here
        # Return 16-bit random integer (between 0 and 65535)
        def rng16(self):
                if (self.index % 4) == 0:
                        (self.a, self.b) = self.belt(self.a, self.b)
                        self.index += 1
                        return (((self.a[1] & 0xff) << 8) |
                                 ((self.a[1] & 0xff00) >> 8))
                self.index += 1
                if (self.index % 4) == 2:
                        return(((self.a[1] & 0xff0000) >> 8) |
                                ((self.a[1] & 0xff000000) >> 24))
                elif (self.index % 4) == 3:
                        return(((self.a[2] & 0xff) << 8) |
                                ((self.a[2] & 0xff00) >> 8))
                elif (self.index % 4) == 0:
                        return(((self.a[2] & 0xff0000) >> 8) |
                                ((self.a[2] & 0xff000000) >> 24))
                else: # Should never get here
                        return -1
        # Return 32-bit random integer
        def rng32(self):
                if(self.index & 1):
                        self.index += 1
                self.index &= 2
                if(self.index):
                        self.index = 0
                        return (((self.a[2] & 0xff) << 24) |
                                ((self.a[2] & 0xff000000) >> 24) |
                                ((self.a[2] & 0xff00) << 8) |
                                ((self.a[2] & 0xff0000) >> 8))
                (self.a, self.b) = self.belt(self.a, self.b)
                self.index = 2
                return (((self.a[1] & 0xff) << 24) |
                        ((self.a[1] & 0xff000000) >> 24) |
                        ((self.a[1] & 0xff00) << 8) |
                        ((self.a[1] & 0xff0000) >> 8))
        # Return 64-bit random integer
        def rng64(self):
                left = self.rng32()
                right = self.rng32()
                return ((left << 32) | right)
        # Return number between 0 (can be 0) and 1 (can be slightly smaller
        # than 1 but never 1)
        def random(self):
                return float(self.rng64()) / 18446744073709551616
        # Return a number between a and b
        def randint(self, low, high):
                if(low == high):
                        return low
                if(high < low):
                        swap = low
                        low = high
                        high = swap
                range = 1 + high - low
                # For low ranges, we can use 16-bit ints to get number
                if(range <= 10000):
                        max = 65536 - (65536 % range)
                        number = max
                        while number >= max:
                                number = self.rng16()
                        return low + (number % range)
                # int() returns the floor, e.g. int(1.99999) returns 1
                return int(low + (self.random() * range))

def do_rg32_test(testInput):
    # 16 16-bit numbers
    rg32test = RadioGatun32(testInput)
    line = "16-bit:    "
    for a in range(16):
        line += ("%04x" % (rg32test.rng16()))
    print(line)
    # 8 32-bit numbers
    rg32test = RadioGatun32(testInput)
    line = "32-bit:    "
    for a in range(8):
        line += ("%08x" % (rg32test.rng32()))
    print(line)
    # 4 64-bit numbers
    rg32test = RadioGatun32(testInput)
    line = "64-bit:    "
    for a in range(4):
        line += ("%016x" % (rg32test.rng64()))
    print(line)
    # 16-bit then 32-bit
    rg32test = RadioGatun32(testInput)
    line = "16/32 bit: "
    for a in range(4):
        line += ("%04x" % (rg32test.rng16()))
        line += "----"
        line += ("%08x" % (rg32test.rng32()))
    print(line)
    # 32-bit then 16-bit
    rg32test = RadioGatun32(testInput)
    line = "32/16 bit: "
    for a in range(4):
        line += ("%08x" % (rg32test.rng32()))
        line += ("%04x" % (rg32test.rng16()))
        line += "----"
    print(line)
    # Mix it up (16,16,32,64,64,32,16,16)
    rg32test = RadioGatun32(testInput)
    line = "Mix it up: "
    line += ("%04x" % (rg32test.rng16()))
    line += ("%04x" % (rg32test.rng16()))
    line += ("%08x" % (rg32test.rng32()))
    line += ("%016x" % (rg32test.rng64()))
    line += ("%016x" % (rg32test.rng64()))
    line += ("%08x" % (rg32test.rng32()))
    line += ("%04x" % (rg32test.rng16()))
    line += ("%04x" % (rg32test.rng16()))
    print(line)

##### END BSD LICENSED CODE ##############################################

if __name__ != "__main__":
    from CvPythonExtensions import *
    import CvUtil
    import CvMapGeneratorUtil 

from array import array
from random import random,randint,seed
import math
import sys
import time
import os

class MapConstants :
    def __init__(self):
        return
    def initialize(self):
        print "Initializing map constants"
##############################################################################
## GLOBAL TUNING VARIABLES: Change these to customize the map results
       
        gc = CyGlobalContext()
        mmap = gc.getMap()

        # Default seed
        self.randomSeed = 0

        #Percent of land vs. water
        self.landPercent = 0.29
        
        #If this variable is set to False, a shower of colossal meteors will attempt to
        #break up any pangea-like continents. Setting this variable to True will allow
        #pangeas to sometimes occur and should be greatly favored by any dinosaurs
        #that might be living on this planet at the time.
        self.AllowPangeas = False

        #This variable can be used to turn off 'New world' logic and place starting
        #positions anywhere in the world. For some mods, a new world doesn't make
        #sense.
        self.AllowNewWorld = True
        self.ShareContinent = False
        self.ShareContinentIndex = 1
        
        #How many land squares will be above peak threshold and thus 'peaks'.
        self.PeakPercent = 0.12

        #How many land squares will be above hill threshold and thus 'hills' unless
        #they are also above peak threshold in which case they will be 'peaks'.
        self.HillPercent = 0.35

        #In addition to the relative peak and hill generation, there is also a
        #process that changes flats to hills or peaks based on altitude. This tends
        #to randomize the high altitude areas somewhat and improve their appearance.
        #These variables control the frequency of hills and peaks at the highest altitude.
        self.HillChanceAtOne = .50
        self.PeakChanceAtOne = .27

        #How many land squares will be below desert rainfall threshold. In this case,
        #rain levels close to zero are very likely to be desert, while rain levels close
        #to the desert threshold will more likely be plains.
        self.DesertPercent = 0.20

        #How many land squares will be below plains rainfall threshold. Rain levels close
        #to the desert threshold are likely to be plains, while those close to the plains
        #threshold are likely to be grassland. 
        self.PlainsPercent = 0.42
        
        #---The following variables are not based on percentages. Because temperature
        #---is so strongly tied to latitude, using percentages for things like ice and
        #---tundra leads to very strange results if most of the worlds land lies near
        #---the equator

        #What temperature will be considered cold enough to be ice. Temperatures range
        #from coldest 0.0 to hottest 1.0.
        self.SnowTemp = .30

        #What temperature will be considered cold enough to be tundra. Temperatures range
        #from coldest 0.0 to hottest 1.0.
        self.TundraTemp = .35

        #Hotter than this temperature will be considered deciduous forest, colder will
        #be evergreen forest.Temperatures range from coldest 0.0 to hottest 1.0.
        self.ForestTemp = .50

        #What temperature will be considered hot enough to be jungle. Temperatures range
        #from coldest 0.0 to hottest 1.0.
        self.JungleTemp = .7

        #Sets the threshold for jungle rainfall by modifying the plains threshold by this factor.
        self.TreeFactor = 1.5

        #This is the maximum chance for a tree to be placed when rainfall is above jungle level.
        #use a value between 0.0 and 1.0
        self.MaxTreeChance = 1.0

        #This variable adjusts the amount of bonuses on the map. Values above 1.0 will add bonus
        #bonuses. People often want lots of bonuses, and for those people, this variable is definately
        #a bonus.
        self.BonusBonus = 1.0
        # This determines if we use Perfect World's way of spreading
        # resources (False), or use a more normal resource distribution
        self.spreadResources = False
        
        #How many squares are added to a lake for each unit of drainage flowing
        #into it.
        self.LakeSizePerDrainage = 14.0

        #This value modifies LakeSizePerRiverLength when a lake begins in desert
        self.DesertLakeModifier = .60

        #This value controls the amount of siltification in lakes
        self.maxSiltPanSize = 200

        #This value controls the number of mid-altitude lake depressions per
        #map square. It will become a lake if enough water flows into the
        #depression.
        self.numberOfLakesPerPlot = 0.003

        #This value sets the minimum altitude of lake depressions. They
        #generally look better higher up.
        self.minLakeAltitude = 0.45
                
        #This value is used to decide if enough water has accumulated to form a river.
        #A lower value creates more rivers over the entire map.
        self.RiverThreshold = 4
        
        #The percent chance that an oasis may appear in desert. A tile must be desert and
        #surrounded on all sides by desert.
        self.OasisChance = .08

        #This sets the amount of heat lost at the highest altitude. 1.0 loses all heat
        #0.0 loses no heat.
        self.heatLostAtOne = 1.0
        
        #This value is an exponent that controls the curve associated with
        #temperature loss. Higher values create a steeper curve.
        self.temperatureLossCurve = 1.3
        
        #Degrees latitude for the top and bottom of the map. This allows
        #for more specific climate zones
        self.topLatitude = 90
        self.bottomLatitude = -90

        #Horse latitudes and polar fronts plus and minus in case you
        #want some zones to be compressed or emphasized.
        self.horseLatitude = 30
        self.polarFrontLatitude = 60

        #Tropics of Cancer and Capricorn plus and minus respectively
        self.tropicsLatitude = 23

        #Oceans are slow to gain and lose heat, so the max and min temps
        #are reduced and raised by this much.
        self.oceanTempClamp = .10

        #Minimum amount of rain dropped by default before other factors
        #add to the amount of rain dropped
        self.minimumRainCost = 0.01

        #Strength of geostrophic rainfall versus monsoon rainfall
        self.geostrophicFactor = 6.0

        #Monsoon uplift factor. This value is an ajustment so that monsoon uplift
        #matches geostrophic uplift.
        self.monsoonUplift = 500.0
        
        #Height and Width of main climate and height maps. This does not
        #reflect the resulting map size. Both dimensions( + 1 if wrapping in
        #that dimension = False) must be evenly divisble by self.hmMaxGrain
        # Note: The bigger map option may rewrite these values (see below)
        self.hmWidth = 144
        self.hmHeight = 97

        #Controls wrapping (not sure if this makes sense yet)
        self.WrapX = True
        self.WrapY = False
        
        #Size of largest map increment to begin midpoint displacement. Must
        #be a power of 2.
        self.hmMaxGrain = 16

        #Option to divide map into two continents as far as the midpoint
        #displacement is concerned. For guaranteed continent separation, further
        #steps will be needed but this option will cause more ocean in the
        #middle of the map. The possible choices are 0 = NO_SEPARATION,
        #1 = NORTH_SOUTH_SEPARATION and 2 = EAST_WEST_SEPARATION.
        self.hmSeparation = 0

        #Creates a water margin around the map edges. 
        self.northMargin = False
        self.southMargin = False
        self.eastMargin = False
        self.westMargin = False

        #If you sink the margins all the way to 0.0, they become too obvious.
        #This variable sets the maximum amount of sinking
        self.hmMarginDepth = 0.60

        #Margin of ocean around map edge when not wrapping and also through
        #middle when using separation.
        self.hmGrainMargin = 2

        #These are not mountain peaks, but points on the height map initialized
        #to 1.0 before the midpoint displacement process begins. This sets the
        #percentage of 'peaks' for points that are not on the grain margin.
        self.hmInitialPeakPercent = 0.30
        
        #Scales the heuristic for random midpoint displacement. A higher number
        #will create more noise(bumpy), a smaller number will make less
        #noise(smooth).
        self.hmNoiseLevel = 2.0

        #Number of tectonic plates
        self.hmNumberOfPlates = int(float(self.hmWidth * self.hmHeight) * 0.0016)

        #Influence of the plate map, or how much of it is added to the height map.
        self.plateMapScale = 1.1

        #Minimun distance from one plate seed to another
        self.minSeedRange = 15

        #Minimum distance from a plate seed to edge of map
        self.minEdgeRange = 5

        #Chance for plates to grow. Higher chance tends to make more regular
        #shapes. Lower chance makes more irregular shapes and takes longer.
        self.plateGrowthChanceX = 0.3
        self.plateGrowthChanceY = 0.3

        #This sets the amount that tectonic plates differ in altitude.
        self.plateStagger = 0.1

        #This sets the max amount a plate can be staggered up to on the heightmap
        self.plateStaggerRange = 1.0

        #This is the chance for a plate to sink into the water when it is on map edge
        self.chanceForWaterEdgePlate = 0.45
        
        #This is the frequency of the cosine ripple near plate boundaries.
        self.rippleFrequency = 0.5

        #This is the amplitude of the ripples near plate boundaries.
        self.rippleAmplitude = 0.75

        #This is the amount of noise added to the plate map.
        self.plateNoiseFactor = 1.2

        #Filter size for temperature smoothing. Must be odd number
        self.filterSize = 15

        #Filter size for altitude smoothing and distance finding. Must be
        #odd number
        self.distanceFilterSize = 5

        #It is necessary to eliminate small inland lakes during the initial
        #heightmap generation. Keep in mind this number is in relation to
        #the initial large heightmap (mc.hmWidth, mc.hmHeight) before the
        #shrinking process
        self.minInlandSeaSize = 100
        
        #After generating the heightmap, bands of ocean can be added to the map
        #to allow a more consistent climate generation. These bands are useful
        #if you are generating part of a world where the weather might be coming
        #in from off the map. These bands can be kept if needed or cropped off
        #later in the process.
        self.northWaterBand = 10
        self.southWaterBand = 10
        self.eastWaterBand = 0
        self.westWaterBand = 0

        #These variables are intended for use with the above water band variables
        #but you can crop the map edge after climate generation for any reason.
        self.northCrop = 10
        self.southCrop = 10
        self.eastCrop = 0
        self.westCrop = 0

        #Too many meteors will simply destroy the Earth, and just
        #in case the meteor shower can't break the pangaea, this will also
        #prevent and endless loop.
        self.maximumMeteorCount = 15
        
        #Minimum size for a meteor strike that attemps to break pangaeas.
        #Don't bother to change this it will be overwritten depending on
        #map size.
        self.minimumMeteorSize = 6      
        
        #---These values are for evaluating starting locations
        
        #Minimum number of hills in fat cross
        self.MinHillsInFC = 2

        #Max number of peaks in fat cross
        self.MaxPeaksInFC = 3

        #Max number of bad features(jungle) in fat cross
        self.MaxBadFeaturesInFC = 4

        #The following values are used for assigning starting locations. For now,
        #they have the same ratio that is found in CvPlot::getFoundValue
        self.CommerceValue = 20
        self.ProductionValue = 40
        self.FoodValue = 10

        #Coastal cities are important, how important is determined by this
        #value.
        self.CoastalCityValueBonus = 1.3

        #River side cities are also important, how important is determined by this
        #value.
        self.RiverCityValueBonus = 1.2
       
        handicap = mmap.getCustomMapOption(2)
        #Bonus resources to add depending on difficulty settings
        self.SettlerBonus = handicap
        self.ChieftainBonus = handicap 
        self.WarlordBonus = handicap
        self.NobleBonus = handicap
        self.PrinceBonus = handicap
        self.MonarchBonus = handicap
        self.EmperorBonus = handicap 
        self.ImmortalBonus = handicap
        self.DeityBonus = handicap
        
        #Decides whether to use the Python random generator or the one that is
        #intended for use with civ maps. The Python random has much higher precision
        #than the civ one. 53 bits for Python result versus 16 for getMapRand. The
        #rand they use is actually 32 bits, but they shorten the result to 16 bits.
        #However, the problem with using the Python random is that it may create
        #syncing issues for multi-player now or in the future, therefore it must
        #be optional.
        self.UsePythonRandom = True        
    
        # T2 change: Add the ability to select climate
        self.iceChance = 1.0 # Chance of having iceberg at top/bottom of map
        self.iceRange = 4 # Number of squares we add icebergs to
        self.iceSlope = 0.66 # How quickly we reduce icebergs
        #clim = mmap.getClimate()
        clim = 2 # Only Arid because this is for Arabian maps
        if clim == 1: # Tropical
            self.tropicsLatitude = 46
            # q3max changes
            self.DesertPercent = .10 # added
            self.PlainsPercent = .30 # added
            self.SnowTemp = .20 # added
            self.TundraTemp = .30 # added
            self.ForestTemp = .35 # added
            self.JungleTemp = .50 # added
            # End q3max changes
            self.iceSlope = 0.33 # Less ice
        elif clim == 2: # Arid
            self.DesertPercent = 0.40
            self.PlainsPercent = 0.82
            self.iceSlope = 0.33 # Less ice
        elif clim == 3: # Rocky
            self.PeakPercent = 0.24
            self.HillPercent = 0.70
            self.HillChanceAtOne = 0.70
            self.PeakChanceAtOne = 0.43
            self.iceSlope = 0.75 # Some more ice
            self.iceRange = 6
        elif clim == 4: # Cold
            self.tropicsLatitude = 0
            self.SnowTemp = .50
            self.TundraTemp = .75
            self.ForestTemp = .85
            self.JungleTemp = .99
            self.iceRange = 12
            self.iceChance = 1.2
            self.iceSlope = 0.87 # Lots of ice

        #Below here are static defines. If you change these, the map won't work.
        #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        self.L = 0
        self.N = 1
        self.S = 2
        self.E = 3
        self.W = 4
        self.NE = 5
        self.NW = 6
        self.SE = 7
        self.SW = 8

        self.NO_SEPARATION = 0
        self.NORTH_SOUTH_SEPARATION = 1
        self.EAST_WEST_SEPARATION = 2

        self.width = 104
        self.height = 64

        self.OCEAN = 0
        self.LAND = 1
        self.HILLS = 2
        self.PEAK = 3

        self.OCEAN = 0
        self.COAST = 1
        self.MARSH = 2
        self.GRASS = 3
        self.PLAINS = 4
        self.DESERT = 5
        self.TUNDRA = 6
        self.SNOW = 7

        self.minimumLandInChoke = 0.5

        return
    
    def initInGameOptions(self):
        gc = CyGlobalContext()
        mmap = gc.getMap()
        #New World Rules
        #selectionID = mmap.getCustomMapOption(0)
        selectionID = 2
        if selectionID == 1:
            self.AllowNewWorld = not self.AllowNewWorld
        if selectionID == 2: # Everyone on same landmass (largest)
            self.AllowNewWorld = True
            self.ShareContinent = True
        if selectionID == 3: # Everyone on same landmass (second largest)
            self.AllowNewWorld = True
            self.ShareContinent = True
            self.ShareContinentIndex = 2
        #Pangaea Rules
        selectionID = mmap.getCustomMapOption(1)
        selectionID = 0 # Pangeas not allowed
        if selectionID == 1:
            self.AllowPangeas = not self.AllowPangeas

        # Bigger maps option
        #selectionID = mmap.getCustomMapOption(4)
        selectionID = 0 # Always 144 x 96
        # Default size is 144 wide, 97 tall
        if selectionID == 1: # Big maps
            self.hmHeight = 129
            self.hmWidth = 192
        elif selectionID == 2: # Small maps
            self.hmHeight = 65
            self.hmWidth = 96
            self.hmNumberOfPlates = (int(
                     float(self.hmWidth * self.hmHeight) * 0.0016))

        #Wrap options
        #selectionID = mmap.getCustomMapOption(2)
        selectionID = 0 # Cylindrical, always
        wrapString = "Cylindrical"
        if selectionID == 1: #Toroidal
            self.hmHeight -= 1
            self.WrapY = True
            self.northWaterBand = 0
            self.northCrop = 0
            self.southWaterBand = 0
            self.southCrop = 0
            wrapString = "Toroidal"
            
        elif selectionID == 2: #Flat
            self.hmWidth += 1
            self.WrapX = False
            wrapString = "Flat"
          
        # How we distribute resources
        selectionID = mmap.getCustomMapOption(0)
        if selectionID == 0:
            self.BonusBonus = 1.5 # Increases resources
            self.spreadResources = True
        elif selectionID == 1: # Evenly spaced resources
            self.BonusBonus = 0.7 
            self.spreadResources = True
        elif selectionID == 2: # Like Perfect World
            self.BonusBonus = 1.0 
            self.spreadResources = False
        else:
            self.BonusBonus = 1.5 # Increases resources
            self.spreadResources = True

        # Do we use a fixed or random map seed?
        selectionID = mmap.getCustomMapOption(1)
        if selectionID == 8: # Fixed random seed (plains/desert start)
            self.randomSeed = 36933
        elif selectionID == 4: # Amira
            self.randomSeed = 2997
        elif selectionID == 5: # Caulixtla
            self.randomSeed = -2
        elif selectionID == 6: # Jungle start
            self.randomSeed = 75487
        elif selectionID == 7: # Caulixtla Jungle start
            self.randomSeed = -3
        elif selectionID != 3: # Anything but "Free form"
            # We choose one of many possible Arabian adventures
            localSeedList = []
            if selectionID == 0: # Large (Epic or Marathon)
                for a in range(len(seedList)):
                    if seedList[a][0] >= 1400:
                        localSeedList.append(seedList[a])
            elif selectionID == 1: # Small (Normal or Epic)
                for a in range(len(seedList)):
                    if seedList[a][0] < 1400:
                        localSeedList.append(seedList[a])
            else: # Otherwise, choose any map at random
                localSeedList = seedList
            seedIndex = int(random() * len(localSeedList))
            self.randomSeed = localSeedList[seedIndex][1]

        self.optionsString = "Map Options: \n"
        if self.AllowNewWorld:
            self.optionsString += "AllowNewWorld = true\n"
        else:
            self.optionsString += "AllowNewWorld = false\n"
        if self.AllowPangeas:
            self.optionsString += "AllowPangeas = true\n"
        else:
            self.optionsString += "AllowPangeas = false\n"
        self.optionsString += "Wrap Option = " + wrapString + "\n"

        return
    
mc = MapConstants()

class PythonRandom :
    def __init__(self):
        self.rg32 = RadioGatun32('12345678')
        return
    def seed(self):
        #Python randoms are not usable in network games.
        if mc.UsePythonRandom:
            self.usePR = True
        else:
            self.usePR = False
        if self.usePR and CyGame().isNetworkMultiPlayer():
            print "Detecting network game. Setting UsePythonRandom to False."
            self.usePR = False
        if self.usePR:
            # Python 'long' has unlimited precision, while the random generator
            # has 53 bits of precision, so I'm using a 53 bit integer to seed the map!
            seed() #Start with system time
            seedValue = randint(0,9007199254740991)
            self.rg32 = True
            if mc.randomSeed == 0:
                seedValue = "R"
                seedletter="abcdefghijkl7nopqrstuv8xyz" # No wide letters
                for seedMake in range(12):
                    seedMe = randint(0,25)
                    seedValue += seedletter[seedMe:seedMe+1]
                self.seedString = "Random seed (Using RG32 rand) for this map is " + seedValue
            elif mc.randomSeed == -2 or mc.randomSeed == -3:
                self.rg32 = False
                seed(8939185639133313) # Caulixtla
                seedValue = mc.randomSeed
                self.seedString = "Fixed seed: Caulixtla map"
            else:
                seedValue = "RT" + str(mc.randomSeed)
                self.seedString = "Fixed seed (Using RG32 rand) for this map is " + seedValue
            mc.randomSeed = seedValue
            if self.rg32:
                self.rg32 = RadioGatun32(seedValue)
##            seedValue = 4316490043753041
##            seed(seedValue)
##            self.seedString = "Pre-set seed (Using Pyhon rands) for this map is %(s)20d" % {"s":seedValue}     
        else:
            gc = CyGlobalContext()
            self.mapRand = gc.getGame().getMapRand()
            
            seedValue = self.mapRand.get(65535,"Seeding mapRand - FairWeather.py")
            self.mapRand.init(seedValue)
            self.seedString = "Random seed (Using getMapRand) for this map is %(s)20d" % {"s":seedValue}            
            
##            seedValue = 56870
##            self.mapRand.init(seedValue)
##            self.seedString = "Pre-set seed (Using getMapRand) for this map is %(s)20d" % {"s":seedValue}
            
        #print self.seedString
        return
    def random(self):
        if self.usePR:
            if self.rg32:
                return self.rg32.random()
            else:
                return random()
        else:
            #This formula is identical to the getFloat function in CvRandom. It
            #is not exposed to Python so I have to recreate it.
            fResult = float(self.mapRand.get(65535,"Getting float -FairWeather.py"))/float(65535)
#            print fResult
            return fResult
    def randint(self,rMin,rMax):
        #if rMin and rMax are the same, then return the only option
        if rMin == rMax:
            return rMin
        #returns a number between rMin and rMax inclusive
        if self.usePR:
            if self.rg32:
                return self.rg32.randint(rMin,rMax)
            else:
                return randint(rMin,rMax)
        else:
            #mapRand.get() is not inclusive, so we must make it so
            return rMin + self.mapRand.get(rMax + 1 - rMin,"Getting a randint - FairWeather.py")
#Set up random number system for global access
PRand = PythonRandom()

################################################################################
## Global functions
################################################################################

def errorPopUp(message):
    gc = CyGlobalContext()
    iPlayerNum = 0
    for iPlayer in range(gc.getMAX_PLAYERS()):
        player = gc.getPlayer(iPlayer)
        if player.isAlive():
            iPlayerNum = iPlayerNum + 1
            if player.isHuman():
                text = message + "\n\n" + mc.optionsString + "\n" + PRand.seedString
                popupInfo = CyPopupInfo()
                popupInfo.setButtonPopupType(ButtonPopupTypes.BUTTONPOPUP_PYTHON)
                popupInfo.setText(text)
                popupInfo.setOnClickedPythonCallback("")
                popupInfo.addPythonButton("Ok","")
                popupInfo.addPopup(iPlayer)
                
#This function converts x and y to an index.
def GetIndex(x,y):
    #Check X for wrap
    if mc.WrapX == True:
        xx = x % mc.width
    elif x < 0 or x >= mc.width:
        return -1
    else:
        xx = x
    #Check y for wrap
    if mc.WrapY == True:
        yy = y % mc.height
    elif y < 0 or y >= mc.height:
        return -1
    else:
        yy = y

    i = yy * mc.width + xx
    return i

def GetHmIndex(x,y):
    #Check X for wrap
    if mc.WrapX == True:
        xx = x % mc.hmWidth
    elif x < 0 or x >= mc.hmWidth:
        return -1
    else:
        xx = x
    #Check y for wrap
    if mc.WrapY == True:
        yy = y % mc.hmHeight
    elif y < 0 or y >= mc.hmHeight:
        return -1
    else:
        yy = y

    i = yy * mc.hmWidth + xx
    return i

#Handles arbitrary size
def GetIndexGeneral(x,y,width,height):
    #Check X for wrap
    if mc.WrapX == True:
        xx = x % width
    elif x < 0 or x >= width:
        return -1
    else:
        xx = x
    #Check y for wrap
    if mc.WrapY == True:
        yy = y % height
    elif y < 0 or y >= height:
        return -1
    else:
        yy = y

    i = yy * width + xx
    return i


#This function scales a float map so that all values are between
#0.0 and 1.0.
def NormalizeMap(fMap,width,height):
    #find highest and lowest points
    maxAlt = 0.0
    minAlt = 0.0
    for y in range(height):
        for x in range(width):
            plot = fMap[GetIndexGeneral(x,y,width,height)]
            if plot > maxAlt:
                maxAlt = plot
            if plot < minAlt:
                minAlt = plot
    #normalize map so that all altitudes are between 1 and 0
    #first add minAlt to all values if necessary
    if minAlt < 0.0:
        for y in range(height):
            for x in range(width):
                fMap[GetIndexGeneral(x,y,width,height)] -= minAlt
    #add minAlt to maxAlt also before scaling entire map
    maxAlt -= minAlt
    scaler = 1.0/maxAlt
    for y in range(height):
        for x in range(width):
            fMap[GetIndexGeneral(x,y,width,height)] = fMap[GetIndexGeneral(x,y,width,height)] * scaler              
    return
def ShrinkMap(largeMap,lWidth,lHeight,sWidth,sHeight):
    smallMap = array('d')
    yScale = float(lHeight)/float(sHeight)
    xScale = float(lWidth)/float(sWidth)
    for y in range(sHeight):
        for x in range(sWidth):
##            print "x = %d, y = %d" % (x,y)
            weights = 0.0
            contributors = 0.0
            yyStart = int(y * yScale)
            yyStop = int((y + 1) * yScale)
            if yyStop < ((y + 1) * yScale):
                yyStop += 1
            for yy in range(yyStart,yyStop):
                xxStart = int(x * xScale)
                xxStop = int((x + 1) * xScale)
                if xxStop < ((x + 1) * xScale):
                    xxStop += 1
                for xx in range(xxStart,xxStop):
##                    print "  xx = %d, yy = %d" % (xx,yy)
                    weight = GetWeight(x,y,xx,yy,xScale,yScale)
##                    print "  weight = %f" % weight
                    i = yy * lWidth + xx
##                    print "  i = %d" % i
                    contributor = largeMap[i]
##                    print "  contributer = %f" % contributor
                    weights += weight
                    contributors += weight * contributor
##            print " final height = %f" % (contributors/weights)        
            smallMap.append(contributors/weights)
                    
    return smallMap
def GetWeight(x,y,xx,yy,xScale,yScale):
    xWeight = 1.0
##    print "   xScale = %f" % xScale
##    print "   x * xScale = %f, xx = %f" % ((x * xScale),xx)
    if float(xx) < x * xScale:
##        print "   first"
        xWeight = 1.0 - ((x * xScale) - float(xx))
    elif float(xx + 1) > (x + 1) * xScale:
##        print "   second"
        xWeight = ((x + 1) * xScale) - float(xx)
##    print "   xWeight = %f" % xWeight
        
    yWeight = 1.0
##    print "   yScale = %f" % yScale
##    print "   y * yScale = %f, yy = %f" % ((y * yScale),yy)
    if float(yy) < y * yScale:
##        print "   first"
        yWeight = 1.0 - ((y * yScale) - float(yy))
    elif float(yy + 1) > (y + 1) * yScale:
##        print "   second"
        yWeight = ((y + 1) * yScale) - float(yy)
##    print "   yWeight = %f" % yWeight
        
    return xWeight * yWeight

def CropMap(theMap):
    newMap = array('d')
    for y in range(mc.hmHeight):
        if y < mc.southCrop or y >= mc.hmHeight - mc.northCrop:
            continue
        for x in range(mc.hmWidth):
            if x < mc.westCrop or x >= mc.hmWidth - mc.eastCrop:
                continue
            i = GetHmIndex(x,y)
            newMap.append(theMap[i])
    return newMap

def AngleDifference(a1,a2):
    diff = a1 - a2
    while(diff < -180.0):
        diff += 360.0
    while(diff > 180.0):
        diff -= 360.0
    return diff
def AppendUnique(theList,newItem):
    if IsInList(theList,newItem) == False:
        theList.append(newItem)
    return

def IsInList(theList,newItem):
    itemFound = False
    for item in theList:
        if item == newItem:
            itemFound = True
            break
    return itemFound

def DeleteFromList(theList,oldItem):
    for n in range(len(theList)):
        if theList[n] == oldItem:
            del theList[n]
            break
    return  
    
def ShuffleList(theList):
        preshuffle = list()
        shuffled = list()
        numElements = len(theList)
        for i in range(numElements):
            preshuffle.append(theList[i])
        for i in range(numElements):
                n = PRand.randint(0,len(preshuffle)-1)
                shuffled.append(preshuffle[n])
                del preshuffle[n]
        return shuffled
    
def GetInfoType(string):
	cgc = CyGlobalContext()
	return cgc.getInfoTypeForString(string)
    
def GetDistance(x,y,dx,dy):
    distance = math.sqrt(abs((float(x - dx) * float(x - dx)) + (float(y - dy) * float(y - dy))))
    return distance

def GetOppositeDirection(direction):
    opposite = mc.L
    if direction == mc.N:
        opposite = mc.S
    elif direction == mc.S:
        opposite = mc.N
    elif direction == mc.E:
        opposite = mc.W
    elif direction == mc.W:
        opposite = mc.E
    elif direction == mc.NW:
        opposite = mc.SE
    elif direction == mc.SE:
        opposite = mc.NW
    elif direction == mc.SW:
        opposite = mc.NE
    elif direction == mc.NE:
        opposite = mc.SW
    return opposite

def GetXYFromDirection(x,y,direction):
    xx = x
    yy = y
    if direction == mc.N:
        yy += 1
    elif direction == mc.S:
        yy -= 1
    elif direction == mc.E:
        xx += 1
    elif direction == mc.W:
        xx -= 1
    elif direction == mc.NW:
        yy += 1
        xx -= 1
    elif direction == mc.NE:
        yy += 1
        xx += 1
    elif direction == mc.SW:
        yy -= 1
        xx -= 1
    elif direction == mc.SE:
        yy -= 1
        xx += 1
    return xx,yy    

##This function is a general purpose value tuner. It finds a value that will be greater
##than or less than the desired percent of a whole map within a given tolerance. Map values
##should be between 0 and 1. To exclude parts of the map, set them to value 0.0
def FindValueFromPercent(mmap,width,height,percent,tolerance,greaterThan):
    inTolerance = False
    #to speed things up a little, lets take some time to find the middle value
    #in the dataset and use that to begin our search
    minV = 100.0
    maxV = 0.0
    totalCount = 0
    for i in range(height*width):
        if mmap[i] != 0.0:
            totalCount += 1
            if minV > mmap[i]:
                minV = mmap[i]
            if maxV < mmap[i]:
                maxV = mmap[i]
    mid = (maxV - minV)/2.0 + minV
    overMinCount = 0
    equalMinCount = 0
    for i in range(height*width):
        if mmap[i] > minV:
            overMinCount += 1
        elif mmap[i] == minV:
            equalMinCount += 1
##    print "--------------------------------------------------------------"
##    print "totalCount = %d" % totalCount
##    print "overMinCount = %d" % overMinCount
##    print "equalMinCount = %d" % equalMinCount
##    print "starting threshold = %f" % mid
##    print "desired percent = %f" % percent
##    print "minV = %f, maxV = %f" % (minV,maxV)
    
    threshold = mid
    thresholdChange = mid
    iterations = 0
    lastAdded = False
    while not inTolerance:
        iterations += 1
        if(iterations > 500):
            print "can't find value within tolerance, end value = "
            print "threshold = %f, thresholdChange = %f" % (threshold, thresholdChange)
            break #close enough
        matchCount = 0
        for i in range(height*width):
            if mmap[i] != 0.0:
                if greaterThan == True:
                    if(mmap[i] > threshold):
                        matchCount += 1
                else:
                    if(mmap[i] < threshold):  
                        matchCount += 1
##        print "current threshold = %f" % threshold
##        print "current thresholdChange = %f" % thresholdChange
##        print "matchCount = %d" % matchCount
        currentPercent = float(matchCount)/float(totalCount)
##        print "currentPercent = %f" % currentPercent
        if currentPercent < percent + tolerance and \
           currentPercent > percent - tolerance:
            inTolerance = True
        elif greaterThan == True:
            if currentPercent < percent:
##                print "threshold subtract"
                threshold -= thresholdChange
                if lastAdded:
                    #only cut thresholdChange when direction is changed
                    thresholdChange = thresholdChange/2.0
                lastAdded = False
            else:
##                print "threshold add"
                threshold += thresholdChange
                if not lastAdded:
                    thresholdChange = thresholdChange/2.0
                lastAdded = True
        else:
            if currentPercent > percent:
##                print "threshold subtract"
                threshold -= thresholdChange
                if lastAdded:
                    #only cut thresholdChange when direction is changed
                    thresholdChange = thresholdChange/2.0
                lastAdded = False
            else:
##                print "threshold add"
                threshold += thresholdChange
                if not lastAdded:
                    thresholdChange = thresholdChange/2.0
                lastAdded = True
##        print "--------------"

        #at this point value should be in tolerance or close to it
##    print "^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"
    return threshold
def isWaterMatch(x,y):
    result = hm.isBelowSeaLevel(x,y)
##    print "match function results - x = %d,y = %d,result = %d" % (x,y,result)
    return result

class HeightMap :
    def __init__(self):
        return
    
    def generateHeightMap(self):
        self.heightMap = array('d')
        for i in range(mc.hmWidth * mc.hmHeight):
            self.heightMap.append(0.0)

        self.generateMidpointDisplacement()
        return
    
    def checkMaxGrain(self):
        #hm map dimensions(minus 1 if no wrapping) must be evenly divisible
        #by max grain
        ok = True
        width = mc.hmWidth
        height = mc.hmHeight
        if mc.WrapX == False:
            width -= 1
        if mc.WrapY == False:
            height -= 1
            
        if 0 != width % mc.hmMaxGrain:
            ok = False
        if 0 != height % mc.hmMaxGrain:
            ok = False

        if ok == False:
            raise ValueError, "height map dimesions not divisible by mc.hmMaxGrain. also check wrapping options"
            
        return

    def isPlotOnMargin(self,x,y):
        #first check top and bottom
        if mc.southMargin == True:
            if y < (mc.hmMaxGrain * mc.hmGrainMargin):
                return True
        if mc.northMargin == True:
            if y > (mc.hmHeight - (mc.hmMaxGrain * mc.hmGrainMargin)):
                return True
        #check right and left
        if mc.westMargin == True:
            if x < (mc.hmMaxGrain * mc.hmGrainMargin):
                return True
        if mc.eastMargin == True:
            if x > (mc.hmWidth - (mc.hmMaxGrain * mc.hmGrainMargin)):
                return True

        #now check middle
        if mc.hmSeparation != mc.NO_SEPARATION:
            if mc.hmSeparation == mc.NORTH_SOUTH_SEPARATION:
                dimension = y
                middle = mc.hmHeight/2
            elif mc.hmSeparation == mc.EAST_WEST_SEPARATION:
                dimension = x
                middle = mc.hmWidth/2
            else:
                raise ValueError, "bad hmSeparation type"

            if dimension > middle - (mc.hmMaxGrain * mc.hmGrainMargin) \
            and dimension < middle + (mc.hmMaxGrain * mc.hmGrainMargin):
                return True

        return False
    
    def generateMidpointDisplacement(self):
        self.checkMaxGrain()
        
        #make list of map plots that aren't on margin for each
        #map quadrant. We want to place the initial peaks randomly, but we
        #also want to ensure fairly even distribution so that
        #not all the peaks are on one side of the map. For this purpose
        #we will treat each map quadrant separately.

        peaksNWList = list()
        peaksNEList = list()
        peaksSWList = list()
        peaksSEList = list()
        middleX = mc.hmWidth/2
        middleY = mc.hmHeight/2
        for y in range(0,mc.hmHeight,mc.hmMaxGrain):
            for x in range(0,mc.hmWidth,mc.hmMaxGrain):
                if not self.isPlotOnMargin(x,y):
                    if x < middleX and y < middleY:
                        peaksSWList.append((x,y))
                    elif x >= middleX and y < middleY:
                        peaksSEList.append((x,y))
                    elif x < middleX and y >= middleY:
                        peaksNWList.append((x,y))
                    elif x >= middleX and y >= middleY:
                        peaksNEList.append((x,y))
        #shuffle the lists
        peaksNWList = ShuffleList(peaksNWList)
        peaksNEList = ShuffleList(peaksNEList)
        peaksSWList = ShuffleList(peaksSWList)
        peaksSEList = ShuffleList(peaksSEList)

        #place desired number of peaks in each quadrant
        totalNonMargin = len(peaksNWList)
        totalNonMargin += len(peaksNEList)
        totalNonMargin += len(peaksSWList)
        totalNonMargin += len(peaksSEList)
        
        count = max(1,int(float(totalNonMargin) * mc.hmInitialPeakPercent * 0.25))
        print "peak count = %d" % (count)
        for n in range(count):
            x,y = peaksNWList[n]
            i = GetHmIndex(x,y)
            self.heightMap[i] = 1.0
            print "%d,%d = 1.0" % (x,y)
            
            x,y = peaksNEList[n]
            i = GetHmIndex(x,y)
            self.heightMap[i] = 1.0
            
            x,y = peaksSWList[n]
            i = GetHmIndex(x,y)
            self.heightMap[i] = 1.0
            
            x,y = peaksSEList[n]
            i = GetHmIndex(x,y)
            self.heightMap[i] = 1.0
            
        self.printInitialPeaks()

        #Now use a diamond-square algorithm(sort of) to generate the rest
        currentGrain = float(mc.hmMaxGrain)
        while currentGrain > 1.0:
            #h is scalar for random displacement
            h = (currentGrain/float(mc.hmMaxGrain)) * float(mc.hmNoiseLevel)
            #First do the 'square' pass
            for y in range(0,mc.hmHeight,int(currentGrain)):
                for x in range(0,mc.hmWidth,int(currentGrain)):
                    #on the square pass, GetHmIndex should handle all wrapping needs
                    topLeft = GetHmIndex(x,y)
                    topRight = GetHmIndex(x + int(currentGrain),y)
                    if topRight == -1:
                        continue #this means no wrap in x direction
                    bottomLeft = GetHmIndex(x,y + int(currentGrain))
                    if bottomLeft == -1:
                        continue #this means no wrap in y direction
                    bottomRight = GetHmIndex(x + int(currentGrain),y + int(currentGrain))
                    middle = GetHmIndex(x + int(currentGrain/2.0),y + int(currentGrain/2.0))
                    average = (self.heightMap[topLeft] + self.heightMap[topRight] \
                    + self.heightMap[bottomLeft] + self.heightMap[bottomRight])/4.0
                    displacement = h * PRand.random() - h/2.0
                    self.heightMap[middle] = average + displacement
                    #now add that heuristic to the four points to diminish
                    #artifacts. We don't need this on the diamond pass I don't think
                    displacement = h * PRand.random() - h/2.0
                    self.heightMap[topLeft] += displacement
                    displacement = h * PRand.random() - h/2.0
                    self.heightMap[topRight] += displacement
                    displacement = h * PRand.random() - h/2.0
                    self.heightMap[bottomLeft] += displacement
                    displacement = h * PRand.random() - h/2.0
                    self.heightMap[bottomRight] += displacement
            #Now do the 'diamond' pass, there are two diamonds for each x.
            #Possible wrapping is a big complication on this pass. Sorry!
            for y in range(0,mc.hmHeight,int(currentGrain)):
                for x in range(0,mc.hmWidth,int(currentGrain)):
                    #first do the right facing diamond
                    left = GetHmIndex(x,y)
                    right = GetHmIndex(x + int(currentGrain),y)
                    if right != -1: #if we're off map at this point go to next diamond
                        average = self.heightMap[left] + self.heightMap[right]
                        contributers = 2 #each diamond may have two or three contributers, 2 so far
                        top = GetHmIndex(x + int(currentGrain/2.0),y - int(currentGrain/2.0))
                        if top != -1:
                            contributers += 1
                            average += self.heightMap[top]
                        bottom = GetHmIndex(x + int(currentGrain/2.0),y + int(currentGrain/2.0))
                        if bottom != -1:
                            contributers += 1
                            average += self.heightMap[bottom]
                        average = average/float(contributers)
                        middle = GetHmIndex(x + int(currentGrain/2.0),y)
                        displacement = h * PRand.random() - h/2.0
                        self.heightMap[middle] = average + displacement
                    #now do the down facing diamond
                    top = GetHmIndex(x,y)
                    bottom = GetHmIndex(x,y + int(currentGrain))
                    if bottom != -1:
                        average = self.heightMap[top] + self.heightMap[bottom]
                        contributers = 2
                        right = GetHmIndex(x + int(currentGrain/2.0),y + int(currentGrain/2.0))
                        if right != -1:
                            contributers += 1
                            average += self.heightMap[right]
                        left = GetHmIndex(x - int(currentGrain/2.0),y + int(currentGrain/2.0))
                        if left != -1:
                            contributers += 1
                            average += self.heightMap[left]
                        average = average/float(contributers)
                        middle = GetHmIndex(x,y + int(currentGrain/2.0))
                        displacement = h * PRand.random() - h/2.0
                        self.heightMap[middle] = average + displacement
                        
            currentGrain = currentGrain/2.0

        NormalizeMap(self.heightMap,mc.hmWidth,mc.hmHeight)
        
        return
    
    def performTectonics(self):
        self.plateMap = list()
        borderMap = array('i')#this will help in later distance calculations
        self.plateHeightMap = array('d')
        preSmoothMap = array('d')
        growthPlotList = list()
        plateList = list()
        maxDistance = math.sqrt(pow(float(mc.distanceFilterSize/2),2) + pow(float(mc.distanceFilterSize/2),2))
        #initialize maps
        for y in range(mc.hmHeight):
            for x in range(mc.hmWidth):
                i = GetHmIndex(x,y)
                self.plateMap.append(PlatePlot(0,maxDistance))
                borderMap.append(False)
                self.plateHeightMap.append(0.0)
                preSmoothMap.append(0.0)

        plateList.append(Plate(0,-1,-1))#zero placeholder (very silly I know)
        #seed plates
        for i in range(1,mc.hmNumberOfPlates + 1):
            #first find a random seed point that is not blocked by
            #previous points
            iterations = 0
            while(True):
                iterations += 1
                if iterations > 10000:
                    raise ValueError, "endless loop in region seed placement"
                seedX = PRand.randint(0,mc.hmWidth + 1)
                seedY = PRand.randint(0,mc.hmHeight + 1)
                n = GetHmIndex(seedX,seedY)
                if self.isSeedBlocked(plateList,seedX,seedY) == False:
                    self.plateMap[n].plateID = i
                    plate = Plate(i,seedX,seedY)
                    plateList.append(plate)
                    #Now fill a 3x3 area to insure a minimum region size
                    for direction in range(1,9,1):
                        xx,yy = GetXYFromDirection(seedX,seedY,direction)
                        nn = GetHmIndex(xx,yy)
                        if nn != -1:
                            self.plateMap[nn].plateID = i
                            plot = (xx,yy,i)
                            growthPlotList.append(plot)

                    break
                
##        self.printPlateMap(self.plateMap)
        
        #Now cause the seeds to grow into plates
        iterations = 0
        while(len(growthPlotList) > 0):
            iterations += 1
            if iterations > 200000:
                self.printPlateMap(self.plateMap)
                print "length of growthPlotList = %d" % (len(growthPlotList))
                raise ValueError, "endless loop in plate growth"
            plot = growthPlotList[0]
            roomLeft = False
            for direction in range(1,5,1):
                x,y,plateID = plot
                i = GetHmIndex(x,y)
                xx,yy = GetXYFromDirection(x,y,direction)
                ii = GetHmIndex(xx,yy)
                if ii == -1:
                    plateList[plateID].isOnMapEdge = True
                    continue
                if self.plateMap[ii].plateID != plateID and self.plateMap[ii].plateID != 0:
                    borderMap[i] = True
                    borderMap[ii] = True                   
                elif self.plateMap[ii].plateID == 0:
                    roomLeft = True
                    if direction == mc.N or direction == mc.S:
                        growthChance = mc.plateGrowthChanceY
                    else:
                        growthChance = mc.plateGrowthChanceX
                    if PRand.random() < growthChance:
                        self.plateMap[ii].plateID = plateID
                        newPlot = (xx,yy,plateID)
                        growthPlotList.append(newPlot)
                
                    
            #move plot to the end of the list if room left, otherwise
            #delete it if no room left
            if roomLeft:
                growthPlotList.append(plot)
            del growthPlotList[0]
                            
##        self.printPlateMap(self.plateMap)

        #to balance the map we want at least one plate stagger upward
        #in each quadrant
        NWfound = False
        NEfound = False
        SEfound = False
        SWfound = False
        for plate in plateList:
            if plate.GetQuadrant() == plate.NW and NWfound == False:
                plate.raiseOnly = True
                NWfound = True
            if plate.GetQuadrant() == plate.NE and NEfound == False:
                plate.raiseOnly = True
                NEfound = True
            if plate.GetQuadrant() == plate.SE and SEfound == False:
                plate.raiseOnly = True
                SEfound = True
            if plate.GetQuadrant() == plate.SW and SWfound == False:
                plate.raiseOnly = True
                SWfound = True
        
        #Stagger the plates somewhat to add interest
        steps = int(mc.plateStaggerRange/mc.plateStagger)
        for i in range(0,mc.hmHeight*mc.hmWidth):
            if plateList[self.plateMap[i].plateID].isOnMapEdge and PRand.random() < mc.chanceForWaterEdgePlate:
                preSmoothMap[i] = 0.0
            elif plateList[self.plateMap[i].plateID].raiseOnly:
                preSmoothMap[i] = (float(self.plateMap[i].plateID % steps) * mc.plateStagger)/2.0 + 0.5               
            else:
                preSmoothMap[i] = float(self.plateMap[i].plateID % steps) * mc.plateStagger

##        self.printPreSmoothMap(preSmoothMap)

        #Now smooth the plate height map and create the distance map at the same time
        #Since the algorithm is the same
        for y in range(0,mc.hmHeight):
            for x in range(0,mc.hmWidth):
                contributers = 0
                avg = 0
                i = GetHmIndex(x,y)
                isBorder = False
                if borderMap[i] == True:
                    isBorder = True
                plateID = self.plateMap[i].plateID
                for yy in range(y - mc.distanceFilterSize/2,y + mc.distanceFilterSize/2 + 1,1):
                    for xx in range(x - mc.distanceFilterSize/2,x + mc.distanceFilterSize/2 + 1,1):
                        ii = GetHmIndex(xx,yy)
                        if ii == -1:
                            continue
                        contributers += 1
                        avg += preSmoothMap[ii]
                        if isBorder and plateID != self.plateMap[ii].plateID:
                            distance = math.sqrt(pow(float(y - yy),2) + pow(float(x - xx),2))
                            if distance < self.plateMap[ii].distanceList[plateID]:
                                self.plateMap[ii].distanceList[plateID] = distance
                avg = avg/float(contributers)
                self.plateHeightMap[i] = avg
                
##        self.printPlateHeightMap()
#        self.printDistanceMap(distanceMap,maxDistance)

        #Now add ripple formula to plateHeightMap
        for i in range(mc.hmWidth*mc.hmHeight):
            avgRippleTop = 0.0
            avgRippleBottom = 0.0
            for plateID in range(1,mc.hmNumberOfPlates + 1):
                distanceWeight = maxDistance - self.plateMap[i].distanceList[plateID]
#                print "a1 = %f, a2 = %f" % (plateList[self.plateMap[i].plateID].angle,plateList[plateID].angle)
                if plateList[plateID].seedX < plateList[self.plateMap[i].plateID].seedX:
                    angleDifference = AngleDifference(plateList[self.plateMap[i].plateID].angle,plateList[plateID].angle)
                else:
                    angleDifference = AngleDifference(plateList[plateID].angle,plateList[self.plateMap[i].plateID].angle)
#                print angleDifference
                ripple = (pow(math.cos(mc.rippleFrequency * self.plateMap[i].distanceList[plateID]) * \
                (-self.plateMap[i].distanceList[plateID]/maxDistance + 1),2) + (-self.plateMap[i].distanceList[plateID]/maxDistance + 1)) \
                * mc.rippleAmplitude * math.sin(math.radians(angleDifference))
                avgRippleTop += (ripple * distanceWeight)
                avgRippleBottom += distanceWeight
            if avgRippleBottom == 0.0:
                avgRipple = 0.0
            else:
                avgRipple = avgRippleTop/avgRippleBottom
            self.plateHeightMap[i] += avgRipple - (avgRipple * PRand.random() * mc.plateNoiseFactor)
            
        NormalizeMap(self.plateHeightMap,mc.hmWidth,mc.hmHeight)
##        self.printPlateHeightMap()


    def combineMaps(self):                    
        #Now add plateHeightMap to HeightMap
        for i in range(mc.hmWidth * mc.hmHeight):
            self.heightMap[i] += self.plateHeightMap[i] * mc.plateMapScale

        #depress margins, this time with brute force
        marginSize = mc.hmMaxGrain * mc.hmGrainMargin
        for y in range(mc.hmHeight):
            for x in range(mc.hmWidth):
                i = GetHmIndex(x,y)
                if mc.westMargin == True:
                    if x < marginSize:
                        self.heightMap[i] *= (float(x)/float(marginSize)) * (1.0 - mc.hmMarginDepth) + mc.hmMarginDepth
                if mc.eastMargin == True:
                    if mc.hmWidth - x < marginSize:
                        self.heightMap[i] *= (float(mc.hmWidth - x)/float(marginSize)) * (1.0 - mc.hmMarginDepth) + mc.hmMarginDepth
                if mc.southMargin == True:
                    if y < marginSize:
                        self.heightMap[i] *= (float(y)/float(marginSize)) * (1.0 - mc.hmMarginDepth) + mc.hmMarginDepth
                if mc.northMargin == True:
                    if mc.hmHeight - y < marginSize:
                        self.heightMap[i] *= (float(mc.hmHeight - y)/float(marginSize)) * (1.0 - mc.hmMarginDepth) + mc.hmMarginDepth

                if mc.hmSeparation == mc.NORTH_SOUTH_SEPARATION:
                    difference = abs((mc.hmHeight/2) - y)
                    if difference < marginSize:
                        self.heightMap[i] *= (float(difference)/float(marginSize)) * (1.0 - mc.hmMarginDepth) + mc.hmMarginDepth

                elif mc.hmSeparation == mc.EAST_WEST_SEPARATION:
                    difference = abs((mc.hmWidth/2) - x)
                    if difference < marginSize:
                        self.heightMap[i] *= (float(difference)/float(marginSize)) * (1.0 - mc.hmMarginDepth) + mc.hmMarginDepth
                        
##        #Now lets square the heightmap to simulate erosion
##        for i in range(mc.hmWidth * mc.hmHeight):
##            self.heightMap[i] = self.heightMap[i] * self.heightMap[i]

        NormalizeMap(self.heightMap,mc.hmWidth,mc.hmHeight)

    def addWaterBands(self):
        #validate water bands. Maps that wrap cannot have one in that direction
        if mc.WrapX and (mc.eastWaterBand != 0 or mc.westWaterBand != 0):
            raise ValueError,"east/west water bands cannot be used when wrapping in X direction."
        if mc.WrapY and (mc.northWaterBand != 0 or mc.southWaterBand != 0):
            raise ValueError,"north/south water bands cannot be used when wrapping in Y direction."
        
        newWidth = mc.hmWidth + mc.eastWaterBand + mc.westWaterBand
        newHeight = mc.hmHeight + mc.northWaterBand + mc.southWaterBand
        newHeightMap = array('d')
        for y in range(newHeight):
            for x in range(newWidth):
                oldX = x - mc.westWaterBand
                oldY = y - mc.southWaterBand
#                i = GetIndexGeneral(x,y,newWidth,newHeight)
                ii = GetHmIndex(oldX,oldY)
                if ii == -1:
                    newHeightMap.append(0.0)
                else:
                    newHeightMap.append(self.heightMap[ii])

        mc.hmWidth = newWidth
        mc.hmHeight = newHeight
        self.heightMap = newHeightMap
        
    def calculateSeaLevel(self):
        self.seaLevel = FindValueFromPercent(self.heightMap,mc.hmWidth,mc.hmHeight,mc.landPercent,0.02,True)
        return
    
    def isBelowSeaLevel(self,x,y):
        i = GetHmIndex(x,y)
##        print "heightMap = %f at %d,%d" % (self.heightMap[i],x,y)
##        print "seaLevel = %f" % self.seaLevel
        if self.heightMap[i] < self.seaLevel:
##            print "True"
            return True
##        print "False"
        return False
    
    ## This function returns altitude in relation to sea level with
    ## 0.0 being seaLevel and 1.0 being highest altitude
    def getAltitudeAboveSeaLevel(self,x,y):
        i = GetHmIndex(x,y)
        if i == -1:
            return 0.0
        altitude = self.heightMap[i]
        if altitude < self.seaLevel:
            return 0.0
        altitude = 1.0/(1.0 - self.seaLevel) * (altitude - self.seaLevel)
        return altitude

    def setAltitudeAboveSeaLevel(self,x,y,altitude):
        i = GetHmIndex(x,y)
        if i == -1:
            return
        self.heightMap[i] = ((1.0 - self.seaLevel) * altitude) + self.seaLevel
        
##    def Erode(self):
##        for y in range(mc.hmHeight):
##            for x in range(mc.hmWidth):
##                alt = self.getAltitudeAboveSeaLevel(x,y)
##                if alt > 0:
##                    eroded = pow(alt,mc.erosionPower)
##                    self.setAltitudeAboveSeaLevel(x,y,eroded)
                
    def isSeedBlocked(self,plateList,seedX,seedY):
        for plate in plateList:
            if seedX > plate.seedX - mc.minSeedRange and seedX < plate.seedX + mc.minSeedRange:
                if seedY > plate.seedY - mc.minSeedRange and seedY < plate.seedY + mc.minSeedRange:
                    return True
        #Check for edge
        if seedX < mc.minEdgeRange or seedX >= (mc.hmWidth + 1) - mc.minEdgeRange:
            return True
        if seedY < mc.minEdgeRange or seedY >= (mc.hmHeight + 1) - mc.minEdgeRange:
            return True
        return False
    def GetInfluFromDistance(self,sinkValue,peakValue,searchRadius,distance):
        influence = peakValue
        maxDistance = math.sqrt(pow(float(searchRadius),2) + pow(float(searchRadius),2))
        #minDistance = 1.0
        influence -= ((peakValue - sinkValue)* (distance - 1.0))/(maxDistance - 1.0)
        return influence
    def FindDistanceToPlateBoundary(self,x,y,searchRadius):
        minDistance = 10.0
        i = self.GetIndex(x,y)
        for yy in range(y - searchRadius,y + searchRadius):
            for xx in range(x - searchRadius,x + searchRadius):
                ii = self.GetIndex(xx,yy)
                if self.plateMap[i] != self.plateMap[ii]:
                    distance = math.sqrt(pow(float(xx-x),2) + pow(float(yy-y),2))
                    if distance < minDistance:
                        minDistance = distance
                           
        if minDistance == 10.0:
            return 0.0
        
        return minDistance
    
    def fillInLakes(self):
        #smaller lakes need to be filled in for now. The river system will
        #most likely recreate them later due to drainage calculation
        #according to certain rules. This makes the lakes look much better
        #and more sensible.
        am = Areamap(mc.hmWidth,mc.hmHeight,True,True)
        am.defineAreas(isWaterMatch)
##        am.PrintAreaMap()
        oceanID = am.getOceanID()
        for y in range(mc.hmHeight):
            for x in range(mc.hmWidth):
                i = GetHmIndex(x,y)
                if self.isBelowSeaLevel(x,y) and am.areaMap[i] != oceanID:
                    #check the size of this body of water, if too small,
                    #change to land
                    for a in am.areaList:
                        if a.ID == am.areaMap[i] and a.size < mc.minInlandSeaSize:
                            self.heightMap[i] = self.seaLevel
        
        return
    
    def printInitialPeaks(self):
        lineString = "midpoint displacement peaks and margins"
        print lineString
        if not mc.WrapY:
            adjustedHeight = mc.hmHeight - 1
        else:
            adjustedHeight = mc.hmHeight - mc.hmMaxGrain
        for y in range(adjustedHeight,-1,-mc.hmMaxGrain):
            lineString = ""
            for x in range(0,mc.hmWidth,mc.hmMaxGrain):
                i = GetHmIndex(x,y)
                if self.isPlotOnMargin(x,y):
                    lineString += "*"
                elif self.heightMap[i] == 1.0:
                    lineString += "1"
                elif self.heightMap[i] == 0.0:
                    lineString += "0"
            print lineString
        lineString = " "
        print lineString
        
    def printHeightMap(self):
        lineString = "Height Map"
        print lineString
        for y in range(mc.hmHeight - 1,-1,-1):
            lineString = ""
            for x in range(0,mc.hmWidth,1):
                i = GetHmIndex(x,y)
                mapLoc = int((self.heightMap[i] - self.seaLevel)/(1.0 - self.seaLevel) * 10)
                #mapLoc = int(self.heightMap[i] * 10)
                if self.heightMap[i] < self.seaLevel:
                    lineString += '.'
                else:
                    lineString += chr(mapLoc + 48)
            print lineString
        lineString = " "
        print lineString
        
    def printPlateMap(self,plateMap):
        lineString = "Plate Map"
        print lineString
        for y in range(mc.hmHeight - 1,-1,-1):
            lineString = ""
            for x in range(0,mc.hmWidth,1):
                i = GetHmIndex(x,y)
                mapLoc = plateMap[i].plateID
                if mapLoc > 40:
                    mapLoc = 41
                lineString += chr(mapLoc + 48)
            print lineString
        lineString = " "
        print lineString
        
    def printPreSmoothMap(self,preSmoothMap):
        lineString = "Pre-Smooth Map"
        print lineString
        for y in range(mc.hmHeight - 1,-1,-1):
            lineString = ""
            for x in range(0,mc.hmWidth,1):
                i = GetHmIndex(x,y)
                mapLoc = int(preSmoothMap[i] * 40)
                lineString += chr(mapLoc + 48)
            print lineString
        lineString = " "
        print lineString
        
    def printPlateHeightMap(self):
        lineString = "Plate Height Map"
        print lineString
        for y in range(mc.hmHeight - 1,-1,-1):
            lineString = ""
            for x in range(0,mc.hmWidth,1):
                i = GetHmIndex(x,y)
                mapLoc = int(self.plateHeightMap[i] * 40)
                lineString += chr(mapLoc + 48)
            print lineString
        lineString = " "
        print lineString
        
    def printDistanceMap(self,distanceMap,maxDistance):
        lineString = "Plate Height Map"
        print lineString
        for y in range(mc.hmHeight - 1,-1,-1):
            lineString = ""
            for x in range(0,mc.hmWidth,1):
                i = GetHmIndex(x,y)
                mapLoc = int((distanceMap[i]/maxDistance) * 40)
                lineString += chr(mapLoc + 48)
            print lineString
        lineString = " "
        print lineString
        
class Plate :
    def __init__(self,ID,seedX,seedY):
        self.ID = ID
        self.seedX = seedX
        self.seedY = seedY
        self.isOnMapEdge = False
        self.angle = (PRand.random() * 360) - 180
        self.raiseOnly = False
        self.NW = 0
        self.NE = 1
        self.SE = 2
        self.SW = 3
    def GetQuadrant(self):
        if self.seedY < mc.hmHeight/2:
            if self.seedX < mc.hmWidth/2:
                return self.SW
            else:
                return self.SE
        else:
            if self.seedX < mc.hmWidth/2:
                return self.NW
            else:
                return self.NE
                
class PlatePlot :
    def __init__(self,plateID,maxDistance):
        self.plateID = plateID
        self.distanceList = list()
        for i in range(mc.hmNumberOfPlates + 1):
            self.distanceList.append(maxDistance)
            
class ClimateMap :
    def __init__(self):
        return
    def createClimateMaps(self):
        summerSunMap = array('d')
        winterSunMap = array('d')
        self.summerTempsMap = array('d')
        self.winterTempsMap = array('d')
        self.averageTempMap = array('d')
        self.moistureMap = array('d')
        self.rainFallMap = array('d')

        self.initializeTempMap(summerSunMap,mc.tropicsLatitude)
        self.initializeTempMap(winterSunMap,-mc.tropicsLatitude)

        #smooth both sun maps into the temp maps
        for y in range(0,mc.hmHeight):
            for x in range(0,mc.hmWidth):
                contributers = 0
                summerAvg = 0
                winterAvg = 0
                i = GetHmIndex(x,y)
                for yy in range(y - mc.filterSize/2,y + mc.filterSize/2 + 1,1):
                    for xx in range(x - mc.filterSize/2,x + mc.filterSize/2 + 1,1):
                        ii = GetHmIndex(xx,yy)
                        if ii == -1:
                            continue
                        contributers += 1
                        summerAvg += summerSunMap[ii]
                        winterAvg += winterSunMap[ii]
                summerAvg = summerAvg/float(contributers)
                winterAvg = winterAvg/float(contributers)
                self.summerTempsMap.append(summerAvg)
                self.winterTempsMap.append(winterAvg)
                
        #create average temp map
        for y in range(mc.hmHeight):
            for x in range(mc.hmWidth):
                i = GetHmIndex(x,y)
                #average summer and winter
                avgTemp = (self.summerTempsMap[i] + self.winterTempsMap[i])/2.0
                #cool map for altitude
                self.averageTempMap.append(avgTemp * (1.0 - pow(hm.getAltitudeAboveSeaLevel(x,y),mc.temperatureLossCurve) * mc.heatLostAtOne))
        
        #init moisture and rain maps
        for i in range(mc.hmHeight*mc.hmWidth):
            self.moistureMap.append(0.0)
            self.rainFallMap.append(0.0)
            
        #create sortable plot list for summer monsoon rains
        temperatureList = list()
        for y in range(mc.hmHeight):
            for x in range(mc.hmWidth):
                i = GetHmIndex(x,y)
                rainPlot = RainPlot(x,y,self.summerTempsMap[i],0)
                temperatureList.append(rainPlot)
        #sort by temperature, coldest first
        temperatureList.sort(lambda x,y:cmp(x.order,y.order))
          
        #Drop summer monsoon rains
        self.dropRain(temperatureList,self.summerTempsMap,False,None)

        #clear moisture map
        for i in range(mc.hmHeight*mc.hmWidth):
            self.moistureMap[i] = 0.0
            
        #create sortable plot list for winter monsoon rains
        temperatureList = list()
        for y in range(mc.hmHeight):
            for x in range(mc.hmWidth):
                i = GetHmIndex(x,y)
                rainPlot = RainPlot(x,y,self.winterTempsMap[i],0)
                temperatureList.append(rainPlot)
        #sort by temperature, coldest first
        temperatureList.sort(lambda x,y:cmp(x.order,y.order))
          
        #Drop winter monsoon rains
        self.dropRain(temperatureList,self.winterTempsMap,False,None)

        #clear moisture map
        for i in range(mc.hmHeight*mc.hmWidth):
            self.moistureMap[i] = 0.0
            
        #set up WindZones class
        wz = WindZones(mc.hmHeight,mc.topLatitude,mc.bottomLatitude)

        #create ordered list for geostrophic rain
        orderList = list()
        for zone in range(6):
            topY = wz.GetYFromZone(zone,True)
            bottomY = wz.GetYFromZone(zone,False)
            if topY == -1 and bottomY == -1:
                continue #This wind zone is not represented on this map at all so skip it
            if topY == -1: #top off map edge
                topY = mc.hmHeight - 1
            if bottomY == -1:
                bottomY = 0

            dx,dy = wz.GetWindDirectionsInZone(zone)
            if dy < 0:
                yStart = topY
                yStop = bottomY - 1
            else:
                yStart = bottomY
                yStop = topY + 1
            if dx < 0:
                xStart = mc.hmWidth - 1
                xStop = -1
            else:
                xStart = 0
                xStop = mc.hmWidth
            order = 0.0
            for y in range(yStart,yStop,dy):
                for x in range(xStart,xStop,dx):
                    rainPlot = RainPlot(x,y,order,abs(yStop - y))
                    orderList.append(rainPlot)
                    order += 1.0

        #Sort order list
        orderList.sort(lambda x,y:cmp(x.order,y.order))

        #drop geostrophic rain            
        self.dropRain(orderList,self.averageTempMap,True,wz)
        

        NormalizeMap(self.rainFallMap,mc.hmWidth,mc.hmHeight)

##        self.printRainFallMap(True)
##        self.printRainFallMap(False)
        
                
    def dropRain(self,plotList, tempMap, bGeostrophic, windZones):
        countRemaining = len(plotList)
        bDebug = False
        for plot in plotList:
            i = GetHmIndex(plot.x,plot.y)
            if bDebug:
                print "rainplot at %d,%d" % (plot.x,plot.y)
                print "order = %f" % (plot.order)
                print "initial moisture = %f" % (self.moistureMap[i])
            #First collect moisture from sea
            if hm.isBelowSeaLevel(plot.x,plot.y):
                self.moistureMap[i] += tempMap[i]
                if bDebug:
                    print "collecting %f moisture from sea" % (tempMap[i])
                    
            nList = list()
            if bGeostrophic:
                #make list of neighbors in geostrophic zone, even if off map
                zone = windZones.GetZone(plot.y)
                dx,dy = windZones.GetWindDirectionsInZone(zone)
                if bDebug:
                    if dy < 0:
                        yString = "v"
                    else:
                        yString = "^"
                    if dx < 0:
                        xString = "<"
                    else:
                        xString = ">"
                    print "Wind direction ------------------------------- %s%s - %s" % (xString,yString,windZones.GetZoneName(zone))
                nList.append((plot.x,plot.y + dy))
                nList.append((plot.x + dx,plot.y))
                nList.append((plot.x + dx,plot.y + dy))
                
            else:
                #make list of neighbors with higher temp
                for direction in range(1,9,1):
                    xx,yy = GetXYFromDirection(plot.x,plot.y,direction)
                    ii = GetHmIndex(xx,yy)
                    if ii != -1 and tempMap[i] <= tempMap[ii]:
                        nList.append((xx,yy))
                #divide moisture by number of neighbors for distribution
                if len(nList) == 0:
                    continue #dead end, dump appropriate rain
            moisturePerNeighbor = self.moistureMap[i]/float(len(nList))
            if bDebug:
                print "moisturePerNeighbor = %f for %d neighbors" % (moisturePerNeighbor,len(nList))

            geostrophicFactor = 1.0
            if bGeostrophic:
                geostrophicFactor = mc.geostrophicFactor
            for xx,yy in nList:
                ii = GetHmIndex(xx,yy)
                if bDebug:
                    print "  neighbor %d,%d" % (xx,yy)
                    print "  countRemaining = %d" % countRemaining
                #Get the rain cost to enter this plot. Cost is
                #percentage of present moisture available for this
                #neighbor
                if bGeostrophic:
                    cost = self.getRainCost(plot.x,plot.y,xx,yy,plot.uplift)
                else:
                    cost = self.getRainCost(plot.x,plot.y,xx,yy,countRemaining/mc.monsoonUplift)
                    
                if bDebug:
                    print "  rain cost = %f" % cost

                #Convert moisture into rain
                #self.moistureMap[i] -= cost * moisturePerNeighbor (this line is unecessary actually, we are finished with moisture map for this plot) 
                self.rainFallMap[i] += cost * moisturePerNeighbor * geostrophicFactor #geostrophicFactor is not involved with moisture, only to weigh against monsoons
                if bDebug:
                    print "  dropping %f rain here" % (cost * moisturePerNeighbor)

                #send remaining moisture to neighbor
                if ii != -1:
                    self.moistureMap[ii] += moisturePerNeighbor - (cost * moisturePerNeighbor)
                    if bDebug:
                        print "  remaining moisture to neighbor = %f" % (moisturePerNeighbor - (cost * moisturePerNeighbor))

            if bDebug:
                print "total rainfall = %f" % self.rainFallMap[i]
            countRemaining -= 1
            
    def getRainCost(self,x1,y1,x2,y2,distanceToUplift):
        cost = mc.minimumRainCost
        cRange = 1.0 - mc.minimumRainCost/1.0#We don't want to go over 1.0 so the range is reduced
        upliftCost = (1.0/(float(distanceToUplift) + 1.0)) * cRange
        i = GetHmIndex(x1,y1)
        ii = GetHmIndex(x2,y2)
        cost += max((self.averageTempMap[ii] - self.averageTempMap[i]) * 2.0 * cRange,upliftCost)
        return cost
            
    def initializeTempMap(self,tempMap,tropic):
        for y in range(mc.hmHeight):
            for x in range(mc.hmWidth):
                tempMap.append(self.getInitialTemp(x,y,tropic))
        return
    def getInitialTemp(self,x,y,tropic):
        i = GetHmIndex(x,y)
        lat = self.getLatitude(y)
        latRange = float(90 + abs(tropic))
        latDifference = abs(float(lat - tropic))
        aboveSeaLevel = hm.heightMap[i] > hm.seaLevel
        if aboveSeaLevel:
            tempPerLatChange = 1.0/latRange
            temp = 1.0 - (tempPerLatChange * latDifference)
        else:
            tempPerLatChange = (1.0 - (2.0*mc.oceanTempClamp))/latRange
            temp = 1.0 - mc.oceanTempClamp - (tempPerLatChange * latDifference)

        return temp

    def getLatitude(self,y):
        latitudeRange = mc.topLatitude - mc.bottomLatitude
        degreesPerDY = float(latitudeRange)/float(mc.hmHeight - mc.northCrop - mc.southCrop)
        if y > mc.hmHeight - mc.northCrop:
            return mc.topLatitude
        if y < mc.southCrop:
            return mc.bottomLatitude
        latitude = (mc.bottomLatitude + (int(round(float(y - mc.southCrop)* degreesPerDY))))
        return latitude
    
    def printRainFallMap(self,bOcean):
        lineString = "Rainfall Map"
        print lineString
        wz = WindZones(mc.hmHeight,mc.topLatitude,mc.bottomLatitude)
        for y in range(mc.hmHeight - 1,-1,-1):
            lineString = ""
            for x in range(0,mc.hmWidth,1):
                i = GetHmIndex(x,y)
                if bOcean:
                    if self.rainFallMap[i] < 0.1:
                        mapLoc = int(self.rainFallMap[i] * 100)
                        lineString += chr(mapLoc + 48)
                    else:    
                        mapLoc = int(self.rainFallMap[i] * 10)
                        lineString += chr(mapLoc + 65)
                else:
                    if hm.isBelowSeaLevel(x,y):
                        lineString += '.'
                    elif self.rainFallMap[i] < 0.00001:
                        lineString += 'X'
                    else:
                        if self.rainFallMap[i] < 0.1:
                            mapLoc = int(self.rainFallMap[i] * 100)
                            lineString += chr(mapLoc + 48)
                        else:    
                            mapLoc = int(self.rainFallMap[i] * 10)
                            lineString += chr(mapLoc + 65)
            z = wz.GetZone(y)
            dx,dy = wz.GetWindDirectionsInZone(z)
            lineString += ' - '
            if dx < 0:
                lineString += '<'
            else:
                lineString += '>'
            if dy < 0:
                lineString += 'v'
            else:
                lineString += '^'
            lineString += ' ' + wz.GetZoneName(z)
            print lineString
        lineString = " "
        print lineString
    def printTempMap(self,tempMap):
        lineString = "Temp Map"
        print lineString
        wz = WindZones(mc.hmHeight,mc.topLatitude,mc.bottomLatitude)
        for y in range(mc.hmHeight - 1,-1,-1):
            lineString = ""
            for x in range(0,mc.hmWidth,1):
                i = GetHmIndex(x,y)
                mapLoc = int(tempMap[i] * 10)
                lineString += chr(mapLoc + 48)
            z = wz.GetZone(y)
            dx,dy = wz.GetWindDirectionsInZone(z)
            lineString += ' - '
            if dx < 0:
                lineString += '<'
            else:
                lineString += '>'
            if dy < 0:
                lineString += 'v'
            else:
                lineString += '^'
            lineString += ' ' + wz.GetZoneName(z)
            print lineString
        lineString = " "
        print lineString
        
class RainPlot :
    def __init__(self,x,y,order,uplift):
        self.x = x
        self.y = y
        self.order = order
        self.uplift = uplift
        
class WindZones :
    def __init__(self,mapHeight,topLat,botLat):
        self.NPOLAR = 0
        self.NTEMPERATE = 1
        self.NEQUATOR = 2
        self.SEQUATOR = 3
        self.STEMPERATE = 4
        self.SPOLAR = 5
        self.NOZONE = 99
        self.mapHeight = mapHeight
        self.topLat = topLat
        self.botLat = botLat
    def GetZone(self,y):
        if y < 0 or y >= self.mapHeight:
            return self.NOZONE
        lat = cm.getLatitude(y)
        if lat > mc.polarFrontLatitude:
            return self.NPOLAR
        elif lat > mc.horseLatitude:
            return self.NTEMPERATE
        elif lat > 0:
            return self.NEQUATOR
        elif lat > -mc.horseLatitude:
            return self.SEQUATOR
        elif lat > -mc.polarFrontLatitude:
            return self.STEMPERATE
        else:
            return self.SPOLAR
        return
    def GetZoneName(self,zone):
        if zone == self.NPOLAR:
            return "NPOLAR"
        elif zone == self.NTEMPERATE:
            return "NTEMPERATE"
        elif zone == self.NEQUATOR:
            return "NEQUATOR"
        elif zone == self.SEQUATOR:
            return "SEQUATOR"
        elif zone == self.STEMPERATE:
            return "STEMPERATE"
        else:
            return "SPOLAR"
        return
    def GetYFromZone(self,zone,bTop):
        if bTop:
            for y in range(self.mapHeight - 1,-1,-1):
                if zone == self.GetZone(y):
                    return y
        else:
            for y in range(self.mapHeight):
                if zone == self.GetZone(y):
                    return y
        return -1
    def GetZoneSize(self):
        latitudeRange = self.topLat - self.botLat
        degreesPerDY = float(latitudeRange)/float(self.mapHeight)
        size = 30.0/degreesPerDY
        return size
    def GetWindDirections(self,y):
        z = self.GetZone(y)
        #get x,y directions
        return self.GetWindDirectionsInZone(z)
    def GetWindDirectionsInZone(self,z):
        #get x,y directions
        if z == self.NPOLAR:
            return (-1,-1)
        elif z == self.NTEMPERATE:
            return (1,1)
        elif z == self.NEQUATOR:
            return (-1,-1)
        elif z == self.SEQUATOR:
            return (-1,1)
        elif z == self.STEMPERATE:
            return (1,-1)
        elif z == self.SPOLAR:
            return (-1,1)
        return (0,0)

def isSmallWaterMatch(x,y):
    return sm.isBelowSeaLevel(x,y)

class SmallMaps :
    def __init__(self):
        return
    def initialize(self):
        self.cropMaps()
        newHeightMap = ShrinkMap(hm.heightMap,mc.hmWidth ,mc.hmHeight,mc.width,mc.height)
        newRainFallMap = ShrinkMap(cm.rainFallMap,mc.hmWidth,mc.hmHeight,mc.width,mc.height)
        newAverageTempMap = ShrinkMap(cm.averageTempMap,mc.hmWidth,mc.hmHeight,mc.width,mc.height)

        self.heightMap = array('d')
        self.rainFallMap = array('d')
        self.averageTempMap = array('d')

        for y in range(mc.height):
            for x in range(mc.width):
                oldX = x
                i = GetIndexGeneral(oldX,y,mc.width,mc.height)
                if i != -1:
                    self.heightMap.append(newHeightMap[i])
                    self.rainFallMap.append(newRainFallMap[i])
                    self.averageTempMap.append(newAverageTempMap[i])
                else:
                    self.heightMap.append(hm.seaLevel - 0.000001)
                    self.rainFallMap.append(0.0)
                    self.averageTempMap.append(0.0)

        #Smooth coasts so there are fewer hills on coast
        for y in range(mc.height):
            for x in range(mc.width):
                if self.isBelowSeaLevel(x,y):
                    i = GetIndex(x,y)
                    self.heightMap[i] = hm.seaLevel - 0.000001
                    
        self.fillInLakes()

        self.createPlotMap()
        self.printPlotMap()
        self.createTerrainMap()
        continentMap.generateContinentMap()

    def fillInLakes(self):
        #smaller lakes need to be filled in again because the map
        #shrinker sometimes creates lakes.
        am = Areamap(mc.width,mc.height,True,True)
        am.defineAreas(isSmallWaterMatch)
##        am.PrintAreaMap()
        oceanID = am.getOceanID()
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                if self.isBelowSeaLevel(x,y) and am.areaMap[i] != oceanID:
                    #check the size of this body of water, if too small,
                    #change to land
                    for a in am.areaList:
                        if a.ID == am.areaMap[i] and a.size < mc.minInlandSeaSize:
                            self.heightMap[i] = hm.seaLevel
        
        return
        
    def isBelowSeaLevel(self,x,y):
        i = GetIndex(x,y)
        if self.heightMap[i] < hm.seaLevel:
            return True
        return False
    
    ## This function returns altitude in relation to sea level with
    ## 0.0 being seaLevel and 1.0 being highest altitude
    def getAltitudeAboveSeaLevel(self,x,y):
        i = GetIndex(x,y)
        if i == -1:
            return 0.0
        altitude = self.heightMap[i]
        if altitude < hm.seaLevel:
            return 0.0
        altitude = 1.0/(1.0 - hm.seaLevel) * (altitude - hm.seaLevel)
        return altitude
    

    def createPlotMap(self):
        print "creating plot map"
        self.plotMap = array('i')
        #create height difference map to allow for tuning
        diffMap = array('d')
        for i in range(0,mc.height*mc.width):
            diffMap.append(0.0)
        #I tried using a deviation from surrounding average altitude
        #to determine hills and peaks but I didn't like the
        #results. Therefore I an using lowest neighbor
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                myAlt = self.heightMap[i]
                minAlt = 1.0
                for direction in range(1,9,1):
                    xx,yy = GetXYFromDirection(x,y,direction)
                    ii = GetIndex(xx,yy)
                    if ii == -1:
                        continue
                    if self.heightMap[ii] < minAlt:
                        minAlt = self.heightMap[ii]
                diffMap[i] = myAlt - minAlt

        NormalizeMap(diffMap,mc.width,mc.height)

        #zero out water tiles so percent is percent of land
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                if self.isBelowSeaLevel(x,y):
                    diffMap[i] = 0.0
                    
        peakHeight = FindValueFromPercent(diffMap,mc.width,mc.height,mc.PeakPercent,0.01,True)
        hillHeight = FindValueFromPercent(diffMap,mc.width,mc.height,mc.HillPercent,0.01,True)

        self.plotMap = array('i')
        #initialize map with 0CEAN
        for i in range(0,mc.height*mc.width):
            self.plotMap.append(mc.OCEAN)
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                altDiff = diffMap[i]
                if self.heightMap[i] < hm.seaLevel:
                    self.plotMap[i] = mc.OCEAN
                elif altDiff < hillHeight:
                    self.plotMap[i] = mc.LAND
                elif altDiff < peakHeight:
                    self.plotMap[i] = mc.HILLS
                else:
                    self.plotMap[i] = mc.PEAK

        #Randomize high altitude areas
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                if self.plotMap[i] == mc.LAND:
                    randomNum = PRand.random()
                    if randomNum < mc.PeakChanceAtOne * self.getAltitudeAboveSeaLevel(x,y):
                        self.plotMap[i] = mc.PEAK
                    elif randomNum < mc.HillChanceAtOne * self.getAltitudeAboveSeaLevel(x,y):
                        self.plotMap[i] = mc.HILLS

        #break up large clusters of hills and peaks
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                if self.plotMap[i] == mc.HILLS:
                    allHills = True
                    for direction in range(1,9,1):
                        xx,yy = GetXYFromDirection(x,y,direction)
                        ii = GetIndex(xx,yy)
                        if self.plotMap[ii] != mc.HILLS:
                            allHills = False
                    if allHills == True:
                        self.plotMap[i] = mc.LAND
                if self.plotMap[i] == mc.PEAK:
                    allPeaks = True
                    peakCount = 0
                    nextToOcean = False
                    for direction in range(1,9,1):
                        xx,yy = GetXYFromDirection(x,y,direction)
                        ii = GetIndex(xx,yy)
                        if self.plotMap[ii] != mc.PEAK:
                            allPeaks = False
                        else:
                            peakCount += 1
                        if self.plotMap[ii] == mc.OCEAN:
                            nextToOcean = True
                    if allPeaks == True or peakCount>3 or nextToOcean == True:
                        self.plotMap[i] = mc.HILLS
        
        return
    def createTerrainMap(self):
        print "creating terrain map"
        self.terrainMap = array('i')
        #initialize terrainMap with OCEAN
        for i in range(0,mc.height*mc.width):
            self.terrainMap.append(mc.OCEAN)

        #Find minimum rainfall on land
        minRain = 10.0
        for i in range(mc.width*mc.height):
            if self.plotMap[i] != mc.OCEAN:
                if self.rainFallMap[i] < minRain:
                    minRain = self.rainFallMap[i]

        #zero water tiles to obtain percent of land            
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                if self.isBelowSeaLevel(x,y):
                    self.rainFallMap[i] = 0.0
                    
        self.desertThreshold = FindValueFromPercent(self.rainFallMap,mc.width,mc.height,mc.DesertPercent,.001,False)
        self.plainsThreshold = FindValueFromPercent(self.rainFallMap,mc.width,mc.height,mc.PlainsPercent,.001,False)
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                if self.plotMap[i] == mc.OCEAN:
                    for direction in range (1,9,1):
                        xx,yy = GetXYFromDirection(x,y,direction)
                        ii = GetIndex(xx,yy)
                        if ii == -1:
                            continue
                        if self.plotMap[ii] != mc.OCEAN:
                            self.terrainMap[i] = mc.COAST

                #instead of harsh thresholds, allow a random deviation chance
                #based on how close to the threshold the rainfall is
                elif self.rainFallMap[i] < self.desertThreshold:
                    if self.averageTempMap[i] < mc.SnowTemp:
                        self.terrainMap[i] = mc.SNOW
                    elif self.averageTempMap[i] < mc.TundraTemp:
                        self.terrainMap[i] = mc.TUNDRA
                    else:
                        if self.rainFallMap[i] < (PRand.random() * (self.desertThreshold - minRain) + self.desertThreshold - minRain)/2.0 + minRain:
                            self.terrainMap[i] = mc.DESERT
                        else:
                            self.terrainMap[i] = mc.PLAINS
                elif self.rainFallMap[i] < self.plainsThreshold:
                    if self.averageTempMap[i] < mc.SnowTemp:
                        self.terrainMap[i] = mc.SNOW
                    elif self.averageTempMap[i] < mc.TundraTemp:
                        self.terrainMap[i] = mc.TUNDRA
                    else:
                        if self.rainFallMap[i] < ((PRand.random() * (self.plainsThreshold - self.desertThreshold) + self.plainsThreshold - self.desertThreshold))/2.0 + self.desertThreshold: 
                            self.terrainMap[i] = mc.PLAINS
                        else:
                            self.terrainMap[i] = mc.GRASS
                else:
                    if self.averageTempMap[i] < mc.SnowTemp:
                        self.terrainMap[i] = mc.SNOW
                    elif self.averageTempMap[i] < mc.TundraTemp:
                        self.terrainMap[i] = mc.TUNDRA
                    else:
                        self.terrainMap[i] = mc.GRASS

        #Make sure ice is always higher than tundra, and tundra is always higher than
        #everything else. Also, desert does not blend well with these so change it.
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                if self.terrainMap[i] == mc.OCEAN or self.terrainMap[i] == mc.COAST:
                    continue
                if self.terrainMap[i] == mc.SNOW:
                    lowerFound = False
                    for direction in range(1,9,1):
                        xx,yy = GetXYFromDirection(x,y,direction)
                        ii = GetIndex(xx,yy)
                        if ii == -1:
                            continue
                        if self.terrainMap[ii] != mc.OCEAN and self.terrainMap[ii] != mc.COAST \
                        and self.terrainMap[ii] != mc.SNOW:
                            lowerFound = True
                        if self.terrainMap[ii] != mc.TUNDRA and self.terrainMap[ii] != mc.SNOW and\
                        self.terrainMap[ii] != mc.OCEAN and self.terrainMap[ii] != mc.COAST:
                            self.terrainMap[i] = mc.TUNDRA
                        if self.terrainMap[ii] == mc.DESERT:
                            self.terrainMap[i] = mc.PLAINS
                    if lowerFound and self.plotMap[i] == mc.LAND:
                        self.plotMap[i] = mc.HILLS
                elif self.terrainMap[i] == mc.TUNDRA:
                    lowerFound = False
                    for direction in range(1,9,1):
                        xx,yy = GetXYFromDirection(x,y,direction)
                        ii = GetIndex(xx,yy)
                        if ii == -1:
                            continue
                        if self.terrainMap[ii] != mc.OCEAN and self.terrainMap[ii] != mc.COAST \
                        and self.terrainMap[ii] != mc.SNOW and self.terrainMap[ii] != mc.TUNDRA:
                            lowerFound = True
                        if self.terrainMap[ii] == mc.DESERT:
                            self.terrainMap[i] = mc.PLAINS
                    if lowerFound and self.plotMap[i] == mc.LAND:
                        if PRand.random() < 0.5:
                            self.plotMap[i] = mc.HILLS
                        else:
                            self.plotMap[i] = mc.PEAK
                else:
                    higherFound = False
                    for direction in range(1,9,1):
                        xx,yy = GetXYFromDirection(x,y,direction)
                        ii = GetIndex(xx,yy)
                        if self.terrainMap[ii] == mc.SNOW or self.terrainMap[ii] == mc.TUNDRA:
                            higherFound = True
                    if higherFound and self.plotMap[i] != mc.LAND:
                        self.plotMap[i] = mc.LAND
        return
    def cropMaps(self):
        hm.heightMap = CropMap(hm.heightMap)
        cm.averageTempMap = CropMap(cm.averageTempMap)
        cm.rainFallMap = CropMap(cm.rainFallMap)
        mc.hmWidth = mc.hmWidth - mc.westCrop - mc.eastCrop
        mc.hmHeight = mc.hmHeight - mc.northCrop - mc.southCrop

    def printHeightMap(self):
        lineString = "Height Map"
        print lineString
        for y in range(mc.height - 1,-1,-1):
            lineString = ""
            for x in range(0,mc.width,1):
                i = GetIndexGeneral(x,y,mc.width,mc.height)
                mapLoc = int((self.heightMap[i] - hm.seaLevel)/(1.0 - hm.seaLevel) * 10)
                #mapLoc = int(self.heightMap[i] * 10)
                if self.heightMap[i] < hm.seaLevel:
                    lineString += '.'
                else:
                    lineString += chr(mapLoc + 48)
            print lineString
        lineString = " "
        print lineString
        
    def printPlotMap(self):
        print "Plot Map"
        for y in range(mc.height - 1,-1,-1):
            lineString = ""
            for x in range(mc.width):
                mapLoc = self.plotMap[GetIndex(x,y)]
                if mapLoc == mc.PEAK:
                    lineString += 'A'
                elif mapLoc == mc.HILLS:
                    lineString += 'n'
                elif mapLoc == mc.LAND:
                    lineString += '+'
                else:
                    lineString += '.'
            print lineString
        lineString = " "
        print lineString
    def printTerrainMap(self):
        print "Terrain Map"
        wz = WindZones(mc.height,80,-80)
        for y in range(mc.height - 1,-1,-1):
            lineString = ""
            for x in range(mc.width):
                mapLoc = self.terrainMap[GetIndex(x,y)]
                if mapLoc == mc.OCEAN:
                    lineString += ','
                elif mapLoc == mc.COAST:
                    lineString += '.'
                elif mapLoc == mc.DESERT:
                    lineString += 'D'
                elif mapLoc == mc.GRASS:
                    lineString += '+'
                elif mapLoc == mc.MARSH:
                    lineString += 'M'
                elif mapLoc == mc.PLAINS:
                    lineString += 'P'
                elif mapLoc == mc.TUNDRA:
                    lineString += 'T'
                elif mapLoc == mc.SNOW:
                    lineString += 'I'
            lineString += "-" + wz.GetZoneName(wz.GetZone(y))
            print lineString
        lineString = " "
        print lineString

def isHmWaterMatch(x,y):
    i = GetHmIndex(x,y)
    if pb.distanceMap[i] > mc.minimumMeteorSize/3:
        return True
    return False

class PangaeaBreaker :
    def __init__(self):
        return
    def breakPangaeas(self):
        self.areaMap = Areamap(mc.hmWidth,mc.hmHeight,True,True)
        meteorThrown = False
        pangeaDetected = False
##        anotherPangaea = True
#        self.cm.PrintAreaMap()
##        while anotherPangaea:
##            NormalizeMap(hm.heightMap,mc.hmWidth,mc.hmHeight)
##            hm.calculateSeaLevel()
        self.createDistanceMap()
##        self.printDistanceMap()
        self.areaMap.defineAreas(isHmWaterMatch)
##        self.areaMap.PrintAreaMap()
        meteorCount = 0
        while not mc.AllowPangeas and self.isPangea() and meteorCount < mc.maximumMeteorCount:
            pangeaDetected = True
            x,y = self.getMeteorStrike()
            print "A meteor has struck the Earth at %(x)d, %(y)d!!" % {"x":x,"y":y}
            self.castMeteorUponTheEarth(x,y)
            meteorThrown = True
            meteorCount += 1
##            hm.printHeightMap()
            self.createDistanceMap()
##            self.printDistanceMap()
            self.areaMap.defineAreas(isHmWaterMatch)
##            self.areaMap.PrintAreaMap()
##            anotherPangaea = False
            
        if meteorThrown:
            print "The age of dinosours has come to a cataclysmic end."
        if meteorCount == 15:
            print "Maximum meteor count of %d has been reached. Pangaea may still exist." % meteorCount
        if mc.AllowPangeas:
            print "Pangeas are allowed on this map and will not be suppressed."
        elif pangeaDetected == False:
            print "No pangea detected on this map."
##        self.areaMap.PrintAreaMap()
    def isPangea(self):
##        starttime = time.clock()
        continentList = list()
        for a in self.areaMap.areaList:
            if a.water == False:
                continentList.append(a)

        totalLand = 0             
        for c in continentList:
            totalLand += c.size
            
        #sort all the continents by size, largest first
        continentList.sort(lambda x,y:cmp(x.size,y.size))
        continentList.reverse()
        biggestSize = continentList[0].size
        if 0.70 < float(biggestSize)/float(totalLand):
##            endtime = time.clock()
##            elapsed = endtime - starttime
##            print "isPangea time = %(t)s" % {"t":str(elapsed)}
            return True
##        endtime = time.clock()
##        elapsed = endtime - starttime
##        print "isPangea time = "
##        print elapsed
##        print
        return False
    def getMeteorStrike(self):
##        starttime = time.clock()
        continentList = list()
        for a in self.areaMap.areaList:
            if a.water == False:
                continentList.append(a)
            
        #sort all the continents by size, largest first
        continentList.sort(lambda x,y:cmp(x.size,y.size))
        continentList.reverse()
        biggestContinentID = continentList[0].ID

        x,y = self.getHighestCentrality(biggestContinentID)

        return x,y
        
##        chokeList = list()
##        for y in range(mc.hmHeight):
##            for x in range(mc.hmWidth):
##                i = GetHmIndex(x,y)
##                if i == -1:
##                    continue
##                if self.areaMap.areaMap[i] == biggestContinentID and\
##                not hm.isBelowSeaLevel(x,y): #this helps narrow the search
##                    if self.isChokePoint(x,y,biggestContinentID):
####                        print "chokepoint area at %d,%d = %d" % (x,y,biggestContinentID)
##                        ap = AreaPlot(x,y)
##                        chokeList.append(ap)
##        #calculate distances to center
##        center = self.getContinentCenter(biggestContinentID)
##        xCenter,yCenter = center
##
##        for n in range(len(chokeList)):
##            distance = self.getDistance(chokeList[n].x,chokeList[n].y,xCenter,yCenter)
##            chokeList[n].avgDistance = distance
##            
##        #sort plotList for most avg distance and chokeList for least
##        #average distance
##        chokeList.sort(lambda x,y:cmp(x.avgDistance,y.avgDistance))
##
##        if len(chokeList) == 0:#return bad value if no chokepoints
####            endtime = time.clock()
####            elapsed = endtime - starttime
####            print "getMeteorStrike time = "
####            print elapsed
####            print
##            return -1,-1
##
####        endtime = time.clock()
####        elapsed = endtime - starttime
####        print "getMeteorStrike time = "
####        print elapsed
####        print
##        
##        return chokeList[0].x,chokeList[0].y
                
    def isChokePoint(self,x,y,biggestContinentID):
        circlePoints = self.getCirclePoints(x,y,mc.minimumMeteorSize)
        waterOpposite = False
        landOpposite = False
        for cp in circlePoints:
            if isHmWaterMatch(cp.x,cp.y):
                #Find opposite
                ox = x + (x - cp.x)
                oy = y + (y - cp.y)
                if isHmWaterMatch(ox,oy):
                    waterOpposite = True
            else:
                #Find opposite
                ox = x + (x - cp.x)
                oy = y + (y - cp.y)
                if not isHmWaterMatch(ox,oy):
                    landOpposite = True
        if landOpposite and waterOpposite:
            percent = self.getLandPercentInCircle(circlePoints,biggestContinentID)
            if percent >= mc.minimumLandInChoke:
                return True
        return False
    def getLandPercentInCircle(self,circlePoints,biggestContinentID):
        land = 0
        water = 0
        circlePoints.sort(lambda n,m:cmp(n.y,m.y))
        for n in range(0,len(circlePoints),2):
            cy = circlePoints[n].y
            if circlePoints[n].x < circlePoints[n + 1].x:
                x1 = circlePoints[n].x
                x2 = circlePoints[n + 1].x
            else:
                x2 = circlePoints[n].x
                x1 = circlePoints[n + 1].x
            landLine,waterLine = self.countCraterLine(x1,x2,cy,biggestContinentID)
            land += landLine
            water += waterLine
        percent = float(land)/float(land + water)
        return percent
            
    def countCraterLine(self,x1,x2,y,biggestContinentID):
        land = 0
        water = 0
        for x in range(x1,x2 + 1):
            i = GetHmIndex(x,y)
            if self.areaMap.areaMap[i] == biggestContinentID:
                land += 1
            else:
                water += 1
        return land,water
        
    def getContinentCenter(self,ID):
        IDCount = 0
        xTotal = 0
        yTotal = 0
        for y in range(mc.hmHeight):
            for x in range(mc.hmWidth):
                i = GetHmIndex(x,y)
                if self.areaMap.areaMap[i] == ID:
                    IDCount += 1
                    xTotal += x
                    yTotal += y
        xCenter = round(float(xTotal)/float(IDCount))
        yCenter = round(float(yTotal)/float(IDCount))
##        #first find center in x direction
##        changes = list()
##        yMin = mc.height
##        yMax = -1
##        meridianOverlap = False
##        onContinent = False
##        for x in range(mc.hmWidth):
##            continentFoundThisPass = False
##            for y in range(mc.hmHeight):
##                i = GetHmIndex(x,y)
##                if self.areaMap.areaMap[i] == ID:
##                    continentFoundThisPass = True
##                    if y < yMin:
##                        yMin = y
##                    elif y > yMax:
##                        yMax = y
##            if x == 0 and continentFoundThisPass:
##                meridianOverlap = True
##                onContinent = True
##            if onContinent and not continentFoundThisPass:
##                changes.append(x)
##                onContinent = False
##            elif not onContinent and continentFoundThisPass:
##                changes.append(x)
##                onContinent = True
##        changes.sort()
##        xCenter = -1
##        if len(changes) == 0: #continent is continuous
##            xCenter = -1
##        elif len(changes) == 1:#continent extends to map edge
##            if meridianOverlap:
##                xCenter = changes[0]/2
##            else:
##                xCenter = (mc.width - changes[0])/2 + changes[0]
##        else:
##            if meridianOverlap:
##                xCenter = ((changes[1] - changes[0])/2 + changes[0] + (mc.hmWidth/2)) % mc.hmWidth
##            else:
##                xCenter = (changes[1] - changes[0])/2 + changes[0]
##        yCenter = (yMax - yMin)/2 + yMin
        center = xCenter,yCenter
        return center
    
    def getDistance(self,x,y,dx,dy):
        xx = x - dx
        if abs(xx) > mc.hmWidth/2:
            xx = mc.hmWidth - abs(xx)
            
        distance = max(abs(xx),abs(y - dy))
        return distance
    def castMeteorUponTheEarth(self,x,y):
##        starttime = time.clock()
        radius = PRand.randint(mc.minimumMeteorSize,max(mc.minimumMeteorSize + 1,mc.hmWidth/16))
        circlePointList = self.getCirclePoints(x,y,radius)
##        print "circlePointList"
##        print circlePointList
        circlePointList.sort(lambda n,m:cmp(n.y,m.y))
        for n in range(0,len(circlePointList),2):
            cy = circlePointList[n].y
            if circlePointList[n].x < circlePointList[n + 1].x:
                x1 = circlePointList[n].x
                x2 = circlePointList[n + 1].x
            else:
                x2 = circlePointList[n].x
                x1 = circlePointList[n + 1].x
            self.drawCraterLine(x1,x2,cy)
            
##        for n in range(0,len(circlePointList),2): not needed since this is happening on heightmap only
##            cy = circlePointList[n].y
##            if circlePointList[n].x < circlePointList[n + 1].x:
##                x1 = circlePointList[n].x
##                x2 = circlePointList[n + 1].x
##            else:
##                x2 = circlePointList[n].x
##                x1 = circlePointList[n + 1].x
##            self.drawCraterCoastLine(x1,x2,cy)
        return
    
##    def drawCraterCoastLine(self,x1,x2,y): not needed since this is happening on heightmap only
##        if y < 0 or y >= mc.hmHeight:
##            return
##        for x in range(x1,x2 + 1):
##            if self.hasLandNeighbor(x,y):
##                i = GetHmIndex(x,y)
##                sm.terrainMap[i] = mc.COAST                   
##        return
    def drawCraterLine(self,x1,x2,y):
        if y < 0 or y >= mc.hmHeight:
            return
        for x in range(x1,x2 + 1):
            i = GetHmIndex(x,y)
##            sm.terrainMap[i] = mc.OCEAN
            hm.heightMap[i] = 0.0
##            sm.plotMap[i] = mc.OCEAN
        return
##    def hasLandNeighbor(self,x,y): not needed since this is happening on heightmap only
##        #y cannot be outside of map so I'm not testing for it
##        for yy in range(y - 1,y + 2):
##            for xx in range(x - 1,x + 2):
##                if yy == y and xx == x:
##                    continue
##                ii = GetHmIndex(xx,yy)
##                if sm.terrainMap[ii] != mc.COAST and sm.terrainMap[ii] != mc.OCEAN:
##                    return True
##        return False
    def getCirclePoints(self,xCenter,yCenter,radius):
        circlePointList = list()
        x = 0
        y = radius
        p = 1 - radius

        self.addCirclePoints(xCenter,yCenter,x,y,circlePointList)

        while (x < y):
            x += 1
            if p < 0:
                p += 2*x + 1
            else:
                y -= 1
                p += 2*(x - y) + 1
            self.addCirclePoints(xCenter,yCenter,x,y,circlePointList)
            
        return circlePointList
    
    def addCirclePoints(self,xCenter,yCenter,x,y,circlePointList):
        circlePointList.append(CirclePoint(xCenter + x,yCenter + y))
        circlePointList.append(CirclePoint(xCenter - x,yCenter + y))
        circlePointList.append(CirclePoint(xCenter + x,yCenter - y))
        circlePointList.append(CirclePoint(xCenter - x,yCenter - y))
        circlePointList.append(CirclePoint(xCenter + y,yCenter + x))
        circlePointList.append(CirclePoint(xCenter - y,yCenter + x))
        circlePointList.append(CirclePoint(xCenter + y,yCenter - x))
        circlePointList.append(CirclePoint(xCenter - y,yCenter - x))
        return
    
    def createDistanceMap(self):
        self.distanceMap = array('i')
        processQueue = []
        for y in range(mc.hmHeight):
            for x in range(mc.hmWidth):
                if hm.isBelowSeaLevel(x,y):
                    self.distanceMap.append(1000)
                else:
                    self.distanceMap.append(0)
                    processQueue.append((x,y))
                    
        while len(processQueue) > 0:
            x,y = processQueue[0]
            i = GetHmIndex(x,y)
            del processQueue[0]
            distanceToLand = self.distanceMap[i]
            for direction in range(1,9,1):
                xx,yy = GetXYFromDirection(x,y,direction)
                ii = GetHmIndex(xx,yy)
                neighborDistanceToLand = self.distanceMap[ii]
                if neighborDistanceToLand > distanceToLand + 1:
                    self.distanceMap[ii] = distanceToLand + 1
                    processQueue.append((xx,yy))
            
    def printDistanceMap(self):
        lineString = "Pangaea Breaker distance map"
        print lineString
        for y in range(mc.hmHeight - 1,-1,-1):
            lineString = ""
            for x in range(0,mc.hmWidth,1):
                i = GetHmIndex(x,y)
                mapLoc = int(self.distanceMap[i])
                #mapLoc = int(self.heightMap[i] * 10)
                if mapLoc > 9:
                    lineString += '.'
                else:
                    lineString += chr(mapLoc + 48)
            print lineString
        lineString = " "
        print lineString
        
    def getHighestCentrality(self,ID):
        C = self.createCentralityList(ID)
        C.sort(lambda x,y:cmp(x.centrality,y.centrality))
        C.reverse()
        return C[0].x,C[0].y
    def createContinentList(self,ID):
        C = []
        indexMap = []
        gap = 5
        n = 0
        for y in range(0,mc.hmHeight):
            for x in range(0,mc.hmWidth):
                i = GetHmIndex(x,y)
##                print "h %% gap = %d, w %% gap = %d" % (y % gap,y % gap)
                if y % gap == 0 and x % gap == 0 and \
                self.areaMap.areaMap[i] == ID:
                    C.append(CentralityScore(x,y))
                    indexMap.append(n)
                    n += 1
                else:
                    indexMap.append(-1)

        n = 0
        for s in C:
##            print "s at %d,%d index %d is neighbors with" % (s.x,s.y,n)
            #Check 4 nieghbors
            xx = s.x - gap
            if xx < 0:
                xx = mc.hmWidth/gap * gap
            i = GetHmIndex(xx,s.y)
            if i != -1 and self.areaMap.areaMap[i] == ID:
                s.neighborList.append(indexMap[i])
##                print "%d,%d index %d" % (xx,s.y,indexMap[i])
            xx = s.x + gap
            if xx >= mc.hmWidth:
                xx = 0
            i = GetHmIndex(xx,s.y)
            if i != -1 and self.areaMap.areaMap[i] == ID:
                s.neighborList.append(indexMap[i])
##                print "%d,%d index %d" % (xx,s.y,indexMap[i])
            yy = s.y - gap
            if yy < 0:
                yy = mc.hmHeight/gap * gap
            i = GetHmIndex(s.x,yy)
            if i != -1 and self.areaMap.areaMap[i] == ID:
                s.neighborList.append(indexMap[i])
##                print "%d,%d index %d" % (s.x,yy,indexMap[i])
            yy = s.y + gap
            if yy > mc.hmHeight:
                yy = 0
            i = GetHmIndex(s.x,yy)
            if i != -1 and self.areaMap.areaMap[i] == ID:
                s.neighborList.append(indexMap[i])
##                print "%d,%d index %d" % (s.x,yy,indexMap[i])

            n += 1

##        self.areaMap.PrintAreaMap()
##        self.printContinentList(ID,gap)

        return C
            
    def printContinentList(self,ID,gap):
        lineString = "Continent neighbor map"
        print lineString
        for y in range(mc.hmHeight - 1,-1,-1):
            lineString = ""
            for x in range(0,mc.hmWidth,1):
                i = GetHmIndex(x,y)
                if y % gap == 0 and x % gap == 0 and \
                self.areaMap.areaMap[i] == ID:
                    lineString += '@'
                elif self.areaMap.areaMap[i] == ID:
                    lineString += '*'
                else:
                    lineString += '.'
            print lineString
        lineString = " "
        print lineString
        
    
    def createCentralityList(self,ID):
        C = self.createContinentList(ID)
        
        for s in range(len(C)):
            S = []
            P = []
            sigma = []
            d = []
            delta = []
            for t in range(len(C)):
                sigma.append(0)
                d.append(-1)
                P.append([])
                delta.append(0)
            sigma[s] = 1
            d[s] = 0
            Q = []
            Q.append(s)
            while len(Q) > 0:
                v = Q.pop(0)
##                print len(Q)
                S.append(v)
                for w in C[v].neighborList:
                    if d[w] < 0:
                        Q.append(w)
#                            print len(Q)
                        d[w] = d[v] + 1
                    if d[w] == d[v] + 1:
                        sigma[w] = sigma[w] + sigma[v]
                        P[w].append(v)
            while len(S) > 0:
                w = S.pop()
                for v in P[w]:
                    delta[v] = delta[v] + (sigma[v]/sigma[w]) * (1 + delta[w])
                    if w != s:
                        C[w].centrality = C[w].centrality + delta[w]
##            print s
        
        return C
    
    def isNeighbor(self,x,y,xx,yy):
            #Check X for wrap
        if mc.WrapX == True:
            mx = xx % mc.hmWidth
        elif x < 0 or x >= mc.hmWidth:
            return False
        else:
            mx = xx
        #Check y for wrap
        if mc.WrapY == True:
            my = yy % mc.hmHeight
        elif y < 0 or y >= mc.hmHeight:
            return False
        else:
            my = yy

        if abs(x - mx) <= 1 and abs(y - my) <= 1:
            if x == mx and y == my:
                return False
            else:
                return True
        return False
            
                
                    
pb = PangaeaBreaker()

class CirclePoint :
    def __init__(self,x,y):
        self.x = x
        self.y = y
class CentralityScore :
    def __init__(self,x,y):
        self.x = x
        self.y = y
        self.centrality = 0
        self.neighborList = []
        
def isNonCoastWaterMatch(x,y):
    i = GetIndex(x,y)
    if sm.terrainMap[i] == mc.OCEAN:
        return True
    return False
        
class ContinentMap :
    def __init__(self):
        return
    def generateContinentMap(self):
        self.areaMap = Areamap(mc.width,mc.height,True,True)
        self.areaMap.defineAreas(isNonCoastWaterMatch)
##        self.areaMap.PrintAreaMap()
        self.newWorldID = self.getNewWorldID()
#        self.cm.PrintAreaMap()
        return
    def getNewWorldID(self):
        nID = 0
        continentList = list()
        for a in self.areaMap.areaList:
            if a.water == False:
                continentList.append(a)

        totalLand = 0             
        for c in continentList:
            totalLand += c.size
            
##        print totalLand

        #sort all the continents by size, largest first
#        continentList.sort(key=operator.attrgetter('size'),reverse=True)
        continentList.sort(lambda x,y:cmp(x.size,y.size))
        continentList.reverse()
        
        print ''
        print "All continents"
        print self.areaMap.PrintList(continentList)

        #now remove a percentage of the landmass to be considered 'Old World'
        oldWorldSize = 0
        #biggest continent is automatically 'Old World'
        oldWorldSize += continentList[0].size
        if mc.ShareContinentIndex == 2:
            oldWorldContinent = continentList[0]
        del continentList[0]

        #If this was the only continent than we have a pangaea. Oh well.
        if len(continentList) == 0:
            return -1
        
        #get the next largest continent and temporarily remove from list
        #add it back later and is automatically 'New World'
        biggestNewWorld = continentList[0]
        del continentList[0]
        
        #sort list by ID rather than size to make things
        #interesting and possibly bigger new worlds
#        continentList.sort(key=operator.attrgetter('ID'),reverse=True)
        continentList.sort(lambda x,y:cmp(x.ID,y.ID))
        continentList.reverse()
        
        for n in range(len(continentList)):
            oldWorldSize += continentList[0].size
            if mc.ShareContinent == False:
                del continentList[0]
            if float(oldWorldSize)/float(totalLand) > 0.60:
                break

        # add back the biggestNewWorld continent unless we're putting
        # everyone on the second biggest continent
        if mc.ShareContinentIndex != 2:
            continentList.append(biggestNewWorld)
        else:
            continentList.append(oldWorldContinent)
        
        #what remains in the list will be considered 'New World'
        print ''
        print "New World Continents"
        print self.areaMap.PrintList(continentList)

        #get ID for the next continent, we will use this ID for 'New World'
        #designation
        nID = continentList[0].ID
        del continentList[0] #delete to avoid unnecessary overwrite

        #now change all the remaining continents to also have nID as their ID
        for i in range(mc.height*mc.width):
            for c in continentList:
                if c.ID == self.areaMap.areaMap[i]:
                    self.areaMap.areaMap[i] = nID
 
        return nID
continentMap = ContinentMap()

class Areamap :
    def __init__(self,width,height,b8connected,bSwitch4Or8OnFalseMatch):
        self.mapWidth = width
        self.mapHeight = height
        self.areaMap = array('i')
        self.b8connected = b8connected
        self.bSwitch4Or8OnFalseMatch = bSwitch4Or8OnFalseMatch
        #initialize map with zeros
        for i in range(0,self.mapHeight*self.mapWidth):
            self.areaMap.append(0)
        return
    def defineAreas(self,matchFunction):
#        self.areaSizes = array('i')
##        starttime = time.clock()
        self.areaList = list()
        areaID = 0
        #make sure map is erased in case it is used multiple times
        for i in range(0,self.mapHeight*self.mapWidth):
            self.areaMap[i] = 0
#        for i in range(0,1):
        for i in range(0,self.mapHeight*self.mapWidth):
            if self.areaMap[i] == 0: #not assigned to an area yet
                areaID += 1
                areaSize,match = self.fillArea(i,areaID,matchFunction)
                area = Area(areaID,areaSize,match)
                self.areaList.append(area)

##        endtime = time.clock()
##        elapsed = endtime - starttime
##        print "defineAreas time ="
##        print elapsed
##        print

        return

##    def isWater(self,x,y,coastIsLand):
##        #coastIsLand = True means that we are trying to find continents that
##        #are not connected by coasts to the main landmasses, allowing us to
##        #find continents suitable as a 'New World'. Otherwise, we
##        #are just looking to fill in lakes and coast needs to be considered
##        #water in that case
##        ii = self.getIndex(x,y)
##        if ii == -1:
##            return False
##        if coastIsLand:
##            if hm.plotMap[ii] == hm.OCEAN and terr.terrainMap[ii] != terr.COAST:
##                return True
##            else:
##                return False
##        else:
##            if hm.isBelowSeaLevel(x,y):
##                return True
##            else:
##                return False
##            
##        return False
    def getAreaByID(self,areaID):
        for i in range(len(self.areaList)):
            if self.areaList[i].ID == areaID:
                return self.areaList[i]
        return None
    def getOceanID(self):
#        self.areaList.sort(key=operator.attrgetter('size'),reverse=True)
        self.areaList.sort(lambda x,y:cmp(x.size,y.size))
        self.areaList.reverse()
        for a in self.areaList:
            if a.water == True:
                return a.ID
                        
    def getIndex(self,x,y):
        #Check X for wrap
        if mc.WrapX == True:
            xx = x % self.mapWidth
        elif x < 0 or x >= self.mapWidth:
            return -1
        else:
            xx = x
        #Check y for wrap
        if mc.WrapY == True:
            yy = y % self.mapHeight
        elif y < 0 or y >= self.mapHeight:
            return -1
        else:
            yy = y

        i = yy * self.mapWidth + xx
        return i
    
    def fillArea(self,index,areaID,matchFunction):
        #first divide index into x and y
        y = index/self.mapWidth
        x = index%self.mapWidth
        #We check 8 neigbors for land,but 4 for water. This is because
        #the game connects land squares diagonally across water, but
        #water squares are not passable diagonally across land
        self.segStack = list()
        self.size = 0
        matchValue = matchFunction(x,y)
        #place seed on stack for both directions
        seg = LineSegment(y,x,x,1)
        self.segStack.append(seg) 
        seg = LineSegment(y+1,x,x,-1)
        self.segStack.append(seg) 
        while(len(self.segStack) > 0):
            seg = self.segStack.pop()
            self.scanAndFillLine(seg,areaID,matchValue,matchFunction)
##            if (seg.y < 8 and seg.y > 4) or (seg.y < 70 and seg.y > 64):
##            if (areaID == 4
##                PrintPlotMap(hm)
##                self.PrintAreaMap()
        
        return self.size,matchFunction(x,y)
    def scanAndFillLine(self,seg,areaID,matchValue,matchFunction):
        #check for y + dy being off map
        i = self.getIndex(seg.xLeft,seg.y + seg.dy)
        if i < 0:
##            print "scanLine off map ignoring",str(seg)
            return
        debugReport = False
##        if (seg.y < 8 and seg.y > 4) or (seg.y < 70 and seg.y > 64):
##        if (areaID == 4):
##            debugReport = True
        #for land tiles we must look one past the x extents to include
        #8-connected neighbors
        if self.b8connected:
            if self.bSwitch4Or8OnFalseMatch and matchValue:
                landOffset = 0
            else:
                landOffset = 1
        else:
            if self.bSwitch4Or8OnFalseMatch and matchValue:
                landOffset = 1
            else:
                landOffset = 0
        
        lineFound = False
        #first scan and fill any left overhang
        if debugReport:
            print ""
            print "areaID = %(a)4d" % {"a":areaID}
            print "matchValue = %(w)2d, landOffset = %(l)2d" % {"w":matchValue,"l":landOffset} 
            print str(seg)
            print "Going left"
        if mc.WrapX == True:
            xStop = 0 - (self.mapWidth*20)
        else:
            xStop = -1
        for xLeftExtreme in range(seg.xLeft - landOffset,xStop,-1):
            i = self.getIndex(xLeftExtreme,seg.y + seg.dy)
            if debugReport:
                print "xLeftExtreme = %(xl)4d" % {'xl':xLeftExtreme}
            if debugReport:
                print "i = %d, seg.y + seg.dy = %d" % (i,seg.y + seg.dy)
                print "areaMap[i] = %d, matchValue match = %d" % (self.areaMap[i],matchValue == matchFunction(xLeftExtreme,seg.y + seg.dy))
            if self.areaMap[i] == 0 and matchValue == matchFunction(xLeftExtreme,seg.y + seg.dy):
                self.areaMap[i] = areaID
                self.size += 1
                lineFound = True
            else:
                #if no line was found, then xLeftExtreme is fine, but if
                #a line was found going left, then we need to increment
                #xLeftExtreme to represent the inclusive end of the line
                if lineFound:
                    xLeftExtreme += 1
                break
        if debugReport:
            print "xLeftExtreme finally = %(xl)4d" % {'xl':xLeftExtreme}
            print "Going Right"
        #now scan right to find extreme right, place each found segment on stack
#        xRightExtreme = seg.xLeft - landOffset #needed sometimes? one time it was not initialized before use.
        xRightExtreme = seg.xLeft #needed sometimes? one time it was not initialized before use.
        if mc.WrapX == True:
            xStop = self.mapWidth*20
        else:
            xStop = self.mapWidth
        for xRightExtreme in range(seg.xLeft + lineFound - landOffset,xStop,1):
            if debugReport:            
                print "xRightExtreme = %(xr)4d" % {'xr':xRightExtreme}
            i = self.getIndex(xRightExtreme,seg.y + seg.dy)
            if debugReport:
                print "i = %d, seg.y + seg.dy = %d" % (i,seg.y + seg.dy)
                print "areaMap[i] = %d, matchValue match = %d" % (self.areaMap[i],matchValue == matchFunction(xRightExtreme,seg.y + seg.dy))
            if self.areaMap[i] == 0 and matchValue == matchFunction(xRightExtreme,seg.y + seg.dy):
                self.areaMap[i] = areaID
                self.size += 1
                if lineFound == False:
                    lineFound = True
                    xLeftExtreme = xRightExtreme #starting new line
                    if debugReport:
                        print "starting new line at xLeftExtreme= %(xl)4d" % {'xl':xLeftExtreme}
            elif lineFound == True: #found the right end of a line segment!                
                lineFound = False
                #put same direction on stack
                newSeg = LineSegment(seg.y + seg.dy,xLeftExtreme,xRightExtreme - 1,seg.dy)
                self.segStack.append(newSeg)
                if debugReport:
                    print "same direction to stack",str(newSeg)
                #determine if we must put reverse direction on stack
                if xLeftExtreme < seg.xLeft or xRightExtreme >= seg.xRight:
                    #out of shadow so put reverse direction on stack also
                    newSeg = LineSegment(seg.y + seg.dy,xLeftExtreme,xRightExtreme - 1,-seg.dy)
                    self.segStack.append(newSeg)
                    if debugReport:
                        print "opposite direction to stack",str(newSeg)
                if xRightExtreme >= seg.xRight + landOffset:
                    if debugReport:
                        print "finished with line"
                    break; #past the end of the parent line and this line ends
            elif lineFound == False and xRightExtreme >= seg.xRight + landOffset:
                if debugReport:
                    print "no additional lines found"
                break; #past the end of the parent line and no line found
            else:
                continue #keep looking for more line segments
        if lineFound == True: #still a line needing to be put on stack
            if debugReport:
                print "still needing to stack some segs"
            lineFound = False
            #put same direction on stack
            newSeg = LineSegment(seg.y + seg.dy,xLeftExtreme,xRightExtreme - 1,seg.dy)
            self.segStack.append(newSeg)
            if debugReport:
                print str(newSeg)
            #determine if we must put reverse direction on stack
            if xLeftExtreme < seg.xLeft or xRightExtreme - 1 > seg.xRight:
                #out of shadow so put reverse direction on stack also
                newSeg = LineSegment(seg.y + seg.dy,xLeftExtreme,xRightExtreme - 1,-seg.dy)
                self.segStack.append(newSeg)
                if debugReport:
                    print str(newSeg)
        
        return
    #for debugging
    def PrintAreaMap(self):
        
        print "Area Map"
        for y in range(self.mapHeight - 1,-1,-1):
            lineString = ""
            for x in range(self.mapWidth):
                mapLoc = self.areaMap[self.getIndex(x,y)]
                if mapLoc + 34 > 127:
                    mapLoc = 127 - 34
                lineString += chr(mapLoc + 34)
            lineString += "-" + str(y)
            print lineString
        oid = self.getOceanID()
        if oid == None or oid + 34 > 255:
            print "Ocean ID is unknown"
        else:
            print "Ocean ID is %(oid)4d or %(c)s" % {'oid':oid,'c':chr(oid + 34)}
        lineString = " "
        print lineString

        return
    def PrintList(self,s):
        for a in s:
            char = chr(a.ID + 34)
            lineString = str(a) + ' ' + char
            print lineString
            
class LineSegment :
    def __init__(self,y,xLeft,xRight,dy):
        self.y = y
        self.xLeft = xLeft
        self.xRight = xRight
        self.dy = dy
    def __str__ (self):
        string = "y = %(y)3d, xLeft = %(xl)3d, xRight = %(xr)3d, dy = %(dy)2d" % \
        {'y':self.y,'xl':self.xLeft,'xr':self.xRight,'dy':self.dy}
        return string
                       
class Area :
    def __init__(self,iD,size,water):
        self.ID = iD
        self.size = size
        self.water = water

    def __str__(self):
        string = "{ID = %(i)4d, size = %(s)4d, water = %(w)1d}" % \
        {'i':self.ID,'s':self.size,'w':self.water}
        return string
class AreaPlot :
    def __init__(self,x,y):
        self.x = x
        self.y = y
        self.avgDistance = -1
        
#OK! now that directions N,S,E,W are important, we have to keep in mind that
#the map plots are ordered from 0,0 in the SOUTH west corner! NOT the northwest
#corner! That means that Y increases as you go north.
class RiverMap :
    def __init__(self):
        #To provide global access without allocating alot of resources for
        #nothing, object initializer must be empty
        return
    def generateRiverMap(self):
        self.L = 0 #also denotes a 'pit' or 'flat'
        self.N = 1
        self.S = 2
        self.E = 3
        self.W = 4
        self.NE = 5
        self.NW = 6
        self.SE = 7
        self.SW = 8
        self.O = 5 #used for ocean or land without a river

        #averageHeightMap, flowMap, averageRainfallMap and drainageMap are offset from the other maps such that
        #each element coincides with a four tile intersection on the game map
        self.averageHeightMap = array('d')
        self.flowMap = array('i')
        self.averageRainfallMap = array('d')        
        self.drainageMap = array('d')
        self.riverMap = array('i')
        #initialize maps with zeros
        for i in range(0,mc.height*mc.width):
            self.averageHeightMap.append(0.0)
            self.flowMap.append(0)
            self.averageRainfallMap.append(0.0)
            self.drainageMap.append(0.0)
            self.riverMap.append(self.O)
        #Get highest intersection neighbor
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                maxHeight = 0.0;
                for yy in range(y,y-2,-1):
                    for xx in range(x,x+2):
                        ii = GetIndex(xx,yy)
                        #use an average hight of <0 to denote an ocean border
                        #this will save processing time later
                        if(sm.plotMap[ii] == mc.OCEAN):
                            maxHeight = -100.0
                        elif maxHeight < sm.heightMap[ii] and maxHeight >= 0:
                            maxHeight = sm.heightMap[ii]
                self.averageHeightMap[i] = maxHeight
        #Now try to silt in any lakes
        self.siltifyLakes()
        self.createLakeDepressions()
        #create flowMap by checking for the lowest of each 4 connected
        #neighbor plus self       
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                lowestAlt = self.averageHeightMap[i]
                if(lowestAlt < 0.0):
                    #if height is <0 then that means this intersection is
                    #adjacent to an ocean and has no flow
                    self.flowMap[i] = self.O
                else:
                    #First assume this place is lowest, like a 'pit'. Then
                    #for each place that is lower, add it to a list to be
                    #randomly chosen as the drainage path
                    drainList = list()
                    nonDrainList = list()
                    self.flowMap[i] = self.L 
                    ii = GetIndex(x,y+1)
                    #in the y direction, avoid wrapping
                    if(y > 0 and self.averageHeightMap[ii] < lowestAlt):
                        drainList.append(self.N)
                    else:
                        nonDrainList.append(self.N)
                    ii = GetIndex(x,y-1)
                    if(y < mc.height - 1 and self.averageHeightMap[ii] < lowestAlt):
                        drainList.append(self.S)
                    else:
                        nonDrainList.append(self.S)
                    ii = GetIndex(x-1,y)
                    if(self.averageHeightMap[ii] < lowestAlt):
                        drainList.append(self.W)
                    else:
                        nonDrainList.append(self.W)
                    ii = GetIndex(x+1,y)
                    if(self.averageHeightMap[ii] < lowestAlt):
                        drainList.append(self.E)
                    else:
                        nonDrainList.append(self.E)
                        
                    #never go straight when you have other choices
                    count = len(drainList)
                    if count == 3:
                        oppDir = GetOppositeDirection(nonDrainList[0])
                        for n in range(count):
                            if drainList[n] == oppDir:
                                del drainList[n]
                                break
                        count = len(drainList)
                            
                    if count > 0:
                        choice = int(PRand.random()*count)
#                        print count,choice
                        self.flowMap[i] = drainList[choice]
                  
        #Create average rainfall map so that each intersection is an average
        #of the rainfall from rm.rainMap
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                avg = 0.0;
                for yy in range(y,y-2,-1):
                    for xx in range(x,x+2):
                        ii = GetIndex(xx,yy)
                        avg += sm.rainFallMap[ii]
                avg = avg/4.0
                self.averageRainfallMap[i] = avg
               
        #Now use the flowMap as a guide to distribute average rainfall.
        #Wherever the most rainfall ends up is where the rivers will be.
        print "Distributing rainfall"
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                flow = self.flowMap[i]
                rainFall = self.averageRainfallMap[i]
                xx = x
                yy = y
                while(flow != self.L and flow != self.O):
                    if(flow == self.N):
                        yy += 1
                    elif(flow == self.S):
                        yy -= 1
                    elif(flow == self.W):
                        xx -= 1
                    elif(flow == self.E):
                        xx += 1
                    #wrap
                    if(xx < 0):
                        xx = mc.width - 1
                    elif(xx >= mc.width):
                        xx = 0
                    if(yy < 0):
                        yy = mc.height - 1
                    elif(yy >= mc.height):
                        yy = 0
                    #dump rainfall here
                    ii = GetIndex(xx,yy)
                    self.drainageMap[ii] += rainFall
                    #reset flow
                    flow = self.flowMap[ii]
                    
        
        riverThreshold = sm.plainsThreshold * mc.RiverThreshold
        for i in range(mc.height*mc.width):
            if(self.drainageMap[i] > riverThreshold):
##                    riverCount += 1
                self.riverMap[i] = self.flowMap[i]
            else:
                self.riverMap[i] = self.O

        #at this point river should be in tolerance or close to it
        #riverMap is ready for use

    def rxFromPlot(self,x,y,direction):
        if direction == self.NE:
            return x,y + 1
        if direction == self.SW:
            return x - 1,y 
        if direction == self.SE:
            return x,y 
        raise ValueError,"rxFromPlot using bad direction input"
    
    def siltifyLakes(self):
        lakeList = []
        onQueueMap = array('i')
        for y in range(mc.height):
            for x in range(mc.width):
                onQueueMap.append(0)
                i = GetIndex(x,y)
                if self.isLake(x,y):
                    lakeList.append((x,y,1))
                    onQueueMap[i] = 1
##        print "initial lakes = %d" % (len(lakeList))
        largestLength = len(lakeList)
        while len(lakeList) > 0:
##            print "len = %d" % (len(lakeList))
            if len(lakeList) > largestLength:
                largestLength = len(lakeList)
            x,y,lakeSize = lakeList[0]
            del lakeList[0]
            i = GetIndex(x,y)
            onQueueMap[i] = 0

            if lakeSize > mc.maxSiltPanSize:
                continue
            lakeSize += 1
##            print x,y
            lowestNeighborAlt = self.getLowestNeighborAltitude(x,y)
            self.averageHeightMap[i] = lowestNeighborAlt + 0.005
            for direction in range(1,5,1):
                xx,yy = GetXYFromDirection(x,y,direction)
                ii = GetIndex(xx,yy)
                if ii == -1:
                    continue
                if self.isLake(xx,yy) and onQueueMap[ii] == 0:
##                    print "appending lake at %d,%d" % (xx,yy)
                    lakeList.append((xx,yy,lakeSize))
                    onQueueMap[ii] = 1
##        print "returning from siltify"
##        print "largest length of lakeList = %d" % largestLength
        return
    def isLake(self,x,y):
        i = GetIndex(x,y)
        alt = self.averageHeightMap[i]
        if alt < 0.0:
            return False
        for direction in range(1,5,1):
            xx,yy = GetXYFromDirection(x,y,direction)
            ii = GetIndex(xx,yy)
            if ii == -1:
                continue
            if self.averageHeightMap[ii] < alt:
                return False
        return True
    def getLowestNeighborAltitude(self,x,y):
        lowest = 1.0
        for direction in range(1,5,1):
            xx,yy = GetXYFromDirection(x,y,direction)
            ii = GetIndex(xx,yy)
            if ii == -1:
                continue
            if self.averageHeightMap[ii] < lowest:
                lowest = self.averageHeightMap[ii]
        return lowest
    def createLakeDepressions(self):
        lakeList = []
        for y in range(mc.height):
            for x in range(mc.width):
                i = GetIndex(x,y)
                if self.averageHeightMap[i] > mc.minLakeAltitude:
                    lakeList.append((x,y))
        lakeList = ShuffleList(lakeList)
        numLakes = int(mc.height * mc.width * mc.numberOfLakesPerPlot)
        for n in range(numLakes):
            x,y = lakeList[n]
            i = GetIndex(x,y)
            lowestAlt = self.getLowestNeighborAltitude(x,y)
            if lowestAlt < 0.0:
                continue
            self.averageHeightMap[i] = lowestAlt - 0.001
        
    
    def printRiverMap(self):
        print "River Map"
        wz = WindZones(mc.height,80,-80)
        for y in range(mc.height - 1,-1,-1):
            lineString = ""
            for x in range(mc.width):
                mapLoc = self.riverMap[GetIndex(x,y)]
                if mapLoc == self.O:
                    lineString += '.'
                elif mapLoc == self.L:
                    lineString += 'L'
                elif mapLoc == self.N:
                    lineString += 'N'
                elif mapLoc == self.S:
                    lineString += 'S'
                elif mapLoc == self.E:
                    lineString += 'E'
                elif mapLoc == self.W:
                    lineString += 'W'
            lineString += "-" + wz.GetZoneName(wz.GetZone(y))
            print lineString
        lineString = " "
        print lineString
            
    def printFlowMap(self):
        print "Flow Map"
        wz = WindZones(mc.height,80,-80)
        for y in range(mc.height - 1,-1,-1):
            lineString = ""
            for x in range(mc.width):
                mapLoc = self.flowMap[GetIndex(x,y)]
                if mapLoc == self.O:
                    lineString += '.'
                elif mapLoc == self.L:
                    lineString += 'L'
                elif mapLoc == self.N:
                    lineString += 'N'
                elif mapLoc == self.S:
                    lineString += 'S'
                elif mapLoc == self.E:
                    lineString += 'E'
                elif mapLoc == self.W:
                    lineString += 'W'
            lineString += "-" + wz.GetZoneName(wz.GetZone(y))
            print lineString
        lineString = " "
        print lineString
    def printRiverAndTerrainAlign(self):
        print "River Alignment Check"
        for y in range(mc.height - 1,-1,-1):
            lineString1 = ""
            lineString2 = ""
            for x in range(mc.width):
                mapLoc = sm.terrainMap[GetIndex(x,y)]
                if mapLoc == mc.OCEAN:
                    lineString1 += ',.'
                elif mapLoc == mc.COAST:
                    lineString1 += ',.'
                elif mapLoc == mc.DESERT:
                    lineString1 += 'D.'
                elif mapLoc == mc.GRASS:
                    lineString1 += 'R.'
                elif mapLoc == mc.PLAINS:
                    lineString1 += 'P.'
                elif mapLoc == mc.TUNDRA:
                    lineString1 += 'T.'
                elif mapLoc == mc.MARSH:
                    lineString1 += 'M.'
                elif mapLoc == mc.SNOW:
                    lineString1 += 'I.'
                mapLoc = rm.riverMap[GetIndex(x,y)]
                if mapLoc == rm.O:
                    lineString2 += '..'
                elif mapLoc == rm.L:
                    lineString2 += '.L'
                elif mapLoc == rm.N:
                    lineString2 += '.^'
                elif mapLoc == rm.S:
                    lineString2 += '.v'
                elif mapLoc == rm.E:
                    lineString2 += '.>'
                elif mapLoc == rm.W:
                    lineString2 += '.<'
##            lineString1 += "-" + wz.GetZoneName(wz.GetZone(y))
##            lineString2 += "-" + wz.GetZoneName(wz.GetZone(y))
            print lineString1
            print lineString2
        lineString1 = " "
        print lineString1
class EuropeMap :
    def __init__(self):
        return
    def initialize(self):
        self.europeMap = array('i')
        for i in range(mc.width*mc.height):
            self.europeMap.append(0)
            
class BonusPlacer :
    def __init__(self):
        return
    def AddBonuses(self):
        gc = CyGlobalContext()
        gameMap = CyMap()
        gameMap.recalculateAreas()
        self.AssignBonusAreas()
        numBonuses = gc.getNumBonusInfos()
        for order in range(numBonuses):
            placementList = []
            for i in range(numBonuses):
                bonusInfo = gc.getBonusInfo(self.bonusList[i].eBonus)
                if bonusInfo.getPlacementOrder() == order:
                    for n in range(self.bonusList[i].desiredBonusCount):
                        placementList.append(self.bonusList[i].eBonus)
                        
            #Create a list of map indices and shuffle them
            plotIndexList = []
            for i in range(mc.width*mc.height):
                plotIndexList.append(i)
            plotIndexList = ShuffleList(plotIndexList)
            
            if len(placementList) > 0:
                placementList = ShuffleList(placementList)
                for eBonus in placementList:
                    self.AddBonusType(eBonus,plotIndexList)                        
                

        #now check to see that all resources have been placed at least once, this
        #pass ignoring area rules
        for i in range(numBonuses):
            bonus = self.bonusList[i]
            if bonus.currentBonusCount == 0 and bonus.desiredBonusCount > 0:
                self.AddEmergencyBonus(bonus,False)

        #now check again to see that all resources have been placed at least once,
        #this time ignoring area rules and also class spacing
        for i in range(numBonuses):
            bonus = self.bonusList[i]
            if bonus.currentBonusCount == 0 and bonus.desiredBonusCount > 0:
                self.AddEmergencyBonus(bonus,True)                                       

        #now report resources that simply could not be placed
        for i in range(numBonuses):
            bonus = self.bonusList[i]
            if bonus.currentBonusCount == 0 and bonus.desiredBonusCount > 0:
                bonusInfo = gc.getBonusInfo(bonus.eBonus)
                print "No room at all found for %(bt)s!!!" % {"bt":bonusInfo.getType()} 
        return
    def AddEmergencyBonus(self,bonus,ignoreClass):
        gc = CyGlobalContext()
        gameMap = CyMap()
        featureForest = gc.getInfoTypeForString("FEATURE_FOREST")
        plotIndexList = list()
        for i in range(mc.width*mc.height):
            plotIndexList.append(i)
        plotIndexList = ShuffleList(plotIndexList)
        bonusInfo = gc.getBonusInfo(bonus.eBonus)
        for i in range(len(plotIndexList)):
            index = plotIndexList[i]
            plot = gameMap.plotByIndex(index)
            x = plot.getX()
            y = plot.getY()
            if (ignoreClass and self.PlotCanHaveBonus(plot,bonus.eBonus,False,True)) or \
            self.CanPlaceBonusAt(plot,bonus.eBonus,False,True):
                #temporarily remove any feature
                featureEnum = plot.getFeatureType()
                if featureEnum == featureForest:
                    featureVariety = plot.getFeatureVariety()
                    plot.setFeatureType(FeatureTypes.NO_FEATURE,-1)
                #place bonus
                plot.setBonusType(bonus.eBonus)
                bonus.currentBonusCount += 1
                #restore the feature if possible
                if featureEnum == featureForest:
                    if bonusInfo == None or bonusInfo.isFeature(featureEnum):
                        plot.setFeatureType(featureEnum,featureVariety)
                print "Emergency placement of 1 %(bt)s" % {"bt":bonusInfo.getType()} 
                break
         
        return
    def AddBonusType(self,eBonus,plotIndexList):
        gc = CyGlobalContext()
        gameMap = CyMap()
        featureForest = gc.getInfoTypeForString("FEATURE_FOREST")
        #first get bonus/area link
        for i in range(gc.getNumBonusInfos()):
            if self.bonusList[i].eBonus == eBonus:
                bonus = self.bonusList[i]
        bonusInfo = gc.getBonusInfo(eBonus)
        
        if bonus.currentBonusCount >= bonus.desiredBonusCount:
            return False

        bonusPlaced = False
        #now add bonuses
        for i in range(len(plotIndexList)):
            index = plotIndexList[i]
            plot = gameMap.plotByIndex(index)
            x = plot.getX()
            y = plot.getY()
            if self.CanPlaceBonusAt(plot,eBonus,False,False):
                #temporarily remove any feature
                featureEnum = plot.getFeatureType()
                if featureEnum == featureForest:
                    featureVariety = plot.getFeatureVariety()
                    plot.setFeatureType(FeatureTypes.NO_FEATURE,-1)
                #place bonus
                plot.setBonusType(eBonus)
                bonusPlaced = True
                bonus.currentBonusCount += 1
                #restore the feature if possible
                if featureEnum == featureForest:
                    if bonusInfo == None or bonusInfo.isFeature(featureEnum) or (bonusInfo.getTechReveal() != TechTypes.NO_TECH):
                        plot.setFeatureType(featureEnum,featureVariety)
                groupRange = bonusInfo.getGroupRange()
                for dx in range(-groupRange,groupRange + 1):
                    for dy in range(-groupRange,groupRange + 1):
                        if bonus.currentBonusCount < bonus.desiredBonusCount:
                            loopPlot = self.plotXY(x,y,dx,dy)
                            if loopPlot != None:
                                if loopPlot.getX() == -1:
                                    raise ValueError, "plotXY returns invalid plots plot= %(x)d, %(y)d" % {"x":x,"y":y}
                                if self.CanPlaceBonusAt(loopPlot,eBonus,False,False):
                                    if PRand.randint(0,99) < bonusInfo.getGroupRand():
                                        #temporarily remove any feature
                                        featureEnum = loopPlot.getFeatureType()
                                        if featureEnum == featureForest:
                                            featureVariety = loopPlot.getFeatureVariety()
                                            loopPlot.setFeatureType(FeatureTypes.NO_FEATURE,-1)
                                        #place bonus
                                        loopPlot.setBonusType(eBonus)
                                        bonus.currentBonusCount += 1
                                        #restore the feature if possible
                                        if featureEnum == featureForest:
                                            if bonusInfo == None or bonusInfo.isFeature(featureEnum) or (bonusInfo.getTechReveal() != TechTypes.NO_TECH):
                                                loopPlot.setFeatureType(featureEnum,featureVariety)
            if bonusPlaced:
                break
        return bonusPlaced
    
    def plotXY(self,x,y,dx,dy):
        gameMap = CyMap()
        #The one that civ uses will return junk so I have to make one
        #that will not
        x = (x + dx) % mc.width
        y = y + dy
        if y < 0 or y > mc.height - 1:
            return None
        return gameMap.plot(x,y)
        
    def AssignBonusAreas(self):
        gc = CyGlobalContext()
        self.areas = CvMapGeneratorUtil.getAreas()
        gameMap = CyMap()
        self.bonusList = list()
        #Create and shuffle the bonus list and keep tally on
        #one-area bonuses and find the smallest min area requirement
        #among those
        numUniqueBonuses = 0
        minLandAreaSize = -1
        for i in range(gc.getNumBonusInfos()):
            bonus = BonusArea()
            bonus.eBonus = i
            self.bonusList.append(bonus)
            bonusInfo = gc.getBonusInfo(i)
            if bonusInfo.isOneArea() == True:
                numUniqueBonuses += 1
                minAreaSize = bonusInfo.getMinAreaSize()
                if (minLandAreaSize == -1 or minLandAreaSize > minAreaSize) and \
                minAreaSize > 0:
                    minLandAreaSize = minAreaSize
        self.bonusList = ShuffleList(self.bonusList)
        numBonuses = gc.getNumBonusInfos()
        for i in range(numBonuses):
            self.bonusList[i].desiredBonusCount = self.CalculateNumBonusesToAdd(self.bonusList[i].eBonus)
            bonusInfo = gc.getBonusInfo(self.bonusList[i].eBonus)
            eBonus = self.bonusList[i].eBonus
            if bonusInfo.isOneArea() == False:
                continue #Only assign areas to area bonuses
##            print "Trying to find room for %(bt)s, desiredCount=%(dc)d" % {"bt":bonusInfo.getType(),"dc":self.bonusList[i].desiredBonusCount}
            areaSuitabilityList = list()
            for area in self.areas:
                if area.getNumTiles() >= minLandAreaSize:
                    aS = AreaSuitability(area.getID())
                    aS.suitability,aS.numPossible = self.CalculateAreaSuitability(area,eBonus)
                    areaSuitabilityList.append(aS)
##                    print "suitability on areaID=%(aid)d, size=%(s)d is %(r)f" % \
##                    {"aid":area.getID(),"s":area.getNumTiles(),"r":aS.suitability}
            #Calculate how many areas to assign (numUniqueBonuses will be > 0 if we get here)
##            areasPerBonus = (len(areaSuitabilityList)/numUniqueBonuses) + 1
            areasPerBonus =  1
            #Sort areaSuitabilityList best first
            areaSuitabilityList.sort(lambda x,y:cmp(x.numPossible,y.numPossible))
            areaSuitabilityList.reverse()
            #assign the best areas to this bonus
            for n in range(areasPerBonus):
                self.bonusList[i].areaList.append(areaSuitabilityList[n].areaID)
            #assign areas that have a high suitability also
            for n in range(areasPerBonus,len(areaSuitabilityList)):
                if areaSuitabilityList[n].suitability > 0.3:
                    self.bonusList[i].areaList.append(areaSuitabilityList[n].areaID)
        return
    def CanPlaceBonusAt(self,plot,eBonus,bIgnoreLatitude,bIgnoreArea):
        gc = CyGlobalContext()
        gameMap = CyMap()
        x = plot.getX()
        y = plot.getY()
        areaID = plot.getArea()
        if self.PlotCanHaveBonus(plot,eBonus,bIgnoreLatitude,bIgnoreArea) == False:
            return False
        for i in range(DirectionTypes.NUM_DIRECTION_TYPES):
            loopPlot = plotDirection(x,y,DirectionTypes(i))
            if loopPlot.getBonusType(TeamTypes.NO_TEAM) != BonusTypes.NO_BONUS and loopPlot.getBonusType(TeamTypes.NO_TEAM) != eBonus:
               return False

        bonusInfo = gc.getBonusInfo(eBonus)
        classInfo = gc.getBonusClassInfo(bonusInfo.getBonusClassType())
        if plot.isWater() == True:
            if gameMap.getNumBonusesOnLand(eBonus) * 100/(gameMap.getNumBonuses(eBonus) + 1) < bonusInfo.getMinLandPercent():
                return False
        #Make sure there are no bonuses of the same class (but a different type) nearby:
        if classInfo != None:
            try:
                iRange = classInfo.getUniqueRange()
            except:
                iRange = classInfo.getUniqueRange #<--attribute for vanilla
                
            iRange = max(0,int(iRange - (round(mc.BonusBonus) - 1)))
            
            for dx in range(-iRange,iRange+1):
                for dy in range(-iRange,iRange+1):
                    loopPlot = self.plotXY(x,y,dx,dy)
                    if loopPlot != None:
                        if areaID == loopPlot.getArea():
                            if plotDistance(x, y, loopPlot.getX(), loopPlot.getY()) <= iRange:
                                eOtherBonus = loopPlot.getBonusType(TeamTypes.NO_TEAM)
                                if eOtherBonus != BonusTypes.NO_BONUS:
                                    if gc.getBonusInfo(eOtherBonus).getBonusClassType() == bonusInfo.getBonusClassType():
                                        return False
        #Make sure there are no bonuses of the same type nearby:
        iRange = bonusInfo.getUniqueRange()
        iRange = max(0,int(iRange - (round(mc.BonusBonus) - 1)))
        for dx in range(-iRange,iRange+1):
            for dy in range(-iRange,iRange+1):
                loopPlot = self.plotXY(x,y,dx,dy)
                if loopPlot != None:
                    if areaID == loopPlot.getArea():
                        if plotDistance(x, y, loopPlot.getX(), loopPlot.getY()) <= iRange:
                            eOtherBonus = loopPlot.getBonusType(TeamTypes.NO_TEAM)
                            if eOtherBonus != BonusTypes.NO_BONUS:
                                if eOtherBonus == eBonus:
                                    return False
                           
                    
        return True
    def PlotCanHaveBonus(self,plot,eBonus,bIgnoreLatitude,bIgnoreArea):
        #This function is like CvPlot::canHaveBonus but will
        #ignore blocking features and checks for a valid area. 
        gc = CyGlobalContext()
        featureForest = gc.getInfoTypeForString("FEATURE_FOREST")
        if eBonus == BonusTypes.NO_BONUS:
            return True
        if plot.getBonusType(TeamTypes.NO_TEAM) != BonusTypes.NO_BONUS:
            return False
        if plot.isPeak() == True:
            return False
        bonusInfo = gc.getBonusInfo(eBonus)
        #Here is the change from canHaveBonus. Forest does not block bonus
        requiresForest = bonusInfo.isFeature(featureForest)
        plotIsForest = plot.getFeatureType() == featureForest
        #To avoid silk and spices on ice/tundra
        if plotIsForest and requiresForest:
            if bonusInfo.isFeatureTerrain(plot.getTerrainType()) == False:
                return False
        #now that bonuses that require forest are dealt with, count forest
        #as no feature
        else:
            if plot.getFeatureType() != FeatureTypes.NO_FEATURE and not plotIsForest:
                if bonusInfo.isFeature(plot.getFeatureType()) == False:
                    return False           
                if bonusInfo.isFeatureTerrain(plot.getTerrainType()) == False:
                    return False              
            else:
                if bonusInfo.isTerrain(plot.getTerrainType()) == False:
                    return False
                
        if plot.isHills() == True:
            if bonusInfo.isHills() == False:
                return False
        if plot.isFlatlands() == True:
            if bonusInfo.isFlatlands() == False:
                return False
        if bonusInfo.isNoRiverSide() == True:
            if plot.isRiverSide() == True:
                return False
        if bonusInfo.getMinAreaSize() != -1:
            if plot.area().getNumTiles() < bonusInfo.getMinAreaSize():
                return False
        if bIgnoreLatitude == False:
            if plot.getLatitude() > bonusInfo.getMaxLatitude():
                return False
            if plot.getLatitude() < bonusInfo.getMinLatitude():
                return False
        if plot.isPotentialCityWork() == False:
            return False
        
        if (bIgnoreArea == False and bonusInfo.isOneArea() == True and
                 mc.spreadResources == False):
            areaID = plot.getArea()
            areaFound = False
            for i in range(len(self.bonusList)):
                if self.bonusList[i].eBonus == eBonus:
                    areaList = self.bonusList[i].areaList
                    for n in range(len(areaList)):
                        if areaList[n] == areaID:
                            areaFound = True
                            break
                    if areaFound == True:
                        break
            if areaFound == False:
                return False
                        
        return True
    def CalculateNumBonusesToAdd(self,eBonus):
        #This is like the function in CvMapGenerator except it uses
        #self.PlotCanHaveBonus instead of CvPlot::canHaveBonus
        gc = CyGlobalContext()
        gameMap = CyMap()
        game = CyGame()
        bonusInfo = gc.getBonusInfo(eBonus)
        rand1 = PRand.randint(0,bonusInfo.getRandAppearance1())
        rand2 = PRand.randint(0,bonusInfo.getRandAppearance2())
        rand3 = PRand.randint(0,bonusInfo.getRandAppearance3())
        rand4 = PRand.randint(0,bonusInfo.getRandAppearance4())
        baseCount = bonusInfo.getConstAppearance() + rand1 + rand2 + rand3 + rand4

        bIgnoreLatitude = False
        bIgnoreArea = True
        landTiles = 0
        numPossible = 0
        if bonusInfo.getTilesPer() > 0:
            for i in range(mc.width*mc.height):
                plot = gameMap.plotByIndex(i)
                if self.PlotCanHaveBonus(plot,eBonus,bIgnoreLatitude,bIgnoreArea):
                    numPossible += 1
            landTiles += numPossible/bonusInfo.getTilesPer()
        players = game.countCivPlayersAlive() * bonusInfo.getPercentPerPlayer()/100
        bonusCount = baseCount * (landTiles + players)/100
        bonusCount = max(1,int(bonusCount * mc.BonusBonus))
##        print "Calculating bonus amount for %(bt)s" % {"bt":bonusInfo.getType()}
##        print "baseCount=%(bc)d, numPossible=%(np)d, landTiles=%(lt)d, players=%(p)d" % \
##        {"bc":baseCount,"np":numPossible,"lt":landTiles,"p":players}
##        print ""
        return bonusCount
    
    def GetUniqueBonusTypeCountInArea(self,area):
        gc = CyGlobalContext()
        areaID = area.getID()
        uniqueBonusCount = 0
        for i in range(len(self.bonusList)):
            areaList = self.bonusList[i].areaList
            bonusInfo = gc.getBonusInfo(self.bonusList[i].eBonus)
            if bonusInfo.isOneArea() == False:
                continue
            for n in range(len(areaList)):
                if areaList[n] == areaID:
                    uniqueBonusCount += 1
                    break

        return uniqueBonusCount 
    
    def GetSameClassTypeCountInArea(self,area,eBonus):
        gc = CyGlobalContext()
        areaID = area.getID()
        uniqueBonusCount = 0
        bonusInfo = gc.getBonusInfo(eBonus)
        eClass = bonusInfo.getBonusClassType()
        if eClass == BonusClassTypes.NO_BONUSCLASS:
            return 0
        classInfo = gc.getBonusClassInfo(eClass)
        if classInfo == None:
            return 0

        try:
            uRange = classInfo.getUniqueRange()
        except:
            uRange = classInfo.getUniqueRange #<--vanilla Civ4

        uRange = max(0,int(uRange - (round(mc.BonusBonus) - 1)))
                        
        for i in range(len(self.bonusList)):
            areaList = self.bonusList[i].areaList
            bonusInfo = gc.getBonusInfo(self.bonusList[i].eBonus)
            if bonusInfo.isOneArea() == False:
                continue
            if bonusInfo.getBonusClassType() != eClass:
                continue
            for n in range(len(areaList)):
                if areaList[n] == areaID:
                    uniqueBonusCount += 1
                    break
        #Same class types tend to really crowd out any bonus
        #types that are placed later. A single cow can block
        #5 * 5 squares of pig territory for example. Probably
        #shouldn't place them on the same area at all, but
        #sometimes it might be necessary.
        return uniqueBonusCount * uRange * uRange
   
    def CalculateAreaSuitability(self,area,eBonus):
        gc = CyGlobalContext()
        gameMap = CyMap()
        areaID = area.getID()
        uniqueTypesInArea = self.GetUniqueBonusTypeCountInArea(area)
        sameClassTypesInArea = self.GetSameClassTypeCountInArea(area,eBonus)
        #Get the raw number of suitable tiles
        numPossible = 0
        for i in range(mc.width*mc.height):
            plot = gameMap.plotByIndex(i)
            if plot.getArea() == areaID:
                if self.PlotCanHaveBonus(plot,eBonus,False,True):
                    numPossible += 1
        numPossible = numPossible/(uniqueTypesInArea + sameClassTypesInArea + 1)
        suitability = float(numPossible)/float(area.getNumTiles())
        return suitability,numPossible
#Global Access
bp = BonusPlacer()

class BonusArea :
    def __init__(self):
        self.eBonus = -1
        self.desiredBonusCount = -1
        self.currentBonusCount = 0
        self.areaList = list()
            
class AreaSuitability :
    def __init__(self,areaID):
        self.areaID = areaID
        self.suitability = 0
        self.numPossible = 0
        
class StartingPlotFinder :
    def __init__(self):
        return
    def SetStartingPlots(self):
        try:
            gc = CyGlobalContext()
            gameMap = CyMap()
            iPlayers = gc.getGame().countCivPlayersEverAlive()
            gameMap.recalculateAreas()
            areas = CvMapGeneratorUtil.getAreas()

            #get old/new world status
            areaOldWorld = self.setupOldWorldAreaList()
            
            print "len(areaOldWorld) = %d" % len(areaOldWorld)
            
            #Shuffle players so the same player doesn't always get the first pick.
            #lifted from Highlands.py that ships with Civ.
            player_list = []
            for plrCheckLoop in range(gc.getMAX_CIV_PLAYERS()):
                    if CyGlobalContext().getPlayer(plrCheckLoop).isEverAlive():
                            player_list.append(plrCheckLoop)
            shuffledPlayers = []
            for playerLoop in range(iPlayers):
                    # Disabled: First player should get best start
                    #iChoosePlayer = PRand.randint(0,len(player_list)-1)
                    iChoosePlayer = playerLoop # Do not shuffle
                    # Give Caulixtla map Jungle start option
                    if mc.randomSeed == -3 and len(player_list) > 7:
                       if playerLoop == 0:
                           iChoosePlayer = 6
                       elif playerLoop == 6:
                           iChoosePlayer = 0
                    shuffledPlayers.append(player_list[iChoosePlayer])
                    #del player_list[iChoosePlayer]

            self.startingAreaList = list()
            for i in range(len(areas)):
                if areaOldWorld[i] == True and areas[i].getNumTiles() > 5:
                    startArea = StartingArea(areas[i].getID())
                    self.startingAreaList.append(startArea)

            #Get the value of the whole old world
            oldWorldValue = 0
            for i in range(len(self.startingAreaList)):
                oldWorldValue += self.startingAreaList[i].rawValue

            #calulate value per player of old world
            oldWorldValuePerPlayer = oldWorldValue/len(shuffledPlayers)

            #Sort startingAreaList by rawValue
            self.startingAreaList.sort(lambda x, y: cmp(x.rawValue, y.rawValue))

            #Get rid of areas that have less value than oldWorldValuePerPlayer
            #as they are too small to put a player on, however leave at least
            #half as many continents as there are players, just in case the
            #continents are *all* quite small. 
            numAreas = max(1,len(self.startingAreaList) - len(shuffledPlayers)/2)
            for i in range(numAreas):
                if self.startingAreaList[0].rawValue < oldWorldValuePerPlayer:
                    del self.startingAreaList[0]
                else:
                    break #All remaining should be big enough
                
            #Recalculate the value of the whole old world
            oldWorldValue = 0
            for i in range(len(self.startingAreaList)):
                oldWorldValue += self.startingAreaList[i].rawValue

            #Recalulate value per player of old world so we are starting more
            #accurately
            oldWorldValuePerPlayer = oldWorldValue/len(shuffledPlayers)

            #Record the ideal number of players for each continent
            for startingArea in self.startingAreaList:
                startingArea.idealNumberOfPlayers = int(round(float(startingArea.rawValue)/float(oldWorldValuePerPlayer)))

            #Now we want best first
            self.startingAreaList.reverse()
            print "number of starting areas is %(s)3d" % {"s":len(self.startingAreaList)}

            iterations = 0
            while True:
                iterations += 1
                if iterations > 20:
                    raise ValueError, "Too many iterations in starting area choosing loop."
                chosenStartingAreas = list()
                playersPlaced = 0
                #add up idealNumbers
                idealNumbers = 0
                for startingArea in self.startingAreaList:
                    idealNumbers += startingArea.idealNumberOfPlayers
                if idealNumbers < len(shuffledPlayers):
                    self.startingAreaList[0].idealNumberOfPlayers += 1
                elif idealNumbers > len(shuffledPlayers):
                    self.startingAreaList[0].idealNumberOfPlayers -= 1

                #Choose areas
                for startingArea in self.startingAreaList:
                    if startingArea.idealNumberOfPlayers + playersPlaced <= len(shuffledPlayers):
                        chosenStartingAreas.append(startingArea)
                        playersPlaced += startingArea.idealNumberOfPlayers
                        
                #add up idealNumbers again
                idealNumbers = 0
                for startingArea in chosenStartingAreas:
                    idealNumbers += startingArea.idealNumberOfPlayers
                if idealNumbers == len(shuffledPlayers):
                    break
                
            for startingArea in chosenStartingAreas:
                for i in range(startingArea.idealNumberOfPlayers):
                    startingArea.playerList.append(shuffledPlayers[0])
                    del shuffledPlayers[0]
                startingArea.FindStartingPlots()
                            
            if len(shuffledPlayers) > 0:
                raise ValueError,"Some players not placed in starting plot finder!"

            #Now set up for normalization
            self.plotList = list()
            for startingArea in self.startingAreaList:
                for i in range(len(startingArea.plotList)):
    ##                print len(startingArea.plotList)
                    self.plotList.append(startingArea.plotList[i])
                    
            #Remove bad features. (Jungle in the case of standard game)
            #also ensure minimum hills
            for i in range(len(self.plotList)):
                if self.plotList[i].vacant == True:
                    continue
                             
                self.ensureMinimumHills(self.plotList[i].x,self.plotList[i].y)
            
                            
            #find the best totalValue
            self.plotList.sort(lambda x,y:cmp(x.totalValue,y.totalValue))
            self.plotList.reverse()
            bestTotalValue = self.plotList[0].totalValue
            print "bestTotalValue = %(b)6d" % {"b":bestTotalValue}
            for i in range(len(self.plotList)):
                if self.plotList[i].vacant == True:
                    continue
                currentTotalValue = self.plotList[i].totalValue
                percentLacking = 1.0 - (float(currentTotalValue)/float(bestTotalValue))
                if percentLacking > 0:
                    bonuses = min(5,int(percentLacking/0.2))
                    print "boosting plot by %(bv)d" % \
                    {"bv":bonuses}
                    self.boostCityPlotValue(self.plotList[i].x,self.plotList[i].y,bonuses,self.plotList[i].isCoast())

            #add bonuses due to player difficulty settings        
            self.addHandicapBonus()

        except Exception, e:
            errorPopUp("PerfectWorld's starting plot finder has failed due to a rarely occuring bug, and this map likely has unfair starting locations. You may wish to quit this game and generate a new map.")
            raise Exception, e            
        return
    
    def setupOldWorldAreaList(self):
        gc = CyGlobalContext()
        gameMap = CyMap()
        #get official areas and make corresponding lists that determines old
        #world vs. new and also the pre-settled value.
        areas = CvMapGeneratorUtil.getAreas()
        areaOldWorld = list()

        print "number of map areas = %d" % len(areas)
        for i in range(len(areas)):
            for pI in range(mc.height*mc.width):
                plot = gameMap.plotByIndex(pI)
                if plot.getArea() == areas[i].getID():
                    if mc.AllowNewWorld and continentMap.areaMap.areaMap[pI] == continentMap.newWorldID:
                        areaOldWorld.append(False)#new world true = old world false
                    else:
                        areaOldWorld.append(True)
                    break

            
        return areaOldWorld
    def getCityPotentialValue(self,x,y):
        gc = CyGlobalContext()
        gameMap = CyMap()
#        game.gc.getGame()
        totalValue = 0
        totalFood = 0
        plot = gameMap.plot(x,y)
        if plot.isWater() == True:
            return 0,0
        if plot.isImpassable() == True:
            return 0,0
        cityPlotList = list()
        #The StartPlot class has a nifty function to determine
        #salt water vs. fresh
        start = plot
        sPlot = StartPlot(x,y,0)
        for i in range(gc.getNUM_CITY_PLOTS()):
            plot = plotCity(x,y,i)
            if not plot.isWater() and plot.getArea() != start.getArea():
                food,value = 0,0
            else:
                food,value = self.getPlotPotentialValue(plot.getX(),plot.getY(),sPlot.isCoast())
            totalFood += food
            cPlot = CityPlot(food,value)
            cityPlotList.append(cPlot)
        usablePlots = totalFood/gc.getFOOD_CONSUMPTION_PER_POPULATION()
        cityPlotList.sort(lambda x,y:cmp(x.value,y.value))
        cityPlotList.reverse()
        #value is obviously limited to available food
        if usablePlots > gc.getNUM_CITY_PLOTS():
            usablePlots = gc.getNUM_CITY_PLOTS()
        for i in range(usablePlots):
            cPlot = cityPlotList[i]
            totalValue += cPlot.value
        #The StartPlot class has a nifty function to determine
        #salt water vs. fresh
        sPlot = StartPlot(x,y,0)
        if sPlot.isCoast() == True:
            totalValue = int(float(totalValue) * mc.CoastalCityValueBonus)
        if sPlot.isRiverSide() == True:
            totalValue = int(float(totalValue) * mc.RiverCityValueBonus)
                
        return totalFood,totalValue
    def getPlotPotentialValue(self,x,y,coastalCity):
        gc = CyGlobalContext()
        gameMap = CyMap()
        game = gc.getGame()
        debugOut = False
        value = 0
        commerce = 0
        food = 0
        production = 0
        plot = gameMap.plot(x,y)
        if debugOut: print "Evaluating plot x = %(x)d, y = %(y)d" % {"x":x,"y":y}
        commerce += plot.calculateBestNatureYield(YieldTypes.YIELD_COMMERCE,TeamTypes.NO_TEAM)
        food += plot.calculateBestNatureYield(YieldTypes.YIELD_FOOD,TeamTypes.NO_TEAM)
        production += plot.calculateBestNatureYield(YieldTypes.YIELD_PRODUCTION,TeamTypes.NO_TEAM)
        if debugOut: print "Natural yields. Food=%(f)d, Production=%(p)d, Commerce=%(c)d" % \
        {"f":food,"p":production,"c":commerce}
        #Get best bonus improvement score. Test tachnology era of bonus
        #first, then test each improvement
        bestImp = None
        bonusEnum = plot.getBonusType(TeamTypes.NO_TEAM) 
        bonusInfo = gc.getBonusInfo(bonusEnum)
        if bonusInfo != None and (gc.getTechInfo(bonusInfo.getTechCityTrade()) == None or \
        gc.getTechInfo(bonusInfo.getTechCityTrade()).getEra() <= game.getStartEra()) and \
        (gc.getTechInfo(bonusInfo.getTechReveal()) == None or \
        gc.getTechInfo(bonusInfo.getTechReveal()).getEra() <= game.getStartEra()): 
            if bonusInfo == None:
                if debugOut: print "Bonus Type = None"
            else:
                if debugOut: print "Bonus Type = %(b)s <------------------------------------------------------------" % {"b":bonusInfo.getType()}
            commerce += bonusInfo.getYieldChange(YieldTypes.YIELD_COMMERCE)
            food += bonusInfo.getYieldChange(YieldTypes.YIELD_FOOD)
            production += bonusInfo.getYieldChange(YieldTypes.YIELD_PRODUCTION)
            if debugOut: print "Bonus yields. Food=%(f)d, Production=%(p)d, Commerce=%(c)d" % \
            {"f":food,"p":production,"c":commerce}
        else:
            bonusEnum = -1
            bonusInfo = None
        improvementList = list()
        for n in range(gc.getNumBuildInfos()):
            #Test for improvement validity
            buildInfo = gc.getBuildInfo(n)
            impEnum = buildInfo.getImprovement()
            impInfo = gc.getImprovementInfo(impEnum)
            if impInfo == None:
                continue
            #some mods use improvements for other things, so if there's no tech requirement we still don't want it factored in.
            if buildInfo.getTechPrereq() == TechTypes.NO_TECH or gc.getTechInfo(buildInfo.getTechPrereq()).getEra() > game.getStartEra():
                if debugOut: print "Tech era not high enough for %(s)s" % {"s":impInfo.getType()}
                continue
            else:
                if debugOut: print "Tech is high enough for %(s)s" % {"s":impInfo.getType()}
            if plot.canHaveImprovement(impEnum,TeamTypes.NO_TEAM,True) == True:
                if debugOut: print "Plot can have %(s)s" % {"s":impInfo.getType()}
                #This function will not find bonus yield changes for NO_PLAYER much to my annoyance
                impCommerce = plot.calculateImprovementYieldChange(impEnum,YieldTypes.YIELD_COMMERCE,PlayerTypes.NO_PLAYER,False)
                impFood = plot.calculateImprovementYieldChange(impEnum,YieldTypes.YIELD_FOOD,PlayerTypes.NO_PLAYER,False)
                impProduction = plot.calculateImprovementYieldChange(impEnum,YieldTypes.YIELD_PRODUCTION,PlayerTypes.NO_PLAYER,False)

                if bonusEnum != -1:
                    impCommerce += impInfo.getImprovementBonusYield(bonusEnum,YieldTypes.YIELD_COMMERCE)
                    impFood += impInfo.getImprovementBonusYield(bonusEnum,YieldTypes.YIELD_FOOD)
                    impProduction += impInfo.getImprovementBonusYield(bonusEnum,YieldTypes.YIELD_PRODUCTION)
                #See if feature is removed, if so we must subtract the added yield
                #from that feature
                featureEnum = plot.getFeatureType()
                if featureEnum != -1 and buildInfo.isFeatureRemove(featureEnum) == True:
                    featureInfo = gc.getFeatureInfo(featureEnum)
                    if debugOut: print "Removing feature %(s)s" % {"s":featureInfo.getType()}
                    impCommerce -= (featureInfo.getYieldChange(YieldTypes.YIELD_COMMERCE) + \
                    featureInfo.getRiverYieldChange(YieldTypes.YIELD_COMMERCE) + \
                    featureInfo.getHillsYieldChange(YieldTypes.YIELD_COMMERCE))
                    
                    impFood -= (featureInfo.getYieldChange(YieldTypes.YIELD_FOOD) + \
                    featureInfo.getRiverYieldChange(YieldTypes.YIELD_FOOD) + \
                    featureInfo.getHillsYieldChange(YieldTypes.YIELD_FOOD))
                    
                    impProduction -= (featureInfo.getYieldChange(YieldTypes.YIELD_PRODUCTION) + \
                    featureInfo.getRiverYieldChange(YieldTypes.YIELD_PRODUCTION) + \
                    featureInfo.getHillsYieldChange(YieldTypes.YIELD_PRODUCTION))
                
                imp = Improvement(impEnum,impFood,impProduction,impCommerce,0)
                improvementList.append(imp)
                if debugOut: print "Improv yields. Food=%(f)d, Production=%(p)d, Commerce=%(c)d" % \
                {"f":impFood,"p":impProduction,"c":impCommerce}
            else:
                if debugOut: print "Plot can not have %(s)s" % {"s":impInfo.getType()}
                            
        for i in range(len(improvementList)):
            impCommerce = improvementList[i].commerce + commerce
            impFood = improvementList[i].food + food
            impProduction = improvementList[i].production + production
            impValue = impCommerce * mc.CommerceValue + impFood * mc.FoodValue + impProduction * mc.ProductionValue
            #Food surplus makes the square much more valueable than if there
            #is no food here.
            if food >= gc.getFOOD_CONSUMPTION_PER_POPULATION():
                impValue *= 4
            elif food == gc.getFOOD_CONSUMPTION_PER_POPULATION() - 1:
                impValue *= 2
            improvementList[i].value = impValue
        if len(improvementList) > 0:
            #sort all allowed improvement values to find the best
            improvementList.sort(lambda x,y:cmp(x.value,y.value))
            improvementList.reverse()
            bestImp = improvementList[0]
            if debugOut: print "bestImp.value=%(b)d" % {"b":bestImp.value}    
            commerce += bestImp.commerce
            food += bestImp.food
            production += bestImp.production
        else:
            if debugOut: print "no improvement possible here"
        value = commerce * mc.CommerceValue + food * mc.FoodValue + production * mc.ProductionValue
        if debugOut: print "Evaluating. Food=%(f)d, Production=%(p)d, Commerce=%(c)d" % \
        {"f":food,"p":production,"c":commerce}
        #Try to avoid included water food resources for non-coastal starts. It confuses the AI.
        if not coastalCity and plot.isWater():
            value = 0
        #Food surplus makes the square much more valueable than if there
        #is no food here.
        if food >= gc.getFOOD_CONSUMPTION_PER_POPULATION():
            value *= 4
        elif food == gc.getFOOD_CONSUMPTION_PER_POPULATION() - 1:
            value *= 2
        if food + commerce + production < 3:
            value = 0
        if debugOut: print "Final Value = %(v)d" % {"v":value}
        if debugOut: print "****************************************************************"
            
        return food,value
    def boostCityPlotValue(self,x,y,bonuses,isCoastalCity):
        mapGen = CyMapGenerator()
        food,value = self.getCityPotentialValue(x,y)
        debugOut = False
        if debugOut: print "Value before boost = %(v)d" % {"v":value}
        gc = CyGlobalContext()
        gameMap = CyMap()
        game = gc.getGame()
        #Shuffle the bonus order so that different cities have different preferences
        #for bonuses
        bonusList = list()
        numBonuses = gc.getNumBonusInfos()
        for i in range(numBonuses):
            bonusList.append(i)
        shuffledBonuses = list()
        for i in range(numBonuses):
            n = PRand.randint(0,len(bonusList) - 1)
            shuffledBonuses.append(bonusList[n])
            del bonusList[n]

        if len(shuffledBonuses) != numBonuses:
            raise ValueError, "Bad bonus shuffle. Learn 2 shuffle."

        bonusCount = 0
        
        #Do this process in 3 passes for each yield type, then an extra production pass
        yields = []
        yields.append(YieldTypes.YIELD_PRODUCTION)
        yields.append(YieldTypes.YIELD_COMMERCE)
        yields.append(YieldTypes.YIELD_FOOD)
        yields.append(YieldTypes.YIELD_PRODUCTION)

        for n in range(len(yields)):
            for i in range(gc.getNUM_CITY_PLOTS()):
            
                # We need to reshuffle bonus list for each square to get
                # diversity of bonuses
                bonusList = list()
                for iii in range(numBonuses):
                    bonusList.append(iii)
                shuffledBonuses = list()
                for iii in range(numBonuses):
                    nnn = PRand.randint(0,len(bonusList) - 1)
                    shuffledBonuses.append(bonusList[nnn])
                    del bonusList[nnn]

                food,value = self.getCityPotentialValue(x,y)
                
                #switch to food if food is needed
                usablePlots = food/gc.getFOOD_CONSUMPTION_PER_POPULATION()
                if usablePlots <= gc.getNUM_CITY_PLOTS()/2:
                    yields[n] = YieldTypes.YIELD_FOOD
                    
                if debugOut: print "value now at %(v)d" % {"v":value}
                if bonusCount >= bonuses:
                    if debugOut: print "Placed all bonuses."
                    if debugOut: print "****************************************************"
                    return
                plot = plotCity(x,y,i)
                if plot.getX() == x and plot.getY() == y:
                    continue
                if plot.isWater() and not isCoastalCity:
                    continue
                if not plot.isWater() and gameMap.plot(x,y).getArea() != plot.getArea():
                    continue
                if plot.getBonusType(TeamTypes.NO_TEAM) != BonusTypes.NO_BONUS:
                    continue
                #temporarily remove any feature
                featureEnum = plot.getFeatureType()
                if featureEnum != FeatureTypes.NO_FEATURE:
                    featureVariety = plot.getFeatureVariety()
                    plot.setFeatureType(FeatureTypes.NO_FEATURE,-1)
                for b in range(gc.getNumBonusInfos()):
                    bonusEnum = shuffledBonuses[b]
                    bonusInfo = gc.getBonusInfo(bonusEnum)
                    #print "b " + str(b) + " " + bonusInfo.getType() ## DEBUG
                    if bonusInfo.isNormalize() == False:
                        #print "bonusInfo.isNormalize() == False" ## DEBUG
                        continue
                    if bonusInfo.getYieldChange(yields[n]) < 1:
                        #print "bonusInfo.getYieldChange(yields[n])<1" ## DEBUG
                        continue
                    if bonusInfo.getTechCityTrade() == TechTypes.NO_TECH or \
                    gc.getTechInfo(bonusInfo.getTechCityTrade()).getEra() <= game.getStartEra():
                    #if 1 == 1: # Any bonus, regardless of tech
                        #print "bonus tech is good" ## DEBUG
                        if bp.PlotCanHaveBonus(plot,bonusEnum,False,False) == False:
                            #print "Plot can't have %(b)s" % {"b":bonusInfo.getType()} ## DEBUG
                            continue
                        #print "Setting bonus type at %(x)d,%(y)d to %(b)s" % \
                        #{"x":plot.getX(),"y":plot.getY(),"b":bonusInfo.getType()} ## DEBUG
                        plot.setBonusType(bonusEnum)
                        bonusCount += 1
                        break
                #restore the feature if possible
                if featureEnum != FeatureTypes.NO_FEATURE:
                    bonusInfo = gc.getBonusInfo(plot.getBonusType(TeamTypes.NO_TEAM))
                    if bonusInfo == None or bonusInfo.isFeature(featureEnum):
                        plot.setFeatureType(featureEnum,featureVariety)                             
                
        if debugOut: print "Failed to boost city value. value= %(v)d" % {"v":value}
        if debugOut: print "****************************************************"
        return
    def ensureMinimumHills(self,x,y):
        gc = CyGlobalContext()
        gameMap = CyMap()
        hillsFound = 0
        peaksFound = 0
        badFeaturesFound = 0
        plotList = []
        for i in range(gc.getNUM_CITY_PLOTS()):
            plot = plotCity(x,y,i)
            featureInfo = gc.getFeatureInfo(plot.getFeatureType())
            if plot.getX() == x and plot.getY() == y:
                #remove bad feature on start but don't count it.
                if featureInfo != None:
                    totalYield = 0
                    for yi in range(YieldTypes.NUM_YIELD_TYPES):
                        totalYield += featureInfo.getYieldChange(YieldTypes(yi))
                    if totalYield <= 0:#bad feature
                        plot.setFeatureType(FeatureTypes.NO_FEATURE,-1)
                continue
            if plot.getPlotType() == PlotTypes.PLOT_HILLS and gameMap.plot(x,y).getArea() == plot.getArea():
                hillsFound += 1
            if plot.getPlotType() == PlotTypes.PLOT_PEAK:
                peaksFound += 1
            if featureInfo != None:
                #now count the bad features
                totalYield = 0
                for yi in range(YieldTypes.NUM_YIELD_TYPES):
                    totalYield += featureInfo.getYieldChange(YieldTypes(yi))
                if totalYield <= 0:#bad feature
                    badFeaturesFound += 1
            if plot.isWater():
                continue
            if plot.getBonusType(TeamTypes.NO_TEAM) != BonusTypes.NO_BONUS:
                continue
            plotList.append(plot)
        print "badFeaturesFound=%d" % badFeaturesFound
        plotList = ShuffleList(plotList)
        #ensure maximum number of peaks
        if peaksFound > mc.MaxPeaksInFC:
            for plot in plotList:
                if peaksFound == mc.MaxPeaksInFC:
                    break
                if plot.getPlotType() == PlotTypes.PLOT_PEAK:
                    plot.setPlotType(PlotTypes.PLOT_HILLS,True,True)
                    if plot.getArea() == gameMap.plot(x,y).getArea():
                        hillsFound += 1
                    peaksFound -= 1
                    
        #ensure maximum number of bad features
        if badFeaturesFound > mc.MaxBadFeaturesInFC:
            #first loop for hill tiles, then...
            for plot in plotList:
                featureInfo = gc.getFeatureInfo(plot.getFeatureType())
                if badFeaturesFound == mc.MaxBadFeaturesInFC/2: #truncation on this operation will prefer to remove on flats, which is desirable
                    break
                if featureInfo != None and plot.getPlotType() == PlotTypes.PLOT_HILLS:
                    totalYield = 0
                    for yi in range(YieldTypes.NUM_YIELD_TYPES):
                        totalYield += featureInfo.getYieldChange(YieldTypes(yi))
                    if totalYield <= 0:#bad feature
                        badFeaturesFound -= 1
                        print "clearing bad feature from hill"
                        plot.setFeatureType(FeatureTypes.NO_FEATURE,-1)
                        
            #loop for flat tiles, this way land is cleared on both hills and flats in FC
            for plot in plotList:
                featureInfo = gc.getFeatureInfo(plot.getFeatureType())
                if badFeaturesFound == mc.MaxBadFeaturesInFC:
                    break
                if featureInfo != None and plot.getPlotType() == PlotTypes.PLOT_LAND:
                    totalYield = 0
                    for yi in range(YieldTypes.NUM_YIELD_TYPES):
                        totalYield += featureInfo.getYieldChange(YieldTypes(yi))
                    if totalYield <= 0:#bad feature
                        badFeaturesFound -= 1
                        print "clearing bad feature from flat land"
                        plot.setFeatureType(FeatureTypes.NO_FEATURE,-1)
        
        #Ensure minimum number of hills
        plotList = ShuffleList(plotList) #need to re-shuffle so that hills are not the same as removed bad features
        hillsNeeded = mc.MinHillsInFC - hillsFound
        print "hills found = %d, hills needed = %d" % (hillsFound,hillsNeeded)
        if hillsNeeded > 0:
            for plot in plotList:
                if hillsNeeded <= 0:
                    break
                featureInfo = gc.getFeatureInfo(plot.getFeatureType())
                bonusInfo = gc.getBonusInfo(plot.getBonusType(TeamTypes.NO_TEAM))
                if plot.getPlotType() != PlotTypes.PLOT_HILLS and \
                plot.getArea() == gameMap.plot(x,y).getArea() and \
                (featureInfo == None or not featureInfo.isRequiresFlatlands()) and \
                (bonusInfo == None or not bonusInfo.isRequiresFlatlands()):
                    plot.setPlotType(PlotTypes.PLOT_HILLS,True,True)
                    hillsNeeded -= 1
                    print "adding hill"
            if hillsNeeded > 0:
                print "failed to add minimum hills!!!!!!!!!!"

    def addHandicapBonus(self):
        gc = CyGlobalContext()
        for ePlayer in range(gc.getMAX_CIV_PLAYERS()):
            player = gc.getPlayer(ePlayer)
            if player.isEverAlive() and player.isHuman():
                eHandicap = player.getHandicapType()
                startPlot = player.getStartingPlot()
                sPlot = StartPlot(startPlot.getX(),startPlot.getY(),0)
                if eHandicap == gc.getInfoTypeForString("HANDICAP_SETTLER"):
                    if mc.SettlerBonus > 0:
                        print "Human player at Settler difficulty, adding %d resources" % mc.SettlerBonus
                        self.boostCityPlotValue(startPlot.getX(),startPlot.getY(),mc.SettlerBonus,sPlot.isCoast())
                elif eHandicap ==  gc.getInfoTypeForString("HANDICAP_CHIEFTAIN"):       
                    if mc.ChieftainBonus > 0:
                        print "Human player at Chieftain difficulty, adding %d resources" % mc.ChieftainBonus
                        self.boostCityPlotValue(startPlot.getX(),startPlot.getY(),mc.ChieftainBonus,sPlot.isCoast())
                elif eHandicap ==  gc.getInfoTypeForString("HANDICAP_WARLORD"):       
                    if mc.WarlordBonus > 0:
                        print "Human player at Warlord difficulty, adding %d resources" % mc.WarlordBonus
                        self.boostCityPlotValue(startPlot.getX(),startPlot.getY(),mc.WarlordBonus,sPlot.isCoast())
                elif eHandicap ==  gc.getInfoTypeForString("HANDICAP_NOBLE"):       
                    if mc.NobleBonus > 0:
                        print "Human player at Noble difficulty, adding %d resources" % mc.NobleBonus
                        self.boostCityPlotValue(startPlot.getX(),startPlot.getY(),mc.NobleBonus,sPlot.isCoast())
                elif eHandicap ==  gc.getInfoTypeForString("HANDICAP_PRINCE"):       
                    if mc.PrinceBonus > 0:
                        print "Human player at Prince difficulty, adding %d resources" % mc.PrinceBonus
                        self.boostCityPlotValue(startPlot.getX(),startPlot.getY(),mc.PrinceBonus,sPlot.isCoast())
                elif eHandicap ==  gc.getInfoTypeForString("HANDICAP_MONARCH"):       
                    if mc.MonarchBonus > 0:
                        print "Human player at Monarch difficulty, adding %d resources" % mc.MonarchBonus
                        self.boostCityPlotValue(startPlot.getX(),startPlot.getY(),mc.MonarchBonus,sPlot.isCoast())
                elif eHandicap ==  gc.getInfoTypeForString("HANDICAP_EMPEROR"):       
                    if mc.EmperorBonus > 0:
                        print "Human player at Emperor difficulty, adding %d resources" % mc.EmperorBonus
                        self.boostCityPlotValue(startPlot.getX(),startPlot.getY(),mc.EmperorBonus,sPlot.isCoast())
                elif eHandicap ==  gc.getInfoTypeForString("HANDICAP_IMMORTAL"):       
                    if mc.ImmortalBonus > 0:
                        print "Human player at Immortal difficulty, adding %d resources" % mc.ImmortalBonus
                        self.boostCityPlotValue(startPlot.getX(),startPlot.getY(),mc.ImmortalBonus,sPlot.isCoast())
                elif eHandicap ==  gc.getInfoTypeForString("HANDICAP_DEITY"):       
                    if mc.DeityBonus > 0:
                        print "Human player at Deity Difficulty, adding %d resources" % mc.DeityBonus
                        self.boostCityPlotValue(startPlot.getX(),startPlot.getY(),mc.DeityBonus,sPlot.isCoast())
                    
 
#Global access
spf = StartingPlotFinder()
class CityPlot :
    def __init__(self,food,value):
        self.food = food
        self.value = value
class Improvement :
    def __init__(self,e,food,production,commerce,value):
        self.e = e
        self.food = food
        self.production = production
        self.commerce = commerce
        self.value = value

class StartingArea :
    def __init__(self,areaID):
        self.areaID = areaID
        self.playerList = list()
        self.plotList = list()
        self.distanceTable = array('i')
        self.rawValue = 0
        self.CalculatePlotList()
        self.idealNumberOfPlayers = 0
        return
    def CalculatePlotList(self):
        gc = CyGlobalContext()
        gameMap = CyMap()
        
        for y in range(mc.height):
            for x in range(mc.width):
                plot = gameMap.plot(x,y)
                if plot.getArea() == self.areaID:
                    #don't place a city on top of a bonus
                    if plot.getBonusType(TeamTypes.NO_TEAM) != BonusTypes.NO_BONUS:
                        continue
                    food,value = spf.getCityPotentialValue(x,y)
                    if value > 0:
                        startPlot = StartPlot(x,y,value)
                        if plot.isWater() == True:
                            raise ValueError, "potential start plot is water!"
                        self.plotList.append(startPlot)
        #Sort plots by local value
        self.plotList.sort(lambda x, y: cmp(x.localValue, y.localValue))
        
        #To save time and space let's get rid of some of the lesser plots
        cull = (len(self.plotList) * 2) / 3
        for i in range(cull):
            del self.plotList[0]
            
        #You now should be able to eliminate more plots by sorting high to low
        #and having the best plot eat plots within 3 squares, then same for next,
        #etc.
        self.plotList.reverse()
##        print "number of initial plots in areaID = %(a)3d is %(p)5d" % {"a":self.areaID,"p":len(self.plotList)}
        numPlots = len(self.plotList)
        for n in range(numPlots):
            #At some point the length of plot list will be much shorter than at
            #the beginning of the loop, so it can never end normally
            if n >= len(self.plotList) - 1:
                break
            y = self.plotList[n].y
            x = self.plotList[n].x
            for yy in range(y - 3,y + 4):
                for xx in range(x - 3,x + 4):
                    if yy < 0 or yy >= mc.height:
                        continue
                    xx = xx % mc.width#wrap xx
                    if xx < 0:
                        raise ValueError, "xx value not wrapping properly in StartingArea.CalculatePlotList"
                    for m in range(n,len(self.plotList)):
                        #At some point the length of plot list will be much shorter than at
                        #the beginning of the loop, so it can never end normally
                        if m >= len(self.plotList) - 1:
                            break
##                        print "m = %(m)3d, n = %(n)3d" % {"m":m,"n":n}
                        if self.plotList[m] != self.plotList[n]:
                            if self.plotList[m].x == xx and self.plotList[m].y == yy:
##                                print "deleting m = %(m)3d" % {"m":m}
                                del self.plotList[m]
##                                print "length of plotList now %(len)4d" % {"len":len(self.plotList)}
                                 
##        print "number of final plots in areaID = %(a)3d is %(p)5d" % {"a":self.areaID,"p":len(self.plotList)}
                                
        #At this point we should have a list of the very best places
        #to build cities on this continent. Now we need a table with
        #the distance from each city to every other city

        #Create distance table
        for i in range(len(self.plotList)*len(self.plotList)):
            self.distanceTable.append(-11)
        #Fill distance table
        for n in range(len(self.plotList)):
            #While were already looping lets calculate the raw value
            self.rawValue += self.plotList[n].localValue
            avgDistance = 0
            for m in range(n,len(self.plotList)):
                nPlot = gameMap.plot(self.plotList[n].x,self.plotList[n].y)
                mPlot = gameMap.plot(self.plotList[m].x,self.plotList[m].y)
                gameMap.resetPathDistance()
                distance = gameMap.calculatePathDistance(nPlot,mPlot)
#               distance = self.getDistance(nPlot.getX(),nPlot.getY(),mPlot.getX(),mPlot.getY())
                #If path fails try reversing it
##                gameMap.resetPathDistance()
##                newDistance = gameMap.calculatePathDistance(mPlot,nPlot)
##                if distance != newDistance:
##                    print "distance between n=%(n)d nx=%(nx)d,ny=%(ny)d and m=%(m)d mx=%(mx)d,my=%(my)d is %(d)d or %(nd)d" % \
##                    {"n":n,"nx":nPlot.getX(),"ny":nPlot.getY(),"m":m,"mx":mPlot.getX(),"my":mPlot.getY(),"d":distance,"nd":newDistance}
                self.distanceTable[n*len(self.plotList) + m] = distance
                self.distanceTable[m*len(self.plotList) + n] = distance
                avgDistance += distance
            self.plotList[n].avgDistance = avgDistance
 
        return
    def FindStartingPlots(self):
        gc = CyGlobalContext()
        gameMap = CyMap()
        numPlayers = len(self.playerList)
        if numPlayers <= 0:
            return

        avgDistanceList = list()
        for i in range(len(self.plotList)):
            avgDistanceList.append(self.plotList[i])
            
        #Make sure first guy starts on the end and not in the middle,
        #otherwise if there are two players one will start on the middle
        #and the other on the end
        avgDistanceList.sort(lambda x,y:cmp(x.avgDistance,y.avgDistance))
        avgDistanceList.reverse()
        #First place players as far as possible away from each other
        #Place the first player
        avgDistanceList[0].vacant = False
        for i in range(1,numPlayers):
            distanceList = list()
            for n in range(len(self.plotList)):
                if self.plotList[n].vacant == True:
                    minDistance = -1
                    for m in range(len(self.plotList)):
                        if self.plotList[m].vacant == False:
                            ii = n * len(self.plotList) + m
                            distance = self.distanceTable[ii]
                            if minDistance == -1 or minDistance > distance:
                                minDistance = distance
                    self.plotList[n].nearestStart = minDistance
                    distanceList.append(self.plotList[n])
            #Find biggest nearestStart and place a start there
            distanceList.sort(lambda x,y:cmp(x.nearestStart,y.nearestStart))
            distanceList.reverse()
            distanceList[0].vacant = False
##            print "Placing start at x=%(x)d, y=%(y)d nearestDistance to city is %(n)d" % \
##            {"x":distanceList[0].x,"y":distanceList[0].y,"n":distanceList[0].nearestStart}
                
        self.CalculateStartingPlotValues()
                
##        self.PrintPlotMap()
##        self.PrintPlotList()
##        self.PrintDistanceTable()
      
        #Now place all starting positions
        n = 0
        for m in range(len(self.plotList)):
            if self.plotList[m].vacant == False:
                sPlot = gameMap.plot(self.plotList[m].x,self.plotList[m].y)
                if sPlot.isWater() == True:
                    raise ValueError, "Start plot is water!"
                sPlot.setImprovementType(gc.getInfoTypeForString("NO_IMPROVEMENT"))
                playerID = self.playerList[n]
                player = gc.getPlayer(playerID)
                sPlot.setStartingPlot(True)
                player.setStartingPlot(sPlot,True)
                n += 1

            
        return
    def CalculateStartingPlotValues(self):
        gameMap = CyMap()
        numPlots = len(self.plotList)
        
        for n in range(numPlots):
            self.plotList[n].owner = -1
            self.plotList[n].totalValue = 0
            
        for n in range(numPlots):
            if self.plotList[n].vacant == True:
                continue
            self.plotList[n].totalValue = 0
            self.plotList[n].numberOfOwnedCities = 0
            for m in range(numPlots):
                i = n * numPlots + m
                nDistance = self.distanceTable[i]
                if nDistance == -1:
                    leastDistance = False
                else:
                    leastDistance = True #Being optimistic, prove me wrong
                for p in range(numPlots):
                    if p == n or self.plotList[p].vacant == True:
                        continue
                    ii = p * numPlots + m
                    pDistance = self.distanceTable[ii]
##                    print "n= %(n)3d, m = %(m)3d, p = %(p)3d, nDistance = %(nd)3d, pDistance = %(pd)3d" %\
##                    {"n":n,"m":m,"p":p,"nd":nDistance,"pd":pDistance}
                    if pDistance > -1 and pDistance <= nDistance:
                        leastDistance = False #Proven wrong
                        break
                    
                if leastDistance == True:
                    self.plotList[n].totalValue += self.plotList[m].localValue
#                    print "m = %(m)3d owner change from %(mo)3d to %(n)3d" % {"m":m,"mo":self.plotList[m].owner,"n":n}
                    self.plotList[m].owner = self.plotList[n]
                    self.plotList[m].distanceToOwner = nDistance
                    self.plotList[n].numberOfOwnedCities += 1
                    
        return
    def getDistance(self,x,y,dx,dy):
        xx = x - dx
        if abs(xx) > mc.width/2:
            xx = mc.width - abs(xx)
            
        distance = max(abs(xx),abs(y - dy))
        return distance
    def PrintPlotMap(self):
        gameMap = CyMap()
        print "Starting Plot Map"
        for y in range(hm.mapHeight - 1,-1,-1):
            lineString = ""
            for x in range(hm.mapWidth):
                inList = False
                for n in range(len(self.plotList)):
                    if self.plotList[n].x == x and self.plotList[n].y == y:
                        if self.plotList[n].plot().isWater() == True:
                            if self.plotList[n].vacant == True:
                                lineString += 'VV'
                            else:
                                lineString += 'OO'
                        else:
                            if self.plotList[n].vacant == True:
                                lineString += 'vv'
                            else:
                                lineString += 'oo'
                        inList = True
                        break
                if inList == False:
                    plot = gameMap.plot(x,y)
                    if plot.isWater() == True:
                        lineString += '.;'
                    else:
                        lineString += '[]'

            lineString += "-" + str(y)
            print lineString
            
        lineString = " "
        print lineString

        return
    def PrintPlotList(self):
        for n in range(len(self.plotList)):
            print str(n) + ' ' + str(self.plotList[n])
        return
    
    def PrintDistanceTable(self):
        print "Distance Table"
        lineString = "%(n)05d" % {"n":0} + ' '
        for n in range(len(self.plotList)):
            lineString += "%(n)05d" % {"n":n} + ' '
        print lineString
        lineString = ""
        for n in range(len(self.plotList)):
            lineString = "%(n)05d" % {"n":n} + ' '
            for m in range(len(self.plotList)):
                i = n * len(self.plotList) + m
                lineString += "%(d)05d" % {"d":self.distanceTable[i]} + ' '
            print lineString    
        return

class StartPlot :
    def __init__(self,x,y,localValue):
        self.x = x
        self.y = y
        self.localValue = localValue
        self.totalValue = 0
        self.numberOfOwnedCities = 0
        self.distanceToOwner = -1
        self.nearestStart = -1
        self.vacant = True
        self.owner = None
        self.avgDistance = 0
        return
    def isCoast(self):
        gameMap = CyMap()
        plot = gameMap.plot(self.x,self.y)
        waterArea = plot.waterArea()
        if waterArea.isNone() == True or waterArea.isLake() == True: 
            return False
        return True
    
    def isRiverSide(self):
        gameMap = CyMap()
        plot = gameMap.plot(self.x,self.y)
        return plot.isRiverSide()        

    def plot(self):
        gameMap = CyMap()
        return gameMap.plot(self.x,self.y)
    def copy(self):
        cp = StartPlot(self.x,self.y,self.localValue)
        cp.totalValue = self.totalValue
        cp.numberOfOwnedCities = self.numberOfOwnedCities
        cp.distanceToOwner = self.distanceToOwner
        cp.nearestStart = self.nearestStart
        cp.vacant = self.vacant
        cp.owner = self.owner
        cp.avgDistance = self.avgDistance
        return cp
    def __str__(self):
        linestring = "x=%(x)3d,y=%(y)3d,localValue=%(lv)6d,totalValue =%(tv)6d, nearestStart=%(ad)6d, coastalCity=%(cc)d" % \
        {"x":self.x,"y":self.y,"lv":self.localValue,"tv":self.totalValue,"ad":self.nearestStart,"cc":self.isCoast()}
        return linestring
        
hm = HeightMap()
cm = ClimateMap()
sm = SmallMaps()
rm = RiverMap()
em = EuropeMap()
###############################################################################     
#functions that civ is looking for
###############################################################################
def getDescription():
	"""
	A map's Description is displayed in the main menu when players go to begin a game.
	For no description return an empty string.
	"""
	return "Random map that simulates earth-like plate tectonics, " +\
        "geostrophic and monsoon winds and rainfall."
def getWrapX():
	return mc.WrapX
	
def getWrapY():
    print "mc.WrapY == %d at getWrapY" % mc.WrapY
    return mc.WrapY
    
def getNumCustomMapOptions():
    """
    Number of different user-defined options for this map
    Return an integer
    """
    mc.initialize()
    return 4
	
def getCustomMapOptionName(argsList):
        """
        Returns name of specified option
        argsList[0] is Option ID (int)
        Return a Unicode string
        """
        optionID = argsList[0]
        #if optionID == 0:
        #    return "New World Rules"
        #elif optionID == 1:
        #    return "Pangaea Rules"
        #elif optionID == 2:
        #    return "Wrap Option"
        if optionID == 0:
            return "Resources"
        #elif optionID == 4:
        #    return "Have bigger maps"
        elif optionID == 1:
            return "Map seed"
        elif optionID == 2:
            return "Player bonus resources"
        elif optionID == 3:
            return "Hut placement"

        return u""
	
def getNumCustomMapOptionValues(argsList):
        """
        Number of different choices for a particular setting
        argsList[0] is Option ID (int)
        Return an integer
        """
        optionID = argsList[0]
        if optionID == 0:
            return 3
        elif optionID == 1:
            return 9
        elif optionID == 2:
            return 8
        elif optionID == 3:
            return 6
        return 0
	
def getCustomMapOptionDescAt(argsList):
    """
    Returns name of value of option at specified row
    argsList[0] is Option ID (int)
    argsList[1] is Selection Value ID (int)
    Return a Unicode string
    """
    optionID = argsList[0]
    selectionID = argsList[1]
    if optionID == 0: # Resources
        if selectionID == 0:
            return "Full of resources"
        elif selectionID == 1:
            return "Resources evenly spread"
        elif selectionID == 2:
            return "Like Perfect World"
    elif optionID == 1: # Seed (i.e. land size)
        if selectionID == 0:
            return "Larger start continents"
        elif selectionID == 1:
            return "Smaller start continents"
        elif selectionID == 2:
            return "Random"
        elif selectionID == 3:
            return "Free Form (not Arabian)"
        elif selectionID == 4:
            return "Amira map"
        elif selectionID == 5:
            return "Caulixtla map"
        elif selectionID == 6:
            return "Fixed seed (Jungle start)"
        elif selectionID == 7:
            return "Caulixtla map (Jungle start)"
        elif selectionID == 8:
            return "Fixed seed (Grassland start)"
    elif optionID == 2: # Player bonus resource amount
        if selectionID == 0:
            return "None (Player equal to AI)"
        elif selectionID == 1:
            return "A little"
        elif selectionID == 2:
            return "Some"
        elif selectionID == 3:
            return "Lots (Easier for player)"
        elif selectionID == 4:
            return "Tons (even easier)"
        elif selectionID == 5:
            return "Mega"
        elif selectionID == 6:
            return "Super mega"
        elif selectionID == 7:
            return "Insane (Much easier)"
    if optionID == 3: # Hut placement
        if selectionID == 0:
            return "Civ4 default"
        elif selectionID == 1:
            return "No huts"
        elif selectionID == 2:
            return "Fixed huts per seed"
        elif selectionID == 3:
            return "Huts are rare"
        elif selectionID == 4:
            return "Many desert huts"
        elif selectionID == 5:
            return "Many huts everywhere"
    return u""
	
def getCustomMapOptionDefault(argsList):
	"""
	Returns default value of specified option
	argsList[0] is Option ID (int)
	Return an integer
	"""
	#Always zero in this case
	return 0
    
def isRandomCustomMapOption(argsList):
	"""
	Returns a flag indicating whether a random option should be provided
	argsList[0] is Option ID (int)
	Return a bool
	"""
	return False
    
#This doesn't work with my river system so it is disabled. Some civs
#might start without a river. Boo hoo.
def normalizeAddRiver():
    return
def normalizeAddLakes():
    return
def normalizeAddGoodTerrain():
    return
def normalizeRemoveBadTerrain():
    return
def normalizeRemoveBadFeatures():
    return
def normalizeAddFoodBonuses():
    return
def normalizeAddExtras():
    return
def normalizeRemovePeaks():
    return
def isAdvancedMap():
	"""
	Advanced maps only show up in the map script pulldown on the advanced menu.
	Return 0 if you want your map to show up in the simple singleplayer menu
	"""
	return 0
def isClimateMap():
	"""
	Uses the Climate options
	"""
	return 0
	
def isSeaLevelMap():
	"""
	Uses the Sea Level options
	"""
	return 0
    
def getTopLatitude():
	"Default is 90. 75 is past the Arctic Circle"
	return 90

def getBottomLatitude():
	"Default is -90. -75 is past the Antartic Circle"
	return -90
    
def getGridSize(argsList):
    grid_sizes = {
		WorldSizeTypes.WORLDSIZE_DUEL:		(11,7),
		WorldSizeTypes.WORLDSIZE_TINY:		(15,10),
		WorldSizeTypes.WORLDSIZE_SMALL:		(20,13),
		WorldSizeTypes.WORLDSIZE_STANDARD:	(24,16),
		WorldSizeTypes.WORLDSIZE_LARGE:		(30,20),
		WorldSizeTypes.WORLDSIZE_HUGE:		(36,24)
    }
    # Scale if they want a bigger or smaller world
    [eWorldSize] = argsList
    (sizex, sizey) = (36, 24) # Always 144x96 maps
    #gc = CyGlobalContext()
    #mmap = gc.getMap()
    #if mmap.getCustomMapOption(4) == 1: # Big maps
    #    sizex = sizex + int(sizex / 3) 
    #    sizey = sizey + int(sizey / 3) 
    #elif mmap.getCustomMapOption(4) == 2: # Small maps
    #    sizex = sizex - int(sizex / 3) 
    #    sizey = sizey - int(sizey / 3) 

    if (argsList[0] == -1): # (-1,) is passed to function on loads
            return []
    return (36, 24) # Always 144x96 maps
    #return (sizex, sizey)

def generatePlotTypes():
    gc = CyGlobalContext()
    mmap = gc.getMap()
    mc.width = mmap.getGridWidth()
    mc.height = mmap.getGridHeight()
    mc.minimumMeteorSize = (1 + int(round(float(mc.hmWidth)/float(mc.width)))) * 3
    PRand.seed()
    hm.performTectonics()
    hm.generateHeightMap()
    hm.combineMaps()
    hm.calculateSeaLevel()
    hm.fillInLakes()
    pb.breakPangaeas()
##    hm.Erode()
##    hm.printHeightMap()
    hm.addWaterBands()
##    hm.printHeightMap()
    cm.createClimateMaps()
    sm.initialize()
    rm.generateRiverMap()
    plotTypes = [PlotTypes.PLOT_OCEAN] * (mc.width*mc.height)

    for i in range(mc.width*mc.height):
        mapLoc = sm.plotMap[i]
        if mapLoc == mc.PEAK:
            plotTypes[i] = PlotTypes.PLOT_PEAK
        elif mapLoc == mc.HILLS:
            plotTypes[i] = PlotTypes.PLOT_HILLS
        elif mapLoc == mc.LAND:
            plotTypes[i] = PlotTypes.PLOT_LAND
        else:
            plotTypes[i] = PlotTypes.PLOT_OCEAN
    print "Finished generating plot types."         
    return plotTypes
def generateTerrainTypes():
    NiTextOut("Generating Terrain  ...")
    print "Adding Terrain"
    gc = CyGlobalContext()
    terrainDesert = gc.getInfoTypeForString("TERRAIN_DESERT")
    terrainPlains = gc.getInfoTypeForString("TERRAIN_PLAINS")
    terrainIce = gc.getInfoTypeForString("TERRAIN_SNOW")
    terrainTundra = gc.getInfoTypeForString("TERRAIN_TUNDRA")
    terrainGrass = gc.getInfoTypeForString("TERRAIN_GRASS")
    terrainHill = gc.getInfoTypeForString("TERRAIN_HILL")
    terrainCoast = gc.getInfoTypeForString("TERRAIN_COAST")
    terrainOcean = gc.getInfoTypeForString("TERRAIN_OCEAN")
    terrainPeak = gc.getInfoTypeForString("TERRAIN_PEAK")
    
    terrainTypes = [0]*(mc.width*mc.height)
    for i in range(mc.width*mc.height):
        if sm.terrainMap[i] == mc.OCEAN:
            terrainTypes[i] = terrainOcean
        elif sm.terrainMap[i] == mc.COAST:
            terrainTypes[i] = terrainCoast
        elif sm.terrainMap[i] == mc.DESERT:
            terrainTypes[i] = terrainDesert
        elif sm.terrainMap[i] == mc.PLAINS:
            terrainTypes[i] = terrainPlains
        elif sm.terrainMap[i] == mc.GRASS:
            terrainTypes[i] = terrainGrass
        elif sm.terrainMap[i] == mc.TUNDRA:
            terrainTypes[i] = terrainTundra
        elif sm.terrainMap[i] == mc.SNOW:
            terrainTypes[i] = terrainIce
    print "Finished generating terrain types."
    return terrainTypes

def addRivers():
    NiTextOut("Adding Rivers....")
    print "Adding Rivers"
    gc = CyGlobalContext()
    pmap = gc.getMap()
    for y in range(mc.height):
        for x in range(mc.width):
            placeRiversInPlot(x,y)

##    rm.printRiverAndTerrainAlign()
            
    #peaks and rivers don't always mix well graphically, so lets eliminate
    #these potential glitches. Basically if there are adjacent peaks on both
    #sides of a river, either in a cardinal direction or diagonally, they
    #will look bad.
    for y in range(mc.height):
        for x in range(mc.width):
            plot = pmap.plot(x,y)
            if plot.isPeak() == True:
                if plot.isNOfRiver() == True:
                    for xx in range(x - 1,x + 2,1):
                        yy = y - 1
                        if yy < 0:
                            break
                        #wrap in x direction
                        if xx == -1:
                            xx = mc.width - 1
                        elif xx == mc.width:
                            xx = 0
                        newPlot = pmap.plot(xx,yy)
                        ii = GetIndex(xx,yy)
                        if newPlot.isPeak():
                            plot.setPlotType(PlotTypes.PLOT_HILLS,True,True)
                            sm.plotMap[ii] = mc.HILLS
                            break
            #possibly changed so checked again
            if plot.isPeak() == True:
                if plot.isWOfRiver() == True:
                    for yy in range(y - 1,y + 2,1):
                        xx = x + 1
                        if xx == mc.width:
                            xx = 0
                        #do not wrap in y direction
                        if yy == -1:
                            continue
                        elif yy == mc.height:
                            continue
                        newPlot = pmap.plot(xx,yy)
                        ii = GetIndex(xx,yy)
                        if newPlot.isPeak():
                            plot.setPlotType(PlotTypes.PLOT_HILLS,True,True)
                            sm.plotMap[ii] = mc.HILLS
                            break
    
def placeRiversInPlot(x,y):
    gc = CyGlobalContext()
    pmap = gc.getMap()
    plot = pmap.plot(x,y)
    #NE
    xx,yy = rm.rxFromPlot(x,y,rm.NE)
    ii = GetIndex(xx,yy)
    if ii != -1:
        if rm.riverMap[ii] == rm.S:
            plot.setWOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_SOUTH)
    #SW
    xx,yy = rm.rxFromPlot(x,y,rm.SW)
    ii = GetIndex(xx,yy)
    if ii != -1:
        if rm.riverMap[ii] == rm.E:
            plot.setNOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_EAST)
    #SE
    xx,yy = rm.rxFromPlot(x,y,rm.SE)
    ii = GetIndex(xx,yy)
    if ii != -1:
        if rm.riverMap[ii] == rm.N:
            plot.setWOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_NORTH)
        elif rm.riverMap[ii] == rm.W:
            plot.setNOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_WEST)
'''
This function examines a lake area and removes ugly surrounding rivers. Any
river that is flowing away from the lake, or alongside the lake will be
removed. This function also returns a list of riverID's that flow into the
lake.
'''
def cleanUpLake(x,y):
    gc = CyGlobalContext()
    mmap = gc.getMap()
    riversIntoLake = list()
    plot = mmap.plot(x,y+1)#North
    if plot != 0 and plot.isNOfRiver() == True:
        plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    if plot != 0 and plot.isWOfRiver() == True:
        if plot.getRiverNSDirection() == CardinalDirectionTypes.CARDINALDIRECTION_SOUTH:
            riversIntoLake.append(plot.getRiverID())
        else:
            plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    plot = mmap.plot(x - 1,y)#West
    if plot != 0 and plot.isWOfRiver() == True:
        plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    if plot != 0 and plot.isNOfRiver() == True:
        if plot.getRiverWEDirection() == CardinalDirectionTypes.CARDINALDIRECTION_EAST:
            riversIntoLake.append(plot.getRiverID())
        else:
            plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    plot = mmap.plot(x + 1,y)#East
    if plot != 0 and plot.isNOfRiver() == True:
        if plot.getRiverWEDirection() == CardinalDirectionTypes.CARDINALDIRECTION_WEST:
            riversIntoLake.append(plot.getRiverID())
        else:
            plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    plot = mmap.plot(x,y-1)#South
    if plot != 0 and plot.isWOfRiver() == True:
        if plot.getRiverNSDirection() == CardinalDirectionTypes.CARDINALDIRECTION_NORTH:
            riversIntoLake.append(plot.getRiverID())
        else:
            plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    plot = mmap.plot(x-1,y+1)#Northwest
    if plot != 0 and plot.isWOfRiver() == True:
        if plot.getRiverNSDirection() == CardinalDirectionTypes.CARDINALDIRECTION_SOUTH:
            riversIntoLake.append(plot.getRiverID())
        else:
            plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    if plot != 0 and plot.isNOfRiver() == True:
        if plot.getRiverWEDirection() == CardinalDirectionTypes.CARDINALDIRECTION_EAST:
            riversIntoLake.append(plot.getRiverID())
        else:
            plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    plot = mmap.plot(x+1,y+1)#Northeast
    if plot != 0 and plot.isNOfRiver() == True:
        if plot.getRiverWEDirection() == CardinalDirectionTypes.CARDINALDIRECTION_WEST:
            riversIntoLake.append(plot.getRiverID())
        else:
            plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    plot = mmap.plot(x-1,y-1)#Southhwest
    if plot != 0 and plot.isWOfRiver() == True:
        if plot.getRiverNSDirection() == CardinalDirectionTypes.CARDINALDIRECTION_NORTH:
            riversIntoLake.append(plot.getRiverID())
        else:
            plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    #Southeast plot is not relevant 
            
    return riversIntoLake
'''
This function replaces rivers to update the river crossings after a lake or
channel is placed at X,Y. There had been a long standing problem where water tiles
added after a river were causing graphical glitches and incorrect river rules
due to not updating the river crossings.
'''
def replaceRivers(x,y):
    gc = CyGlobalContext()
    mmap = gc.getMap()
    plot = mmap.plot(x,y+1)#North
    if plot != 0 and plot.isWOfRiver() == True:
        if plot.getRiverNSDirection() == CardinalDirectionTypes.CARDINALDIRECTION_SOUTH:
            #setting the river to what it already is will be ignored by the dll,
            #so it must be unset and then set again.
            plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
            plot.setWOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_SOUTH)
    plot = mmap.plot(x - 1,y)#West
    if plot != 0 and plot.isNOfRiver() == True:
        if plot.getRiverWEDirection() == CardinalDirectionTypes.CARDINALDIRECTION_EAST:
            plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
            plot.setNOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_EAST)
    plot = mmap.plot(x + 1,y)#East
    if plot != 0 and plot.isNOfRiver() == True:
        if plot.getRiverWEDirection() == CardinalDirectionTypes.CARDINALDIRECTION_WEST:
            plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
            plot.setNOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_WEST)
    plot = mmap.plot(x,y-1)#South
    if plot != 0 and plot.isWOfRiver() == True:
        if plot.getRiverNSDirection() == CardinalDirectionTypes.CARDINALDIRECTION_NORTH:
            plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
            plot.setWOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_NORTH)
    plot = mmap.plot(x-1,y+1)#Northwest
    if plot != 0 and plot.isWOfRiver() == True:
        if plot.getRiverNSDirection() == CardinalDirectionTypes.CARDINALDIRECTION_SOUTH:
            plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
            plot.setWOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_SOUTH)
    if plot != 0 and plot.isNOfRiver() == True:
        if plot.getRiverWEDirection() == CardinalDirectionTypes.CARDINALDIRECTION_EAST:
            plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
            plot.setNOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_EAST)
    plot = mmap.plot(x+1,y+1)#Northeast
    if plot != 0 and plot.isNOfRiver() == True:
        if plot.getRiverWEDirection() == CardinalDirectionTypes.CARDINALDIRECTION_WEST:
            plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
            plot.setNOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_WEST)
    plot = mmap.plot(x-1,y-1)#Southhwest
    if plot != 0 and plot.isWOfRiver() == True:
        if plot.getRiverNSDirection() == CardinalDirectionTypes.CARDINALDIRECTION_NORTH:
            plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
            plot.setWOfRiver(True,CardinalDirectionTypes.CARDINALDIRECTION_NORTH)
    #Southeast plot is not relevant 
            
    return

'''
It looks bad to have a lake, fed by a river, sitting right next to the coast.
This function tries to minimize that occurance by replacing it with a
natural harbor, which looks much better.
'''
def makeHarbor(x,y,oceanMap):
    oceanID = oceanMap.getOceanID()
    i = oceanMap.getIndex(x,y)
    if oceanMap.areaMap[i] != oceanID:
        return
    #N
    xx = x
    yy = y + 2
    ii = oceanMap.getIndex(xx,yy)
    if ii > -1 and \
    oceanMap.getAreaByID(oceanMap.areaMap[ii]).water == True and \
    oceanMap.areaMap[ii] != oceanID:
        makeChannel(x,y + 1)
        oceanMap.defineAreas(isSmallWaterMatch)
        oceanID = oceanMap.getOceanID()
    #S
    xx = x
    yy = y - 2
    ii = oceanMap.getIndex(xx,yy)
    if ii > -1 and \
    oceanMap.getAreaByID(oceanMap.areaMap[ii]).water == True and \
    oceanMap.areaMap[ii] != oceanID:
        makeChannel(x,y - 1)
        oceanMap.defineAreas(isSmallWaterMatch)
        oceanID = oceanMap.getOceanID()
    #E
    xx = x + 2
    yy = y 
    ii = oceanMap.getIndex(xx,yy)
    if ii > -1 and \
    oceanMap.getAreaByID(oceanMap.areaMap[ii]).water == True and \
    oceanMap.areaMap[ii] != oceanID:
        makeChannel(x + 1,y)
        oceanMap.defineAreas(isSmallWaterMatch)
        oceanID = oceanMap.getOceanID()
    #W
    xx = x - 2
    yy = y 
    ii = oceanMap.getIndex(xx,yy)
    if ii > -1 and \
    oceanMap.getAreaByID(oceanMap.areaMap[ii]).water == True and \
    oceanMap.areaMap[ii] != oceanID:
        makeChannel(x - 1,y)
        oceanMap.defineAreas(isSmallWaterMatch)
        oceanID = oceanMap.getOceanID()
    #NW
    xx = x - 1
    yy = y + 1
    ii = oceanMap.getIndex(xx,yy)
    if ii > -1 and \
    oceanMap.getAreaByID(oceanMap.areaMap[ii]).water == True and \
    oceanMap.areaMap[ii] != oceanID:
        makeChannel(x - 1,y)
        oceanMap.defineAreas(isSmallWaterMatch)
        oceanID = oceanMap.getOceanID()
    #NE
    xx = x + 1
    yy = y + 1
    ii = oceanMap.getIndex(xx,yy)
    if ii > -1 and \
    oceanMap.getAreaByID(oceanMap.areaMap[ii]).water == True and \
    oceanMap.areaMap[ii] != oceanID:
        makeChannel(x + 1,y)
        oceanMap.defineAreas(isSmallWaterMatch)
        oceanID = oceanMap.getOceanID()
    #SW
    xx = x - 1
    yy = y - 1
    ii = oceanMap.getIndex(xx,yy)
    if ii > -1 and \
    oceanMap.getAreaByID(oceanMap.areaMap[ii]).water == True and \
    oceanMap.areaMap[ii] != oceanID:
        makeChannel(x ,y - 1)
        oceanMap.defineAreas(isSmallWaterMatch)
        oceanID = oceanMap.getOceanID()
    #NW
    xx = x - 1
    yy = y + 1
    ii = oceanMap.getIndex(xx,yy)
    if ii > -1 and \
    oceanMap.getAreaByID(oceanMap.areaMap[ii]).water == True and \
    oceanMap.areaMap[ii] != oceanID:
        makeChannel(x,y + 1)
        oceanMap.defineAreas(isSmallWaterMatch)
        oceanID = oceanMap.getOceanID()
    return
def makeChannel(x,y):
    gc = CyGlobalContext()
    mmap = gc.getMap()
    terrainCoast = gc.getInfoTypeForString("TERRAIN_COAST")
    plot = mmap.plot(x,y)
    cleanUpLake(x,y)
    plot.setTerrainType(terrainCoast,True,True)
    plot.setRiverID(-1)
    plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    replaceRivers(x,y)
    i = GetIndex(x,y)
    sm.plotMap[i] = mc.OCEAN
    return
def expandLake(x,y,riversIntoLake,oceanMap):
    class LakePlot :
        def __init__(self,x,y,altitude):
            self.x = x
            self.y = y
            self.altitude = altitude
    gc = CyGlobalContext()
    mmap = gc.getMap()
    terrainCoast = gc.getInfoTypeForString("TERRAIN_COAST")
    lakePlots = list()
    lakeNeighbors = list()
    i = oceanMap.getIndex(x,y)
    desertModifier = 1.0
    if sm.terrainMap[i] == mc.DESERT:
        desertModifier = mc.DesertLakeModifier
    drainage = rm.drainageMap[i]
    lakeSize = max(3,int(drainage * mc.LakeSizePerDrainage * desertModifier ))
    start = LakePlot(x,y,sm.heightMap[i])
    lakeNeighbors.append(start)
#    print "lakeSize",lakeSize
    while lakeSize > 0 and len(lakeNeighbors) > 0:
#        lakeNeighbors.sort(key=operator.attrgetter('altitude'),reverse=False)
        lakeNeighbors.sort(lambda x,y:cmp(x.altitude,y.altitude))
        currentLakePlot = lakeNeighbors[0]
        del lakeNeighbors[0]
        lakePlots.append(currentLakePlot)
        plot = mmap.plot(currentLakePlot.x,currentLakePlot.y)
        #if you are erasing a river to make a lake, make the lake smaller
        if plot.isNOfRiver() == True or plot.isWOfRiver() == True:
            lakeSize -= 1
        makeChannel(currentLakePlot.x,currentLakePlot.y)
        #Add valid neighbors to lakeNeighbors
        for n in range(4):
            if n == 0:#N
                xx = currentLakePlot.x
                yy = currentLakePlot.y + 1
                ii = oceanMap.getIndex(xx,yy)
            elif n == 1:#S
                xx = currentLakePlot.x
                yy = currentLakePlot.y - 1
                ii = oceanMap.getIndex(xx,yy)
            elif n == 2:#E
                xx = currentLakePlot.x + 1
                yy = currentLakePlot.y
                ii = oceanMap.getIndex(xx,yy)
            elif n == 3:#W
                xx = currentLakePlot.x - 1
                yy = currentLakePlot.y 
                ii = oceanMap.getIndex(xx,yy)
            else:
                raise ValueError, "too many cardinal directions"
            if ii != -1:
                #if this neighbor is in water area, then quit
                areaID = oceanMap.areaMap[ii]
                if areaID == 0:
                    raise ValueError, "areaID = 0 while generating lakes. This is a bug"
                for n in range(len(oceanMap.areaList)):
                    if oceanMap.areaList[n].ID == areaID:
                        if oceanMap.areaList[n].water == True:
#                            print "lake touched waterID = %(id)3d with %(ls)3d squares unused" % {'id':areaID,'ls':lakeSize}
#                            print "n = %(n)3d" % {"n":n}
#                            print str(oceanMap.areaList[n])
                            return
                if rm.riverMap[ii] != rm.L and mmap.plot(xx,yy).isWater() == False:
                    lakeNeighbors.append(LakePlot(xx,yy,sm.heightMap[ii]))
        
        lakeSize -= 1
#    print "lake finished normally at %(x)2d,%(y)2d" % {"x":x,"y":y}
    return
            
def addLakes():
    print "Adding Lakes"
    gc = CyGlobalContext()
    mmap = gc.getMap()
    terrainCoast = gc.getInfoTypeForString("TERRAIN_COAST")
#    PrintFlowMap()
    oceanMap = Areamap(mc.width,mc.height,True,True)
    oceanMap.defineAreas(isSmallWaterMatch)
##    oceanMap.PrintList(oceanMap.areaList)
##    oceanMap.PrintAreaMap()
    for y in range(mc.height):
        for x in range(mc.width):
            i = GetIndex(x,y)
            if rm.flowMap[i] == rm.L:
                riversIntoLake = cleanUpLake(x,y)
                plot = mmap.plot(x,y)
                if len(riversIntoLake) > 0:
##                    plot.setRiverID(-1)
##                    plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
##                    plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
##                    #plot.setPlotType(PlotTypes.PLOT_OCEAN,True,True) setTerrain handles this already
##                    plot.setTerrainType(terrainCoast,True,True)
                    expandLake(x,y,riversIntoLake,oceanMap)
                else:
                    #no lake here, but in that case there should be no rivers either
                    plot.setRiverID(-1)
                    plot.setNOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
                    plot.setWOfRiver(False,CardinalDirectionTypes.NO_CARDINALDIRECTION)
    oceanMap.defineAreas(isSmallWaterMatch)
##    oceanMap.PrintList(oceanMap.areaList)
##    oceanMap.PrintAreaMap()
    for y in range(mc.height):
        for x in range(mc.width):
            i = GetIndex(x,y)
            makeHarbor(x,y,oceanMap)
    return
        
def addFeatures():
    NiTextOut("Generating Features  ...")
    print "Adding Features"
    gc = CyGlobalContext()
    mmap = gc.getMap()
    featureIce = gc.getInfoTypeForString("FEATURE_ICE")
    featureJungle = gc.getInfoTypeForString("FEATURE_JUNGLE")
    featureForest = gc.getInfoTypeForString("FEATURE_FOREST")
    featureOasis = gc.getInfoTypeForString("FEATURE_OASIS")
    featureFloodPlains = gc.getInfoTypeForString("FEATURE_FLOOD_PLAINS")
    FORESTLEAFY = 0
    FORESTEVERGREEN = 1
    FORESTSNOWY = 2

    createIce()
    #Now plant forest or jungle
##    PrintTempMap(tm,tm.tempMap)
##    PrintRainMap(rm,rm.rainMap,False)
    for y in range(mc.height):
        for x in range(mc.width):
            i = GetIndex(x,y)
            plot = mmap.plot(x,y)
            #forest and jungle
            if plot.isWater() == False and sm.terrainMap[i] != mc.DESERT and\
            plot.isPeak() == False:
                if sm.rainFallMap[i] > sm.plainsThreshold * mc.TreeFactor and\
                PRand.random() < mc.MaxTreeChance:#jungle
                    if sm.averageTempMap[i] > mc.JungleTemp:
                        if sm.terrainMap[i] == mc.PLAINS:
                            plot.setFeatureType(featureForest,FORESTLEAFY)
                        else:
                            plot.setFeatureType(featureJungle,0)
                    elif sm.averageTempMap[i] > mc.ForestTemp:
                        plot.setFeatureType(featureForest,FORESTLEAFY)
                    elif sm.averageTempMap[i] > mc.TundraTemp:
                        plot.setFeatureType(featureForest,FORESTEVERGREEN)
                    elif sm.averageTempMap[i] > mc.SnowTemp:
                        plot.setFeatureType(featureForest,FORESTSNOWY)
                elif sm.rainFallMap[i] > sm.desertThreshold:#forest
                    if sm.rainFallMap[i] > PRand.random() * sm.plainsThreshold * mc.TreeFactor / mc.MaxTreeChance:
                        if sm.averageTempMap[i] > mc.ForestTemp:
                           plot.setFeatureType(featureForest,FORESTLEAFY)
                        elif sm.averageTempMap[i] > mc.TundraTemp:
                            plot.setFeatureType(featureForest,FORESTEVERGREEN)
                        elif sm.averageTempMap[i] > mc.SnowTemp * 0.8:
                            plot.setFeatureType(featureForest,FORESTSNOWY)                
            #floodplains and Oasis
            elif sm.terrainMap[i] == mc.DESERT and sm.plotMap[i] != mc.HILLS and\
            sm.plotMap[i] != mc.PEAK and plot.isWater() == False:
                if plot.isRiver() == True:
                    plot.setFeatureType(featureFloodPlains,0)
                else:
                    #is this square surrounded by desert?
                    foundNonDesert = False
                    #print "trying to place oasis"
                    for yy in range(y - 1,y + 2):
                        for xx in range(x - 1,x + 2):
                            ii = GetIndex(xx,yy)
                            surPlot = mmap.plot(xx,yy)
                            if (sm.terrainMap[ii] != mc.DESERT and \
                            sm.plotMap[ii] != mc.PEAK):
                                #print "non desert neighbor"
                                foundNonDesert = True
                            elif surPlot == 0:
                                #print "neighbor off map"
                                foundNonDesert = True
                            elif surPlot.isWater() == True:
                                #print "water neighbor"
                                foundNonDesert = True
                            elif surPlot.getFeatureType() == featureOasis:
                                #print "oasis neighbor"
                                foundNonDesert = True
                    if foundNonDesert == False:
                        if PRand.random() < mc.OasisChance:
                            #print "placing oasis"
                            plot.setFeatureType(featureOasis,0)
                       # else:
                            #print "oasis failed random check"
            
    return
   
def createIce():
    gc = CyGlobalContext()
    mmap = gc.getMap()
    signadded = 0
    featureIce = gc.getInfoTypeForString("FEATURE_ICE")
    iceChance = mc.iceChance
    iceRange = mc.iceRange
    iceSlope = mc.iceSlope
    for y in range(iceRange):
        for x in range(mc.width):
            plot = mmap.plot(x,y)
            if plot != 0 and plot.isWater() == True and PRand.random() < iceChance:
                plot.setFeatureType(featureIce,0)
        iceChance *= iceSlope
    iceChance = mc.iceChance
    for y in range(mc.height - 1,mc.height - 1 - iceRange,-1):
        for x in range(mc.width):
            plot = mmap.plot(x,y)
            if plot != 0 and plot.isWater() == True and PRand.random() < iceChance:
                plot.setFeatureType(featureIce,0)
                if signadded == 0:
                    CyEngine().addSign(plot, -1, str(mc.randomSeed))
                    signadded = 1
        iceChance *= iceSlope
    if signadded == 0:
        CyEngine().addSign(plot, -1, str(mc.randomSeed))
        signadded = 1
        
def addBonuses():
    bp.AddBonuses()
    return
def assignStartingPlots():
    gc = CyGlobalContext()
    gameMap = CyMap()
    iPlayers = gc.getGame().countCivPlayersEverAlive()
    spf.SetStartingPlots()
def beforeInit():
    print "Initializing Custom Map Options"
    mc.initialize()
    mc.initInGameOptions()

def isClimateMap():
    return 0

def isSeaLevelMap():
    return 0

# Add huts to the map
# Use Civ4-specific code to place the hut
def placeHut(x,y):
    cigc = CyGlobalContext()
    gMap = CyMap()
    nativeHut = cigc.getInfoTypeForString("IMPROVEMENT_GOODY_HUT")
    hereGame = gMap.plot(x,y)
    hereGame.setImprovementType(nativeHut)

# Check to see if we can place a hut on a given square
def checkHut(hutSeen, x, y, distance):
    if hutSeen[(y * mc.width) + x] != 0:
        return False
    # If we can place a hut, make sure we can not place any future huts
    # within two squares of this hut
    lo = -2
    hi = 3
    if distance == 1:
        lo = -1
        hi = 2
    elif distance == 3:
        lo = -3
        hi = 4
    for xx in range(lo,hi):
        if x + xx >= 0 and x + xx < mc.width:
            for yy in range(lo,hi):
                if y + yy >= 0 and y + yy < mc.height:
                    hutSeen[((y + yy) * mc.width) + (x + xx)] = 1 # No hut here
    hutSeen[(y * mc.width) + x] = 2 # Physical hut
    placeHut(x,y)
    return True

def addGoodies():
    gc = CyGlobalContext()
    mmap = gc.getMap()
    hutPlacementRules = mmap.getCustomMapOption(3)

    # Note that these constants change below, these are only default values
    # The chance out of 1000 that we have a goody hut on a desert
    # (either flat or hill) square
    desertHutChance = 37 # 3.7 percent
    # The chance out of 1000 we will have a goody hut on a non-desert
    # non-ice land (flat/hill) square
    normalHutChance = 25 # 2.5 percent
    # Minimum distance between huts, divided by 2.  1 means one hut
    # per 3x3 square; 2 means 1 hut/5x5; 3 is 1 hut/7x7
    distance = 2

    if hutPlacementRules == 0: # Civ4 default behavior (huts move each time)
        CyPythonMgr().allowDefaultImpl()
        return
    elif hutPlacementRules == 1: # No huts
        return
    # Note that rare/many desert/many everywhere use fixed per-seed huts
    elif hutPlacementRules == 3: # Rare huts
        desertHutChance = 7 # 0.7 percent
        normalHutChance = 5 # 0.5 percent
        distance = 3
    elif hutPlacementRules == 4: # Many desert huts
        desertHutChance = 105 # 10.5 percent
        normalHutChance = 25 # 2.5 percent (same as above)
        distance = 1
    elif hutPlacementRules == 5: # Many huts everywhere
        desertHutChance = 105 # 10.5 percent
        normalHutChance = 75 # 7.5 percent 
        distance = 1

    # Fixed per-seed huts (each map seed always makes the same huts)

    hutSeen = [0 for i in range(mc.width * mc.height)]
    for x in range(mc.width):
        for y in range(mc.height):
            i = (y * mc.width) + x
            if(sm.plotMap[i] == mc.HILLS or sm.plotMap[i] == mc.LAND):
                # Different terrains have different hut chances
                if(sm.terrainMap[i] == mc.DESERT):
                    if(PRand.randint(0,999) < desertHutChance):
                        checkHut(hutSeen, x, y, distance)
                elif(sm.terrainMap[i] != mc.SNOW):
                    if(PRand.randint(0,999) < normalHutChance):
                        checkHut(hutSeen, x, y, distance)

if __name__ == "__main__":
    import sys
    if(len(sys.argv) > 2 and sys.argv[1] == '--test'):
        do_rg32_test(sys.argv[2])
    else:
        print("Usage: python2 ArabianTotestra.py --test {input}")