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