The Battle for Wesnoth  1.19.0-dev
default_map_generator_job.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2003 - 2024
3  by David White <dave@whitevine.net>
4  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License as published by
8  the Free Software Foundation; either version 2 of the License, or
9  (at your option) any later version.
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY.
12 
13  See the COPYING file for more details.
14 */
15 
16 /**
17  * @file
18  * Map-generator, with standalone testprogram.
19  */
20 
23 #include "game_config_manager.hpp"
24 #include "gettext.hpp"
25 #include "log.hpp"
26 #include "map/map.hpp"
27 #include "generators/map_generator.hpp" // mapgen_exception
28 #include "pathfind/pathfind.hpp"
29 #include "pathutils.hpp"
31 #include "seed_rng.hpp"
32 #include "wml_exception.hpp"
33 
34 #include <SDL2/SDL_timer.h>
35 
36 static lg::log_domain log_mapgen("mapgen");
37 #define ERR_NG LOG_STREAM(err, log_mapgen)
38 #define LOG_NG LOG_STREAM(info, log_mapgen)
39 #define DBG_NG LOG_STREAM(debug, log_mapgen)
40 
41 typedef std::vector<std::vector<int>> height_map;
43 
44 namespace {
45  /**
46  * Calculates the cost of building a road over terrain. For use in the
47  * a_star_search algorithm.
48  */
49  struct road_path_calculator : pathfind::cost_calculator
50  {
51  road_path_calculator(const terrain_map& terrain, const config& cfg, int seed)
52  : calls(0)
53  , map_(terrain)
54  , cfg_(cfg)
55  , windiness_(std::max<int>(1, cfg["road_windiness"].to_int())) // Find out how windey roads should be.
56  , seed_(seed)
57  , cache_()
58  {
59  }
60 
61  virtual double cost(const map_location& loc, const double so_far) const;
62 
63  mutable int calls;
64  private:
65  const terrain_map& map_;
66  const config& cfg_;
67  int windiness_;
68  int seed_;
69  mutable std::map<t_translation::terrain_code, double> cache_;
70  };
71 
72  double road_path_calculator::cost(const map_location& loc, const double /*so_far*/) const
73  {
74  ++calls;
75  if(loc.x < 0 || loc.y < 0 || loc.x >= map_.w || loc.y >= map_.h) {
76 
78  }
79 
80  // We multiply the cost by a random amount,
81  // depending upon how 'windy' the road should be.
82  // If windiness is 1, that will mean that the cost is always genuine,
83  // and so the road always takes the shortest path.
84  // If windiness is greater than 1, we sometimes over-report costs
85  // for some segments, to make the road wind a little.
86 
87  double windiness = 1.0;
88 
89  if(windiness_ > 1) {
90  // modified pseudo_random taken from builder.cpp
91  unsigned int a = (loc.x + 92872973) ^ 918273;
92  unsigned int b = (loc.y + 1672517) ^ 128123;
93  unsigned int c = a*b + a + b + seed_;
94  unsigned int random = c*c;
95  // this is just "big random number modulo windiness_"
96  // but avoid the "modulo by a low number (like 2)"
97  // because it can increase arithmetic patterns
98  int noise = random % (windiness_ * 137) / 137;
99  windiness += noise;
100  }
101 
102  const t_translation::terrain_code c = map_[loc.x][loc.y];
103  const std::map<t_translation::terrain_code, double>::const_iterator itor = cache_.find(c);
104  if(itor != cache_.end()) {
105  return itor->second*windiness;
106  }
107 
108  static std::string terrain;
110  double res = getNoPathValue();
111  if(auto child = cfg_.find_child("road_cost", "terrain", terrain)) {
112  res = child["cost"].to_double();
113  }
114 
115  cache_.emplace(c, res);
116  return windiness*res;
117  }
118 
119 
120  struct is_valid_terrain
121  {
122  is_valid_terrain(const t_translation::ter_map& map, const t_translation::ter_list& terrain_list);
123  bool operator()(int x, int y) const;
124  private:
126  const t_translation::ter_list& terrain_;
127  };
128 
130  : map_(map), terrain_(terrain_list)
131  {
132  }
133 
134  bool is_valid_terrain::operator()(int x, int y) const
135  {
136  if(x < 0 || x >= map_.w || y < 0 || y >= map_.h) {
137 
138  return false;
139  }
140 
141  return std::find(terrain_.begin(),terrain_.end(),map_[x][y]) != terrain_.end();
142  }
143 
144 
145  /* the configuration file should contain a number of [height] tags:
146  * [height]
147  * height=n
148  * terrain=x
149  * [/height]
150  * These should be in descending order of n.
151  * They are checked sequentially, and if height is greater than n for that tile,
152  * then the tile is set to terrain type x.
153  */
154  class terrain_height_mapper
155  {
156  public:
157  explicit terrain_height_mapper(const config& cfg);
158 
159  bool convert_terrain(const int height) const;
160  t_translation::terrain_code convert_to() const;
161 
162  private:
163  int terrain_height;
165  };
166 
167  terrain_height_mapper::terrain_height_mapper(const config& cfg) :
168  terrain_height(cfg["height"]),
170  {
171  const std::string& terrain = cfg["terrain"];
172  if(!terrain.empty()) {
173  to = t_translation::read_terrain_code(terrain);
174  }
175  }
176 
177  bool terrain_height_mapper::convert_terrain(const int height) const
178  {
179  return height >= terrain_height;
180  }
181 
182  t_translation::terrain_code terrain_height_mapper::convert_to() const
183  {
184  return to;
185  }
186 
187 
188  class terrain_converter
189  {
190  public:
191  explicit terrain_converter(const config& cfg);
192 
193  bool convert_terrain(const t_translation::terrain_code & terrain, const int height, const int temperature) const;
194  t_translation::terrain_code convert_to() const;
195 
196  private:
197  int min_temp, max_temp, min_height, max_height;
200  };
201 
202  terrain_converter::terrain_converter(const config& cfg)
203  : min_temp(cfg["min_temperature"].to_int(-100000))
204  , max_temp(cfg["max_temperature"].to_int(100000))
205  , min_height(cfg["min_height"].to_int(-100000))
206  , max_height(cfg["max_height"].to_int(100000))
207  , from(t_translation::read_list(cfg["from"].str()))
209  {
210  const std::string& to_str = cfg["to"];
211  if(!to_str.empty()) {
213  }
214  }
215 
216  bool terrain_converter::convert_terrain(const t_translation::terrain_code & terrain,
217  const int height, const int temperature) const
218  {
219  return std::find(from.begin(),from.end(),terrain) != from.end() && height >= min_height && height <= max_height && temperature >= min_temp && temperature <= max_temp && to != t_translation::NONE_TERRAIN;
220  }
221 
222  t_translation::terrain_code terrain_converter::convert_to() const
223  {
224  return to;
225  }
226 
227 } // end anon namespace
228 
229 
231  : rng_(seed_rng::next_seed())
232  , game_config_(game_config_manager::get()->game_config())
233 {
234 }
235 
237  : rng_(seed)
238  , game_config_(game_config_manager::get()->game_config())
239 {
240 }
241 
242 /**
243  * Generate a height-map.
244  *
245  * Basically we generate a lot of hills, each hill being centered at a certain
246  * point, with a certain radius - being a half sphere. Hills are combined
247  * additively to form a bumpy surface. The size of each hill varies randomly
248  * from 1-hill_size. We generate 'iterations' hills in total. The range of
249  * heights is normalized to 0-1000. 'island_size' controls whether or not the
250  * map should tend toward an island shape, and if so, how large the island
251  * should be. Hills with centers that are more than 'island_size' away from
252  * the center of the map will be inverted (i.e. be valleys). 'island_size' as
253  * 0 indicates no island.
254  */
255 height_map default_map_generator_job::generate_height_map(size_t width, size_t height, size_t iterations, size_t hill_size, size_t island_size, size_t island_off_center)
256 {
257  size_t center_x = width/2;
258  size_t center_y = height/2;
259 
260  LOG_NG << "off-centering...";
261 
262  if(island_off_center != 0) {
263  switch(rng_()%4) {
264  case 0:
265  center_x += island_off_center;
266  break;
267  case 1:
268  center_y += island_off_center;
269  break;
270  case 2:
271  if(center_x < island_off_center) {
272  center_x = 0;
273  } else {
274  center_x -= island_off_center;
275  }
276  break;
277  case 3:
278  if(center_y < island_off_center) {
279  center_y = 0;
280  } else {
281  center_y -= island_off_center;
282  }
283  break;
284  }
285  }
286  return generate_height_map(width, height, iterations, hill_size, island_size, center_x, center_y);
287 }
288 
289 height_map default_map_generator_job::generate_height_map(size_t width, size_t height, size_t iterations, size_t hill_size, size_t island_size, size_t center_x, size_t center_y)
290 {
291  height_map res(width, std::vector<int>(height,0));
292 
293  DBG_NG << iterations << " iterations";
294  for(std::size_t i = 0; i != iterations; ++i) {
295 
296  // (x1,y1) is the location of the hill,
297  // and 'radius' is the radius of the hill.
298  // We iterate over all points, (x2,y2).
299  // The formula for the amount the height is increased by is:
300  // radius - sqrt((x2-x1)^2 + (y2-y1)^2) with negative values ignored.
301  //
302  // Rather than iterate over every single point, we can reduce the points
303  // to a rectangle that contains all the positive values for this formula --
304  // the rectangle is given by min_x,max_x,min_y,max_y.
305 
306  // Is this a negative hill? (i.e. a valley)
307  bool is_valley = false;
308 
309  int x1 = island_size > 0 ? center_x - island_size + (rng_()%(island_size*2)) : static_cast<int>(rng_()%width);
310  int y1 = island_size > 0 ? center_y - island_size + (rng_()%(island_size*2)) : static_cast<int>(rng_()%height);
311 
312  // We have to check whether this is actually a valley
313  if(island_size != 0) {
314  const std::size_t diffx = std::abs(x1 - static_cast<int>(center_x));
315  const std::size_t diffy = std::abs(y1 - static_cast<int>(center_y));
316  const std::size_t dist = std::size_t(std::sqrt(static_cast<double>(diffx*diffx + diffy*diffy)));
317  is_valley = dist > island_size;
318  }
319 
320  const int radius = rng_()%hill_size + 1;
321  DBG_NG << "placing hill at " << x1 << "," << y1 << " radius=" << radius << " is_valley=" << is_valley;
322 
323  const int min_x = x1 - radius > 0 ? x1 - radius : 0;
324  const int max_x = x1 + radius < static_cast<long>(res.size()) ? x1 + radius : res.size();
325  const int min_y = y1 - radius > 0 ? y1 - radius : 0;
326  const int max_y = y1 + radius < static_cast<long>(res.front().size()) ? y1 + radius : res.front().size();
327 
328  for(int x2 = min_x; x2 < max_x; ++x2) {
329  for(int y2 = min_y; y2 < max_y; ++y2) {
330  const int xdiff = (x2-x1);
331  const int ydiff = (y2-y1);
332 
333  const int hill_height = radius - static_cast<int>(std::sqrt(static_cast<double>(xdiff*xdiff + ydiff*ydiff)));
334 
335  if(hill_height > 0) {
336  if(is_valley) {
337  if(hill_height > res[x2][y2]) {
338  res[x2][y2] = 0;
339  } else {
340  res[x2][y2] -= hill_height;
341  }
342  } else {
343  res[x2][y2] += hill_height;
344  }
345  }
346  }
347  }
348  }
349 
350  // Find the highest and lowest points on the map for normalization:
351  int highest = 0, lowest = 100000, x;
352  for(x = 0; std::size_t(x) != res.size(); ++x) {
353  for(int y = 0; std::size_t(y) != res[x].size(); ++y) {
354  if(res[x][y] > highest) {
355  highest = res[x][y];
356  }
357 
358  if(res[x][y] < lowest) {
359  lowest = res[x][y];
360  }
361  }
362  }
363 
364  LOG_NG << "generate_height_map"
365  << " lowest=" << lowest
366  << " highest =" << highest;
367  // Normalize the heights to the range 0-1000:
368  highest -= lowest;
369  for(x = 0; std::size_t(x) != res.size(); ++x) {
370  for(int y = 0; std::size_t(y) != res[x].size(); ++y) {
371  res[x][y] -= lowest;
372  res[x][y] *= 1000;
373  if(highest != 0) {
374  res[x][y] /= highest;
375  }
376  }
377  }
378 
379  return res;
380 }
381 
382 /**
383  * Generate a lake.
384  *
385  * It will create water at (x,y), and then have 'lake_fall_off' % chance to
386  * make another water tile in each of the directions n,s,e,w. In each of the
387  * directions it does make another water tile, it will have 'lake_fall_off'/2 %
388  * chance to make another water tile in each of the directions. This will
389  * continue recursively.
390  */
391 bool default_map_generator_job::generate_lake(terrain_map& terrain, int x, int y, int lake_fall_off, std::set<map_location>& locs_touched)
392 {
393  if(x < 0 || y < 0 || x >= terrain.w || y >= terrain.h || lake_fall_off < 0) {
394  return false;
395  }
396  //we checked for this eariler.
397  unsigned int ulake_fall_off = lake_fall_off;
398  terrain[x][y] = t_translation::SHALLOW_WATER;
399  locs_touched.insert(map_location(x,y));
400 
401  if((rng_()%100) < ulake_fall_off) {
402  generate_lake(terrain,x+1,y,lake_fall_off/2,locs_touched);
403  }
404 
405  if((rng_()%100) < ulake_fall_off) {
406  generate_lake(terrain,x-1,y,lake_fall_off/2,locs_touched);
407  }
408 
409  if((rng_()%100) < ulake_fall_off) {
410  generate_lake(terrain,x,y+1,lake_fall_off/2,locs_touched);
411  }
412 
413  if((rng_()%100) < ulake_fall_off) {
414  generate_lake(terrain,x,y-1,lake_fall_off/2,locs_touched);
415  }
416 
417  return true;
418 }
419 
420 /**
421  * River generation.
422  *
423  * Rivers have a source, and then keep on flowing until they meet another body
424  * of water, which they flow into, or until they reach the edge of the map.
425  * Rivers will always flow downhill, except that they can flow a maximum of
426  * 'river_uphill' uphill. This is to represent the water eroding the higher
427  * ground lower.
428  *
429  * Every possible path for a river will be attempted, in random order, and the
430  * first river path that can be found that makes the river flow into another
431  * body of water or off the map will be used.
432  *
433  * If no path can be found, then the river's generation will be aborted, and
434  * false will be returned. true is returned if the river is generated
435  * successfully.
436  */
437 
439  terrain_map& terrain, int x, int y, std::vector<map_location>& river,
440  std::set<map_location>& seen_locations, int river_uphill)
441 {
442  const bool on_map = x >= 0 && y >= 0 &&
443  x < static_cast<long>(heights.size()) &&
444  y < static_cast<long>(heights.back().size());
445 
446  if(on_map && !river.empty() && heights[x][y] >
447  heights[river.back().x][river.back().y] + river_uphill) {
448 
449  return false;
450  }
451 
452  // If we're at the end of the river
453  if(!on_map || terrain[x][y] == t_translation::SHALLOW_WATER ||
454  terrain[x][y] == t_translation::DEEP_WATER) {
455 
456  LOG_NG << "generating river...";
457 
458  // Generate the river
459  for(auto i : river) {
460  terrain[i.x][i.y] = t_translation::SHALLOW_WATER;
461  }
462 
463  LOG_NG << "done generating river";
464 
465  return true;
466  }
467 
468  map_location current_loc(x,y);
469  auto adj = get_adjacent_tiles(current_loc);
470  std::shuffle(std::begin(adj), std::end(adj), rng_);
471 
472  // Mark that we have attempted from this map_location
473  seen_locations.insert(current_loc);
474  river.push_back(current_loc);
475  for(const map_location& loc : adj) {
476  if(seen_locations.count(loc) == 0) {
477  const bool res = generate_river_internal(heights,terrain,loc.x,loc.y,river,seen_locations,river_uphill);
478  if(res) {
479  return true;
480  }
481 
482  }
483  }
484 
485  river.pop_back();
486 
487  return false;
488 }
489 
490 std::vector<map_location> default_map_generator_job::generate_river(const height_map& heights, terrain_map& terrain, int x, int y, int river_uphill)
491 {
492  std::vector<map_location> river;
493  std::set<map_location> seen_locations;
494  const bool res = generate_river_internal(heights,terrain,x,y,river,seen_locations,river_uphill);
495  if(!res) {
496  river.clear();
497  }
498 
499  return river;
500 }
501 
502 /**
503  * Returns a random tile at one of the borders of a map that is of the given
504  * dimensions.
505  */
506 map_location default_map_generator_job::random_point_at_side(std::size_t width, std::size_t height)
507 {
508  const int side = rng_()%4;
509  if(side < 2) {
510  const int x = rng_()%width;
511  const int y = side == 0 ? 0 : height-1;
512  return map_location(x,y);
513  } else {
514  const int y = rng_()%height;
515  const int x = side == 2 ? 0 : width-1;
516  return map_location(x,y);
517  }
518 }
519 
520 /** Function which, given the map will output it in a valid format. */
521 static std::string output_map(const terrain_map& terrain,
523 {
524  // Remember that we only want the middle 1/9th of the map.
525  // All other segments of the map are there only to give
526  // the important middle part some context.
527  // We also have a border so also adjust for that.
528  const std::size_t begin_x = terrain.w / 3 - gamemap::default_border ;
529  const std::size_t end_x = terrain.w * 2 / 3 + gamemap::default_border;
530  const std::size_t begin_y = terrain.h / 3 - gamemap::default_border;
531  const std::size_t end_y = terrain.h * 2 / 3 + gamemap::default_border;
532 
533  terrain_map map(end_x - begin_x, end_y - begin_y);
534  for(std::size_t y = begin_y; y != end_y; ++y) {
535  for(std::size_t x = begin_x; x != end_x; ++x) {
536  map[x - begin_x][y - begin_y] = terrain[x][y];
537  }
538  }
539 
540  // Since the map has been resized,
541  // the starting locations also need to be fixed
542  for (auto it = starting_positions.left.begin(); it != starting_positions.left.end(); ++it) {
543  starting_positions.left.modify_data(it, [=](t_translation::coordinate& pos) { pos.x -= begin_x; pos.y -= begin_y; });
544  }
546 }
547 
548 static int rank_castle_location(int x, int y, const is_valid_terrain& valid_terrain, int min_x, int max_x, int min_y, int max_y, std::size_t min_distance, const std::vector<map_location>& other_castles, int highest_ranking)
549 {
550  const map_location loc(x,y);
551 
552  std::size_t avg_distance = 0, lowest_distance = 1000;
553 
554  for(std::vector<map_location>::const_iterator c = other_castles.begin(); c != other_castles.end(); ++c) {
555  const std::size_t distance = distance_between(loc,*c);
556  if(distance < 6) {
557  return 0;
558  }
559 
560  if(distance < lowest_distance) {
561  lowest_distance = distance;
562  }
563 
564  if(distance < min_distance) {
565  return -1;
566  }
567 
568  avg_distance += distance;
569  }
570 
571  if(!other_castles.empty()) {
572  avg_distance /= other_castles.size();
573  }
574 
575  for(int i = x-1; i <= x+1; ++i) {
576  for(int j = y-1; j <= y+1; ++j) {
577  if(!valid_terrain(i,j)) {
578  return 0;
579  }
580  }
581  }
582 
583  const int x_from_border = std::min<int>(x - min_x,max_x - x);
584  const int y_from_border = std::min<int>(y - min_y,max_y - y);
585 
586  const int border_ranking = min_distance - std::min<int>(x_from_border,y_from_border) + min_distance - x_from_border - y_from_border;
587 
588  int current_ranking = border_ranking*2 + avg_distance*10 + lowest_distance*10;
589  static const int num_nearby_locations = 11*11;
590 
591  const int max_possible_ranking = current_ranking + num_nearby_locations;
592 
593  if(max_possible_ranking < highest_ranking) {
594  return current_ranking;
595  }
596 
597  int surrounding_ranking = 0;
598 
599  for(int xpos = x-5; xpos <= x+5; ++xpos) {
600  for(int ypos = y-5; ypos <= y+5; ++ypos) {
601  if(valid_terrain(xpos,ypos)) {
602  ++surrounding_ranking;
603  }
604  }
605  }
606 
607  return surrounding_ranking + current_ranking;
608 }
609 
610 typedef std::map<t_translation::terrain_code, t_translation::ter_list> tcode_list_cache;
611 
613  const std::size_t x, const std::size_t y, const std::size_t radius, const config& cfg,
614  tcode_list_cache &adj_liked_cache)
615 {
616  const map_location loc(x,y);
617  std::set<map_location> locs;
618  get_tiles_radius(loc,radius,locs);
619  map_location best_loc;
620  int best_rating = 0;
621  for(auto i : locs) {
622  if(i.x < 0 || i.y < 0 || i.x >= map.w ||
623  i.y >= map.h) {
624 
625  continue;
626  }
627 
628  const t_translation::terrain_code t = map[i.x][i.y];
629  const std::string str = t_translation::write_terrain_code(t);
630  if(auto child = cfg.find_child("village", "terrain", str)) {
631  tcode_list_cache::iterator l = adj_liked_cache.find(t);
632  t_translation::ter_list *adjacent_liked;
633  if(l != adj_liked_cache.end()) {
634  adjacent_liked = &(l->second);
635  } else {
636  adj_liked_cache[t] = t_translation::read_list(child["adjacent_liked"].str());
637  adjacent_liked = &(adj_liked_cache[t]);
638  }
639 
640  int rating = child["rating"];
641  for(const map_location& adj : get_adjacent_tiles({i.x, i.y})) {
642  if(adj.x < 0 || adj.y < 0 || adj.x >= map.w || adj.y >= map.h) {
643  continue;
644  }
645 
646  const t_translation::terrain_code t2 = map[adj.x][adj.y];
647  rating += std::count(adjacent_liked->begin(),adjacent_liked->end(),t2);
648  }
649 
650  if(rating > best_rating) {
651  best_loc = map_location(i.x,i.y);
652  best_rating = rating;
653  }
654  }
655  }
656 
657  return best_loc;
658 }
659 
660 // "flood fill" a tile name to adjacent tiles of certain terrain
661 static void flood_name(const map_location& start, const std::string& name, std::map<map_location,std::string>& tile_names,
662  const t_translation::ter_match& tile_types, const terrain_map& terrain,
663  unsigned width, unsigned height,
664  std::size_t label_count, std::map<map_location,std::string>* labels, const std::string& full_name) {
665 
666  //if adjacent tiles are tiles and unnamed, name them
667  for(const map_location& adj : get_adjacent_tiles(start)) {
668  //we do not care for tiles outside the middle part
669  //cast to unsigned to skip x < 0 || y < 0 as well.
670  if(static_cast<unsigned>(adj.x) >= width / 3 || static_cast<unsigned>(adj.y) >= height / 3) {
671  continue;
672  }
673 
674  const t_translation::terrain_code terr = terrain[adj.x + (width / 3)][adj.y + (height / 3)];
675  if((t_translation::terrain_matches(terr, tile_types)) && (tile_names.find(adj) == tile_names.end())) {
676  tile_names.emplace(adj, name);
677  //labeling decision: this is result of trial and error on what looks best in game
678  if(label_count % 6 == 0) { //ensure that labels do not occur more often than every 6 recursions
679  labels->emplace(adj, full_name);
680  label_count++; //ensure that no adjacent tiles get labeled
681  }
682  flood_name(adj, name, tile_names, tile_types, terrain, width, height, label_count++, labels, full_name);
683  }
684  }
685 }
686 
687 std::string default_map_generator_job::default_generate_map(generator_data data, std::map<map_location,std::string>* labels, const config& cfg)
688 {
689  log_scope("map generation");
690 
691  LOG_NG << "default_generate_map parameters"
692  << " width=" << data.width
693  << " height=" << data.height
694  << " nplayers=" << data.nplayers
695  << " nvillages=" << data.nvillages
696  << " iterations=" << data.iterations
697  << " hill_size=" << data.hill_size
698  << " castle_size=" << data.castle_size
699  << " island_size=" << data.island_size
700  << " island_off_center=" << data.island_off_center
701  << " max_lakes=" << data.max_lakes
702  << " link_castles=" << data.link_castles
703  << " show_labels=" << data.show_labels;
704 
705  // Odd widths are nasty
706  VALIDATE(is_even(data.width), _("Random maps with an odd width aren't supported."));
707 
708  // Try to find configuration for castles
709  auto castle_config = cfg.optional_child("castle");
710 
711  int ticks = SDL_GetTicks();
712 
713  // We want to generate a map that is 9 times bigger than the actual size desired.
714  // Only the middle part of the map will be used, but the rest is so that the map we
715  // end up using can have a context (e.g. rivers flowing from out of the map into the map,
716  // same for roads, etc.)
717  data.width *= 3;
718  data.height *= 3;
719 
720  config naming;
721 
722  if(cfg.has_child("naming")) {
723  naming = game_config_.mandatory_child("naming");
724  naming.append_attributes(cfg.mandatory_child("naming"));
725  }
726 
727  // If the [naming] child is empty, we cannot provide good names.
728  std::map<map_location,std::string>* misc_labels = naming.empty() ? nullptr : labels;
729 
730  std::shared_ptr<name_generator>
731  base_name_generator, river_name_generator, lake_name_generator,
732  road_name_generator, bridge_name_generator, mountain_name_generator,
733  forest_name_generator, swamp_name_generator;
734 
735  if(misc_labels != nullptr) {
736  name_generator_factory base_generator_factory{ naming, {"male", "base", "bridge", "road", "river", "forest", "lake", "mountain", "swamp"} };
737 
738  naming.get_old_attribute("base_names", "male_names", "naming");
739  //Due to the attribute detection feature of the factory we also support male_name_generator= but keep it undocumented.
740 
741  base_name_generator = base_generator_factory.get_name_generator( (naming.has_attribute("base_names") || naming.has_attribute("base_name_generator")) ? "base" : "male" );
742  river_name_generator = base_generator_factory.get_name_generator("river");
743  lake_name_generator = base_generator_factory.get_name_generator("lake");
744  road_name_generator = base_generator_factory.get_name_generator("road");
745  bridge_name_generator = base_generator_factory.get_name_generator("bridge");
746  mountain_name_generator = base_generator_factory.get_name_generator("mountain");
747  forest_name_generator = base_generator_factory.get_name_generator("forest");
748  swamp_name_generator = base_generator_factory.get_name_generator("swamp");
749  }
750 
751  // Generate the height of everything.
752  const height_map heights = generate_height_map(data.width, data.height, data.iterations, data.hill_size, data.island_size, data.island_off_center);
753 
754  LOG_NG << "Done generating height map. " << (SDL_GetTicks() - ticks) << " ticks elapsed";
755  ticks = SDL_GetTicks();
756 
757  // Find out what the 'flatland' on this map is, i.e. grassland.
758  std::string flatland = cfg["default_flatland"];
759  if(flatland.empty()) {
761  }
762 
764 
765  std::vector<terrain_height_mapper> height_conversion;
766  for(const config& h : cfg.child_range("height")) {
767  height_conversion.emplace_back(h);
768  }
769 
770  terrain_map terrain(data.width, data.height, grassland);
771  for(std::size_t x = 0; x != heights.size(); ++x) {
772  for(std::size_t y = 0; y != heights[x].size(); ++y) {
773  for(auto i : height_conversion) {
774  if(i.convert_terrain(heights[x][y])) {
775  terrain[x][y] = i.convert_to();
776  break;
777  }
778  }
779  }
780  }
781 
783  LOG_NG << output_map(terrain, starting_positions);
784  LOG_NG << "Placed landforms. " << (SDL_GetTicks() - ticks) << " ticks elapsed";
785  ticks = SDL_GetTicks();
786 
787  /* Now that we have our basic set of flatland/hills/mountains/water,
788  * we can place lakes and rivers on the map.
789  * All rivers are sourced at a lake.
790  * Lakes must be in high land - at least 'min_lake_height'.
791  * (Note that terrain below a certain altitude may be made into bodies of water
792  * in the code above - i.e. 'sea', but these are not considered 'lakes',
793  * because they are not sources of rivers).
794  *
795  * We attempt to place 'max_lakes' lakes.
796  * Each lake will be placed at a random location, if that random location meets theminimum
797  * terrain requirements for a lake. We will also attempt to source a river from each lake.
798  */
799  std::set<map_location> lake_locs;
800 
801  std::map<map_location, std::string> river_names, lake_names, road_names, bridge_names, mountain_names, forest_names, swamp_names;
802 
803  const std::size_t nlakes = data.max_lakes > 0 ? (rng_()%data.max_lakes) : 0;
804  for(std::size_t lake = 0; lake != nlakes; ++lake) {
805  for(int tries = 0; tries != 100; ++tries) {
806  const int x = rng_()%data.width;
807  const int y = rng_()%data.height;
808 
809  if(heights[x][y] <= cfg["min_lake_height"].to_int()) {
810  continue;
811  }
812 
813  std::vector<map_location> river = generate_river(heights, terrain, x, y, cfg["river_frequency"]);
814 
815  if(!river.empty() && misc_labels != nullptr) {
816  const std::string base_name = base_name_generator->generate();
817  const std::string& name = river_name_generator->generate({{"base", base_name}});
818  LOG_NG << "Named river '" << name << "'";
819 
820  std::size_t name_frequency = 20;
821  for(std::vector<map_location>::const_iterator r = river.begin(); r != river.end(); ++r) {
822  const map_location loc(r->x-data.width/3,r->y-data.height/3);
823 
824  if(((r - river.begin())%name_frequency) == name_frequency/2) {
825  misc_labels->emplace(loc, name);
826  }
827 
828  river_names.emplace(loc, base_name);
829  }
830  }
831 
832  LOG_NG << "Generating lake...";
833 
834  std::set<map_location> locs;
835  if(generate_lake(terrain, x, y, cfg["lake_size"], locs) && misc_labels != nullptr) {
836  bool touches_other_lake = false;
837 
838  std::string base_name = base_name_generator->generate();
839  const std::string& name = lake_name_generator->generate({{"base", base_name}});
840 
841  // Only generate a name if the lake hasn't touched any other lakes,
842  // so that we don't end up with one big lake with multiple names.
843  for(auto i : locs) {
844  if(lake_locs.count(i) != 0) {
845  touches_other_lake = true;
846 
847  // Reassign the name of this lake to be the same as the other lake
848  const map_location loc(i.x-data.width/3,i.y-data.height/3);
849  const std::map<map_location,std::string>::const_iterator other_name = lake_names.find(loc);
850  if(other_name != lake_names.end()) {
851  base_name = other_name->second;
852  }
853  }
854 
855  lake_locs.insert(i);
856  }
857 
858  if(!touches_other_lake) {
859  const map_location loc(x-data.width/3,y-data.height/3);
860  misc_labels->erase(loc);
861  misc_labels->emplace(loc, name);
862  }
863 
864  for(auto i : locs) {
865  const map_location loc(i.x-data.width/3,i.y-data.height/3);
866  lake_names.emplace(loc, base_name);
867  }
868  }
869 
870  break;
871  }
872  }
873 
874  LOG_NG << "Generated rivers. " << (SDL_GetTicks() - ticks) << " ticks elapsed";
875  ticks = SDL_GetTicks();
876 
877  const std::size_t default_dimensions = 40*40*9;
878 
879  /*
880  * Convert grassland terrain to other types of flat terrain.
881  *
882  * We generate a 'temperature map' which uses the height generation
883  * algorithm to generate the temperature levels all over the map. Then we
884  * can use a combination of height and terrain to divide terrain up into
885  * more interesting types than the default.
886  */
887  const height_map temperature_map = generate_height_map(data.width,data.height,
888  cfg["temperature_iterations"].to_int() * data.width * data.height / default_dimensions,
889  cfg["temperature_size"], 0, 0);
890 
891  LOG_NG << "Generated temperature map. " << (SDL_GetTicks() - ticks) << " ticks elapsed";
892  ticks = SDL_GetTicks();
893 
894  std::vector<terrain_converter> converters;
895  for(const config& cv : cfg.child_range("convert")) {
896  converters.emplace_back(cv);
897  }
898 
899  LOG_NG << "Created terrain converters. " << (SDL_GetTicks() - ticks) << " ticks elapsed";
900  ticks = SDL_GetTicks();
901 
902  // Iterate over every flatland tile, and determine what type of flatland it is, based on our [convert] tags.
903  for(int x = 0; x != data.width; ++x) {
904  for(int y = 0; y != data.height; ++y) {
905  for(auto i : converters) {
906  if(i.convert_terrain(terrain[x][y],heights[x][y],temperature_map[x][y])) {
907  terrain[x][y] = i.convert_to();
908  break;
909  }
910  }
911  }
912  }
913 
914  LOG_NG << "Placing castles...";
915 
916  /*
917  * Attempt to place castles at random.
918  *
919  * After they are placed, we run a sanity check to make sure no two castles
920  * are closer than 'min_distance' hexes apart, and that they appear on a
921  * terrain listed in 'valid_terrain'.
922  *
923  * If not, we attempt to place them again.
924  */
925  std::vector<map_location> castles;
926  std::set<map_location> failed_locs;
927 
928  if(castle_config) {
929  /*
930  * Castle configuration tag contains a 'valid_terrain' attribute which is a
931  * list of terrains that the castle may appear on.
932  */
933  const t_translation::ter_list list = t_translation::read_list(castle_config["valid_terrain"].str());
934 
935  const is_valid_terrain terrain_tester(terrain, list);
936 
937  for(int player = 0; player != data.nplayers; ++player) {
938  LOG_NG << "placing castle for " << player;
939  lg::scope_logger inner_scope_logging_object__(lg::general(), "placing castle");
940  const int min_x = data.width/3 + 3;
941  const int min_y = data.height/3 + 3;
942  const int max_x = (data.width/3)*2 - 4;
943  const int max_y = (data.height/3)*2 - 4;
944  int min_distance = castle_config["min_distance"];
945 
946  map_location best_loc;
947  int best_ranking = 0;
948  for(int x = min_x; x != max_x; ++x) {
949  for(int y = min_y; y != max_y; ++y) {
950  const map_location loc(x,y);
951  if(failed_locs.count(loc)) {
952  continue;
953  }
954 
955  const int ranking = rank_castle_location(x, y, terrain_tester, min_x, max_x, min_y, max_y, min_distance, castles, best_ranking);
956  if(ranking <= 0) {
957  failed_locs.insert(loc);
958  }
959 
960  if(ranking > best_ranking) {
961  best_ranking = ranking;
962  best_loc = loc;
963  }
964  }
965  }
966 
967  if(best_ranking == 0) {
968  ERR_NG << "No castle location found, for " << data.nplayers << " players aborting. ";
969  const std::string error = _("No valid castle location found. Too many or too few mountain hexes? (please check the 'max hill size' parameter)");
970  throw mapgen_exception(error);
971  }
972 
973  assert(std::find(castles.begin(), castles.end(), best_loc) == castles.end());
974  castles.push_back(best_loc);
975 
976  // Make sure the location can't get a second castle.
977  failed_locs.insert(best_loc);
978  }
979 
980  LOG_NG << "Placed castles. " << (SDL_GetTicks() - ticks) << " ticks elapsed";
981  }
982  LOG_NG << "Placing roads...";
983  ticks = SDL_GetTicks();
984 
985  // Place roads.
986  // We select two tiles at random locations on the borders of the map
987  // and try to build roads between them.
988  int nroads = cfg["roads"];
989  if(data.link_castles) {
990  nroads += castles.size()*castles.size();
991  }
992 
993  std::set<map_location> bridges;
994 
995  road_path_calculator calc(terrain, cfg, rng_());
996  for(int road = 0; road != nroads; ++road) {
997  lg::scope_logger another_inner_scope_logging_object__(lg::general(), "creating road");
998 
999  /*
1000  * We want the locations to be on the portion of the map we're actually
1001  * going to use, since roads on other parts of the map won't have any
1002  * influence, and doing it like this will be quicker.
1003  */
1004  map_location src = random_point_at_side(data.width/3 + 2,data.height/3 + 2);
1005  map_location dst = random_point_at_side(data.width/3 + 2,data.height/3 + 2);
1006 
1007  src.x += data.width/3 - 1;
1008  src.y += data.height/3 - 1;
1009  dst.x += data.width/3 - 1;
1010  dst.y += data.height/3 - 1;
1011 
1012  if(data.link_castles && road < static_cast<int>(castles.size() * castles.size())) {
1013  const std::size_t src_castle = road/castles.size();
1014  const std::size_t dst_castle = road%castles.size();
1015  if(src_castle >= dst_castle) {
1016  continue;
1017  }
1018 
1019  src = castles[src_castle];
1020  dst = castles[dst_castle];
1021  } else if(src.x == dst.x || src.y == dst.y) {
1022  // If the road isn't very interesting (on the same border), don't draw it.
1023  continue;
1024  }
1025 
1026  if(calc.cost(src, 0.0) >= 1000.0 || calc.cost(dst, 0.0) >= 1000.0) {
1027  continue;
1028  }
1029 
1030  // Search a path out for the road
1031  pathfind::plain_route rt = pathfind::a_star_search(src, dst, 10000.0, calc, data.width, data.height);
1032 
1033  const std::string& road_base_name = misc_labels != nullptr
1034  ? base_name_generator->generate()
1035  : "";
1036  const std::string& road_name = misc_labels != nullptr
1037  ? road_name_generator->generate({{"base", road_base_name}})
1038  : "";
1039  const int name_frequency = 20;
1040  int name_count = 0;
1041 
1042  bool on_bridge = false;
1043 
1044  // Draw the road.
1045  // If the search failed, rt.steps will simply be empty.
1046  for(std::vector<map_location>::const_iterator step = rt.steps.begin();
1047  step != rt.steps.end(); ++step) {
1048 
1049  const int x = step->x;
1050  const int y = step->y;
1051 
1052  if(x < 0 || y < 0 || x >= static_cast<long>(data.width) || y >= static_cast<long>(data.height)) {
1053  continue;
1054  }
1055 
1056  // Find the configuration which tells us what to convert this tile to, to make it into a road.
1057  auto child = cfg.find_child("road_cost", "terrain", t_translation::write_terrain_code(terrain[x][y]));
1058  if(!child || child->empty()){
1059  continue;
1060  }
1061 
1062  /* Convert to bridge means that we want to convert depending on the direction of the road.
1063  * Typically it will be in a format like convert_to_bridge = \,|,/
1064  * '|' will be used if the road is going north-south
1065  * '/' will be used if the road is going south west-north east
1066  * '\' will be used if the road is going south east-north west
1067  * The terrain will be left unchanged otherwise (if there is no clear direction).
1068  */
1069  const std::string& convert_to_bridge = child["convert_to_bridge"];
1070  if(!convert_to_bridge.empty()) {
1071  if(step == rt.steps.begin() || step+1 == rt.steps.end()) {
1072  continue;
1073  }
1074 
1075  const map_location& last = *(step-1);
1076  const map_location& next = *(step+1);
1077 
1078  const auto adj = get_adjacent_tiles(*step);
1079  int direction = -1;
1080 
1081  // If we are going north-south
1082  if((last == adj[0] && next == adj[3]) || (last == adj[3] && next == adj[0])) {
1083  direction = 0;
1084  }
1085 
1086  // If we are going south west-north east
1087  else if((last == adj[1] && next == adj[4]) || (last == adj[4] && next == adj[1])) {
1088  direction = 1;
1089  }
1090 
1091  // If we are going south east-north west
1092  else if((last == adj[2] && next == adj[5]) || (last == adj[5] && next == adj[2])) {
1093  direction = 2;
1094  }
1095 
1096  if(misc_labels != nullptr && !on_bridge) {
1097  on_bridge = true;
1098  std::string bridge_base_name = base_name_generator->generate();
1099  const std::string& name = bridge_name_generator->generate({{"base", bridge_base_name}});
1100  const map_location loc(x - data.width / 3, y-data.height/3);
1101  misc_labels->emplace(loc, name);
1102  bridge_names.emplace(loc, bridge_base_name); //add to use for village naming
1103  bridges.insert(loc);
1104  }
1105 
1106  if(direction != -1) {
1107  const std::vector<std::string> items = utils::split(convert_to_bridge);
1108  if(std::size_t(direction) < items.size() && !items[direction].empty()) {
1109  terrain[x][y] = t_translation::read_terrain_code(items[direction]);
1110  }
1111 
1112  continue;
1113  }
1114  } else {
1115  on_bridge = false;
1116  }
1117 
1118  // Just a plain terrain substitution for a road
1119  const std::string& convert_to = child["convert_to"];
1120  if(!convert_to.empty()) {
1122  if(misc_labels != nullptr && terrain[x][y] != letter && name_count++ == name_frequency && !on_bridge) {
1123  misc_labels->emplace(map_location(x - data.width / 3, y - data.height / 3), road_name);
1124  name_count = 0;
1125  }
1126 
1127  terrain[x][y] = letter;
1128  if(misc_labels != nullptr) {
1129  const map_location loc(x - data.width / 3, y - data.height / 3); //add to use for village naming
1130  if(!road_base_name.empty())
1131  road_names.emplace(loc, road_base_name);
1132  }
1133  }
1134  }
1135  }
1136 
1137  // Now that road drawing is done, we can plonk down the castles.
1138  for(std::vector<map_location>::const_iterator c = castles.begin(); c != castles.end(); ++c) {
1139  if(!c->valid()) {
1140  continue;
1141  }
1142 
1143  const int x = c->x;
1144  const int y = c->y;
1145  const int player = c - castles.begin() + 1;
1146  const t_translation::coordinate coord(x, y);
1147  starting_positions.insert(t_translation::starting_positions::value_type(std::to_string(player), coord));
1148  terrain[x][y] = t_translation::HUMAN_KEEP;
1149 
1150  const int castle_array[13][2] {
1151  {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {0, 1}, {-1, 1},
1152  {-2, 1}, {-2, 0}, {-2, -1}, {-1, -2}, {0, -2}, {1, -2}
1153  };
1154 
1155  for(int i = 0; i < data.castle_size - 1; i++) {
1156  terrain[x+ castle_array[i][0]][y+ castle_array[i][1]] = t_translation::HUMAN_CASTLE;
1157  }
1158 
1159  // Remove all labels under the castle tiles
1160  if(labels != nullptr) {
1161  labels->erase(map_location(x-data.width/3,y-data.height/3));
1162  for(int i = 0; i < data.castle_size - 1; i++) {
1163  labels->erase(map_location(x+ castle_array[i][0]-data.width/3, y+ castle_array[i][1]-data.height/3));
1164  }
1165  }
1166  }
1167 
1168  LOG_NG << "Placed roads. " << (SDL_GetTicks() - ticks) << " ticks elapsed";
1169  ticks = SDL_GetTicks();
1170 
1171  /* Random naming for landforms: mountains, forests, swamps, hills
1172  * we name these now that everything else is placed (as e.g., placing
1173  * roads could split a forest)
1174  */
1175  if(misc_labels != nullptr) {
1176  std::set<std::string> used_names;
1177  for(int x = data.width / 3; x < (data.width / 3)*2; x++) {
1178  for(int y = data.height / 3; y < (data.height / 3) * 2;y++) {
1179  //check the terrain of the tile
1180  const map_location loc(x - data.width / 3, y - data.height / 3);
1181  const t_translation::terrain_code terr = terrain[x][y];
1182  std::string name = "", base_name;
1183 
1185  //name every 15th mountain
1186  if((rng_() % 15) == 0) {
1187  for(std::size_t ntry = 0; ntry != 30 && (ntry == 0 || used_names.count(name) > 0); ++ntry) {
1188  base_name = base_name_generator->generate();
1189  name = mountain_name_generator->generate({{"base", base_name}});
1190  }
1191  misc_labels->emplace(loc, name);
1192  mountain_names.emplace(loc, base_name);
1193  }
1195  // If the forest tile is not named yet, name it
1196  const std::map<map_location, std::string>::const_iterator forest_name = forest_names.find(loc);
1197  if(forest_name == forest_names.end()) {
1198  for(std::size_t ntry = 0; ntry != 30 && (ntry == 0 || used_names.count(name) > 0); ++ntry) {
1199  base_name = base_name_generator->generate();
1200  name = forest_name_generator->generate({{"base", base_name}});
1201  }
1202  forest_names.emplace(loc, base_name);
1203  // name all connected forest tiles accordingly
1204  flood_name(loc, base_name, forest_names, t_translation::ALL_FORESTS, terrain, data.width, data.height, 0, misc_labels, name);
1205  }
1207  // If the swamp tile is not named yet, name it
1208  const std::map<map_location, std::string>::const_iterator swamp_name = swamp_names.find(loc);
1209  if(swamp_name == swamp_names.end()) {
1210  for(std::size_t ntry = 0; ntry != 30 && (ntry == 0 || used_names.count(name) > 0); ++ntry) {
1211  base_name = base_name_generator->generate();
1212  name = swamp_name_generator->generate({{"base", base_name}});
1213  }
1214  swamp_names.emplace(loc, base_name);
1215  // name all connected swamp tiles accordingly
1216  flood_name(loc, base_name, swamp_names, t_translation::ALL_SWAMPS, terrain, data.width, data.height, 0, misc_labels, name);
1217  }
1218  }
1219  if(!name.empty()) {
1220  used_names.insert(name);
1221  }
1222  }
1223  }
1224  }
1225 
1226  LOG_NG << "Named landforms. " << (SDL_GetTicks() - ticks) << " ticks elapsed";
1227  LOG_NG << "Placing villages...";
1228  ticks = SDL_GetTicks();
1229 
1230  /*
1231  * Place villages in a 'grid', to make placing fair, but with villages
1232  * displaced from their position according to terrain and randomness, to
1233  * add some variety.
1234  */
1235  std::set<map_location> villages;
1236 
1237  if(data.nvillages > 0) {
1238 
1239  // First we work out the size of the x and y distance between villages
1240  const std::size_t tiles_per_village = ((data.width*data.height)/9)/data.nvillages;
1241  std::size_t village_x = 1, village_y = 1;
1242 
1243  // Alternate between incrementing the x and y value.
1244  // When they are high enough to equal or exceed the tiles_per_village,
1245  // then we have them to the value we want them at.
1246  while(village_x*village_y < tiles_per_village) {
1247  if(village_x < village_y) {
1248  ++village_x;
1249  } else {
1250  ++village_y;
1251  }
1252  }
1253 
1254  std::set<std::string> used_names;
1255  tcode_list_cache adj_liked_cache;
1256 
1257  config village_naming = game_config_.mandatory_child("village_naming");
1258 
1259  if(cfg.has_child("village_naming")) {
1260  village_naming.append_attributes(cfg.mandatory_child("village_naming"));
1261  }
1262 
1263  // If the [village_naming] child is empty, we cannot provide good names.
1264  std::map<map_location,std::string>* village_labels = village_naming.empty() ? nullptr : labels;
1265 
1266  for(int vx = 0; vx < data.width; vx += village_x) {
1267  LOG_NG << "village at " << vx;
1268 
1269  for(int vy = rng_()%village_y; vy < data.height; vy += village_y) {
1270  const std::size_t add = rng_()%3;
1271  const std::size_t x = (vx + add) - 1;
1272  const std::size_t y = (vy + add) - 1;
1273 
1274  const map_location res = place_village(terrain, x, y, 2, cfg, adj_liked_cache);
1275 
1276  if(res.x < static_cast<long>(data.width ) / 3 ||
1277  res.x >= static_cast<long>(data.width * 2) / 3 ||
1278  res.y < static_cast<long>(data.height ) / 3 ||
1279  res.y >= static_cast<long>(data.height * 2) / 3) {
1280  continue;
1281  }
1282 
1283  const std::string str = t_translation::write_terrain_code(terrain[res.x][res.y]);
1284 
1285  const std::string& convert_to = cfg.find_mandatory_child("village", "terrain", str)["convert_to"].str();
1286  if(convert_to.empty()) {
1287  continue;
1288  }
1289 
1290  terrain[res.x][res.y] = t_translation::read_terrain_code(convert_to);
1291 
1292  villages.insert(res);
1293 
1294  if(village_labels == nullptr) {
1295  continue;
1296  }
1297 
1298  name_generator_factory village_name_generator_factory{ village_naming,
1299  {"base", "male", "village", "lake", "river", "bridge", "grassland", "forest", "hill", "mountain", "mountain_anon", "road", "swamp"} };
1300 
1301  village_naming.get_old_attribute("base_names", "male_names", "village_naming");
1302  //Due to the attribute detection feature of the factory we also support male_name_generator= but keep it undocumented.
1303 
1304  base_name_generator = village_name_generator_factory.get_name_generator(
1305  (village_naming.has_attribute("base_names") || village_naming.has_attribute("base_name_generator")) ? "base" : "male" );
1306 
1307  const map_location loc(res.x-data.width/3,res.y-data.height/3);
1308  const auto adj = get_adjacent_tiles(loc);
1309 
1310  std::string name_type = "village";
1316 
1317  std::size_t field_count = 0, forest_count = 0, mountain_count = 0, hill_count = 0;
1318 
1319  std::map<std::string,std::string> symbols;
1320 
1321  std::size_t n;
1322  for(n = 0; n != 6; ++n) {
1323  const std::map<map_location,std::string>::const_iterator road_name = road_names.find(adj[n]);
1324  if(road_name != road_names.end()) {
1325  symbols["road"] = road_name->second;
1326  name_type = "road";
1327  break;
1328  }
1329 
1330  const std::map<map_location,std::string>::const_iterator river_name = river_names.find(adj[n]);
1331  if(river_name != river_names.end()) {
1332  symbols["river"] = river_name->second;
1333  name_type = "river";
1334 
1335  const std::map<map_location,std::string>::const_iterator bridge_name = bridge_names.find(adj[n]);
1336  if(bridge_name != bridge_names.end()) {
1337  //we should always end up here, since if there is an adjacent bridge, there has to be an adjacent river too
1338  symbols["bridge"] = bridge_name->second;
1339  name_type = "river_bridge";
1340  }
1341 
1342  break;
1343  }
1344 
1345  const std::map<map_location,std::string>::const_iterator forest_name = forest_names.find(adj[n]);
1346  if(forest_name != forest_names.end()) {
1347  symbols["forest"] = forest_name->second;
1348  name_type = "forest";
1349  break;
1350  }
1351 
1352  const std::map<map_location,std::string>::const_iterator lake_name = lake_names.find(adj[n]);
1353  if(lake_name != lake_names.end()) {
1354  symbols["lake"] = lake_name->second;
1355  name_type = "lake";
1356  break;
1357  }
1358 
1359  const std::map<map_location,std::string>::const_iterator mountain_name = mountain_names.find(adj[n]);
1360  if(mountain_name != mountain_names.end()) {
1361  symbols["mountain"] = mountain_name->second;
1362  name_type = "mountain";
1363  break;
1364  }
1365 
1366  const std::map<map_location,std::string>::const_iterator swamp_name = swamp_names.find(adj[n]);
1367  if(swamp_name != swamp_names.end()) {
1368  symbols["swamp"] = swamp_name->second;
1369  name_type = "swamp";
1370  break;
1371  }
1372 
1373  const t_translation::terrain_code terr = terrain[adj[n].x+data.width/3][adj[n].y+data.height/3];
1374 
1375  if(std::count(field.begin(),field.end(),terr) > 0) {
1376  ++field_count;
1377  } else if(std::count(forest.begin(),forest.end(),terr) > 0) {
1378  ++forest_count;
1379  } else if(std::count(hill.begin(),hill.end(),terr) > 0) {
1380  ++hill_count;
1381  } else if(std::count(mountain.begin(),mountain.end(),terr) > 0) {
1382  ++mountain_count;
1383  }
1384  }
1385 
1386  if(n == 6) {
1387  if(field_count == 6) {
1388  name_type = "grassland";
1389  } else if(forest_count >= 2) {
1390  name_type = "forest";
1391  } else if(mountain_count >= 1) {
1392  name_type = "mountain_anon";
1393  } else if(hill_count >= 2) {
1394  name_type = "hill";
1395  }
1396  }
1397 
1398  std::string name;
1399 
1400  symbols["base"] = base_name_generator->generate();
1401  std::shared_ptr<name_generator> village_name_generator = village_name_generator_factory.get_name_generator(name_type);
1402 
1403  for(std::size_t ntry = 0; ntry != 30 && (ntry == 0 || used_names.count(name) > 0); ++ntry) {
1404  name = village_name_generator->generate(symbols);
1405  }
1406 
1407  used_names.insert(name);
1408  village_labels->emplace(loc, name);
1409  }
1410  }
1411  }
1412 
1413  LOG_NG << "Placed villages. " << (SDL_GetTicks() - ticks) << " ticks elapsed";
1414 
1415  return output_map(terrain, starting_positions);
1416 }
double t
Definition: astarsearch.cpp:63
A config object defines a single node in a WML file, with access to child nodes.
Definition: config.hpp:159
const attribute_value & get_old_attribute(config_key_type key, const std::string &old_key, const std::string &in_tag, const std::string &message="") const
Function to handle backward compatibility Get the value of key and if missing try old_key and log a d...
Definition: config.cpp:710
config & mandatory_child(config_key_type key, int n=0)
Returns the nth child with the given key, or throws an error if there is none.
Definition: config.cpp:367
config & find_mandatory_child(config_key_type key, const std::string &name, const std::string &value)
Definition: config.cpp:813
optional_config_impl< config > find_child(config_key_type key, const std::string &name, const std::string &value)
Returns the first child of tag key with a name attribute containing value.
Definition: config.cpp:787
bool has_child(config_key_type key) const
Determine whether a config has a child or not.
Definition: config.cpp:317
bool has_attribute(config_key_type key) const
Definition: config.cpp:155
child_itors child_range(config_key_type key)
Definition: config.cpp:273
void append_attributes(const config &cfg)
Adds attributes from cfg.
Definition: config.cpp:190
bool empty() const
Definition: config.cpp:852
optional_config_impl< config > optional_child(config_key_type key, int n=0)
Euivalent to mandatory_child, but returns an empty optional if the nth child was not found.
Definition: config.cpp:385
height_map generate_height_map(size_t width, size_t height, size_t iterations, size_t hill_size, size_t island_size, size_t island_off_center)
Generate a height-map.
map_location random_point_at_side(std::size_t width, std::size_t height)
Returns a random tile at one of the borders of a map that is of the given dimensions.
std::string default_generate_map(generator_data data, std::map< map_location, std::string > *labels, const config &cfg)
Generate the map.
std::vector< map_location > generate_river(const height_map &heights, terrain_map &terrain, int x, int y, int river_uphill)
bool generate_lake(t_translation::ter_map &terrain, int x, int y, int lake_fall_off, std::set< map_location > &locs_touched)
Generate a lake.
const game_config_view & game_config_
bool generate_river_internal(const height_map &heights, terrain_map &terrain, int x, int y, std::vector< map_location > &river, std::set< map_location > &seen_locations, int river_uphill)
River generation.
std::vector< std::vector< int > > height_map
const config & mandatory_child(config_key_type key) const
static const int default_border
The default border style for a map.
Definition: map.hpp:37
static int rank_castle_location(int x, int y, const is_valid_terrain &valid_terrain, int min_x, int max_x, int min_y, int max_y, std::size_t min_distance, const std::vector< map_location > &other_castles, int highest_ranking)
#define ERR_NG
std::map< t_translation::terrain_code, t_translation::ter_list > tcode_list_cache
static lg::log_domain log_mapgen("mapgen")
t_translation::ter_map terrain_map
static map_location place_village(const t_translation::ter_map &map, const std::size_t x, const std::size_t y, const std::size_t radius, const config &cfg, tcode_list_cache &adj_liked_cache)
#define DBG_NG
static void flood_name(const map_location &start, const std::string &name, std::map< map_location, std::string > &tile_names, const t_translation::ter_match &tile_types, const terrain_map &terrain, unsigned width, unsigned height, std::size_t label_count, std::map< map_location, std::string > *labels, const std::string &full_name)
static std::string output_map(const terrain_map &terrain, t_translation::starting_positions &starting_positions)
Function which, given the map will output it in a valid format.
#define LOG_NG
std::vector< std::vector< int > > height_map
std::size_t i
Definition: function.cpp:968
static std::string _(const char *str)
Definition: gettext.hpp:93
void get_adjacent_tiles(const map_location &a, map_location *res)
Function which, given a location, will place all adjacent locations in res.
Definition: location.cpp:474
std::size_t distance_between(const map_location &a, const map_location &b)
Function which gives the number of hexes between two tiles (i.e.
Definition: location.cpp:545
Standard logging facilities (interface).
#define log_scope(description)
Definition: log.hpp:274
constexpr bool is_even(T num)
Definition: math.hpp:33
CURSOR_TYPE get()
Definition: cursor.cpp:216
static bool is_valid_terrain(const t_translation::terrain_code &c)
EXIT_STATUS start(bool clear_id, const std::string &filename, bool take_screenshot, const std::string &screenshot_filename)
Main interface for launching the editor from the title screen.
std::string base_name(const std::string &file, const bool remove_extension)
Returns the base filename of a file, with directory name stripped.
Game configuration data as global variables.
Definition: build_info.cpp:60
std::vector< game_tip > shuffle(const std::vector< game_tip > &tips)
Shuffles the tips.
Definition: tips.cpp:47
log_domain & general()
Definition: log.cpp:328
const std::vector< std::string > items
plain_route a_star_search(const map_location &src, const map_location &dst, double stop_at, const cost_calculator &calc, const std::size_t width, const std::size_t height, const teleport_map *teleports, bool border)
uint32_t next_seed()
Definition: seed_rng.cpp:32
terrain_code read_terrain_code(std::string_view str, const ter_layer filler)
Reads a single terrain from a string.
const ter_match ALL_FORESTS
std::string write_game_map(const ter_map &map, const starting_positions &starting_positions, coordinate border_offset)
Write a gamemap in to a vector string.
const terrain_code SHALLOW_WATER
const ter_match ALL_SWAMPS("!,*^V*,*^B*,!,S*")
const terrain_code HUMAN_CASTLE
const terrain_code HILL
bool terrain_matches(const terrain_code &src, const terrain_code &dest)
Tests whether a specific terrain matches an expression, for matching rules see above.
std::vector< terrain_code > ter_list
Definition: translation.hpp:77
const terrain_code GRASS_LAND
const terrain_code DEEP_WATER
boost::bimaps::bimap< boost::bimaps::set_of< std::string >, boost::bimaps::multiset_of< coordinate > > starting_positions
const terrain_code FOREST
ter_list read_list(std::string_view str, const ter_layer filler)
Reads a list of terrains from a string, when reading the.
const ter_match ALL_MOUNTAINS("!,*^V*,!,M*")
const terrain_code MOUNTAIN
std::string write_terrain_code(const terrain_code &tcode)
Writes a single terrain code to a string.
const terrain_code HUMAN_KEEP
const terrain_code NONE_TERRAIN
Definition: translation.hpp:58
std::vector< std::string > split(const config_attribute_value &val)
std::string::const_iterator iterator
Definition: tokenizer.hpp:25
This module contains various pathfinding functions and utilities.
void get_tiles_radius(const map_location &center, std::size_t radius, std::set< map_location > &result)
Function that will add to result all locations within radius tiles of center (including center itself...
Definition: pathutils.cpp:70
std::string_view data
Definition: picture.cpp:194
Encapsulates the map of the game.
Definition: location.hpp:38
static double getNoPathValue()
Definition: pathfind.hpp:65
virtual double cost(const map_location &loc, const double so_far) const =0
Structure which holds a single route between one location and another.
Definition: pathfind.hpp:133
std::vector< map_location > steps
Definition: pathfind.hpp:135
This structure can be used for matching terrain strings.
A terrain string which is converted to a terrain is a string with 1 or 2 layers the layers are separa...
Definition: translation.hpp:49
mock_char c
static map_location::DIRECTION n
Add a special kind of assert to validate whether the input from WML doesn't contain any problems that...
#define VALIDATE(cond, message)
The macro to use for the validation of WML.
#define h
#define a
#define b