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
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.
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.
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
31 //#include <boost/foreach.hpp>
33 #include "MapGenerator.h"
46 #include "templelist.h"
48 #include "bridgelist.h"
50 #include "armysetlist.h"
53 #include "RoadPathCalculator.h"
56 #define debug(x) {std::cerr<<__FILE__<<": "<<__LINE__<<": "<<x<<std::endl<<std::flush;}
58 #define offmap(bx,by) (by<0)||(by>=d_height)||(bx<0)||(bx>=d_width)
62 //-------------------------------------------------------------------
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)
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;
75 MapGenerator::~MapGenerator()
83 int MapGenerator::setNoCities(int nocities)
89 d_nocities = nocities;
93 int MapGenerator::setNoRuins(int noruins)
103 int MapGenerator::setNoSignposts(int nosignposts)
108 int tmp = d_nosignposts;
109 d_nosignposts = nosignposts;
113 int MapGenerator::setNoTemples(int notemples)
118 int tmp = d_notemples;
119 d_notemples = notemples;
123 void MapGenerator::setPercentages(int pwater, int pforest, int pswamp,
124 int phills, int pmountains)
126 if ((pswamp < 0) || (pwater < 0) || (pforest < 0) || (phills < 0)
130 if (pswamp + pwater + pforest + phills + pmountains > 100)
137 d_pmountains = pmountains;
141 * Generates a random map . The map is stored as a char array of size
142 * 100x100. Each character stands for something. We use :
153 * c = part of city/castle
154 * See the TileMapTypes enum at the beginning of the class definition.
156 * See printMap() which is used for debugging maps.
158 void MapGenerator::makeMap(int width, int height, bool roads)
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;
170 debug("Making random map:");
172 // create the terrain
173 debug("flatening plains");
174 progress.emit(.090, _("flattening plains..."));
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);
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..."));
203 debug("building cities");
204 progress.emit(.720, _("building cities..."));
205 makeCities(d_nocities);
209 debug("paving roads");
210 progress.emit(.810, _("paving roads..."));
213 rescueLoneTiles(Tile::MOUNTAIN,Tile::HILLS,false);
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");
224 progress.emit(.950, _("building bridges..."));
227 debug("raising signs");
228 progress.emit(.990, _("raising signs..."));
229 makeBuildings(Maptile::SIGNPOST,d_nosignposts);
231 debug("Done making map.");
236 #define NORTH_SOUTH_BRIDGE 1
237 #define EAST_WEST_BRIDGE 2
239 void MapGenerator::placeBridge(Vector<int> pos, int type)
241 Bridgelist *bl = Bridgelist::getInstance();
242 if (type == NORTH_SOUTH_BRIDGE)
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)));
249 else if (type == EAST_WEST_BRIDGE)
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)));
256 GameMap::getInstance()->calculateBlockedAvenues();
259 bool MapGenerator::findBridgePurpose(Vector<int> pos, int type,
260 Vector<int> &src, Vector<int> &dest)
262 if (type == EAST_WEST_BRIDGE)
264 src = GameMap::getInstance()->findNearestObjectToTheWest(pos);
265 dest = GameMap::getInstance()->findNearestObjectToTheEast(pos);
267 else if (type == NORTH_SOUTH_BRIDGE)
269 src = GameMap::getInstance()->findNearestObjectToTheNorth(pos);
270 dest = GameMap::getInstance()->findNearestObjectToTheSouth(pos);
272 if (src == Vector<int>(-1,-1) || dest == Vector<int>(-1,-1))
277 bool MapGenerator::canPlaceBridge(Vector<int> pos, int type, Vector<int> &src, Vector<int> &dest)
279 if (d_building[pos.y*d_width + pos.x] == Maptile::NONE &&
280 findBridgePurpose(pos, type, src, dest) == true)
285 void MapGenerator::makeBridges()
287 GameMap::deleteInstance();
288 Citylist::deleteInstance();
289 Roadlist::deleteInstance();
290 Ruinlist::deleteInstance();
291 Templelist::deleteInstance();
292 Portlist::deleteInstance();
293 Bridgelist::deleteInstance();
295 GameMap::setWidth(d_width);
296 GameMap::setHeight(d_height);
297 GameMap::getInstance("default", "default", "default")->fill(this);
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();
305 //load up the roadlist, and stuff.
307 for (int y = 0; y < d_height; y++)
308 for (int x = 0; x < d_width; x++)
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)));
324 GameMap::getInstance()->calculateBlockedAvenues();
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++)
332 Vector<int> pos = (*it).second + Vector<int>(1,1);
335 if ((*it).first == NORTH_SOUTH_BRIDGE)
337 edge1 = pos - Vector<int>(0, 1);
338 edge2 = pos + Vector<int>(0, 2);
340 else if ((*it).first == EAST_WEST_BRIDGE)
342 edge1 = pos - Vector<int>(1, 0);
343 edge2 = pos + Vector<int>(2, 0);
345 if (offmap(edge1.x, edge1.y) || offmap(edge2.x, edge2.y))
347 if (canPlaceBridge((*it).second + Vector<int>(1,1), (*it).first, src,
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;
359 if (construct_bridge_and_roads)
361 makeRoad(src, edge1);
362 makeRoad(dest, edge2);
363 placeBridge(pos, (*it).first);
366 progress.emit(.950, _("paving bridges..."));
369 Roadlist::deleteInstance();
370 Ruinlist::deleteInstance();
371 Templelist::deleteInstance();
372 GameMap::deleteInstance();
373 Citylist::deleteInstance();
374 Portlist::deleteInstance();
375 Bridgelist::deleteInstance();
378 void MapGenerator::printMap(int j, int i)
381 bool adom_convention=true; // well, except mountains
382 switch(d_terrain[j*d_width + i])
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;
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
402 void MapGenerator::printMap()
404 for(int j = 0; j < d_height; j++)
406 for(int i = 0; i < d_width; i++)
413 const Tile::Type* MapGenerator::getMap(int& width, int& height) const
420 const Maptile::Building* MapGenerator::getBuildings(int& width, int& height) const
427 void MapGenerator::makePlains()
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;
434 void MapGenerator::connectWithWater(Vector<int> from, Vector<int> to)
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
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)
445 int j = (int)(path.x);
446 int i = (int)(path.y);
453 if((!(offmap(i,j))) && (!(offmap(i-1,j-1))))
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;
462 if((!(offmap(i,j))) && (!(offmap(i+1,j+1))))
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;
471 if((!(offmap(i,j))) && (!(offmap(i-1,j+1))))
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;
480 if((!(offmap(i,j))) && (!(offmap(i+1,j-1))))
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;
491 void MapGenerator::findAreasOf(Tile::Type THIS_TILE,std::vector<std::vector<int> >& box,int& how_many)
493 box.resize(d_height);
494 for(int j = 0; j < d_height; j++)
495 box[j].resize(d_width,0);
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++)
502 d_terrain[j*d_width + i] == THIS_TILE &&
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) ||
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) ||
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) ||
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))
521 box[j][i]=++how_many+3000;
526 for(int J = 1; J < d_height-1; J++)
527 for(int I = 1; I < d_width-1; I++)
529 if(d_terrain[J*d_width + I] == THIS_TILE &&
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))
537 box[J][I]=how_many+2000;
540 for(int J = 0; J < d_height; J++)
541 for(int I = 0; I < d_width; I++)
543 if (box[J][I]==how_many+3000)
545 if (box[J][I]==how_many+2000)
546 box[J][I]=how_many+3000;
552 void MapGenerator::verifyIslands()
555 std::vector<std::vector<int> > box;
556 findAreasOf(Tile::GRASS,box,how_many);
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++)
564 counts[box[j][i]] += 1;
566 // find four largest land areas
567 std::set<int> largest;largest.clear();
569 for(int z=0 ; z<4 ; ++z)
572 for(size_t i=0 ; i<counts.size() ; ++i)
574 if(counts[i] > max && largest.find(counts[i]) == largest.end())
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]);
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++)
592 d_terrain[j*d_width + i] = Tile::WATER;
595 void MapGenerator::makeRivers()
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;
603 // count how many separate bodies of water were found
606 int iter=0; // avoid deadlocks
611 std::vector<std::vector<int> > box;
613 findAreasOf(Tile::WATER,box,how_many);
615 // this loop allows maximum 3 distinctly separated bodies of water
616 // so no need to continue the algorithm
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++)
629 counts[box[j][i]] += 1;
630 centers[box[j][i]] += Vector<float>(j,i);
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)
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);
645 // center doesn't necessarily fall on water tile, so fix this.
647 // // for debugging...
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;
655 int shortest = std::min( std::min(i_up,i_dn) , std::min(j_up,j_dn));
657 if(shortest == i_up && I+i_up < d_width)
658 centers[h] = Vector<float>( J , I+i_up );
660 if(shortest == i_dn && I-i_dn >= 0 )
661 centers[h] = Vector<float>( J , I-i_dn );
663 if(shortest == j_up && J+j_up < d_height)
664 centers[h] = Vector<float>( J+j_up , I );
666 if(shortest == j_dn && J-j_dn >= 0 )
667 centers[h] = Vector<float>( J+j_dn , I );
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");
676 // // for debugging...
677 // box[(int)(centers[h].x)][(int)(centers[h].y)]+=4000;
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)
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;
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)
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)
699 if(counts[h] > 0 && counts[k] > 0) // h and k are two different areas
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++)
708 float dj = j - centers[k].x;
709 float di = i - centers[k].y;
710 float dist = dj*dj + di*di;
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++)
726 float dj = j - min_h_j;
727 float di = i - min_h_i;
728 float dist = dj*dj + di*di;
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)) );
750 for(int connect_some_closest=0; connect_some_closest<14; connect_some_closest+=river_style)
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;
757 if(connect_some_closest < 2 ) start_h=the_biggest_area;
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)
765 min = distances[h][k].first;
769 if (closest_h != -1 &&
772 connectWithWater(distances[closest_h][closest_k].second.first , distances[closest_h][closest_k].second.second);
774 distances[closest_h][closest_k].first = d_height*d_height;
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)
784 // BOOST_FOREACH(int i,a)
787 // std::cout << i << " ";
790 // std::cout << "X" << " ";
793 // std::cout << "%" << " ";
796 // std::cout << "!" << " ";
798 // std::cout << "|" << " ";
800 // std::cout << "\n";
802 // std::cout << "\n";
806 //std::cout << "There are " << how_many << (how_many<4?(std::string(" seas")):(std::string(" lakes"))) << " on this map.\n";
808 //std::cout << "There is 1 sea on this map.\n";
809 //std::cout << "River style was: " << river_style << "\n";
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 :
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
830 void MapGenerator::makeTerrain(Tile::Type t, int percent, bool contin)
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
836 while(placed != terrain)
838 // find a random starting position
839 int x = rand() % d_width;
840 int y = rand() % d_height;
841 if (seekPlain(x, y) == false)
845 // now go on until we hit a dead end
846 while (placed < terrain)
848 // if we are on grass, modify this tile first
849 if (d_terrain[y*d_width + x] == Tile::GRASS)
851 d_terrain[y*d_width + x] = t;
856 // from a random direction, check all directions for further progress
858 for (int dir = rand()%8; loop < 8; loop++, dir = (dir+1)%8)
860 int tmpx = x + d_xdir[dir];
861 int tmpy = y + d_ydir[dir];
863 // reject invalid data
864 if (offmap(tmpx, tmpy) || d_terrain[tmpy*d_width + tmpx] != Tile::GRASS)
867 // else move our region of interest by one tile
870 d_terrain[y*d_width + x] = t;
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()
882 if (seekPlain(x, y) == false)
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 :
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
910 void MapGenerator::makeStreamer(Tile::Type t, int percent, int thick)
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
918 while(placed < terrain)
920 // find a random starting position
921 int x = rand() % d_width;
922 int y = rand() % d_height;
923 if (seekPlain(x, y) == false)
925 dir = rand()%8; // pick a random direction
926 // now go on until we hit a dead end
927 while (placed < terrain)
929 // if we are on grass, modify this tile first
930 if (d_terrain[y*d_width + x] == Tile::GRASS)
932 d_terrain[y*d_width + x] = t;
954 int tmpx = x + d_xdir[dir];
955 int tmpy = y + d_ydir[dir];
957 // reject invalid data
958 if (offmap(tmpx, tmpy))// || d_terrain[tmpy*d_width + tmpx] != Tile::GRASS)
961 // else move our region of interest by one tile
964 d_terrain[y*d_width + x] = t;
968 case 1: case 2: case 6: case 5:
970 for (i = 1; i <= thick ; i++)
974 d_terrain[y*d_width + x+i] = t;
979 case 7: case 3: case 0: case 4:
981 for (i = 1; i <= thick; i++)
985 d_terrain[(y+i)*d_width + x] = t;
998 bool MapGenerator::seekPlain(int& x, int& 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).
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.
1012 if (d_terrain[y*d_width + x] == Tile::GRASS)
1015 std::deque<Vector<int> > tiles;
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]));
1022 // now loop until all tiles were checked (should hardly happen)
1023 while (!tiles.empty())
1025 Vector<int> p = tiles.front();
1028 if (offmap(p.x, p.y))
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)
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:
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.
1056 // edge tile; append three new tiles
1057 if (abs(dx) == abs(dy))
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));
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));
1084 // if this line is ever reached, we haven't found a free grass tile
1085 // (should only happen under really exceptional circumstances)
1091 bool MapGenerator::inhospitableTerrain(int x, int y, unsigned int width)
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)
1101 void MapGenerator::makeCities(int cities)
1108 while(city_count < cities)
1110 int x = rand()%(d_width-2);
1111 int y = rand()%(d_height-2);
1112 if (inhospitableTerrain(x, y, cityset->getCityTileWidth()) && (iterations < 1000))
1118 // check if we can put the building
1119 if (!canPutCity(x, y) && iterations < 1000)
1125 putCity(x, y, city_count);
1131 bool MapGenerator::canPutCity(int x,int y)
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)
1141 void MapGenerator::putCity(int x, int y, int& city_count)
1143 d_building[y*d_width + x] = Maptile::CITY;
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;
1158 void MapGenerator::makeBuildings(Maptile::Building b, int building)
1161 int iterations = 10;
1162 bool found_place = false;
1164 unsigned int width = 1;
1169 width = cityset->getCityTileWidth(); break;
1171 width = cityset->getRuinTileWidth(); break;
1172 case Maptile::TEMPLE:
1173 width = cityset->getTempleTileWidth(); break;
1175 case Maptile::SIGNPOST:
1178 case Maptile::BRIDGE:
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++)
1188 for (j = 0; j < iterations; j++)
1191 y = rand()%d_height;
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;
1199 if (found_place == true)
1203 if (found_place == true)
1205 d_terrain[y*d_width + x] = Tile::GRASS;
1206 d_building[y*d_width + x] = b;
1207 found_place = false;
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.
1223 bool MapGenerator::canPutBuilding(int x,int y)
1225 // if the building is on water or mountains, return false
1226 if (d_terrain[y*d_width +x] != Tile::GRASS )
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)))
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++)
1238 if (offmap(locx, locy))
1240 if (d_building[locy*d_width + locx] != Maptile::NONE)
1243 // everything okay here! return true
1248 bool MapGenerator::tryToPlaceCity(int px,int py ,int& city_count)
1250 // first, try to place the city at the given location
1251 if (canPutCity(px, py))
1253 putCity(px, py, city_count);
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]))
1261 putCity(px + d_xdir[dir], py + d_ydir[dir], city_count);
1268 void MapGenerator::normalize()
1270 std::map<guint32,guint32> ajacentTer;
1271 Tile::Type curTer=Tile::NONE, ajTer=Tile::NONE;
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";
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++)
1281 curTer = d_terrain[globy*d_width + globx];
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;
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++)
1295 ajTer = d_terrain[locy*d_width +locx];
1296 ajacentTer[ajTer] += 1;
1299 // we have counted our own tile as well
1300 ajacentTer[curTer] -= 1;
1302 if (curTer==Tile::WATER) // For the moment only water is normalized
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;
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;
1325 void MapGenerator::calculateBlockedAvenue(int x, int y)
1327 for (int i = x - 1; i <= x + 1; i++)
1329 for (int j = y - 1; j <= y + 1; j++)
1331 if (i < 0 || i >= d_width)
1333 if (j < 0 || j >= d_height)
1335 GameMap::getInstance()->calculateBlockedAvenue(i, j);
1340 bool MapGenerator::placePort(int x, int y)
1342 //if (Citylist::getInstance()->getNearestCity(Vector<int>(x, y), 2) == NULL)
1344 if (d_building[y*d_width + x] == 0)
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);
1356 int MapGenerator::tryRoad(Vector<int> src, Vector<int>dest)
1358 return tryRoad (src.x, src.y, dest.x, dest.y);
1361 int MapGenerator::tryRoad(int src_x, int src_y, int dest_x, int dest_y)
1363 Vector<int> src(src_x, src_y);
1364 Vector<int> dest(dest_x, dest_y);
1366 Path *p = new Path();
1369 ArmyProto *basearmy = ArmyProto::createScout();
1370 Army *a = Army::createNonUniqueArmy(*basearmy);
1373 // try to get there with a scout
1374 guint32 moves = p->calculate(&s, dest, false);
1380 bool MapGenerator::makeRoad(Vector<int> src, Vector<int>dest)
1382 return makeRoad (src.x, src.y, dest.x, dest.y);
1385 bool MapGenerator::makeRoad(int src_x, int src_y, int dest_x, int dest_y)
1388 GameMap *gm = GameMap::getInstance();
1389 Vector<int> src(src_x, src_y);
1390 Vector<int> dest(dest_x, dest_y);
1392 RoadPathCalculator rpc(src);
1393 Path *p = rpc.calculate(dest);
1397 Roadlist *rl = Roadlist::getInstance();
1398 for (Path::iterator it = p->begin(); it != p->end(); it++)
1402 if (gm->getTile(x, y)->getMaptileType() == Tile::WATER &&
1403 gm->getTile(x, y)->getBuilding() != Maptile::BRIDGE)
1408 Citylist *cl = Citylist::getInstance();
1409 if (cl->getObjectAt(x, y) == NULL)
1411 if (d_building[y*d_width + x] == 0)
1413 d_building[y*d_width + x] = Maptile::ROAD;
1414 rl->add(new Road(Vector<int>(x, y)));
1415 calculateBlockedAvenue(x, y);
1428 bool MapGenerator::isAccessible(Vector<int> src, Vector<int> dest)
1430 return isAccessible (src.x, src.y, dest.x, dest.y);
1433 bool MapGenerator::isAccessible (int src_x, int src_y, int dest_x, int dest_y)
1436 Vector<int> src(src_x, src_y);
1437 Vector<int> dest(dest_x, dest_y);
1439 Path *p = new Path();
1442 ArmyProto *basearmy = ArmyProto::createScout();
1443 Army *a = Army::createNonUniqueArmy(*basearmy);
1446 // try to get there with a scout
1447 if (p->calculate(&s, dest, true) <= 0)
1454 bool MapGenerator::makeAccessible(Vector<int> src, Vector<int> dest)
1456 return makeAccessible(src.x, src.y, dest.x, dest.y);
1459 bool MapGenerator::makeAccessible(int src_x, int src_y, int dest_x, int dest_y)
1462 GameMap *gm = GameMap::getInstance();
1463 Vector<int> src(src_x, src_y);
1464 Vector<int> dest(dest_x, dest_y);
1466 Path *p = new Path();
1469 ArmyProto *basearmy = ArmyProto::createScout();
1470 Army *a = Army::createNonUniqueArmy(*basearmy);
1473 guint32 moves = p->calculate(&s, dest, false);
1479 ArmyProto *basearmy = ArmyProto::createBat();
1480 a = Army::createNonUniqueArmy(*basearmy);
1483 moves = p->calculate(&s, dest, false);
1488 Path::iterator it = p->begin();
1489 Path::iterator nextit = it;
1491 for ( ; nextit != p->end(); it++, nextit++)
1495 int nextx = (*nextit).x;
1496 int nexty = (*nextit).y;
1497 if (d_terrain[y*d_width + x] == Tile::MOUNTAIN)
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);
1505 if (d_terrain[y*d_width + x] == Tile::WATER &&
1506 d_terrain[nexty*d_width + nextx] != Tile::WATER)
1508 if (placePort(x, y) == true)
1510 if (isAccessible(src_x, src_y, dest.x, dest.y))
1517 else if (d_terrain[y*d_width + x] != Tile::WATER &&
1518 d_terrain[nexty*d_width + nextx] == Tile::WATER)
1520 if (placePort(nextx, nexty) == true)
1522 if (isAccessible(src_x, src_y, dest.x, dest.y))
1539 std::vector<pair<int , Vector<int> > > MapGenerator::findBridgePlaces()
1541 std::vector<pair<int , Vector<int> > > result;
1544 for(int j = 1; j < d_height-5; j++)
1545 for(int i = 1; i < d_width-5; i++)
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
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);
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);
1577 if(count_left > 5 && count_right > 5)
1578 result.push_back(std::make_pair(1, Vector<int>(i,j) ));
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
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);
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);
1611 if(count_top > 5 && count_bottom > 5)
1612 result.push_back(std::make_pair(2, Vector<int>(i,j) ));
1616 std::random_shuffle(result.begin(),result.end());
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)
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]);
1633 void MapGenerator::makeRoads()
1635 GameMap::deleteInstance();
1636 Citylist::deleteInstance();
1637 Roadlist::deleteInstance();
1638 Portlist::deleteInstance();
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();
1650 for (int y = 0; y < d_height; y++)
1651 for (int x = 0; x < d_width; x++)
1653 if (d_building[y*d_width + x] == Maptile::CITY)
1654 Citylist::getInstance()->add
1655 (new City(Vector<int>(x,y), cityset->getCityTileWidth()));
1657 GameMap::getInstance()->calculateBlockedAvenues();
1659 Citylist *cl = Citylist::getInstance();
1660 for (Citylist::iterator it = cl->begin(); it != cl->end(); it++)
1662 if (rand() % 2 == 0)
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,
1672 makeRoad(src, dest);
1673 progress.emit(.810, _("paving roads..."));
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++)
1683 if (isAccessible(center->getPos(), (*it)->getPos()) == false)
1685 makeAccessible(center->getPos(), (*it)->getPos());
1687 progress.emit(.810, _("paving roads..."));
1690 Roadlist::deleteInstance();
1691 GameMap::deleteInstance();
1692 Citylist::deleteInstance();
1693 Portlist::deleteInstance();
1696 void MapGenerator::rescueLoneTiles(Tile::Type FIND_THIS, Tile::Type REPLACE, bool grow)
1699 memset (box, 0, sizeof (box));
1703 for(int j = 1; j < d_height-1; j++)
1704 for(int i = 1; i < d_width-1; i++)
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;
1714 for(int iteration=0; iteration <8 ;++iteration)
1716 for(int j = 0; j < d_height; j++)
1717 for(int i = 0; i < d_width; i++)
1719 if(d_terrain[j*d_width + i] == FIND_THIS)
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]);
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;
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;
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;
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;
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;
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;
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;
1844 void MapGenerator::surroundMountains(int minx, int maxx, int miny, int maxy)
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))
1854 if(d_terrain[(j+J)*d_width + (i+I)] != Tile::WATER)
1855 d_terrain[(j+J)*d_width + (i+I)] = Tile::HILLS;
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;