The Battle for Wesnoth  1.15.0+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.