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