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