git.maemo.org Git - lordsawar/blob - src/MapGenerator.cpp

   1 // Copyright (C) 2002 Vibhu Rishi
   2 // Copyright (C) 2002, 2003, 2004, 2005, 2006 Ulf Lorenz
   3 // Copyright (C) 2004 David Barnsdale
   4 // Copyright (C) 2003 Michael Bartl
   5 // Copyright (C) 2004, 2005 Andrea Paternesi
   6 // Copyright (C) 2006, 2007, 2008, 2009 Ben Asselstine
   7 // Copyright (C) 2008 Janek Kozicki
   8 //
   9 //  This program is free software; you can redistribute it and/or modify
  10 //  it under the terms of the GNU General Public License as published by
  11 //  the Free Software Foundation; either version 3 of the License, or
  12 //  (at your option) any later version.
  13 //
  14 //  This program is distributed in the hope that it will be useful,
  15 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 //  GNU Library General Public License for more details.
  18 //
  19 //  You should have received a copy of the GNU General Public License
  20 //  along with this program; if not, write to the Free Software
  21 //  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  22 //  02110-1301, USA.
  23
  24 #include <stdlib.h>
  25 #include <iostream>
  26 #include <math.h>
  27 #include <algorithm>
  28 #include <set>
  29 #include <string.h>
  30
  31 //#include <boost/foreach.hpp>
  32
  33 #include "MapGenerator.h"
  34 #include "GameMap.h"
  35 #include "stack.h"
  36 #include "path.h"
  37 #include "File.h"
  38 #include "citylist.h"
  39 #include "city.h"
  40 #include "roadlist.h"
  41 #include "road.h"
  42 #include "portlist.h"
  43 #include "port.h"
  44 #include "ruinlist.h"
  45 #include "ruin.h"
  46 #include "templelist.h"
  47 #include "temple.h"
  48 #include "bridgelist.h"
  49 #include "bridge.h"
  50 #include "armysetlist.h"
  51 #include "army.h"
  52 #include "vector.h"
  53 #include "RoadPathCalculator.h"
  54 #include "cityset.h"
  55
  56 #define debug(x) {std::cerr<<__FILE__<<": "<<__LINE__<<": "<<x<<std::endl<<std::flush;}
  57 //#define debug(x)
  58 #define offmap(bx,by) (by<0)||(by>=d_height)||(bx<0)||(bx>=d_width)
  59
  60 using namespace std;
  61
  62 //-------------------------------------------------------------------
  63
  64 MapGenerator::MapGenerator()
  65     //set reasonable default values
  66     :d_terrain(0), d_building(0), d_pswamp(2), d_pwater(25), d_pforest(3),
  67     d_phills(5), d_pmountains(5), d_nocities(11), d_notemples(9), d_noruins(20),
  68     d_nosignposts(30), cityset(NULL)
  69
  70 {
  71     d_xdir[0]=0;d_xdir[1]=-1;d_xdir[2]=-1;d_xdir[3]=-1;d_xdir[4]=0;d_xdir[5]=1;d_xdir[6]=1;d_xdir[7]=1;
  72     d_ydir[0]=-1;d_ydir[1]=-1;d_ydir[2]=0;d_ydir[3]=1;d_ydir[4]=1;d_ydir[5]=1;d_ydir[6]=0;d_ydir[7]=-1;
  73 }
  74
  75 MapGenerator::~MapGenerator()
  76 {
  77     if (d_terrain)
  78         delete[] d_terrain;
  79     if (d_building)
  80         delete[] d_building;
  81 }
  82
  83 int MapGenerator::setNoCities(int nocities)
  84 {
  85     if (nocities <= 0)
  86         return -1;
  87
  88     int tmp = d_nocities;
  89     d_nocities = nocities;
  90     return tmp;
  91 }
  92
  93 int MapGenerator::setNoRuins(int noruins)
  94 {
  95     if (noruins < 0)
  96         return -1;
  97
  98     int tmp = d_noruins;
  99     d_noruins = noruins;
 100     return tmp;
 101 }
 102
 103 int MapGenerator::setNoSignposts(int nosignposts)
 104 {
 105     if (nosignposts < 0)
 106         return -1;
 107
 108     int tmp = d_nosignposts;
 109     d_nosignposts = nosignposts;
 110     return tmp;
 111 }
 112
 113 int MapGenerator::setNoTemples(int notemples)
 114 {
 115     if (notemples < 0)
 116         return -1;
 117
 118     int tmp = d_notemples;
 119     d_notemples = notemples;
 120     return tmp;
 121 }
 122
 123 void MapGenerator::setPercentages(int pwater, int pforest, int pswamp,
 124                                     int phills, int pmountains)
 125 {
 126     if ((pswamp < 0) || (pwater < 0) || (pforest < 0) || (phills < 0)
 127         || (pmountains < 0))
 128         return;
 129
 130     if (pswamp + pwater + pforest + phills + pmountains > 100)
 131         return;
 132
 133     d_pswamp = pswamp;
 134     d_pwater = pwater;
 135     d_pforest = pforest;
 136     d_phills = phills;
 137     d_pmountains = pmountains;
 138 }
 139
 140 /**
 141  * Generates a random map . The map is stored as a char array of size
 142  * 100x100. Each character stands for something. We use :
 143  * M = mountains
 144  * h = hills
 145  * ~ = water
 146  * $ = forest
 147  * . = plains
 148  * _ = swamps
 149  * C = city/castle
 150  * r = ruins
 151  * T = temple
 152  *   = nothing
 153  * c = part of city/castle
 154  * See the TileMapTypes enum at the beginning of the class definition.
 155  *
 156  * See printMap() which is used for debugging maps.
 157  */
 158 void MapGenerator::makeMap(int width, int height, bool roads)
 159 {
 160     d_width = width;
 161     d_height = height;
 162
 163     //initialize terrain and building arrays
 164     d_terrain = new Tile::Type[width*height];
 165     d_building = new Maptile::Building[width*height];
 166     for (int i = 0; i < height; i++)
 167         for (int j = 0; j < width; j++)
 168             d_building[i*width + j] = Maptile::NONE;
 169
 170     debug("Making random map:");
 171
 172     // create the terrain
 173     debug("flatening plains");
 174     progress.emit(.090, _("flattening plains..."));
 175     makePlains();
 176     debug("raining water");
 177     progress.emit(.180, _("raining water..."));
 178     makeTerrain(Tile::WATER, d_pwater, true);
 179     makeStreamer(Tile::WATER, d_pwater/3, 3);
 180     rescueLoneTiles(Tile::WATER,Tile::GRASS,true);
 181     makeRivers();
 182     verifyIslands();
 183     debug("raising hills");
 184     progress.emit(.270, _("raising hills..."));
 185     makeTerrain(Tile::HILLS, d_phills, false);
 186     debug("raising mountains");
 187     progress.emit(.360, _("raising mountains..."));
 188     makeTerrain(Tile::MOUNTAIN, d_pmountains, false);
 189     makeStreamer(Tile::MOUNTAIN, d_pmountains/3, 3);
 190     rescueLoneTiles(Tile::MOUNTAIN,Tile::GRASS,false);
 191     surroundMountains(0, d_width, 0, d_height);
 192     debug("planting forest");
 193     progress.emit(.450, _("planting forests..."));
 194     makeTerrain(Tile::FOREST, d_pforest, false);
 195     debug("watering swamps");
 196     progress.emit(.540, _("watering swamps..."));
 197     makeTerrain(Tile::SWAMP, d_pswamp, false);
 198     debug("normalizing terrain");
 199     progress.emit(.630, _("normalizing terrain..."));
 200     normalize();
 201
 202     // place buildings
 203     debug("building cities");
 204     progress.emit(.720, _("building cities..."));
 205     makeCities(d_nocities);
 206
 207     if (roads)
 208       {
 209         debug("paving roads");
 210         progress.emit(.810, _("paving roads..."));
 211         makeRoads();
 212       }
 213     rescueLoneTiles(Tile::MOUNTAIN,Tile::HILLS,false);
 214
 215     debug("ruining ruins");
 216     progress.emit(.810, _("ruining ruins..."));
 217     makeBuildings(Maptile::RUIN,d_noruins);
 218     debug("spawning temples");
 219     progress.emit(.900, _("spawning temples..."));
 220     makeBuildings(Maptile::TEMPLE,d_notemples);
 221     debug("building bridges");
 222     if (roads == true)
 223       {
 224         progress.emit(.950, _("building bridges..."));
 225         makeBridges();
 226       }
 227     debug("raising signs");
 228     progress.emit(.990, _("raising signs..."));
 229     makeBuildings(Maptile::SIGNPOST,d_nosignposts);
 230
 231     debug("Done making map.");
 232
 233 //    printMap();
 234 }
 235
 236 #define  NORTH_SOUTH_BRIDGE 1
 237 #define  EAST_WEST_BRIDGE 2
 238
 239 void MapGenerator::placeBridge(Vector<int> pos, int type)
 240 {
 241   Bridgelist *bl = Bridgelist::getInstance();
 242   if (type == NORTH_SOUTH_BRIDGE)
 243     {
 244       d_building[pos.y*d_width + pos.x] = Maptile::BRIDGE;
 245       d_building[(pos.y + 1)*d_width + pos.x] = Maptile::BRIDGE;
 246       bl->add(new Bridge(Vector<int>(pos.x, pos.y)));
 247       bl->add(new Bridge(Vector<int>(pos.x+1, pos.y)));
 248     }
 249   else if (type == EAST_WEST_BRIDGE)
 250     {
 251       d_building[pos.y*d_width + pos.x] = Maptile::BRIDGE;
 252       d_building[pos.y*d_width + pos.x + 1] = Maptile::BRIDGE;
 253       bl->add(new Bridge(Vector<int>(pos.x, pos.y)));
 254       bl->add(new Bridge(Vector<int>(pos.x, pos.y+1)));
 255     }
 256   GameMap::getInstance()->calculateBlockedAvenues();
 257 }
 258
 259 bool MapGenerator::findBridgePurpose(Vector<int> pos, int type,
 260                                      Vector<int> &src, Vector<int> &dest)
 261 {
 262   if (type == EAST_WEST_BRIDGE)
 263     {
 264       src = GameMap::getInstance()->findNearestObjectToTheWest(pos);
 265       dest = GameMap::getInstance()->findNearestObjectToTheEast(pos);
 266     }
 267   else if (type == NORTH_SOUTH_BRIDGE)
 268     {
 269       src = GameMap::getInstance()->findNearestObjectToTheNorth(pos);
 270       dest = GameMap::getInstance()->findNearestObjectToTheSouth(pos);
 271     }
 272   if (src == Vector<int>(-1,-1) || dest == Vector<int>(-1,-1))
 273     return false;
 274   return true;
 275 }
 276
 277 bool MapGenerator::canPlaceBridge(Vector<int> pos, int type, Vector<int> &src, Vector<int> &dest)
 278 {
 279   if (d_building[pos.y*d_width + pos.x] == Maptile::NONE &&
 280       findBridgePurpose(pos, type, src, dest) == true)
 281     return true;
 282   return false;
 283 }
 284
 285 void MapGenerator::makeBridges()
 286 {
 287   GameMap::deleteInstance();
 288   Citylist::deleteInstance();
 289   Roadlist::deleteInstance();
 290   Ruinlist::deleteInstance();
 291   Templelist::deleteInstance();
 292   Portlist::deleteInstance();
 293   Bridgelist::deleteInstance();
 294
 295   GameMap::setWidth(d_width);
 296   GameMap::setHeight(d_height);
 297   GameMap::getInstance("default", "default", "default")->fill(this);
 298
 299   //the game map class smooths the map, so let's take what it smoothed.
 300   for (int y = 0; y < d_height; y++)
 301     for (int x = 0; x < d_width; x++)
 302       d_terrain[y*d_width + x] =
 303         GameMap::getInstance()->getTile(x, y)->getMaptileType();
 304
 305   //load up the roadlist, and stuff.
 306
 307   for (int y = 0; y < d_height; y++)
 308     for (int x = 0; x < d_width; x++)
 309       {
 310         if (d_building[y*d_width + x] == Maptile::CITY)
 311           Citylist::getInstance()->add
 312             (new City(Vector<int>(x,y), cityset->getCityTileWidth()));
 313         else if (d_building[y*d_width + x] == Maptile::ROAD)
 314           Roadlist::getInstance()->add(new Road(Vector<int>(x,y)));
 315         else if (d_building[y*d_width + x] == Maptile::RUIN)
 316           Ruinlist::getInstance()->add
 317             (new Ruin(Vector<int>(x,y), cityset->getRuinTileWidth()));
 318         else if (d_building[y*d_width + x] == Maptile::TEMPLE)
 319           Templelist::getInstance()->add
 320             (new Temple(Vector<int>(x,y), cityset->getTempleTileWidth()));
 321         else if (d_building[y*d_width + x] == Maptile::PORT)
 322           Portlist::getInstance()->add(new Port(Vector<int>(x,y)));
 323       }
 324   GameMap::getInstance()->calculateBlockedAvenues();
 325
 326   Vector<int> src, dest;
 327   std::vector<pair<int , Vector<int> > >  bridges;
 328   bridges = findBridgePlaces();
 329   for (std::vector<pair<int, Vector<int> > >::iterator it = bridges.begin();
 330        it != bridges.end(); it++)
 331     {
 332       Vector<int> pos = (*it).second + Vector<int>(1,1);
 333       Vector<int> edge1;
 334       Vector<int> edge2;
 335       if ((*it).first == NORTH_SOUTH_BRIDGE)
 336         {
 337           edge1 = pos - Vector<int>(0, 1);
 338           edge2 = pos + Vector<int>(0, 2);
 339         }
 340       else if ((*it).first == EAST_WEST_BRIDGE)
 341         {
 342           edge1 = pos - Vector<int>(1, 0);
 343           edge2 = pos + Vector<int>(2, 0);
 344         }
 345       if (offmap(edge1.x, edge1.y) || offmap(edge2.x, edge2.y))
 346         continue;
 347       if (canPlaceBridge((*it).second + Vector<int>(1,1), (*it).first, src,
 348                          dest) == true)
 349         {
 350           int leg1 = tryRoad (src, edge1);
 351           int leg2 = tryRoad (dest, edge2);
 352           int shortcut = tryRoad (src, dest);
 353           bool construct_bridge_and_roads = true;
 354           if (leg1 <= 0 || leg2 <= 0)
 355             construct_bridge_and_roads = false;
 356           if (shortcut > 0 && (leg1 + leg2 + 2) > shortcut)
 357             construct_bridge_and_roads = false;
 358
 359           if (construct_bridge_and_roads)
 360             {
 361               makeRoad(src, edge1);
 362               makeRoad(dest, edge2);
 363               placeBridge(pos, (*it).first);
 364             }
 365         }
 366         progress.emit(.950, _("paving bridges..."));
 367     }
 368
 369   Roadlist::deleteInstance();
 370   Ruinlist::deleteInstance();
 371   Templelist::deleteInstance();
 372   GameMap::deleteInstance();
 373   Citylist::deleteInstance();
 374   Portlist::deleteInstance();
 375   Bridgelist::deleteInstance();
 376 }
 377
 378 void MapGenerator::printMap(int j, int i)
 379 {
 380     char ch='?';
 381     bool adom_convention=true; // well, except mountains
 382     switch(d_terrain[j*d_width + i])
 383     {
 384         case Tile::MOUNTAIN:  ch=adom_convention ? 'M' : 'M';break; // mountains
 385         case Tile::HILLS   :  ch=adom_convention ? '~' : 'h';break; // hills
 386         case Tile::WATER   :  ch=adom_convention ? '=' : '~';break; // water
 387         case Tile::FOREST  :  ch=adom_convention ? '&' : '$';break; // forest
 388         case Tile::GRASS   :  ch=adom_convention ? '.' : '.';break; // plains
 389         case Tile::SWAMP   :  ch=adom_convention ? '"' : '_';break; // swamps
 390         case Tile::VOID    :  ch=adom_convention ? '?' : '?';break;
 391
 392             // cannot print those, actually because they don't exist in Tile::Type
 393             //     ch='C';break; // city/castle
 394             //     ch='r';break; // ruins
 395             //     ch='T';break; // temple
 396             //     ch=' ';break; // nothing
 397             //     ch='c';break; // part of city/castle
 398     }
 399     std::cout << ch;
 400 }
 401
 402 void MapGenerator::printMap()
 403 {
 404     for(int j = 0; j < d_height; j++)
 405     {
 406         for(int i = 0; i < d_width; i++)
 407             printMap(j,i);
 408         std::cout << "\n";
 409     }
 410     std::cout << "\n";
 411 }
 412
 413 const Tile::Type* MapGenerator::getMap(int& width, int& height) const
 414 {
 415     width = d_width;
 416     height = d_height;
 417     return d_terrain;
 418 }
 419
 420 const Maptile::Building* MapGenerator::getBuildings(int& width, int& height) const
 421 {
 422     width = d_width;
 423     height = d_height;
 424     return d_building;
 425 }
 426
 427 void MapGenerator::makePlains()
 428 {
 429     for(int j = 0; j < d_height; j++)
 430         for(int i = 0; i < d_width; i++)
 431             d_terrain[j*d_width + i] = Tile::GRASS;
 432 }
 433
 434 void MapGenerator::connectWithWater(Vector<int> from, Vector<int> to)
 435 {
 436     Vector<float> delta = from - to;
 437     if (dist<float>(from,to) > (float)(d_width*0.4))
 438         // we don't want to mess up whole map with straight lines
 439         return;
 440
 441     int kind(rand()%4);
 442     delta /= length(delta)*2;
 443     for(Vector<float>path = Vector<float>(from)+delta*4 ; dist<float>(path,Vector<float>(to)-delta*4) > 0.5 ; path -= delta)
 444     {
 445         int j = (int)(path.x);
 446         int i = (int)(path.y);
 447
 448         if(rand()%3 == 0)
 449             kind = rand()%4;
 450         switch(kind)
 451         {
 452             case 0:
 453                 if((!(offmap(i,j))) && (!(offmap(i-1,j-1))))
 454                 {
 455                     d_terrain[(j  )*d_width + i  ] = Tile::WATER;
 456                     d_terrain[(j-1)*d_width + i-1] = Tile::WATER;
 457                     d_terrain[(j  )*d_width + i-1] = Tile::WATER;
 458                     d_terrain[(j-1)*d_width + i  ] = Tile::WATER;
 459                 }; break;
 460
 461             case 1:
 462                 if((!(offmap(i,j))) && (!(offmap(i+1,j+1))))
 463                 {
 464                     d_terrain[(j  )*d_width + i  ] = Tile::WATER;
 465                     d_terrain[(j+1)*d_width + i+1] = Tile::WATER;
 466                     d_terrain[(j  )*d_width + i+1] = Tile::WATER;
 467                     d_terrain[(j+1)*d_width + i  ] = Tile::WATER;
 468                 }; break;
 469
 470             case 2:
 471                 if((!(offmap(i,j))) && (!(offmap(i-1,j+1))))
 472                 {
 473                     d_terrain[(j  )*d_width + i  ] = Tile::WATER;
 474                     d_terrain[(j+1)*d_width + i-1] = Tile::WATER;
 475                     d_terrain[(j  )*d_width + i-1] = Tile::WATER;
 476                     d_terrain[(j+1)*d_width + i  ] = Tile::WATER;
 477                 }; break;
 478
 479             case 3:
 480                 if((!(offmap(i,j))) && (!(offmap(i+1,j-1))))
 481                 {
 482                     d_terrain[(j  )*d_width + i  ] = Tile::WATER;
 483                     d_terrain[(j-1)*d_width + i+1] = Tile::WATER;
 484                     d_terrain[(j  )*d_width + i+1] = Tile::WATER;
 485                     d_terrain[(j-1)*d_width + i  ] = Tile::WATER;
 486                 }; break;
 487         }
 488     }
 489 }
 490
 491 void MapGenerator::findAreasOf(Tile::Type THIS_TILE,std::vector<std::vector<int> >& box,int& how_many)
 492 {
 493     box.resize(d_height);
 494     for(int j = 0; j < d_height; j++)
 495         box[j].resize(d_width,0);
 496
 497     // find all enclosed areas by scanning the map
 498     // distinct areas have different numbers in box
 499     for(int j = 1; j < d_height-1; j++)
 500         for(int i = 1; i < d_width-1; i++)
 501             if (box[j][i]==0 &&
 502                     d_terrain[j*d_width + i] == THIS_TILE &&
 503                     (
 504                      (d_terrain[(j-1)*d_width + i-1] == THIS_TILE &&
 505                       d_terrain[(j  )*d_width + i-1] == THIS_TILE &&
 506                       d_terrain[(j-1)*d_width + i  ] == THIS_TILE)  ||
 507
 508                      (d_terrain[(j-1)*d_width + i  ] == THIS_TILE &&
 509                       d_terrain[(j-1)*d_width + i+1] == THIS_TILE &&
 510                       d_terrain[(j  )*d_width + i+1] == THIS_TILE) ||
 511
 512                      (d_terrain[(j  )*d_width + i+1] == THIS_TILE &&
 513                       d_terrain[(j+1)*d_width + i+1] == THIS_TILE &&
 514                       d_terrain[(j+1)*d_width + i  ] == THIS_TILE) ||
 515
 516                      (d_terrain[(j+1)*d_width + i  ] == THIS_TILE &&
 517                       d_terrain[(j+1)*d_width + i-1] == THIS_TILE &&
 518                       d_terrain[(j  )*d_width + i-1] == THIS_TILE))
 519                )
 520             {
 521                 box[j][i]=++how_many+3000;
 522                 int counter=1;
 523                 while(counter != 0)
 524                 {
 525                     counter=0;
 526                     for(int J = 1; J < d_height-1; J++)
 527                         for(int I = 1; I < d_width-1; I++)
 528                         {
 529                             if(d_terrain[J*d_width + I] == THIS_TILE &&
 530                                     box[J][I]    ==0 &&
 531                                     (box[J-1][I  ]==how_many+3000 ||
 532                                      box[J  ][I-1]==how_many+3000 ||
 533                                      box[J  ][I+1]==how_many+3000 ||
 534                                      box[J+1][I  ]==how_many+3000))
 535                             {
 536                                 ++counter;
 537                                 box[J][I]=how_many+2000;
 538                             }
 539                         }
 540                     for(int J = 0; J < d_height; J++)
 541                         for(int I = 0; I < d_width; I++)
 542                         {
 543                             if (box[J][I]==how_many+3000)
 544                                 box[J][I]=how_many;
 545                             if (box[J][I]==how_many+2000)
 546                                 box[J][I]=how_many+3000;
 547                         }
 548                 }
 549             }
 550 }
 551
 552 void MapGenerator::verifyIslands()
 553 {
 554     int how_many=0;
 555     std::vector<std::vector<int> > box;
 556     findAreasOf(Tile::GRASS,box,how_many);
 557
 558     // count the size of each area
 559     std::vector<float> counts;
 560     counts.resize(how_many+2,0);
 561     for(int j = 0; j < d_height; j++)
 562         for(int i = 0; i < d_width; i++)
 563             if(box[j][i] != 0)
 564                 counts[box[j][i]] += 1;
 565
 566     // find four largest land areas
 567     std::set<int> largest;largest.clear();
 568     int max;
 569     for(int z=0 ; z<4 ; ++z)
 570     {
 571         max = -1;
 572         for(size_t i=0 ; i<counts.size() ; ++i)
 573         {
 574             if(counts[i] > max && largest.find(counts[i]) == largest.end())
 575                 max = counts[i];
 576         }
 577         largest.insert(max);
 578     }
 579
 580     // largest are good. Also one/third of all others is good:
 581     std::set<int> good(largest);
 582     for(size_t i=0 ; i<counts.size() ; ++i)
 583         if(rand()%3 == 0) // that's one/third here
 584             good.insert(counts[i]);
 585
 586     // now, eliminate all land that is not good
 587     for(int I=0 ; I<(int)(counts.size()) ; ++I)
 588         if(good.find(counts[I]) == good.end())
 589             for(int j = 1; j < d_height-1; j++)
 590                 for(int i = 1; i < d_width-1; i++)
 591                     if(box[j][i] == I)
 592                         d_terrain[j*d_width + i] = Tile::WATER;
 593 }
 594
 595 void MapGenerator::makeRivers()
 596 {
 597     // river style:
 598     //  1 - plenty of short rivers and islands
 599     //  2 - longer rivers, less islands
 600     //  3 - even longer rivers, even less islands
 601     int river_style=rand()%3+1;
 602
 603     // count how many separate bodies of water were found
 604     int how_many;
 605
 606     int iter=0; // avoid deadlocks
 607     while(++iter < 20)
 608     {
 609         how_many=0;
 610
 611         std::vector<std::vector<int> > box;
 612
 613         findAreasOf(Tile::WATER,box,how_many);
 614
 615         // this loop allows maximum 3 distinctly separated bodies of water
 616         // so no need to continue the algorithm
 617         if(how_many<4)
 618             break;
 619
 620         // find two biggest bodies of water, and calculate centers for all of them
 621         std::vector< Vector<float> > centers;
 622         centers.resize(how_many+2,Vector<float>(0,0));
 623         std::vector<float> counts;
 624         counts.resize(how_many+2,0);
 625         for(int j = 0; j < d_height; j++)
 626             for(int i = 0; i < d_width; i++)
 627                 if(box[j][i] != 0)
 628                 {
 629                     counts[box[j][i]] += 1;
 630                     centers[box[j][i]] += Vector<float>(j,i);
 631                 }
 632         // divide sum by counts to get a center
 633         int max_count=0,max_count_2=0;
 634         for(int h = 0; h < how_many+2; ++h)
 635         {
 636             if(counts[h]>0)
 637             {
 638                 centers[h] /= counts[h];
 639                 if(max_count < (int)(counts[h]))
 640                     max_count = (int)(counts[h]);
 641                 if(max_count_2 < (int)(counts[h]) && (int)(counts[h]) != max_count)
 642                     max_count_2 = (int)(counts[h]);
 643                 int J=(int)(centers[h].x), I=(int)(centers[h].y);
 644                 if(box[J][I] != h)
 645                 // center doesn't necessarily fall on water tile, so fix this.
 646                 {
 647                     //      // for debugging...
 648                     //      box[J][I]+=5000;
 649                     int i_up=0,i_dn=0,j_up=0,j_dn=0;
 650                     while((I+i_up <  d_width-1 ) && (box[J     ][I+i_up] != h)) ++i_up;
 651                     while((I-i_dn >  0         ) && (box[J     ][I-i_dn] != h)) ++i_dn;
 652                     while((J+j_up <  d_height-1) && (box[J+j_up][I     ] != h)) ++j_up;
 653                     while((J-j_dn >  0         ) && (box[J-j_dn][I     ] != h)) ++j_dn;
 654
 655                     int shortest = std::min( std::min(i_up,i_dn) , std::min(j_up,j_dn));
 656
 657                     if(shortest == i_up && I+i_up <  d_width)
 658                         centers[h] = Vector<float>( J      , I+i_up );
 659                     else
 660                         if(shortest == i_dn && I-i_dn >= 0      )
 661                             centers[h] = Vector<float>( J      , I-i_dn );
 662                         else
 663                             if(shortest == j_up && J+j_up <  d_height)
 664                                 centers[h] = Vector<float>( J+j_up , I      );
 665                             else
 666                                 if(shortest == j_dn && J-j_dn >= 0       )
 667                                     centers[h] = Vector<float>( J+j_dn , I      );
 668                                 else
 669                                 {
 670                                     std::cout << "Sages are wondering about unforeseen mysteries behind the edge of the world.\n";
 671                                     counts[h] = -1; // that's ok, but an interesting case. I'd like to see a map with such water :)
 672                                     // FIXME - can you make a message box here?
 673                                     //MessageBox("Message from author: this is algorithmically a very interesting map, please make screenshot and send to cosurgi@gmail.com");
 674                                 }
 675                 }
 676                 //      // for debugging...
 677                 //      box[(int)(centers[h].x)][(int)(centers[h].y)]+=4000;
 678             }
 679         }
 680
 681         // determine what are the biggest bodies of water here
 682         int the_biggest_area=0,second_biggest_area=0;
 683         for(int h = 0; h < how_many+2; ++h)
 684         {
 685             if(counts[h]==max_count   && max_count   != 0)
 686                 the_biggest_area = h;
 687             if(counts[h]==max_count_2 && max_count_2 != 0)
 688                 second_biggest_area = h;
 689         }
 690
 691         // find shortest distances between areas
 692         std::vector<std::vector<std::pair<float, std::pair<Vector<int>, Vector<int> > > > > distances; // I would prefer boost::tuple, but oh well...
 693         distances.resize(how_many+2);
 694         for(int h = 0; h < how_many+2; ++h)
 695         {
 696             distances[h].resize(how_many+3,std::make_pair(0,std::make_pair(Vector<int>(0,0),Vector<int>(0,0))));
 697             for(int k = h+1; k < how_many+2; ++k)
 698             {
 699                 if(counts[h] > 0 && counts[k] > 0) // h and k are two different areas
 700                 {
 701                     // find tile from area h closest to the center of k
 702                     float min_dist = d_height*d_height;
 703                     float min_h_j=0,min_h_i=0;
 704                     for(int j = 1; j < d_height-1; j++)
 705                         for(int i = 1; i < d_width-1; i++)
 706                             if(box[j][i] == h)
 707                             {
 708                                 float dj = j - centers[k].x;
 709                                 float di = i - centers[k].y;
 710                                 float dist = dj*dj + di*di;
 711                                 if(dist < min_dist)
 712                                 {
 713                                     min_dist = dist;
 714                                     min_h_j = j;
 715                                     min_h_i = i;
 716                                 }
 717                             }
 718
 719                     // then find tile from area k closest to that tile from h
 720                     min_dist = d_height * d_height;
 721                     float min_k_j=0,min_k_i=0;
 722                     for(int j = 1; j < d_height-1; j++)
 723                         for(int i = 1; i < d_width-1; i++)
 724                             if(box[j][i] == k)
 725                             {
 726                                 float dj = j - min_h_j;
 727                                 float di = i - min_h_i;
 728                                 float dist = dj*dj + di*di;
 729                                 if(dist < min_dist)
 730                                 {
 731                                     min_dist = dist;
 732                                     min_k_j = j;
 733                                     min_k_i = i;
 734                                 }
 735                             }
 736
 737                     if (min_k_j != 0 &&
 738                             min_h_j != 0 &&
 739                             min_k_i != 0 &&
 740                             min_h_i != 0)
 741                     {
 742                         float dj = min_k_j - min_h_j;
 743                         float di = min_k_i - min_h_i;
 744                         distances[h][k] = std::make_pair(dj*dj + di*di , std::make_pair(Vector<int>(min_h_j,min_h_i) , Vector<int>(min_k_j,min_k_i)) );
 745                     }
 746                 }
 747             }
 748         }
 749
 750         for(int connect_some_closest=0; connect_some_closest<14; connect_some_closest+=river_style)
 751         {
 752             // if river_style is 1 then
 753             //   connect 10 closest to each other, and 4 closest to two biggest bodies of water
 754             // otherwise skip some - connect fewer of them.
 755             int closest_h=-1,closest_k=-1,min=d_height*d_height;
 756             int start_h=0;
 757             if(connect_some_closest < 2 ) start_h=the_biggest_area;
 758             else
 759                 if(connect_some_closest < 4) start_h=second_biggest_area;
 760             for(int h = start_h; h < ((connect_some_closest >= 4) ? (how_many+2) : start_h+1); ++h)
 761                 for(int k = h+1; k < how_many+2; ++k)
 762                     if(counts[h] > 0 && counts[k] > 0)
 763                         if(distances[h][k].first > 0 && min > distances[h][k].first)
 764                         {
 765                             min = distances[h][k].first;
 766                             closest_h = h;
 767                             closest_k = k;
 768                         }
 769             if (closest_h != -1 &&
 770                 closest_k != -1)
 771             {
 772                 connectWithWater(distances[closest_h][closest_k].second.first , distances[closest_h][closest_k].second.second);
 773                 // mark as done:
 774                 distances[closest_h][closest_k].first = d_height*d_height;
 775             }
 776         }
 777         //          // for debugging...   print whole box
 778         //          std::cerr << how_many << " separate bodies of water found.\n";
 779         //          std::cerr << the_biggest_area << " is the biggest\n";
 780         //          std::cerr << second_biggest_area << " is second in size\n";
 781         //          std::vector<int> a;
 782         //          BOOST_FOREACH(a,box)
 783         //          {
 784         //              BOOST_FOREACH(int i,a)
 785         //              {
 786         //                  if(i<4000)
 787         //                      std::cout << i << " ";
 788         //                  else
 789         //                      if(i<5000)
 790         //                      std::cout << "X" << " ";
 791         //                      else
 792         //                      if(i<7000)
 793         //                      std::cout << "%" << " ";
 794         //                      else
 795         //                      if(i<14000)
 796         //                      std::cout << "!" << " ";
 797         //                      else
 798         //                      std::cout << "|" << " ";
 799         //              }
 800         //              std::cout << "\n";
 801         //          }
 802         //          std::cout << "\n";
 803
 804     };
 805     //if(how_many>1)
 806         //std::cout << "There are " << how_many << (how_many<4?(std::string(" seas")):(std::string(" lakes"))) << " on this map.\n";
 807     //else
 808         //std::cout << "There is 1 sea on this map.\n";
 809     //std::cout << "River style was: " << river_style << "\n";
 810 }
 811
 812
 813 /**
 814  * Makes Terrains.
 815  * The algorithm is as follows :
 816  * 1. Find a random starting location
 817  * 2. chose a random direction , if x is the starting location, the direction
 818  *    can be from 0-7 as follows :
 819  *    +-+-+-+
 820  *    |0|1|2|
 821  *    +-+-+-+
 822  *    |7|x|3|
 823  *    +-+-+-+
 824  *    |6|5|4|
 825  *    +-+-+-+
 826  * 3. Check if there is some other terrain there ('.' = plains is okay)
 827  * 4. Move one tile in this direction, mutate the tile and continue with 2
 828  * 5. If we hit a dead end (all directions non-grass), continue with 1
 829  */
 830 void MapGenerator::makeTerrain(Tile::Type t, int percent, bool contin)
 831 {
 832     // calculate the total number of tiles for this terrain
 833     int terrain = d_width*d_height*percent / 100;
 834     int placed = 0;  // total of current terrain placed so far
 835
 836     while(placed != terrain)
 837     {
 838         // find a random starting position
 839         int x = rand() % d_width;
 840         int y = rand() % d_height;
 841         if (seekPlain(x, y) == false)
 842           continue;
 843
 844
 845         // now go on until we hit a dead end
 846         while (placed < terrain)
 847         {
 848             // if we are on grass, modify this tile first
 849             if (d_terrain[y*d_width + x] == Tile::GRASS)
 850             {
 851                 d_terrain[y*d_width + x] = t;
 852                 placed++;
 853                 continue;
 854             }
 855
 856             // from a random direction, check all directions for further progress
 857             int loop = 0;
 858             for (int dir = rand()%8; loop < 8; loop++, dir = (dir+1)%8)
 859             {
 860                 int tmpx = x + d_xdir[dir];
 861                 int tmpy = y + d_ydir[dir];
 862
 863                 // reject invalid data
 864                 if (offmap(tmpx, tmpy) || d_terrain[tmpy*d_width + tmpx] != Tile::GRASS)
 865                     continue;
 866
 867                 // else move our region of interest by one tile
 868                 x = tmpx;
 869                 y = tmpy;
 870                 d_terrain[y*d_width + x] = t;
 871                 placed++;
 872                 break;
 873             }
 874
 875             // we have hit a dead end, i.e. we are only surrounded by non-grass
 876             // tiles. Either choose a new random starting point or, if contin
 877             // is set, find a close one via seekPlain()
 878             if (loop == 8)
 879             {
 880                 if (contin)
 881                   {
 882                     if (seekPlain(x, y) == false)
 883                       continue;
 884                   }
 885                 else
 886                     break;
 887             }
 888         }
 889     }
 890 }
 891
 892 /**
 893  * Makes streaming terrain features.
 894  * The algorithm is as follows :
 895  * 1. Find a random starting location
 896  * 2. chose a random direction , if x is the starting location, the direction
 897  *    can be from 0-7 as follows :
 898  *    +-+-+-+
 899  *    |0|1|2|
 900  *    +-+-+-+
 901  *    |7|x|3|
 902  *    +-+-+-+
 903  *    |6|5|4|
 904  *    +-+-+-+
 905  * 3. Drop the tile and move in the direction
 906  * 4. Change the direction every so often
 907  * 5. Keep doing this until we go off the map or we've dropped enough tiles
 908  *
 909  */
 910 void MapGenerator::makeStreamer(Tile::Type t, int percent, int thick)
 911 {
 912     // calculate the total number of tiles for this terrain
 913     int terrain = d_width*d_height*percent / 100;
 914     int placed = 0;  // total of current terrain placed so far
 915     int dir;
 916     int i;
 917
 918     while(placed < terrain)
 919     {
 920         // find a random starting position
 921         int x = rand() % d_width;
 922         int y = rand() % d_height;
 923         if (seekPlain(x, y) == false)
 924           continue;
 925         dir = rand()%8; // pick a random direction
 926         // now go on until we hit a dead end
 927         while (placed < terrain)
 928         {
 929             // if we are on grass, modify this tile first
 930             if (d_terrain[y*d_width + x] == Tile::GRASS)
 931             {
 932                 d_terrain[y*d_width + x] = t;
 933                 placed++;
 934                 continue;
 935             }
 936
 937             if (rand() % 2 == 0)
 938               {
 939                 if (rand() % 2 == 0)
 940                   {
 941                     dir++;
 942                     if (dir > 7)
 943                       dir = 0;
 944                   }
 945                 else
 946                   {
 947                     dir--;
 948                     if (dir < 0)
 949                       dir = 7;
 950                   }
 951             }
 952
 953             {
 954                 int tmpx = x + d_xdir[dir];
 955                 int tmpy = y + d_ydir[dir];
 956
 957                 // reject invalid data
 958                 if (offmap(tmpx, tmpy))// || d_terrain[tmpy*d_width + tmpx] != Tile::GRASS)
 959                     break;
 960
 961                 // else move our region of interest by one tile
 962                 x = tmpx;
 963                 y = tmpy;
 964                 d_terrain[y*d_width + x] = t;
 965                 placed++;
 966                 switch (dir)
 967                   {
 968                     case 1: case 2: case 6: case 5:
 969                       {
 970                         for (i = 1; i <= thick ; i++)
 971                           {
 972                             if (offmap(x+i, y))
 973                               continue;
 974                             d_terrain[y*d_width + x+i] = t;
 975                             placed++;
 976                           }
 977                       }
 978                       break;
 979                     case 7: case 3: case 0: case 4:
 980                       {
 981                         for (i = 1; i <= thick; i++)
 982                           {
 983                             if (offmap(x, y+i))
 984                               continue;
 985                             d_terrain[(y+i)*d_width + x] = t;
 986                             placed++;
 987                           }
 988                       }
 989                       break;
 990                   }
 991             }
 992
 993         }
 994     }
 995
 996 }
 997
 998 bool MapGenerator::seekPlain(int& x, int& y)
 999 {
1000     int orig_x = x;
1001     int orig_y = y;
1002     /* The algorithm here uses a large list of tiles to be checked.
1003      * In the beginning, it is filled with the tiles surrounding the starting
1004      * tile. Each tile is then checked if it contains grass. If not, all
1005      * surrounding tiles are added to the list (we have to take some care to
1006      * avoid infinite loops).
1007      *
1008      * Another way of describing it: The algorithm checks all tiles around the
1009      * position for the existence of grass. It then checks the tiles in larger
1010      * and larger circles around the position until it finds a grass tile.
1011      */
1012     if (d_terrain[y*d_width + x] == Tile::GRASS)
1013         return true;
1014
1015     std::deque<Vector<int> > tiles;
1016
1017     // fill the list with initial values; the rand is there to avoid a bias
1018     // (i.e. prefer a certain direction)
1019     for (int dir = rand() % 8, i = 0; i < 8; i++, dir = (dir+1)%8)
1020         tiles.push_back(Vector<int>(x + d_xdir[dir], y + d_ydir[dir]));
1021
1022     // now loop until all tiles were checked (should hardly happen)
1023     while (!tiles.empty())
1024     {
1025         Vector<int> p = tiles.front();
1026         tiles.pop_front();
1027
1028         if (offmap(p.x, p.y))
1029             continue;
1030
1031         // if we have found a patch of grass, we are lucky and return
1032         if (d_terrain[p.y*d_width + p.x] == Tile::GRASS)
1033         {
1034             x = p.x;
1035             y = p.y;
1036             return true;
1037         }
1038
1039         // not found? Well, then append the surrounding tiles. To avoid double-
1040         // checking (and therefore an infinite loop), only certain surrounding
1041         // tiles are appended. See the following sketch:
1042         //
1043         //              ebbbe
1044         //              b   b
1045         //              b x b
1046         //              b   b
1047         //              ebbbe
1048         //
1049         // This is a circle of radius 2 around the position x. In the case of border
1050         // tiles, only the tile directly outerwards is appended, the edge tiles
1051         // (which can be identified by distx == disty) append two new border and
1052         // one new edge tile.
1053         int dx = p.x - x;
1054         int dy = p.y - y;
1055
1056         // edge tile; append three new tiles
1057         if (abs(dx) == abs(dy))
1058         {
1059             int newx = p.x - 1;
1060             int newy = p.y - 1;
1061
1062             if (dx > 0)
1063                 newx = p.x + 1;
1064             if (dy > 0)
1065                 newy = p.y + 1;
1066
1067             tiles.push_back(Vector<int>(newx, newy));
1068             tiles.push_back(Vector<int>(newx, p.y));
1069             tiles.push_back(Vector<int>(p.x, newy));
1070         }
1071         else
1072         {
1073             if (abs(dx) > abs(dy) && dx > 0)        // right border
1074                 tiles.push_back(Vector<int>(p.x + 1, p.y));
1075             else if (abs(dx) > abs(dy) && dx < 0)   //left border
1076                 tiles.push_back(Vector<int>(p.x - 1, p.y));
1077             else if (abs(dx) < abs(dy) && dy > 0)   // top border
1078                 tiles.push_back(Vector<int>(p.x, p.y + 1));
1079             else if (abs(dx) < abs(dy) && dy < 0)   // lower border
1080                 tiles.push_back(Vector<int>(p.x, p.y - 1));
1081         }
1082     }
1083
1084     // if this line is ever reached, we haven't found a free grass tile
1085     // (should only happen under really exceptional circumstances)
1086     x = orig_x;
1087     y = orig_y;
1088     return false;
1089 }
1090
1091 bool MapGenerator::inhospitableTerrain(int x, int y, unsigned int width)
1092 {
1093   for (unsigned int i = 0; i < width; i++)
1094     for (unsigned int j = 0; j < width; j++)
1095       if (d_terrain[(y+i)*d_width +(x+j)] == Tile::WATER ||
1096           d_terrain[(y+i)*d_width +(x+j)] == Tile::MOUNTAIN)
1097         return true;
1098   return false;
1099 }
1100
1101 void MapGenerator::makeCities(int cities)
1102 {
1103
1104     int city_count = 0;
1105     int iterations = 0;
1106
1107     // place the cities
1108     while(city_count < cities)
1109     {
1110         int x = rand()%(d_width-2);
1111         int y = rand()%(d_height-2);
1112         if (inhospitableTerrain(x, y, cityset->getCityTileWidth()) && (iterations < 1000))
1113         {
1114             iterations++;
1115             continue;
1116         }
1117
1118         // check if we can put the building
1119         if (!canPutCity(x, y) && iterations < 1000)
1120         {
1121             iterations++;
1122             continue;
1123         }
1124
1125         putCity(x, y, city_count);
1126         iterations=0;
1127     }
1128
1129 }
1130
1131 bool MapGenerator::canPutCity(int x,int y)
1132 {
1133   for (unsigned int i = 0; i < cityset->getCityTileWidth(); i++)
1134     for (unsigned int j = 0; j < cityset->getCityTileWidth(); j++)
1135       if (canPutBuilding(x+i,y+j) == false)
1136         return false;
1137
1138   return true;
1139 }
1140
1141 void MapGenerator::putCity(int x, int y, int& city_count)
1142 {
1143         d_building[y*d_width + x] = Maptile::CITY;
1144
1145         //cities shall only sit on grass tiles
1146         for (unsigned int i = 0; i < cityset->getCityTileWidth(); i++)
1147           for (unsigned int j = 0; j < cityset->getCityTileWidth(); j++)
1148             d_terrain[(y+i)*d_width + (x+j)] = Tile::GRASS;
1149         //cities cannot neighbor with mountain tiles
1150         for (int Y = -1; Y <= (int)cityset->getCityTileWidth(); ++Y )
1151             for (int X = -1; X <= (int)cityset->getCityTileWidth(); ++X)
1152                 if (d_terrain[(y+Y)*d_width + x+X] == Tile::MOUNTAIN)
1153                     d_terrain[(y+Y)*d_width + x+X] = Tile::HILLS;
1154
1155         city_count++;
1156 }
1157
1158 void MapGenerator::makeBuildings(Maptile::Building b, int building)
1159 {
1160     int i, j, x, y;
1161     int iterations = 10;
1162     bool found_place = false;
1163
1164     unsigned int width = 1;
1165
1166     switch (b)
1167       {
1168       case Maptile::CITY:
1169         width = cityset->getCityTileWidth(); break;
1170       case Maptile::RUIN:
1171         width = cityset->getRuinTileWidth(); break;
1172       case Maptile::TEMPLE:
1173         width = cityset->getTempleTileWidth(); break;
1174       case Maptile::NONE:
1175       case Maptile::SIGNPOST:
1176       case Maptile::ROAD:
1177       case Maptile::PORT:
1178       case Maptile::BRIDGE:
1179         width = 1;
1180         break;
1181       }
1182
1183    //If number of iterations is smaller 10, look for a suitable
1184    //place. If this number is exceeded, place the temple on an
1185    //island if neccessary.
1186     for (i = 0; i < building; i++)
1187     {
1188         for (j = 0; j < iterations; j++)
1189         {
1190              x = rand()%d_width;
1191              y = rand()%d_height;
1192
1193              found_place = true;
1194              for (unsigned int k = 0; k < width; k++)
1195                for (unsigned int l = 0; l < width; l++)
1196                  if (canPutBuilding(x+k, y+l) == false)
1197                    found_place = false;
1198
1199              if (found_place == true)
1200                break;
1201         }
1202
1203         if (found_place == true)
1204         {
1205              d_terrain[y*d_width + x] = Tile::GRASS;
1206              d_building[y*d_width + x] = b;
1207              found_place = false;
1208         }
1209     }
1210 }
1211
1212 /**
1213  * canPutBuilding
1214  * Checks if we can put a building at the specified place.
1215  * If we are on a square with water, we cannot put it
1216  * nor if it is too close.
1217  * Checks for neighboring buildings yet sometimes these
1218  * are bang next to each other - why?
1219  * UL: Propably too many tries, then the algorithm forces the
1220  * building to be placed.
1221  */
1222
1223 bool MapGenerator::canPutBuilding(int x,int y)
1224 {
1225     // if the building is on water or mountains, return false
1226     if (d_terrain[y*d_width +x] != Tile::GRASS )
1227         return false;
1228
1229     //if the building is close to the map boundaries, return false
1230     if ((x < 3) || (x > (d_width-3)) || (y < 3) || (y > (d_height-3)))
1231         return false;
1232
1233     int dist = (int)cityset->getCityTileWidth() + 1;
1234     //if there is another building too close, return false
1235     for (int locx = x-dist; locx <= x+dist; locx++)
1236         for (int locy = y-dist; locy <= y+dist; locy++)
1237         {
1238             if (offmap(locx, locy))
1239                 continue;
1240             if (d_building[locy*d_width + locx] != Maptile::NONE)
1241                 return false;
1242         }
1243     // everything okay here! return true
1244     return true;
1245
1246 }
1247
1248 bool MapGenerator::tryToPlaceCity(int px,int py ,int& city_count)
1249 {
1250     // first, try to place the city at the given location
1251     if (canPutCity(px, py))
1252     {
1253         putCity(px, py, city_count);
1254         return true;
1255     }
1256
1257     // else try all surrounding squares
1258     for (int dir = 0; dir < 8; dir++)
1259         if (canPutCity(px + d_xdir[dir], py + d_ydir[dir]))
1260         {
1261             putCity(px + d_xdir[dir], py + d_ydir[dir], city_count);
1262             return true;
1263         }
1264
1265     return false;
1266 }
1267
1268 void MapGenerator::normalize()
1269 {
1270     std::map<guint32,guint32> ajacentTer;
1271     Tile::Type curTer=Tile::NONE, ajTer=Tile::NONE;
1272
1273     // that was 40 before. Now with rivers, the smaller the value - the more connected rivers we got.
1274     int center_tiles = rand()%40;
1275     //std::cerr << center_tiles << "\% chance of disconnecting rivers.\n";
1276
1277     // Go through every tile bar the outer edge
1278     for(int globy = 1; globy < (d_height-2); globy++)
1279         for(int globx = 1; globx < (d_width-2); globx++)
1280         {
1281             curTer = d_terrain[globy*d_width + globx];
1282
1283             // reset all counters
1284             ajacentTer[Tile::GRASS] = 0;
1285             ajacentTer[Tile::WATER] = 0;
1286             ajacentTer[Tile::FOREST] = 0;
1287             ajacentTer[Tile::HILLS] = 0;
1288             ajacentTer[Tile::MOUNTAIN] = 0;
1289             ajacentTer[Tile::SWAMP] = 0;
1290
1291             // count how many neighbours of each type we have
1292             for(int locx = globx - 1; locx <= globx+1; locx++)
1293                 for(int locy = globy - 1; locy <= globy+1; locy++)
1294                 {
1295                      ajTer = d_terrain[locy*d_width +locx];
1296                      ajacentTer[ajTer] += 1;
1297                 }
1298
1299             // we have counted our own tile as well
1300             ajacentTer[curTer] -= 1;
1301
1302             if (curTer==Tile::WATER) // For the moment only water is normalized
1303             {
1304                 if (ajacentTer[curTer]==0)
1305                     d_terrain[globy*d_width +globx] = Tile::GRASS;
1306                 else if ((ajacentTer[curTer]==1) && (rand()%100 < 95 ))
1307                     d_terrain[globy*d_width +globx] = Tile::GRASS;
1308                 else if ((ajacentTer[curTer]==2) && (rand()%100 < 70 ))
1309                     d_terrain[globy*d_width +globx] = Tile::GRASS;
1310                 else if ((ajacentTer[curTer]==3) && (rand()%100 < center_tiles ))
1311                     d_terrain[globy*d_width +globx] = Tile::GRASS;
1312             }
1313             else
1314             {
1315                 if (ajacentTer[Tile::WATER]==8)
1316                     d_terrain[globy*d_width +globx] = Tile::WATER;
1317                 else if ((ajacentTer[Tile::WATER]==7) && (rand()%100 < 70 ))
1318                     d_terrain[globy*d_width +globx] = Tile::WATER;
1319                 else if ((ajacentTer[Tile::WATER]==6) && (rand()%100 < 40 ))
1320                     d_terrain[globy*d_width +globx] = Tile::WATER;
1321              }
1322         }
1323 }
1324
1325 void MapGenerator::calculateBlockedAvenue(int x, int y)
1326 {
1327   for (int i = x - 1; i <= x + 1; i++)
1328     {
1329       for (int j = y - 1; j <= y + 1; j++)
1330         {
1331           if (i < 0 || i >= d_width)
1332             continue;
1333           if (j < 0 || j >= d_height)
1334             continue;
1335           GameMap::getInstance()->calculateBlockedAvenue(i, j);
1336         }
1337     }
1338 }
1339
1340 bool MapGenerator::placePort(int x, int y)
1341 {
1342   //if (Citylist::getInstance()->getNearestCity(Vector<int>(x, y), 2) == NULL)
1343     {
1344       if (d_building[y*d_width + x] == 0)
1345         {
1346           Portlist *pl = Portlist::getInstance();
1347           d_building[y*d_width + x] = Maptile::PORT;
1348           pl->add(new Port(Vector<int>(x, y)));
1349           calculateBlockedAvenue(x, y);
1350           return true;
1351         }
1352     }
1353   return false;
1354 }
1355
1356 int MapGenerator::tryRoad(Vector<int> src, Vector<int>dest)
1357 {
1358   return tryRoad (src.x, src.y, dest.x, dest.y);
1359 }
1360
1361 int MapGenerator::tryRoad(int src_x, int src_y, int dest_x, int dest_y)
1362 {
1363   Vector<int> src(src_x, src_y);
1364   Vector<int> dest(dest_x, dest_y);
1365
1366   Path *p = new Path();
1367   Stack s(NULL, src);
1368
1369   ArmyProto *basearmy = ArmyProto::createScout();
1370   Army *a = Army::createNonUniqueArmy(*basearmy);
1371   delete basearmy;
1372   s.push_back(a);
1373   // try to get there with a scout
1374   guint32 moves = p->calculate(&s, dest, false);
1375
1376   delete p;
1377   return (int)moves;
1378 }
1379
1380 bool MapGenerator::makeRoad(Vector<int> src, Vector<int>dest)
1381 {
1382   return makeRoad (src.x, src.y, dest.x, dest.y);
1383 }
1384
1385 bool MapGenerator::makeRoad(int src_x, int src_y, int dest_x, int dest_y)
1386 {
1387   bool retval = true;
1388   GameMap *gm = GameMap::getInstance();
1389   Vector<int> src(src_x, src_y);
1390   Vector<int> dest(dest_x, dest_y);
1391
1392   RoadPathCalculator rpc(src);
1393   Path *p = rpc.calculate(dest);
1394
1395   if (p->size() > 0)
1396     {
1397       Roadlist *rl = Roadlist::getInstance();
1398       for (Path::iterator it = p->begin(); it != p->end(); it++)
1399         {
1400           int x = (*it).x;
1401           int y = (*it).y;
1402           if (gm->getTile(x, y)->getMaptileType() == Tile::WATER &&
1403               gm->getTile(x, y)->getBuilding() != Maptile::BRIDGE)
1404             {
1405               retval = false;
1406               break;
1407             }
1408           Citylist *cl = Citylist::getInstance();
1409           if (cl->getObjectAt(x, y) == NULL)
1410             {
1411               if (d_building[y*d_width + x] == 0)
1412                 {
1413                   d_building[y*d_width + x] = Maptile::ROAD;
1414                   rl->add(new Road(Vector<int>(x, y)));
1415                   calculateBlockedAvenue(x, y);
1416                 }
1417             }
1418         }
1419
1420     }
1421   else
1422     retval = false;
1423   delete p;
1424
1425   return retval;
1426 }
1427
1428 bool MapGenerator::isAccessible(Vector<int> src, Vector<int> dest)
1429 {
1430   return isAccessible (src.x, src.y, dest.x, dest.y);
1431 }
1432
1433 bool MapGenerator::isAccessible (int src_x, int src_y, int dest_x, int dest_y)
1434 {
1435   bool retval = true;
1436   Vector<int> src(src_x, src_y);
1437   Vector<int> dest(dest_x, dest_y);
1438
1439   Path *p = new Path();
1440   Stack s(NULL, src);
1441
1442   ArmyProto *basearmy = ArmyProto::createScout();
1443   Army *a = Army::createNonUniqueArmy(*basearmy);
1444   delete basearmy;
1445   s.push_back(a);
1446   // try to get there with a scout
1447   if (p->calculate(&s, dest, true) <= 0)
1448     retval = false;
1449   delete p;
1450
1451   return retval;
1452 }
1453
1454 bool MapGenerator::makeAccessible(Vector<int> src, Vector<int> dest)
1455 {
1456   return makeAccessible(src.x, src.y, dest.x, dest.y);
1457 }
1458
1459 bool MapGenerator::makeAccessible(int src_x, int src_y, int dest_x, int dest_y)
1460 {
1461   bool retval = true;
1462   GameMap *gm = GameMap::getInstance();
1463   Vector<int> src(src_x, src_y);
1464   Vector<int> dest(dest_x, dest_y);
1465
1466   Path *p = new Path();
1467   Stack s(NULL, src);
1468
1469   ArmyProto *basearmy = ArmyProto::createScout();
1470   Army *a = Army::createNonUniqueArmy(*basearmy);
1471   delete basearmy;
1472   s.push_back(a);
1473   guint32 moves = p->calculate(&s, dest, false);
1474
1475   if (moves <= 0)
1476     {
1477       s.clear();
1478       delete a;
1479       ArmyProto *basearmy = ArmyProto::createBat();
1480       a = Army::createNonUniqueArmy(*basearmy);
1481       delete basearmy;
1482       s.push_back(a);
1483       moves = p->calculate(&s, dest, false);
1484     }
1485
1486   if (moves != 0)
1487     {
1488       Path::iterator it = p->begin();
1489       Path::iterator nextit = it;
1490       nextit++;
1491       for ( ; nextit != p->end(); it++, nextit++)
1492         {
1493           int x = (*it).x;
1494           int y = (*it).y;
1495           int nextx = (*nextit).x;
1496           int nexty = (*nextit).y;
1497           if (d_terrain[y*d_width + x] == Tile::MOUNTAIN)
1498             {
1499               d_terrain[y*d_width +x] = Tile::HILLS;
1500               Maptile *t = new Maptile(gm->getTileset(),
1501                                        x, y, Tile::HILLS, NULL);
1502               gm->setTile(x, y, t);
1503               calculateBlockedAvenue(x, y);
1504             }
1505           if (d_terrain[y*d_width + x] == Tile::WATER &&
1506               d_terrain[nexty*d_width + nextx] != Tile::WATER)
1507             {
1508               if (placePort(x, y) == true)
1509                 {
1510                   if (isAccessible(src_x, src_y, dest.x, dest.y))
1511                     {
1512                       retval = true;
1513                       break;
1514                     }
1515                 }
1516             }
1517           else if (d_terrain[y*d_width + x] != Tile::WATER &&
1518                    d_terrain[nexty*d_width + nextx] == Tile::WATER)
1519             {
1520               if (placePort(nextx, nexty) == true)
1521                 {
1522                   if (isAccessible(src_x, src_y, dest.x, dest.y))
1523                     {
1524                       retval = true;
1525                       break;
1526                     }
1527                 }
1528             }
1529
1530         }
1531     }
1532   else
1533     retval = false;
1534
1535   delete p;
1536   return retval;
1537 }
1538
1539 std::vector<pair<int , Vector<int> > > MapGenerator::findBridgePlaces()
1540 {
1541     std::vector<pair<int , Vector<int> > > result;
1542     result.clear();
1543
1544     for(int j = 1; j < d_height-5; j++)
1545         for(int i = 1; i < d_width-5; i++)
1546         {
1547             if (
1548                 d_terrain[(j  )*d_width + i+1] != Tile::WATER &&
1549                 d_terrain[(j+1)*d_width + i+1] == Tile::WATER &&
1550                 d_terrain[(j+2)*d_width + i+1] == Tile::WATER &&
1551                 d_terrain[(j+3)*d_width + i+1] != Tile::WATER &&
1552                 d_terrain[(j+1)*d_width + i  ] == Tile::WATER &&
1553                 d_terrain[(j+2)*d_width + i  ] == Tile::WATER &&
1554                 d_terrain[(j+1)*d_width + i+2] == Tile::WATER &&
1555                 d_terrain[(j+2)*d_width + i+2] == Tile::WATER
1556                 )
1557             {
1558                 int count_left =
1559                 (int)(d_terrain[(j  )*d_width + i  ] == Tile::WATER) +
1560                 (int)(d_terrain[(j+1)*d_width + i  ] == Tile::WATER) +
1561                 (int)(d_terrain[(j+2)*d_width + i  ] == Tile::WATER) +
1562                 (int)(d_terrain[(j+3)*d_width + i  ] == Tile::WATER) +
1563                 (int)(d_terrain[(j  )*d_width + i-1] == Tile::WATER) +
1564                 (int)(d_terrain[(j+1)*d_width + i-1] == Tile::WATER) +
1565                 (int)(d_terrain[(j+2)*d_width + i-1] == Tile::WATER) +
1566                 (int)(d_terrain[(j+3)*d_width + i-1] == Tile::WATER);
1567                 int count_right =
1568                 (int)(d_terrain[(j  )*d_width + i+2] == Tile::WATER) +
1569                 (int)(d_terrain[(j+1)*d_width + i+2] == Tile::WATER) +
1570                 (int)(d_terrain[(j+2)*d_width + i+2] == Tile::WATER) +
1571                 (int)(d_terrain[(j+3)*d_width + i+2] == Tile::WATER) +
1572                 (int)(d_terrain[(j  )*d_width + i+3] == Tile::WATER) +
1573                 (int)(d_terrain[(j+1)*d_width + i+3] == Tile::WATER) +
1574                 (int)(d_terrain[(j+2)*d_width + i+3] == Tile::WATER) +
1575                 (int)(d_terrain[(j+3)*d_width + i+3] == Tile::WATER);
1576
1577                 if(count_left > 5 && count_right > 5)
1578                     result.push_back(std::make_pair(1, Vector<int>(i,j) ));
1579             }
1580             if (
1581                 d_terrain[(j+1)*d_width + i  ] != Tile::WATER &&
1582                 d_terrain[(j+1)*d_width + i+1] == Tile::WATER &&
1583                 d_terrain[(j+1)*d_width + i+2] == Tile::WATER &&
1584                 d_terrain[(j+1)*d_width + i+3] != Tile::WATER &&
1585                 d_terrain[(j  )*d_width + i+1] == Tile::WATER &&
1586                 d_terrain[(j  )*d_width + i+2] == Tile::WATER &&
1587                 d_terrain[(j+2)*d_width + i+1] == Tile::WATER &&
1588                 d_terrain[(j+2)*d_width + i+2] == Tile::WATER
1589                 )
1590             {
1591                 int count_top =
1592                 (int)(d_terrain[(j  )*d_width + i  ] == Tile::WATER) +
1593                 (int)(d_terrain[(j  )*d_width + i+1] == Tile::WATER) +
1594                 (int)(d_terrain[(j  )*d_width + i+2] == Tile::WATER) +
1595                 (int)(d_terrain[(j  )*d_width + i+3] == Tile::WATER) +
1596                 (int)(d_terrain[(j-1)*d_width + i  ] == Tile::WATER) +
1597                 (int)(d_terrain[(j-1)*d_width + i+1] == Tile::WATER) +
1598                 (int)(d_terrain[(j-1)*d_width + i+2] == Tile::WATER) +
1599                 (int)(d_terrain[(j-1)*d_width + i+3] == Tile::WATER);
1600
1601                 int count_bottom =
1602                 (int)(d_terrain[(j+2)*d_width + i  ] == Tile::WATER) +
1603                 (int)(d_terrain[(j+2)*d_width + i+1] == Tile::WATER) +
1604                 (int)(d_terrain[(j+2)*d_width + i+2] == Tile::WATER) +
1605                 (int)(d_terrain[(j+2)*d_width + i+3] == Tile::WATER) +
1606                 (int)(d_terrain[(j+3)*d_width + i  ] == Tile::WATER) +
1607                 (int)(d_terrain[(j+3)*d_width + i+1] == Tile::WATER) +
1608                 (int)(d_terrain[(j+3)*d_width + i+2] == Tile::WATER) +
1609                 (int)(d_terrain[(j+3)*d_width + i+3] == Tile::WATER);
1610
1611                 if(count_top > 5 && count_bottom > 5)
1612                     result.push_back(std::make_pair(2, Vector<int>(i,j) ));
1613             }
1614         }
1615     // randomize
1616     std::random_shuffle(result.begin(),result.end());
1617
1618     // remove those that are too close to each other
1619     std::set<int> bad;bad.clear();
1620     for(size_t r = 0; r<result.size() ; ++r)
1621         for(size_t s = r+1; s<result.size() ; ++s)
1622             if(dist(Vector<float>(result[r].second),Vector<float>(result[s].second)) < 4.5)
1623                 bad.insert(r);
1624     std::vector<pair<int , Vector<int> > > filter;filter.clear();
1625     for(size_t r = 0; r<result.size() ; ++r)
1626         if(bad.find(r) == bad.end())
1627             filter.push_back(result[r]);
1628     result=filter;
1629
1630     return result;
1631 }
1632
1633 void MapGenerator::makeRoads()
1634 {
1635   GameMap::deleteInstance();
1636   Citylist::deleteInstance();
1637   Roadlist::deleteInstance();
1638   Portlist::deleteInstance();
1639
1640   GameMap::setWidth(d_width);
1641   GameMap::setHeight(d_height);
1642   GameMap::getInstance("default", "default", cityset->getSubDir())->fill(this);
1643   Roadlist::getInstance();
1644   //the game map class smooths the map, so let's take what it smoothed.
1645   for (int y = 0; y < d_height; y++)
1646     for (int x = 0; x < d_width; x++)
1647       d_terrain[y*d_width + x] =
1648         GameMap::getInstance()->getTile(x, y)->getMaptileType();
1649
1650   for (int y = 0; y < d_height; y++)
1651     for (int x = 0; x < d_width; x++)
1652       {
1653         if (d_building[y*d_width + x] == Maptile::CITY)
1654           Citylist::getInstance()->add
1655             (new City(Vector<int>(x,y), cityset->getCityTileWidth()));
1656       }
1657   GameMap::getInstance()->calculateBlockedAvenues();
1658
1659   Citylist *cl = Citylist::getInstance();
1660   for (Citylist::iterator it = cl->begin(); it != cl->end(); it++)
1661     {
1662       if (rand() % 2 == 0)
1663         continue;
1664       City *c = cl->getNearestCityPast((*it)->getPos(), 13);
1665       Vector<int> dest = c->getPos();
1666       Vector<int> src = (*it)->getPos();
1667       //does it already have a road going to it?
1668       if (Roadlist::getInstance()->getNearestObjectBefore(dest,
1669                                                           c->getSize() + 1))
1670         continue;
1671
1672       makeRoad(src, dest);
1673       progress.emit(.810, _("paving roads..."));
1674     }
1675
1676   //make all cities accessible by allowing movement to a central city
1677   Vector<int> pos = GameMap::getCenterOfMap();
1678   City *center = cl->getNearestCity(pos);
1679   for (Citylist::iterator it = cl->begin(); it != cl->end(); it++)
1680     {
1681       if (center == *it)
1682         continue;
1683       if (isAccessible(center->getPos(), (*it)->getPos()) == false)
1684         {
1685         makeAccessible(center->getPos(), (*it)->getPos());
1686         }
1687       progress.emit(.810, _("paving roads..."));
1688     }
1689
1690   Roadlist::deleteInstance();
1691   GameMap::deleteInstance();
1692   Citylist::deleteInstance();
1693   Portlist::deleteInstance();
1694 }
1695
1696 void MapGenerator::rescueLoneTiles(Tile::Type FIND_THIS, Tile::Type REPLACE, bool grow)
1697 {
1698     int box[3][3];
1699     memset (box, 0, sizeof (box));
1700
1701     if(grow)
1702     {
1703         for(int j = 1; j < d_height-1; j++)
1704             for(int i = 1; i < d_width-1; i++)
1705             {
1706                 if (d_terrain[j*d_width + i] == FIND_THIS &&
1707                    (d_terrain[(j-1)*d_width + i-1] == FIND_THIS &&
1708                     d_terrain[(j  )*d_width + i-1] == FIND_THIS &&
1709                     d_terrain[(j-1)*d_width + i  ] != FIND_THIS))
1710                     d_terrain[(j-1)*d_width + i  ] =  FIND_THIS;
1711             }
1712     }
1713
1714     for(int iteration=0; iteration <8 ;++iteration)
1715     {
1716         for(int j = 0; j < d_height; j++)
1717             for(int i = 0; i < d_width; i++)
1718             {
1719                 if(d_terrain[j*d_width + i] == FIND_THIS)
1720                 {
1721                     for (int I = -1; I <= +1; ++I)
1722                         for (int J = -1; J <= +1; ++J)
1723                             if (!(offmap(i+I,j+J)))
1724                                 box[J+1][I+1] = (d_terrain[(j+J)*d_width + (i+I)] == d_terrain[j*d_width + i]);
1725                             else
1726                                 box[J+1][I+1] = 0;
1727
1728                     if (!box[0][2] && !box[1][2] && /***********/
1729                         /***********/  box[1][1] &&  box[2][1] &&
1730                         !box[0][0] && !box[1][0]    /***********/)
1731                             d_terrain[j*d_width + i] = REPLACE;
1732                     if (/***********/ !box[1][2] && !box[2][2] &&
1733                          box[0][1] &&  box[1][1] && /***********/
1734                         /***********/ !box[1][0] && !box[2][0])
1735                             d_terrain[j*d_width + i] = REPLACE;
1736                     if (!box[0][2] && /***********/ !box[2][2] &&
1737                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1738                         /***********/  box[1][0]    /***********/)
1739                             d_terrain[j*d_width + i] = REPLACE;
1740                     if (/***********/  box[1][2] && /***********/
1741                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1742                         !box[0][0] && /***********/ !box[2][0])
1743                             d_terrain[j*d_width + i] = REPLACE;
1744
1745                     if (/***********/ !box[1][2] && /***********/
1746                         /***********/  box[1][1] &&  box[2][1] &&
1747                         !box[0][0] && !box[1][0]    /***********/)
1748                             d_terrain[j*d_width + i] = REPLACE;
1749                     if (/***********/ !box[1][2] && /***********/
1750                          box[0][1] &&  box[1][1] && /***********/
1751                         /***********/ !box[1][0] && !box[2][0])
1752                             d_terrain[j*d_width + i] = REPLACE;
1753                     if (/***********/ /***********/ !box[2][2] &&
1754                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1755                         /***********/  box[1][0]    /***********/)
1756                             d_terrain[j*d_width + i] = REPLACE;
1757                     if (/***********/  box[1][2] && /***********/
1758                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1759                         /***********/ /***********/ !box[2][0])
1760                             d_terrain[j*d_width + i] = REPLACE;
1761
1762                     if (!box[0][2] && !box[1][2] && /***********/
1763                         /***********/  box[1][1] &&  box[2][1] &&
1764                         /***********/ !box[1][0]    /***********/)
1765                             d_terrain[j*d_width + i] = REPLACE;
1766                     if (/***********/ !box[1][2] && !box[2][2] &&
1767                          box[0][1] &&  box[1][1] && /***********/
1768                         /***********/ !box[1][0]    /***********/)
1769                             d_terrain[j*d_width + i] = REPLACE;
1770                     if (!box[0][2] && /***********/ /***********/
1771                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1772                         /***********/  box[1][0]    /***********/)
1773                             d_terrain[j*d_width + i] = REPLACE;
1774                     if (/***********/  box[1][2] && /***********/
1775                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1776                         !box[0][0]    /***********/ /***********/)
1777                             d_terrain[j*d_width + i] = REPLACE;
1778
1779                     if (/***********/ !box[1][2] && /***********/
1780                         !box[0][1] &&  box[1][1] &&  box[2][1] &&
1781                         /***********/ !box[1][0]    /***********/)
1782                             d_terrain[j*d_width + i] = REPLACE;
1783                     if (/***********/ !box[1][2] && /***********/
1784                          box[0][1] &&  box[1][1] && !box[2][1] &&
1785                         /***********/ !box[1][0]    /***********/)
1786                             d_terrain[j*d_width + i] = REPLACE;
1787                     if (/***********/ !box[1][2] && /***********/
1788                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1789                         /***********/  box[1][0]    /***********/)
1790                             d_terrain[j*d_width + i] = REPLACE;
1791                     if (/***********/  box[1][2] && /***********/
1792                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1793                         /***********/ !box[1][0]    /***********/)
1794                             d_terrain[j*d_width + i] = REPLACE;
1795
1796                     if ( box[0][2] && !box[1][2] && /***********/
1797                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1798                         /***********/ !box[1][0]    /***********/)
1799                             d_terrain[j*d_width + i] = REPLACE;
1800                     if (/***********/ !box[1][2] &&  box[2][2] &&
1801                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1802                         /***********/ !box[1][0]    /***********/)
1803                             d_terrain[j*d_width + i] = REPLACE;
1804                     if (/***********/ !box[1][2] && /***********/
1805                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1806                          box[0][0] && !box[1][0]    /***********/)
1807                             d_terrain[j*d_width + i] = REPLACE;
1808                     if (/***********/ !box[1][2] && /***********/
1809                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1810                         /***********/ !box[1][0] &&  box[2][0])
1811                             d_terrain[j*d_width + i] = REPLACE;
1812
1813
1814                     if ( box[0][2] && !box[1][2] &&  box[2][2] &&
1815                          box[0][1] &&  box[1][1] &&  box[2][1] &&
1816                          box[0][0] && !box[1][0] &&  box[2][0])
1817                             d_terrain[j*d_width + i+(rand()%2?+1:-1)] = FIND_THIS;
1818                     if ( box[0][2] &&  box[1][2] &&  box[2][2] &&
1819                         !box[0][1] &&  box[1][1] && !box[2][1] &&
1820                          box[0][0] &&  box[1][0] &&  box[2][0])
1821                             d_terrain[(j+(rand()%2?+1:-1))*d_width + i] = FIND_THIS;
1822
1823                     if ( box[0][2] && !box[1][2] && !box[2][2] &&
1824                          box[0][1] &&  box[1][1] && !box[2][1] &&
1825                         !box[0][0] &&  box[1][0] &&  box[2][0])
1826                             d_terrain[j*d_width + i] = REPLACE;
1827                     if (!box[0][2] && !box[1][2] &&  box[2][2] &&
1828                         !box[0][1] &&  box[1][1] &&  box[2][1] &&
1829                          box[0][0] &&  box[1][0] && !box[2][0])
1830                             d_terrain[j*d_width + i] = REPLACE;
1831                     if ( box[0][2] &&  box[1][2] && !box[2][2] &&
1832                         !box[0][1] &&  box[1][1] &&  box[2][1] &&
1833                         !box[0][0] && !box[1][0] &&  box[2][0])
1834                             d_terrain[j*d_width + i] = REPLACE;
1835                     if (!box[0][2] &&  box[1][2] &&  box[2][2] &&
1836                          box[0][1] &&  box[1][1] && !box[2][1] &&
1837                          box[0][0] && !box[1][0] && !box[2][0])
1838                             d_terrain[j*d_width + i] = REPLACE;
1839                 }
1840             }
1841     }
1842 }
1843
1844 void MapGenerator::surroundMountains(int minx, int maxx, int miny, int maxy)
1845 {
1846   for(int j = miny; j < maxy; j++)
1847     for(int i = minx; i < maxx; i++)
1848       if(d_terrain[j*d_width + i] == Tile::MOUNTAIN)
1849         for(int J = -1; J <= +1; ++J)
1850           for(int I = -1; I <= +1; ++I)
1851             if((!(offmap(i+I,j+J))) &&
1852                (d_terrain[(j+J)*d_width + (i+I)] != Tile::MOUNTAIN))
1853               {
1854                 if(d_terrain[(j+J)*d_width + (i+I)] != Tile::WATER)
1855                   d_terrain[(j+J)*d_width + (i+I)] = Tile::HILLS;
1856                 else
1857                   // water has priority here, there was some work done to conenct bodies of water
1858                   // so don't break those connections.
1859                   d_terrain[(j  )*d_width + (i  )] = Tile::HILLS;
1860               }
1861 }