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