← Back to branch summary

~ubuntu-branches/ubuntu/saucy/lordsawar/saucy

« back to all changes in this revision

Viewing changes to src/MapGenerator.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Barry deFreese, Barry deFreese
  • Date: 2008-12-20 13:52:12 UTC
  • mfrom: (1.1.6 upstream) (5.1.2 squeeze)
  • Revision ID: james.westby@ubuntu.com-20081220135212-noeb2w3y98ebo7o9
Tags: 0.1.4-1
[ Barry deFreese ]
* New upstream release.
* Move 0.0.8-2.1 changelog entry to correct point in changelog.
* Make lordsawar-data suggest lordsawar.
* Update my e-mail address.
* Add build-depends on intltool, uuid-dev, and libboost-dev.
* Don't install locales since there are no translations currently.
* Add simple man page for new lordsawar-pbm binary.
* Drop gcc4.3 patches as they have been fixed upstream.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/MapGenerator.cpp
4
4
// Copyright (C) 2003 Michael Bartl
5
5
// Copyright (C) 2004, 2005 Andrea Paternesi
6
6
// Copyright (C) 2006, 2007, 2008 Ben Asselstine
 
7
// Copyright (C) 2008 Janek Kozicki
7
8
//
8
9
//  This program is free software; you can redistribute it and/or modify
9
10
//  it under the terms of the GNU General Public License as published by
23
24
#include <stdlib.h>
24
25
#include <iostream>
25
26
#include <math.h>  
26
 
#include <deque>
27
 
#include "vector.h"
 
27
#include <algorithm>
 
28
#include <set>
 
29
 
 
30
//#include <boost/foreach.hpp>
28
31
 
29
32
#include "MapGenerator.h"
30
33
#include "GameMap.h"
31
34
#include "stack.h"
32
35
#include "path.h"
33
36
#include "File.h"
34
 
#include "defs.h"
35
37
#include "citylist.h"
36
38
#include "roadlist.h"
37
39
#include "portlist.h"
 
40
#include "ruinlist.h"
 
41
#include "templelist.h"
 
42
#include "bridgelist.h"
38
43
#include "armysetlist.h"
39
44
#include "army.h"
 
45
#include "vector.h"
40
46
 
41
 
//#define debug(x) {std::cerr<<__FILE__<<": "<<__LINE__<<": "<<x<<std::endl<<std::flush;}
42
 
#define debug(x)
 
47
#define debug(x) {std::cerr<<__FILE__<<": "<<__LINE__<<": "<<x<<std::endl<<std::flush;}
 
48
//#define debug(x)
43
49
#define offmap(bx,by) (by<0)||(by>=d_height)||(bx<0)||(bx>=d_width)
44
50
 
45
51
using namespace std;
137
143
 *   = nothing
138
144
 * c = part of city/castle
139
145
 * See the TileMapTypes enum at the beginning of the class definition.
 
146
 *
 
147
 * See printMap() which is used for debugging maps.
140
148
 */
141
149
void MapGenerator::makeMap(int width, int height, bool roads)
142
150
{
150
158
        for (int j = 0; j < width; j++)
151
159
            d_building[i*width + j] = Maptile::NONE;
152
160
 
153
 
    cout <<_("Making random map") <<endl;
 
161
    debug("Making random map:");
154
162
   
155
163
    // create the terrain
156
 
    cout <<_("Flatening Plains  ... 10%") <<endl;
 
164
    debug("flatening plains");
157
165
    progress.emit(.090, _("flattening plains..."));
158
166
    makePlains();
159
 
    cout <<_("Raining Water     ... 30%") <<endl;
 
167
    debug("raining water");
160
168
    progress.emit(.180, _("raining water..."));
161
169
    makeTerrain(Tile::WATER, d_pwater, true);  
162
170
    makeStreamer(Tile::WATER, d_pwater/3, 3);
163
 
    cout <<_("Raising Hills     ... 20%") <<endl;
 
171
    rescueLoneTiles(Tile::WATER,Tile::GRASS,true);
 
172
    makeRivers();
 
173
    verifyIslands();
 
174
    debug("raising hills");
164
175
    progress.emit(.270, _("raising hills..."));
165
176
    makeTerrain(Tile::HILLS, d_phills, false);
166
 
    cout <<_("Raising Mountains ... 30%") <<endl;
 
177
    debug("raising mountains");
167
178
    progress.emit(.360, _("raising mountains..."));
168
179
    makeTerrain(Tile::MOUNTAIN, d_pmountains, false);
169
180
    makeStreamer(Tile::MOUNTAIN, d_pmountains/3, 3);
170
 
    cout <<_("Planting Forest   ... 40%") <<endl;
 
181
    rescueLoneTiles(Tile::MOUNTAIN,Tile::GRASS,false);
 
182
    surroundMountains(0, d_width, 0, d_height);
 
183
    debug("planting forest");
171
184
    progress.emit(.450, _("planting forests..."));
172
185
    makeTerrain(Tile::FOREST, d_pforest, false);
173
 
    cout <<_("Watering Swamps   ... 50%") <<endl;
 
186
    debug("watering swamps");
174
187
    progress.emit(.540, _("watering swamps..."));
175
188
    makeTerrain(Tile::SWAMP, d_pswamp, false);
176
 
    cout <<_("Normalizing       ... 60%") <<endl;
 
189
    debug("normalizing terrain");
177
190
    progress.emit(.630, _("normalizing terrain..."));
178
191
    normalize();
179
 
           
 
192
 
180
193
    // place buildings
181
 
    cout <<_("Building Cities   ... 70%") <<endl;
 
194
    debug("building cities");
182
195
    progress.emit(.720, _("building cities..."));
183
196
    makeCities(d_nocities);
184
197
 
185
198
    if (roads)
186
199
      {
187
 
        cout <<_("Paving Roads      ... 75%") <<endl;
 
200
        debug("paving roads");
188
201
        progress.emit(.810, _("paving roads..."));
189
202
        makeRoads();
190
203
      }
 
204
    rescueLoneTiles(Tile::MOUNTAIN,Tile::HILLS,false);
191
205
 
192
 
    cout <<_("Ruining Ruins     ... 80%") <<endl;
 
206
    debug("ruining ruins");
193
207
    progress.emit(.810, _("ruining ruins..."));
194
208
    makeBuildings(Maptile::RUIN,d_noruins);
195
 
    cout <<_("Raising Signs     ... 88%") <<endl;
196
 
    progress.emit(.900, _("raising signs..."));
 
209
    debug("spawning temples");
 
210
    progress.emit(.900, _("spawning temples..."));
 
211
    makeBuildings(Maptile::TEMPLE,d_notemples);
 
212
    debug("building bridges");
 
213
    progress.emit(.950, _("building bridges..."));
 
214
    makeBridges();
 
215
    debug("raising signs");
 
216
    progress.emit(.990, _("raising signs..."));
197
217
    makeBuildings(Maptile::SIGNPOST,d_nosignposts);
198
 
    cout <<_("Spawning temples  ... 90%") <<endl;
199
 
    progress.emit(.990, _("spawning temples..."));
200
 
    makeBuildings(Maptile::TEMPLE,d_notemples);
201
 
    cout <<_("Done making map   ... 100%") <<endl;
 
218
 
 
219
    debug("Done making map.");
 
220
 
 
221
//    printMap();
 
222
}
 
223
        
 
224
#define  NORTH_SOUTH_BRIDGE 1
 
225
#define  EAST_WEST_BRIDGE 2
 
226
 
 
227
void MapGenerator::placeBridge(Vector<int> pos, int type)
 
228
{
 
229
  Bridgelist *bl = Bridgelist::getInstance();
 
230
  if (type == NORTH_SOUTH_BRIDGE)
 
231
    {
 
232
      d_building[pos.y*d_width + pos.x] = Maptile::BRIDGE;
 
233
      d_building[(pos.y + 1)*d_width + pos.x] = Maptile::BRIDGE;
 
234
      bl->push_back(new Bridge(Vector<int>(pos.x, pos.y)));
 
235
      bl->push_back(new Bridge(Vector<int>(pos.x+1, pos.y)));
 
236
    }
 
237
  else if (type == EAST_WEST_BRIDGE)
 
238
    {
 
239
      d_building[pos.y*d_width + pos.x] = Maptile::BRIDGE;
 
240
      d_building[pos.y*d_width + pos.x + 1] = Maptile::BRIDGE;
 
241
      bl->push_back(new Bridge(Vector<int>(pos.x, pos.y)));
 
242
      bl->push_back(new Bridge(Vector<int>(pos.x, pos.y+1)));
 
243
    }
 
244
  GameMap::getInstance()->calculateBlockedAvenues();
 
245
}
 
246
 
 
247
bool MapGenerator::findBridgePurpose(Vector<int> pos, int type, 
 
248
                                     Vector<int> &src, Vector<int> &dest)
 
249
{
 
250
  if (type == EAST_WEST_BRIDGE)
 
251
    {
 
252
      src = GameMap::getInstance()->findNearestObjectToTheWest(pos);
 
253
      dest = GameMap::getInstance()->findNearestObjectToTheEast(pos);
 
254
    }
 
255
  else if (type == NORTH_SOUTH_BRIDGE)
 
256
    {
 
257
      src = GameMap::getInstance()->findNearestObjectToTheNorth(pos);
 
258
      dest = GameMap::getInstance()->findNearestObjectToTheSouth(pos);
 
259
    }
 
260
  if (src == Vector<int>(-1,-1) || dest == Vector<int>(-1,-1))
 
261
    return false;
 
262
  return true;
 
263
}
 
264
 
 
265
bool MapGenerator::canPlaceBridge(Vector<int> pos, int type, Vector<int> &src, Vector<int> &dest)
 
266
{
 
267
  if (d_building[pos.y*d_width + pos.x] == Maptile::NONE &&
 
268
      findBridgePurpose(pos, type, src, dest) == true)
 
269
    return true;
 
270
  return false;
 
271
}
 
272
 
 
273
void MapGenerator::makeBridges()
 
274
{
 
275
  GameMap::deleteInstance();
 
276
  Citylist::deleteInstance();
 
277
  Roadlist::deleteInstance();
 
278
  Ruinlist::deleteInstance();
 
279
  Templelist::deleteInstance();
 
280
  Portlist::deleteInstance();
 
281
  Bridgelist::deleteInstance();
 
282
 
 
283
  GameMap::setWidth(d_width);
 
284
  GameMap::setHeight(d_height);
 
285
  GameMap::getInstance("default", "default", "default")->fill(this);
 
286
 
 
287
  //the game map class smooths the map, so let's take what it smoothed.
 
288
  for (int y = 0; y < d_height; y++)
 
289
    for (int x = 0; x < d_width; x++)
 
290
      d_terrain[y*d_width + x] = 
 
291
        GameMap::getInstance()->getTile(x, y)->getMaptileType();
 
292
 
 
293
  //load up the roadlist, and stuff.
 
294
 
 
295
  for (int y = 0; y < d_height; y++)
 
296
    for (int x = 0; x < d_width; x++)
 
297
      {
 
298
        if (d_building[y*d_width + x] == Maptile::CITY)
 
299
          Citylist::getInstance()->push_back(new City(Vector<int>(x,y)));
 
300
        else if (d_building[y*d_width + x] == Maptile::ROAD)
 
301
          Roadlist::getInstance()->push_back(new Road(Vector<int>(x,y)));
 
302
        else if (d_building[y*d_width + x] == Maptile::RUIN)
 
303
          Ruinlist::getInstance()->push_back(new Ruin(Vector<int>(x,y)));
 
304
        else if (d_building[y*d_width + x] == Maptile::TEMPLE)
 
305
          Templelist::getInstance()->push_back(new Temple(Vector<int>(x,y)));
 
306
        else if (d_building[y*d_width + x] == Maptile::PORT)
 
307
          Portlist::getInstance()->push_back(new Port(Vector<int>(x,y)));
 
308
      }
 
309
  GameMap::getInstance()->calculateBlockedAvenues();
 
310
 
 
311
  Vector<int> src, dest;
 
312
  std::vector<pair<int , Vector<int> > >  bridges;
 
313
  bridges = findBridgePlaces();
 
314
  for (std::vector<pair<int, Vector<int> > >::iterator it = bridges.begin();
 
315
       it != bridges.end(); it++)
 
316
    {
 
317
      Vector<int> pos = (*it).second + Vector<int>(1,1);
 
318
      Vector<int> edge1; 
 
319
      Vector<int> edge2; 
 
320
      if ((*it).first == NORTH_SOUTH_BRIDGE)
 
321
        {
 
322
          edge1 = pos - Vector<int>(0, 1);
 
323
          edge2 = pos + Vector<int>(0, 2);
 
324
        }
 
325
      else if ((*it).first == EAST_WEST_BRIDGE)
 
326
        {
 
327
          edge1 = pos - Vector<int>(1, 0);
 
328
          edge2 = pos + Vector<int>(2, 0);
 
329
        }
 
330
      if (offmap(edge1.x, edge1.y) || offmap(edge2.x, edge2.y))
 
331
        continue;
 
332
      if (canPlaceBridge((*it).second + Vector<int>(1,1), (*it).first, src, 
 
333
                         dest) == true)
 
334
        {
 
335
          int leg1 = tryRoad (src, edge1);
 
336
          int leg2 = tryRoad (dest, edge2);
 
337
          int shortcut = tryRoad (src, dest);
 
338
          bool construct_bridge_and_roads = true;
 
339
          if (leg1 <= 0 || leg2 <= 0)
 
340
            construct_bridge_and_roads = false;
 
341
          if (shortcut > 0 && (leg1 + leg2 + 2) > shortcut)
 
342
            construct_bridge_and_roads = false;
 
343
 
 
344
          if (construct_bridge_and_roads)
 
345
            {
 
346
              makeRoad(src, edge1);
 
347
              makeRoad(dest, edge2);
 
348
              placeBridge(pos, (*it).first);
 
349
            }
 
350
        }
 
351
        progress.emit(.950, _("paving bridges..."));
 
352
    }
 
353
 
 
354
  Roadlist::deleteInstance();
 
355
  Ruinlist::deleteInstance();
 
356
  Templelist::deleteInstance();
 
357
  GameMap::deleteInstance();
 
358
  Citylist::deleteInstance();
 
359
  Portlist::deleteInstance();
 
360
  Bridgelist::deleteInstance();
 
361
}
 
362
 
 
363
void MapGenerator::printMap(int j, int i)
 
364
{
 
365
    char ch='?';
 
366
    bool adom_convention=true; // well, except mountains
 
367
    switch(d_terrain[j*d_width + i])
 
368
    {
 
369
        case Tile::MOUNTAIN:  ch=adom_convention ? 'M' : 'M';break; // mountains
 
370
        case Tile::HILLS   :  ch=adom_convention ? '~' : 'h';break; // hills
 
371
        case Tile::WATER   :  ch=adom_convention ? '=' : '~';break; // water
 
372
        case Tile::FOREST  :  ch=adom_convention ? '&' : '$';break; // forest
 
373
        case Tile::GRASS   :  ch=adom_convention ? '.' : '.';break; // plains
 
374
        case Tile::SWAMP   :  ch=adom_convention ? '"' : '_';break; // swamps
 
375
        case Tile::VOID    :  ch=adom_convention ? '?' : '?';break;
 
376
 
 
377
            // cannot print those, actually because they don't exist in Tile::Type
 
378
            //     ch='C';break; // city/castle
 
379
            //     ch='r';break; // ruins
 
380
            //     ch='T';break; // temple
 
381
            //     ch=' ';break; // nothing
 
382
            //     ch='c';break; // part of city/castle
 
383
    }
 
384
    std::cout << ch;
 
385
}
 
386
 
 
387
void MapGenerator::printMap()
 
388
{
 
389
    for(int j = 0; j < d_height; j++)
 
390
    {
 
391
        for(int i = 0; i < d_width; i++)
 
392
            printMap(j,i);
 
393
        std::cout << "\n";
 
394
    }
 
395
    std::cout << "\n";
202
396
}
203
397
 
204
398
const Tile::Type* MapGenerator::getMap(int& width, int& height) const
222
416
            d_terrain[j*d_width + i] = Tile::GRASS;
223
417
}
224
418
 
 
419
void MapGenerator::connectWithWater(Vector<int> from, Vector<int> to)
 
420
{
 
421
    Vector<float> delta = from - to;
 
422
    if (dist<float>(from,to) > (float)(d_width*0.4))
 
423
        // we don't want to mess up whole map with straight lines
 
424
        return;
 
425
 
 
426
    int kind(rand()%4);
 
427
    delta /= length(delta)*2;
 
428
    for(Vector<float>path = Vector<float>(from)+delta*4 ; dist<float>(path,Vector<float>(to)-delta*4) > 0.5 ; path -= delta)
 
429
    {
 
430
        int j = (int)(path.x);
 
431
        int i = (int)(path.y);
 
432
 
 
433
        if(rand()%3 == 0) 
 
434
            kind = rand()%4;
 
435
        switch(kind)
 
436
        {
 
437
            case 0:
 
438
                if((!(offmap(i,j))) && (!(offmap(i-1,j-1))))
 
439
                {
 
440
                    d_terrain[(j  )*d_width + i  ] = Tile::WATER;
 
441
                    d_terrain[(j-1)*d_width + i-1] = Tile::WATER;
 
442
                    d_terrain[(j  )*d_width + i-1] = Tile::WATER;
 
443
                    d_terrain[(j-1)*d_width + i  ] = Tile::WATER;
 
444
                }; break;
 
445
 
 
446
            case 1:
 
447
                if((!(offmap(i,j))) && (!(offmap(i+1,j+1))))
 
448
                {
 
449
                    d_terrain[(j  )*d_width + i  ] = Tile::WATER;
 
450
                    d_terrain[(j+1)*d_width + i+1] = Tile::WATER;
 
451
                    d_terrain[(j  )*d_width + i+1] = Tile::WATER;
 
452
                    d_terrain[(j+1)*d_width + i  ] = Tile::WATER;
 
453
                }; break;
 
454
 
 
455
            case 2:
 
456
                if((!(offmap(i,j))) && (!(offmap(i-1,j+1))))
 
457
                {
 
458
                    d_terrain[(j  )*d_width + i  ] = Tile::WATER;
 
459
                    d_terrain[(j+1)*d_width + i-1] = Tile::WATER;
 
460
                    d_terrain[(j  )*d_width + i-1] = Tile::WATER;
 
461
                    d_terrain[(j+1)*d_width + i  ] = Tile::WATER;
 
462
                }; break;
 
463
 
 
464
            case 3:
 
465
                if((!(offmap(i,j))) && (!(offmap(i+1,j-1))))
 
466
                {
 
467
                    d_terrain[(j  )*d_width + i  ] = Tile::WATER;
 
468
                    d_terrain[(j-1)*d_width + i+1] = Tile::WATER;
 
469
                    d_terrain[(j  )*d_width + i+1] = Tile::WATER;
 
470
                    d_terrain[(j-1)*d_width + i  ] = Tile::WATER;
 
471
                }; break;
 
472
        }
 
473
    }
 
474
}
 
475
 
 
476
void MapGenerator::findAreasOf(Tile::Type THIS_TILE,std::vector<std::vector<int> >& box,int& how_many)
 
477
{
 
478
    box.resize(d_height);
 
479
    for(int j = 0; j < d_height; j++)
 
480
        box[j].resize(d_width,0);
 
481
 
 
482
    // find all enclosed areas by scanning the map
 
483
    // distinct areas have different numbers in box
 
484
    for(int j = 1; j < d_height-1; j++)
 
485
        for(int i = 1; i < d_width-1; i++)
 
486
            if (box[j][i]==0 &&
 
487
                    d_terrain[j*d_width + i] == THIS_TILE &&
 
488
                    (
 
489
                     (d_terrain[(j-1)*d_width + i-1] == THIS_TILE &&
 
490
                      d_terrain[(j  )*d_width + i-1] == THIS_TILE &&
 
491
                      d_terrain[(j-1)*d_width + i  ] == THIS_TILE)  ||
 
492
 
 
493
                     (d_terrain[(j-1)*d_width + i  ] == THIS_TILE &&
 
494
                      d_terrain[(j-1)*d_width + i+1] == THIS_TILE &&
 
495
                      d_terrain[(j  )*d_width + i+1] == THIS_TILE) ||
 
496
 
 
497
                     (d_terrain[(j  )*d_width + i+1] == THIS_TILE &&
 
498
                      d_terrain[(j+1)*d_width + i+1] == THIS_TILE &&
 
499
                      d_terrain[(j+1)*d_width + i  ] == THIS_TILE) ||
 
500
 
 
501
                     (d_terrain[(j+1)*d_width + i  ] == THIS_TILE &&
 
502
                      d_terrain[(j+1)*d_width + i-1] == THIS_TILE &&
 
503
                      d_terrain[(j  )*d_width + i-1] == THIS_TILE))
 
504
               )
 
505
            {
 
506
                box[j][i]=++how_many+3000;
 
507
                int counter=1;
 
508
                while(counter != 0)
 
509
                {
 
510
                    counter=0;
 
511
                    for(int J = 1; J < d_height-1; J++)
 
512
                        for(int I = 1; I < d_width-1; I++)
 
513
                        {
 
514
                            if(d_terrain[J*d_width + I] == THIS_TILE &&
 
515
                                    box[J][I]    ==0 &&
 
516
                                    (box[J-1][I  ]==how_many+3000 ||
 
517
                                     box[J  ][I-1]==how_many+3000 ||
 
518
                                     box[J  ][I+1]==how_many+3000 ||
 
519
                                     box[J+1][I  ]==how_many+3000))
 
520
                            {
 
521
                                ++counter;
 
522
                                box[J][I]=how_many+2000;
 
523
                            }
 
524
                        }
 
525
                    for(int J = 0; J < d_height; J++)
 
526
                        for(int I = 0; I < d_width; I++)
 
527
                        {
 
528
                            if (box[J][I]==how_many+3000)
 
529
                                box[J][I]=how_many;
 
530
                            if (box[J][I]==how_many+2000)
 
531
                                box[J][I]=how_many+3000;
 
532
                        }
 
533
                }
 
534
            }
 
535
}
 
536
 
 
537
void MapGenerator::verifyIslands()
 
538
{
 
539
    int how_many=0;
 
540
    std::vector<std::vector<int> > box;
 
541
    findAreasOf(Tile::GRASS,box,how_many);
 
542
 
 
543
    // count the size of each area
 
544
    std::vector<float> counts;
 
545
    counts.resize(how_many+2,0);
 
546
    for(int j = 0; j < d_height; j++)
 
547
        for(int i = 0; i < d_width; i++)
 
548
            if(box[j][i] != 0)
 
549
                counts[box[j][i]] += 1;
 
550
 
 
551
    // find four largest land areas
 
552
    std::set<int> largest;largest.clear();
 
553
    int max;
 
554
    for(int z=0 ; z<4 ; ++z)
 
555
    {
 
556
        max = -1;
 
557
        for(size_t i=0 ; i<counts.size() ; ++i)
 
558
        {
 
559
            if(counts[i] > max && largest.find(counts[i]) == largest.end())
 
560
                max = counts[i];
 
561
        }
 
562
        largest.insert(max);
 
563
    }
 
564
 
 
565
    // largest are good. Also one/third of all others is good:
 
566
    std::set<int> good(largest);
 
567
    for(size_t i=0 ; i<counts.size() ; ++i)
 
568
        if(rand()%3 == 0) // that's one/third here
 
569
            good.insert(counts[i]);
 
570
 
 
571
    // now, eliminate all land that is not good
 
572
    for(int I=0 ; I<(int)(counts.size()) ; ++I)
 
573
        if(good.find(counts[I]) == good.end())
 
574
            for(int j = 1; j < d_height-1; j++)
 
575
                for(int i = 1; i < d_width-1; i++)
 
576
                    if(box[j][i] == I)
 
577
                        d_terrain[j*d_width + i] = Tile::WATER;
 
578
}
 
579
 
 
580
void MapGenerator::makeRivers()
 
581
{
 
582
    // river style:
 
583
    //  1 - plenty of short rivers and islands
 
584
    //  2 - longer rivers, less islands
 
585
    //  3 - even longer rivers, even less islands
 
586
    int river_style=rand()%3+1;
 
587
 
 
588
    // count how many separate bodies of water were found
 
589
    int how_many;
 
590
 
 
591
    int iter=0; // avoid deadlocks
 
592
    while(++iter < 20)
 
593
    {
 
594
        how_many=0;
 
595
 
 
596
        std::vector<std::vector<int> > box;
 
597
        
 
598
        findAreasOf(Tile::WATER,box,how_many);
 
599
 
 
600
        // this loop allows maximum 3 distinctly separated bodies of water
 
601
        // so no need to continue the algorithm
 
602
        if(how_many<4)
 
603
            break;
 
604
 
 
605
        // find two biggest bodies of water, and calculate centers for all of them
 
606
        std::vector< Vector<float> > centers;
 
607
        centers.resize(how_many+2,Vector<float>(0,0));
 
608
        std::vector<float> counts;
 
609
        counts.resize(how_many+2,0);
 
610
        for(int j = 0; j < d_height; j++)
 
611
            for(int i = 0; i < d_width; i++)
 
612
                if(box[j][i] != 0)
 
613
                {
 
614
                    counts[box[j][i]] += 1;
 
615
                    centers[box[j][i]] += Vector<float>(j,i);
 
616
                }
 
617
        // divide sum by counts to get a center
 
618
        int max_count=0,max_count_2=0;
 
619
        for(int h = 0; h < how_many+2; ++h)
 
620
        {
 
621
            if(counts[h]>0)
 
622
            {
 
623
                centers[h] /= counts[h];
 
624
                if(max_count < (int)(counts[h]))
 
625
                    max_count = (int)(counts[h]);
 
626
                if(max_count_2 < (int)(counts[h]) && (int)(counts[h]) != max_count)
 
627
                    max_count_2 = (int)(counts[h]);
 
628
                int J=(int)(centers[h].x), I=(int)(centers[h].y);
 
629
                if(box[J][I] != h)
 
630
                // center doesn't necessarily fall on water tile, so fix this.
 
631
                {
 
632
                    //      // for debugging...
 
633
                    //      box[J][I]+=5000;
 
634
                    int i_up=0,i_dn=0,j_up=0,j_dn=0;
 
635
                    while((I+i_up <  d_width-1 ) && (box[J     ][I+i_up] != h)) ++i_up;
 
636
                    while((I-i_dn >  0         ) && (box[J     ][I-i_dn] != h)) ++i_dn;
 
637
                    while((J+j_up <  d_height-1) && (box[J+j_up][I     ] != h)) ++j_up;
 
638
                    while((J-j_dn >  0         ) && (box[J-j_dn][I     ] != h)) ++j_dn;
 
639
 
 
640
                    int shortest = std::min( std::min(i_up,i_dn) , std::min(j_up,j_dn));
 
641
 
 
642
                    if(shortest == i_up && I+i_up <  d_width)
 
643
                        centers[h] = Vector<float>( J      , I+i_up );
 
644
                    else
 
645
                        if(shortest == i_dn && I-i_dn >= 0      )
 
646
                            centers[h] = Vector<float>( J      , I-i_dn );
 
647
                        else
 
648
                            if(shortest == j_up && J+j_up <  d_height)
 
649
                                centers[h] = Vector<float>( J+j_up , I      );
 
650
                            else
 
651
                                if(shortest == j_dn && J-j_dn >= 0       )
 
652
                                    centers[h] = Vector<float>( J+j_dn , I      );
 
653
                                else
 
654
                                {
 
655
                                    std::cout << "Sages are wondering about unforeseen mysteries behind the edge of the world.\n";
 
656
                                    counts[h] = -1; // that's ok, but an interesting case. I'd like to see a map with such water :)
 
657
                                    // FIXME - can you make a message box here?
 
658
                                    //MessageBox("Message from author: this is algorithmically a very interesting map, please make screenshot and send to cosurgi@gmail.com");
 
659
                                }
 
660
                }
 
661
                //      // for debugging...
 
662
                //      box[(int)(centers[h].x)][(int)(centers[h].y)]+=4000;
 
663
            }
 
664
        }
 
665
 
 
666
        // determine what are the biggest bodies of water here
 
667
        int the_biggest_area=0,second_biggest_area=0;
 
668
        for(int h = 0; h < how_many+2; ++h)
 
669
        {
 
670
            if(counts[h]==max_count   && max_count   != 0)
 
671
                the_biggest_area = h;
 
672
            if(counts[h]==max_count_2 && max_count_2 != 0)
 
673
                second_biggest_area = h;
 
674
        }
 
675
 
 
676
        // find shortest distances between areas
 
677
        std::vector<std::vector<std::pair<float, std::pair<Vector<int>, Vector<int> > > > > distances; // I would prefer boost::tuple, but oh well...
 
678
        distances.resize(how_many+2);
 
679
        for(int h = 0; h < how_many+2; ++h)
 
680
        {
 
681
            distances[h].resize(how_many+3,std::make_pair(0,std::make_pair(Vector<int>(0,0),Vector<int>(0,0))));
 
682
            for(int k = h+1; k < how_many+2; ++k)
 
683
            {
 
684
                if(counts[h] > 0 && counts[k] > 0) // h and k are two different areas
 
685
                {
 
686
                    // find tile from area h closest to the center of k 
 
687
                    float min_dist = d_height*d_height;
 
688
                    float min_h_j=0,min_h_i=0;
 
689
                    for(int j = 1; j < d_height-1; j++)
 
690
                        for(int i = 1; i < d_width-1; i++)
 
691
                            if(box[j][i] == h)
 
692
                            {
 
693
                                float dj = j - centers[k].x;
 
694
                                float di = i - centers[k].y;
 
695
                                float dist = dj*dj + di*di;
 
696
                                if(dist < min_dist)
 
697
                                {
 
698
                                    min_dist = dist;
 
699
                                    min_h_j = j;
 
700
                                    min_h_i = i;
 
701
                                }
 
702
                            }
 
703
 
 
704
                    // then find tile from area k closest to that tile from h
 
705
                    min_dist = d_height * d_height;
 
706
                    float min_k_j=0,min_k_i=0;
 
707
                    for(int j = 1; j < d_height-1; j++)
 
708
                        for(int i = 1; i < d_width-1; i++)
 
709
                            if(box[j][i] == k)
 
710
                            {
 
711
                                float dj = j - min_h_j;
 
712
                                float di = i - min_h_i;
 
713
                                float dist = dj*dj + di*di;
 
714
                                if(dist < min_dist)
 
715
                                {
 
716
                                    min_dist = dist;
 
717
                                    min_k_j = j;
 
718
                                    min_k_i = i;
 
719
                                }
 
720
                            }
 
721
 
 
722
                    if (min_k_j != 0 && 
 
723
                            min_h_j != 0 && 
 
724
                            min_k_i != 0 && 
 
725
                            min_h_i != 0)
 
726
                    {
 
727
                        float dj = min_k_j - min_h_j;
 
728
                        float di = min_k_i - min_h_i;
 
729
                        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)) );
 
730
                    }
 
731
                }
 
732
            }
 
733
        }
 
734
 
 
735
        for(int connect_some_closest=0; connect_some_closest<14; connect_some_closest+=river_style)
 
736
        {
 
737
            // if river_style is 1 then
 
738
            //   connect 10 closest to each other, and 4 closest to two biggest bodies of water
 
739
            // otherwise skip some - connect fewer of them.
 
740
            int closest_h=-1,closest_k=-1,min=d_height*d_height;
 
741
            int start_h=0;
 
742
            if(connect_some_closest < 2 ) start_h=the_biggest_area;
 
743
            else
 
744
                if(connect_some_closest < 4) start_h=second_biggest_area;
 
745
            for(int h = start_h; h < ((connect_some_closest >= 4) ? (how_many+2) : start_h+1); ++h)
 
746
                for(int k = h+1; k < how_many+2; ++k)
 
747
                    if(counts[h] > 0 && counts[k] > 0)
 
748
                        if(distances[h][k].first > 0 && min > distances[h][k].first)
 
749
                        {
 
750
                            min = distances[h][k].first;
 
751
                            closest_h = h;
 
752
                            closest_k = k;
 
753
                        }
 
754
            if (closest_h != -1 &&
 
755
                closest_k != -1)
 
756
            {
 
757
                connectWithWater(distances[closest_h][closest_k].second.first , distances[closest_h][closest_k].second.second);
 
758
                // mark as done:
 
759
                distances[closest_h][closest_k].first = d_height*d_height;
 
760
            }
 
761
        }
 
762
        //          // for debugging...   print whole box
 
763
        //          std::cerr << how_many << " separate bodies of water found.\n";
 
764
        //          std::cerr << the_biggest_area << " is the biggest\n";
 
765
        //          std::cerr << second_biggest_area << " is second in size\n";
 
766
        //          std::vector<int> a;
 
767
        //          BOOST_FOREACH(a,box)
 
768
        //          {
 
769
        //              BOOST_FOREACH(int i,a)
 
770
        //              {
 
771
        //                  if(i<4000)
 
772
        //                      std::cout << i << " ";
 
773
        //                  else
 
774
        //                      if(i<5000)
 
775
        //                      std::cout << "X" << " ";
 
776
        //                      else
 
777
        //                      if(i<7000)
 
778
        //                      std::cout << "%" << " ";
 
779
        //                      else
 
780
        //                      if(i<14000)
 
781
        //                      std::cout << "!" << " ";
 
782
        //                      else
 
783
        //                      std::cout << "|" << " ";
 
784
        //              }
 
785
        //              std::cout << "\n";
 
786
        //          }
 
787
        //          std::cout << "\n";
 
788
 
 
789
    };
 
790
    //if(how_many>1)
 
791
        //std::cout << "There are " << how_many << (how_many<4?(std::string(" seas")):(std::string(" lakes"))) << " on this map.\n";
 
792
    //else
 
793
        //std::cout << "There is 1 sea on this map.\n";
 
794
    //std::cout << "River style was: " << river_style << "\n";
 
795
}
 
796
 
 
797
 
225
798
/**
226
799
 * Makes Terrains.
227
800
 * The algorithm is as follows :
500
1073
    return false;
501
1074
}
502
1075
 
 
1076
bool MapGenerator::inhospitableTerrain(int x, int y, unsigned int width)
 
1077
{
 
1078
  for (unsigned int i = 0; i < width; i++)
 
1079
    for (unsigned int j = 0; j < width; j++)
 
1080
      if (d_terrain[(y+i)*d_width +(x+j)] == Tile::WATER ||
 
1081
          d_terrain[(y+i)*d_width +(x+j)] == Tile::MOUNTAIN)
 
1082
        return true;
 
1083
  return false;
 
1084
}
 
1085
 
503
1086
void MapGenerator::makeCities(int cities)
504
1087
{
505
1088
 
511
1094
    {
512
1095
        int x = rand()%(d_width-2);
513
1096
        int y = rand()%(d_height-2);
514
 
        if((d_terrain[y*d_width +x] == Tile::WATER
515
 
            || d_terrain[y*d_width + x+1] == Tile::WATER 
516
 
            || d_terrain[(y+1)*d_width + x] == Tile::WATER
517
 
            || d_terrain[(y+1)*d_width + x+1] == Tile::WATER
518
 
            || d_terrain[y*d_width +x] == Tile::MOUNTAIN
519
 
            || d_terrain[y*d_width + x+1] == Tile::MOUNTAIN
520
 
            || d_terrain[(y+1)*d_width + x] == Tile::MOUNTAIN
521
 
            || d_terrain[(y+1)*d_width + x+1] == Tile::MOUNTAIN)
522
 
            && (iterations < 1000))
 
1097
        if (inhospitableTerrain(x, y, CITY_TILE_WIDTH) && (iterations < 1000))
523
1098
        {
524
1099
            iterations++;
525
1100
            continue;
526
1101
        }
527
1102
        
528
1103
        // check if we can put the building
529
 
        if ((!canPutBuilding(x, y) || !canPutBuilding(x + 1, y) ||
530
 
            !canPutBuilding(x, y + 1) || !canPutBuilding(x + 1,y + 1)) &&
531
 
            ((iterations < 1000)))
 
1104
        if (!canPutCity(x, y) && iterations < 1000)
532
1105
        {
533
1106
            iterations++;
534
1107
            continue;
542
1115
 
543
1116
bool MapGenerator::canPutCity(int x,int y)
544
1117
{
545
 
    if ((canPutBuilding(x,y))&&(canPutBuilding(x+1,y))&&(canPutBuilding(x,y+1))&&(canPutBuilding(x+1,y+1)))
546
 
        return true;
547
 
    else
 
1118
  for (unsigned int i = 0; i < CITY_TILE_WIDTH; i++)
 
1119
    for (unsigned int j = 0; j < CITY_TILE_WIDTH; j++)
 
1120
      if (canPutBuilding(x+i,y+j) == false)
548
1121
        return false;
 
1122
        
 
1123
  return true;
549
1124
}
550
1125
 
551
1126
void MapGenerator::putCity(int x, int y, int& city_count)
553
1128
        d_building[y*d_width + x] = Maptile::CITY;
554
1129
 
555
1130
        //cities shall only sit on grass tiles
556
 
        d_terrain[y*d_width + x] = Tile::GRASS;
557
 
        d_terrain[y*d_width + x+1]     = Tile::GRASS;
558
 
        d_terrain[(y+1)*d_width + x]   = Tile::GRASS;
559
 
        d_terrain[(y+1)*d_width + x+1] = Tile::GRASS;
 
1131
        for (unsigned int i = 0; i < CITY_TILE_WIDTH; i++)
 
1132
          for (unsigned int j = 0; j < CITY_TILE_WIDTH; j++)
 
1133
            d_terrain[(y+i)*d_width + (x+j)] = Tile::GRASS;
 
1134
        //cities cannot neighbor with mountain tiles
 
1135
        for (int Y = -1; Y <= (int)CITY_TILE_WIDTH; ++Y )
 
1136
            for (int X = -1; X <= (int)CITY_TILE_WIDTH; ++X)
 
1137
                if (d_terrain[(y+Y)*d_width + x+X] == Tile::MOUNTAIN)
 
1138
                    d_terrain[(y+Y)*d_width + x+X] = Tile::HILLS;
560
1139
 
561
1140
        city_count++;
562
1141
}
567
1146
    int iterations = 10;
568
1147
    bool found_place = false;
569
1148
 
 
1149
    unsigned int width = 1;
 
1150
 
 
1151
    switch (b)
 
1152
      {
 
1153
      case Maptile::CITY:
 
1154
        width = CITY_TILE_WIDTH; break;
 
1155
      case Maptile::RUIN:
 
1156
        width = RUIN_TILE_WIDTH; break;
 
1157
      case Maptile::TEMPLE:
 
1158
        width = TEMPLE_TILE_WIDTH; break;
 
1159
      case Maptile::NONE:
 
1160
      case Maptile::SIGNPOST:
 
1161
      case Maptile::ROAD:
 
1162
      case Maptile::PORT:
 
1163
      case Maptile::BRIDGE:
 
1164
        width = 1;
 
1165
        break;
 
1166
      }
 
1167
 
570
1168
   //If number of iterations is smaller 10, look for a suitable
571
1169
   //place. If this number is exceeded, place the temple on an
572
1170
   //island if neccessary.
577
1175
             x = rand()%d_width;
578
1176
             y = rand()%d_height;
579
1177
        
580
 
             if (canPutBuilding(x, y) == true)
581
 
             {
582
 
                 found_place = true;
583
 
                 break;
584
 
             }
 
1178
             found_place = true;
 
1179
             for (unsigned int k = 0; k < width; k++)
 
1180
               for (unsigned int l = 0; l < width; l++)
 
1181
                 if (canPutBuilding(x+k, y+l) == false)
 
1182
                   found_place = false;
 
1183
 
 
1184
             if (found_place == true)
 
1185
               break;
585
1186
        }
586
1187
 
587
1188
        if (found_place == true)
613
1214
    //if the building is close to the map boundaries, return false
614
1215
    if ((x < 3) || (x > (d_width-3)) || (y < 3) || (y > (d_height-3)))
615
1216
        return false;
616
 
        
 
1217
 
 
1218
    int dist = (int)CITY_TILE_WIDTH + 1;
617
1219
    //if there is another building too close, return false
618
 
    for (int locx = x-3; locx <= x+3; locx++)
619
 
        for (int locy = y-3; locy <= y+3; locy++)
 
1220
    for (int locx = x-dist; locx <= x+dist; locx++)
 
1221
        for (int locy = y-dist; locy <= y+dist; locy++)
620
1222
        {
621
1223
            if (offmap(locx, locy))
622
1224
                continue;
652
1254
{
653
1255
    std::map<Uint32,Uint32> ajacentTer;
654
1256
    Tile::Type curTer=Tile::NONE, ajTer=Tile::NONE;
655
 
    
 
1257
 
 
1258
    // that was 40 before. Now with rivers, the smaller the value - the more connected rivers we got.
 
1259
    int center_tiles = rand()%40;
 
1260
    //std::cerr << center_tiles << "\% chance of disconnecting rivers.\n";
 
1261
 
656
1262
    // Go through every tile bar the outer edge
657
1263
    for(int globy = 1; globy < (d_height-2); globy++)
658
1264
        for(int globx = 1; globx < (d_width-2); globx++)
686
1292
                    d_terrain[globy*d_width +globx] = Tile::GRASS;
687
1293
                else if ((ajacentTer[curTer]==2) && (rand()%100 < 70 ))
688
1294
                    d_terrain[globy*d_width +globx] = Tile::GRASS;
689
 
                else if ((ajacentTer[curTer]==3) && (rand()%100 < 40 ))
 
1295
                else if ((ajacentTer[curTer]==3) && (rand()%100 < center_tiles ))
690
1296
                    d_terrain[globy*d_width +globx] = Tile::GRASS;
691
1297
            }
692
1298
            else 
715
1321
        }
716
1322
    }
717
1323
}
 
1324
 
718
1325
bool MapGenerator::placePort(int x, int y)
719
1326
{
720
1327
  //if (Citylist::getInstance()->getNearestCity(Vector<int>(x, y), 2) == NULL)
723
1330
        {
724
1331
          Portlist *pl = Portlist::getInstance();
725
1332
          d_building[y*d_width + x] = Maptile::PORT;
726
 
          pl->push_back(Port(Vector<int>(x, y)));
 
1333
          pl->push_back(new Port(Vector<int>(x, y)));
727
1334
          calculateBlockedAvenue(x, y);
728
1335
          return true;
729
1336
        }
731
1338
  return false;
732
1339
}
733
1340
 
 
1341
int MapGenerator::tryRoad(Vector<int> src, Vector<int>dest)
 
1342
{
 
1343
  return tryRoad (src.x, src.y, dest.x, dest.y);
 
1344
}
 
1345
 
 
1346
int MapGenerator::tryRoad(int src_x, int src_y, int dest_x, int dest_y)
 
1347
{
 
1348
  bool retval = true;
 
1349
  GameMap *gm = GameMap::getInstance();
 
1350
  Vector<int> src(src_x, src_y);
 
1351
  Vector<int> dest(dest_x, dest_y);
 
1352
 
 
1353
  Path *p = new Path();
 
1354
  Stack s(NULL, src);
 
1355
 
 
1356
  Armysetlist *al = Armysetlist::getInstance();
 
1357
  Uint32 armyset = al->getArmysetId("Default", Tileset::getDefaultTileSize());
 
1358
  const ArmyProto* basearmy = Armysetlist::getInstance()->getArmy(armyset, 1);
 
1359
  Army *a = Army::createNonUniqueArmy(*basearmy);
 
1360
  s.push_back(a);
 
1361
  // try to get there with a scout
 
1362
  Uint32 moves = p->calculate(&s, dest, false);
 
1363
 
 
1364
  delete p;
 
1365
  return (int)moves;
 
1366
}
 
1367
 
734
1368
bool MapGenerator::makeRoad(Vector<int> src, Vector<int>dest)
735
1369
{
736
1370
  return makeRoad (src.x, src.y, dest.x, dest.y);
747
1381
  Stack s(NULL, src);
748
1382
 
749
1383
  Armysetlist *al = Armysetlist::getInstance();
750
 
  Uint32 armyset = al->getArmysetId("Default");
751
 
  const Army* basearmy = Armysetlist::getInstance()->getArmy(armyset, 1);
752
 
  Army *a = new Army(*basearmy, NULL);
 
1384
  Uint32 armyset = al->getArmysetId("Default", Tileset::getDefaultTileSize());
 
1385
  const ArmyProto* basearmy = Armysetlist::getInstance()->getArmy(armyset, 1);
 
1386
  Army *a = Army::createNonUniqueArmy(*basearmy);
753
1387
  s.push_back(a);
754
1388
  // try to get there with a scout
755
1389
  Uint32 moves = p->calculate(&s, dest, false);
761
1395
        {
762
1396
          int x = (**it).x;
763
1397
          int y = (**it).y;
764
 
          if (gm->getTile(x, y)->getMaptileType() == Tile::WATER)
 
1398
          if (gm->getTile(x, y)->getMaptileType() == Tile::WATER &&
 
1399
              gm->getTile(x, y)->getBuilding() != Maptile::BRIDGE)
765
1400
            {
766
1401
              retval = false;
767
1402
              break;
772
1407
              if (d_building[y*d_width + x] == 0)
773
1408
                {
774
1409
                  d_building[y*d_width + x] = Maptile::ROAD;
775
 
                  rl->push_back(Road(Vector<int>(x, y)));
 
1410
                  rl->push_back(new Road(Vector<int>(x, y)));
776
1411
                  calculateBlockedAvenue(x, y);
777
1412
                }
778
1413
            }
801
1436
  Stack s(NULL, src);
802
1437
 
803
1438
  Armysetlist *al = Armysetlist::getInstance();
804
 
  Uint32 armyset = al->getArmysetId("Default");
805
 
  const Army* basearmy = Armysetlist::getInstance()->getArmy(armyset, 1);
806
 
  Army *a = new Army(*basearmy, NULL);
 
1439
  Uint32 armyset = al->getArmysetId("Default", Tileset::getDefaultTileSize());
 
1440
  const ArmyProto* basearmy = Armysetlist::getInstance()->getArmy(armyset, 1);
 
1441
  Army *a = Army::createNonUniqueArmy(*basearmy);
807
1442
  s.push_back(a);
808
1443
  // try to get there with a scout
809
1444
  if (p->calculate(&s, dest, true) == 0)
829
1464
  Stack s(NULL, src);
830
1465
 
831
1466
  Armysetlist *al = Armysetlist::getInstance();
832
 
  Uint32 armyset = al->getArmysetId("Default");
833
 
  const Army* basearmy = Armysetlist::getInstance()->getArmy(armyset, 16);
834
 
  Army *a = new Army(*basearmy, NULL);
 
1467
  Uint32 armyset = al->getArmysetId("Default", Tileset::getDefaultTileSize());
 
1468
  const ArmyProto* basearmy = Armysetlist::getInstance()->getArmy(armyset, 16);
 
1469
  Army *a = Army::createNonUniqueArmy(*basearmy);
835
1470
  s.push_back(a);
836
1471
  // try to get there with a giant bat
837
1472
  Uint32 moves = p->calculate(&s, dest, false);
849
1484
          int nexty = (**nextit).y;
850
1485
          if (d_terrain[y*d_width + x] == Tile::MOUNTAIN)
851
1486
            {
852
 
              d_terrain[y*d_width +x] = Tile::GRASS;
 
1487
              d_terrain[y*d_width +x] = Tile::HILLS;
853
1488
              Maptile *t = new Maptile(gm->getTileset(), 
854
 
                                       x, y, Tile::GRASS, NULL);
 
1489
                                       x, y, Tile::HILLS, NULL);
855
1490
              gm->setTile(x, y, t);
856
1491
              calculateBlockedAvenue(x, y);
857
1492
            }
888
1523
 
889
1524
  return retval;
890
1525
}
 
1526
 
 
1527
std::vector<pair<int , Vector<int> > > MapGenerator::findBridgePlaces()
 
1528
{
 
1529
    std::vector<pair<int , Vector<int> > > result;
 
1530
    result.clear();
 
1531
 
 
1532
    for(int j = 1; j < d_height-5; j++)
 
1533
        for(int i = 1; i < d_width-5; i++)
 
1534
        {
 
1535
            if (
 
1536
                d_terrain[(j  )*d_width + i+1] != Tile::WATER &&
 
1537
                d_terrain[(j+1)*d_width + i+1] == Tile::WATER &&
 
1538
                d_terrain[(j+2)*d_width + i+1] == Tile::WATER &&
 
1539
                d_terrain[(j+3)*d_width + i+1] != Tile::WATER &&
 
1540
                d_terrain[(j+1)*d_width + i  ] == Tile::WATER &&
 
1541
                d_terrain[(j+2)*d_width + i  ] == Tile::WATER &&
 
1542
                d_terrain[(j+1)*d_width + i+2] == Tile::WATER &&
 
1543
                d_terrain[(j+2)*d_width + i+2] == Tile::WATER
 
1544
                )
 
1545
            {
 
1546
                int count_left =
 
1547
                (int)(d_terrain[(j  )*d_width + i  ] == Tile::WATER) +
 
1548
                (int)(d_terrain[(j+1)*d_width + i  ] == Tile::WATER) +
 
1549
                (int)(d_terrain[(j+2)*d_width + i  ] == Tile::WATER) +
 
1550
                (int)(d_terrain[(j+3)*d_width + i  ] == Tile::WATER) +
 
1551
                (int)(d_terrain[(j  )*d_width + i-1] == Tile::WATER) +
 
1552
                (int)(d_terrain[(j+1)*d_width + i-1] == Tile::WATER) +
 
1553
                (int)(d_terrain[(j+2)*d_width + i-1] == Tile::WATER) +
 
1554
                (int)(d_terrain[(j+3)*d_width + i-1] == Tile::WATER);
 
1555
                int count_right =
 
1556
                (int)(d_terrain[(j  )*d_width + i+2] == Tile::WATER) +
 
1557
                (int)(d_terrain[(j+1)*d_width + i+2] == Tile::WATER) +
 
1558
                (int)(d_terrain[(j+2)*d_width + i+2] == Tile::WATER) +
 
1559
                (int)(d_terrain[(j+3)*d_width + i+2] == Tile::WATER) +
 
1560
                (int)(d_terrain[(j  )*d_width + i+3] == Tile::WATER) +
 
1561
                (int)(d_terrain[(j+1)*d_width + i+3] == Tile::WATER) +
 
1562
                (int)(d_terrain[(j+2)*d_width + i+3] == Tile::WATER) +
 
1563
                (int)(d_terrain[(j+3)*d_width + i+3] == Tile::WATER);
 
1564
                
 
1565
                if(count_left > 5 && count_right > 5)
 
1566
                    result.push_back(std::make_pair(1, Vector<int>(i,j) ));
 
1567
            }
 
1568
            if (
 
1569
                d_terrain[(j+1)*d_width + i  ] != Tile::WATER &&
 
1570
                d_terrain[(j+1)*d_width + i+1] == Tile::WATER &&
 
1571
                d_terrain[(j+1)*d_width + i+2] == Tile::WATER &&
 
1572
                d_terrain[(j+1)*d_width + i+3] != Tile::WATER &&
 
1573
                d_terrain[(j  )*d_width + i+1] == Tile::WATER &&
 
1574
                d_terrain[(j  )*d_width + i+2] == Tile::WATER &&
 
1575
                d_terrain[(j+2)*d_width + i+1] == Tile::WATER &&
 
1576
                d_terrain[(j+2)*d_width + i+2] == Tile::WATER
 
1577
                )
 
1578
            {
 
1579
                int count_top =
 
1580
                (int)(d_terrain[(j  )*d_width + i  ] == Tile::WATER) +
 
1581
                (int)(d_terrain[(j  )*d_width + i+1] == Tile::WATER) +
 
1582
                (int)(d_terrain[(j  )*d_width + i+2] == Tile::WATER) +
 
1583
                (int)(d_terrain[(j  )*d_width + i+3] == Tile::WATER) +
 
1584
                (int)(d_terrain[(j-1)*d_width + i  ] == Tile::WATER) +
 
1585
                (int)(d_terrain[(j-1)*d_width + i+1] == Tile::WATER) +
 
1586
                (int)(d_terrain[(j-1)*d_width + i+2] == Tile::WATER) +
 
1587
                (int)(d_terrain[(j-1)*d_width + i+3] == Tile::WATER);
 
1588
 
 
1589
                int count_bottom =
 
1590
                (int)(d_terrain[(j+2)*d_width + i  ] == Tile::WATER) +
 
1591
                (int)(d_terrain[(j+2)*d_width + i+1] == Tile::WATER) +
 
1592
                (int)(d_terrain[(j+2)*d_width + i+2] == Tile::WATER) +
 
1593
                (int)(d_terrain[(j+2)*d_width + i+3] == Tile::WATER) +
 
1594
                (int)(d_terrain[(j+3)*d_width + i  ] == Tile::WATER) +
 
1595
                (int)(d_terrain[(j+3)*d_width + i+1] == Tile::WATER) +
 
1596
                (int)(d_terrain[(j+3)*d_width + i+2] == Tile::WATER) +
 
1597
                (int)(d_terrain[(j+3)*d_width + i+3] == Tile::WATER);
 
1598
 
 
1599
                if(count_top > 5 && count_bottom > 5)
 
1600
                    result.push_back(std::make_pair(2, Vector<int>(i,j) ));
 
1601
            }
 
1602
        }
 
1603
    // randomize
 
1604
    std::random_shuffle(result.begin(),result.end());
 
1605
 
 
1606
    // remove those that are too close to each other
 
1607
    std::set<int> bad;bad.clear();
 
1608
    for(size_t r = 0; r<result.size() ; ++r)
 
1609
        for(size_t s = r+1; s<result.size() ; ++s)
 
1610
            if(dist(Vector<float>(result[r].second),Vector<float>(result[s].second)) < 4.5)
 
1611
                bad.insert(r);
 
1612
    std::vector<pair<int , Vector<int> > > filter;filter.clear();
 
1613
    for(size_t r = 0; r<result.size() ; ++r)
 
1614
        if(bad.find(r) == bad.end())
 
1615
            filter.push_back(result[r]);
 
1616
    result=filter;
 
1617
 
 
1618
    return result;
 
1619
}
 
1620
 
891
1621
void MapGenerator::makeRoads()
892
1622
{
893
1623
  GameMap::deleteInstance();
909
1639
    for (int x = 0; x < d_width; x++)
910
1640
      {
911
1641
        if (d_building[y*d_width + x] == Maptile::CITY)
912
 
          Citylist::getInstance()->push_back(City(Vector<int>(x,y)));
 
1642
          Citylist::getInstance()->push_back(new City(Vector<int>(x,y)));
913
1643
      }
914
1644
  GameMap::getInstance()->calculateBlockedAvenues();
915
1645
 
918
1648
    {
919
1649
      if (rand() % 2 == 0)
920
1650
        continue;
921
 
      City *c = cl->getNearestCityPast((*it).getPos(), 13);
 
1651
      City *c = cl->getNearestCityPast((*it)->getPos(), 13);
922
1652
      Vector<int> dest = c->getPos();
923
 
      Vector<int> src = (*it).getPos();
 
1653
      Vector<int> src = (*it)->getPos();
924
1654
      //does it already have a road going to it?
925
1655
      if (Roadlist::getInstance()->getNearestObjectBefore(dest, 
926
1656
                                                          c->getSize() + 1))
927
1657
        continue;
928
1658
 
929
1659
      makeRoad(src, dest);
 
1660
      progress.emit(.810, _("paving roads..."));
930
1661
    }
931
1662
 
932
1663
  //make all cities accessible by allowing movement to a central city
934
1665
  City *center = cl->getNearestCity(pos);
935
1666
  for (Citylist::iterator it = cl->begin(); it != cl->end(); it++)
936
1667
    {
937
 
      if (center == &*it)
 
1668
      if (center == *it)
938
1669
        continue;
939
 
      if (isAccessible(center->getPos(), (*it).getPos()) == false)
940
 
        makeAccessible(center->getPos(), (*it).getPos());
 
1670
      if (isAccessible(center->getPos(), (*it)->getPos()) == false)
 
1671
        makeAccessible(center->getPos(), (*it)->getPos());
 
1672
      progress.emit(.810, _("paving roads..."));
941
1673
    }
942
1674
 
943
1675
  Roadlist::deleteInstance();
945
1677
  Citylist::deleteInstance();
946
1678
  Portlist::deleteInstance();
947
1679
}
 
1680
 
 
1681
void MapGenerator::rescueLoneTiles(Tile::Type FIND_THIS, Tile::Type REPLACE, bool grow)
 
1682
{
 
1683
    int box[3][3];
 
1684
    memset (box, 0, sizeof (box));
 
1685
 
 
1686
    if(grow)
 
1687
    {
 
1688
        for(int j = 1; j < d_height-1; j++)
 
1689
            for(int i = 1; i < d_width-1; i++)
 
1690
            {
 
1691
                if (d_terrain[j*d_width + i] == FIND_THIS &&
 
1692
                   (d_terrain[(j-1)*d_width + i-1] == FIND_THIS &&
 
1693
                    d_terrain[(j  )*d_width + i-1] == FIND_THIS &&
 
1694
                    d_terrain[(j-1)*d_width + i  ] != FIND_THIS))
 
1695
                    d_terrain[(j-1)*d_width + i  ] =  FIND_THIS;
 
1696
            }
 
1697
    }
 
1698
 
 
1699
    for(int iteration=0; iteration <8 ;++iteration)
 
1700
    {
 
1701
        for(int j = 0; j < d_height; j++)
 
1702
            for(int i = 0; i < d_width; i++)
 
1703
            {
 
1704
                if(d_terrain[j*d_width + i] == FIND_THIS)
 
1705
                { 
 
1706
                    for (int I = -1; I <= +1; ++I)
 
1707
                        for (int J = -1; J <= +1; ++J)
 
1708
                            if (!(offmap(i+I,j+J)))
 
1709
                                box[J+1][I+1] = (d_terrain[(j+J)*d_width + (i+I)] == d_terrain[j*d_width + i]);
 
1710
                            else
 
1711
                                box[J+1][I+1] = 0;
 
1712
 
 
1713
                    if (!box[0][2] && !box[1][2] && /***********/ 
 
1714
                        /***********/  box[1][1] &&  box[2][1] && 
 
1715
                        !box[0][0] && !box[1][0]    /***********/)
 
1716
                            d_terrain[j*d_width + i] = REPLACE;
 
1717
                    if (/***********/ !box[1][2] && !box[2][2] && 
 
1718
                         box[0][1] &&  box[1][1] && /***********/
 
1719
                        /***********/ !box[1][0] && !box[2][0])
 
1720
                            d_terrain[j*d_width + i] = REPLACE;
 
1721
                    if (!box[0][2] && /***********/ !box[2][2] && 
 
1722
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1723
                        /***********/  box[1][0]    /***********/)
 
1724
                            d_terrain[j*d_width + i] = REPLACE;
 
1725
                    if (/***********/  box[1][2] && /***********/
 
1726
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1727
                        !box[0][0] && /***********/ !box[2][0])
 
1728
                            d_terrain[j*d_width + i] = REPLACE;
 
1729
 
 
1730
                    if (/***********/ !box[1][2] && /***********/ 
 
1731
                        /***********/  box[1][1] &&  box[2][1] && 
 
1732
                        !box[0][0] && !box[1][0]    /***********/)
 
1733
                            d_terrain[j*d_width + i] = REPLACE;
 
1734
                    if (/***********/ !box[1][2] && /***********/ 
 
1735
                         box[0][1] &&  box[1][1] && /***********/
 
1736
                        /***********/ !box[1][0] && !box[2][0])
 
1737
                            d_terrain[j*d_width + i] = REPLACE;
 
1738
                    if (/***********/ /***********/ !box[2][2] && 
 
1739
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1740
                        /***********/  box[1][0]    /***********/)
 
1741
                            d_terrain[j*d_width + i] = REPLACE;
 
1742
                    if (/***********/  box[1][2] && /***********/
 
1743
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1744
                        /***********/ /***********/ !box[2][0])
 
1745
                            d_terrain[j*d_width + i] = REPLACE;
 
1746
 
 
1747
                    if (!box[0][2] && !box[1][2] && /***********/ 
 
1748
                        /***********/  box[1][1] &&  box[2][1] && 
 
1749
                        /***********/ !box[1][0]    /***********/)
 
1750
                            d_terrain[j*d_width + i] = REPLACE;
 
1751
                    if (/***********/ !box[1][2] && !box[2][2] && 
 
1752
                         box[0][1] &&  box[1][1] && /***********/
 
1753
                        /***********/ !box[1][0]    /***********/)
 
1754
                            d_terrain[j*d_width + i] = REPLACE;
 
1755
                    if (!box[0][2] && /***********/ /***********/ 
 
1756
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1757
                        /***********/  box[1][0]    /***********/)
 
1758
                            d_terrain[j*d_width + i] = REPLACE;
 
1759
                    if (/***********/  box[1][2] && /***********/
 
1760
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1761
                        !box[0][0]    /***********/ /***********/)
 
1762
                            d_terrain[j*d_width + i] = REPLACE;
 
1763
 
 
1764
                    if (/***********/ !box[1][2] && /***********/ 
 
1765
                        !box[0][1] &&  box[1][1] &&  box[2][1] && 
 
1766
                        /***********/ !box[1][0]    /***********/)
 
1767
                            d_terrain[j*d_width + i] = REPLACE;
 
1768
                    if (/***********/ !box[1][2] && /***********/ 
 
1769
                         box[0][1] &&  box[1][1] && !box[2][1] &&
 
1770
                        /***********/ !box[1][0]    /***********/)
 
1771
                            d_terrain[j*d_width + i] = REPLACE;
 
1772
                    if (/***********/ !box[1][2] && /***********/ 
 
1773
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1774
                        /***********/  box[1][0]    /***********/)
 
1775
                            d_terrain[j*d_width + i] = REPLACE;
 
1776
                    if (/***********/  box[1][2] && /***********/
 
1777
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1778
                        /***********/ !box[1][0]    /***********/)
 
1779
                            d_terrain[j*d_width + i] = REPLACE;
 
1780
 
 
1781
                    if ( box[0][2] && !box[1][2] && /***********/
 
1782
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1783
                        /***********/ !box[1][0]    /***********/)
 
1784
                            d_terrain[j*d_width + i] = REPLACE;
 
1785
                    if (/***********/ !box[1][2] &&  box[2][2] && 
 
1786
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1787
                        /***********/ !box[1][0]    /***********/)
 
1788
                            d_terrain[j*d_width + i] = REPLACE;
 
1789
                    if (/***********/ !box[1][2] && /***********/ 
 
1790
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1791
                         box[0][0] && !box[1][0]    /***********/)
 
1792
                            d_terrain[j*d_width + i] = REPLACE;
 
1793
                    if (/***********/ !box[1][2] && /***********/  
 
1794
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1795
                        /***********/ !box[1][0] &&  box[2][0])
 
1796
                            d_terrain[j*d_width + i] = REPLACE;
 
1797
 
 
1798
 
 
1799
                    if ( box[0][2] && !box[1][2] &&  box[2][2] &&  
 
1800
                         box[0][1] &&  box[1][1] &&  box[2][1] && 
 
1801
                         box[0][0] && !box[1][0] &&  box[2][0])
 
1802
                            d_terrain[j*d_width + i+(rand()%2?+1:-1)] = FIND_THIS;
 
1803
                    if ( box[0][2] &&  box[1][2] &&  box[2][2] &&  
 
1804
                        !box[0][1] &&  box[1][1] && !box[2][1] && 
 
1805
                         box[0][0] &&  box[1][0] &&  box[2][0])
 
1806
                            d_terrain[(j+(rand()%2?+1:-1))*d_width + i] = FIND_THIS;
 
1807
 
 
1808
                    if ( box[0][2] && !box[1][2] && !box[2][2] &&  
 
1809
                         box[0][1] &&  box[1][1] && !box[2][1] && 
 
1810
                        !box[0][0] &&  box[1][0] &&  box[2][0])
 
1811
                            d_terrain[j*d_width + i] = REPLACE;
 
1812
                    if (!box[0][2] && !box[1][2] &&  box[2][2] &&  
 
1813
                        !box[0][1] &&  box[1][1] &&  box[2][1] && 
 
1814
                         box[0][0] &&  box[1][0] && !box[2][0])
 
1815
                            d_terrain[j*d_width + i] = REPLACE;
 
1816
                    if ( box[0][2] &&  box[1][2] && !box[2][2] &&  
 
1817
                        !box[0][1] &&  box[1][1] &&  box[2][1] && 
 
1818
                        !box[0][0] && !box[1][0] &&  box[2][0])
 
1819
                            d_terrain[j*d_width + i] = REPLACE;
 
1820
                    if (!box[0][2] &&  box[1][2] &&  box[2][2] &&  
 
1821
                         box[0][1] &&  box[1][1] && !box[2][1] && 
 
1822
                         box[0][0] && !box[1][0] && !box[2][0])
 
1823
                            d_terrain[j*d_width + i] = REPLACE;
 
1824
                }
 
1825
            }
 
1826
    }
 
1827
}
 
1828
 
 
1829
void MapGenerator::surroundMountains(int minx, int maxx, int miny, int maxy)
 
1830
{
 
1831
  for(int j = miny; j < maxy; j++)
 
1832
    for(int i = minx; i < maxx; i++)
 
1833
      if(d_terrain[j*d_width + i] == Tile::MOUNTAIN)
 
1834
        for(int J = -1; J <= +1; ++J)
 
1835
          for(int I = -1; I <= +1; ++I)
 
1836
            if((!(offmap(i+I,j+J))) &&
 
1837
               (d_terrain[(j+J)*d_width + (i+I)] != Tile::MOUNTAIN))
 
1838
              {
 
1839
                if(d_terrain[(j+J)*d_width + (i+I)] != Tile::WATER)
 
1840
                  d_terrain[(j+J)*d_width + (i+I)] = Tile::HILLS;
 
1841
                else 
 
1842
                  // water has priority here, there was some work done to conenct bodies of water
 
1843
                  // so don't break those connections.
 
1844
                  d_terrain[(j  )*d_width + (i  )] = Tile::HILLS;
 
1845
              }
 
1846
}