The Battle for Wesnoth  1.19.0-dev
cave_map_generator.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2003 - 2024
3  by David White <dave@whitevine.net>
4  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License as published by
8  the Free Software Foundation; either version 2 of the License, or
9  (at your option) any later version.
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY.
12 
13  See the COPYING file for more details.
14 */
15 
16 /**
17  * @file
18  * Map-generator for caves.
19  */
20 
22 #include "log.hpp"
23 #include "map/map.hpp"
24 #include "pathfind/pathfind.hpp"
26 #include "seed_rng.hpp"
27 
28 static lg::log_domain log_engine("engine");
29 #define LOG_NG LOG_STREAM(info, log_engine)
30 
31 static lg::log_domain log_wml("wml");
32 #define ERR_WML LOG_STREAM(err, log_wml)
33 
35  wall_(t_translation::CAVE_WALL),
36  clear_(t_translation::CAVE),
38  castle_(t_translation::DWARVEN_CASTLE),
40  cfg_(cfg),
41  width_(50),
42  height_(50),
43  village_density_(0),
44  flipx_chance_(cfg_["flipx_chance"]),
45  flipy_chance_(cfg_["flipy_chance"])
46 {
47  width_ = cfg_["map_width"];
48  height_ = cfg_["map_height"];
49 
50  village_density_ = cfg_["village_density"];
51 }
52 
54 {
55  return "";
56 }
57 
59 {
60  if(flipx_) {
61  x = params.width_ - x - 1;
62  }
63 
64  return x;
65 }
66 
68 {
69  if(flipy_) {
70  y = params.height_ - y - 1;
71  }
72 
73  return y;
74 }
75 
76 std::string cave_map_generator::create_map(std::optional<uint32_t> randomseed)
77 {
78  const config res = create_scenario(randomseed);
79  return res["map_data"];
80 }
81 
82 config cave_map_generator::create_scenario(std::optional<uint32_t> randomseed)
83 {
84  cave_map_generator_job job(*this, randomseed);
85  return job.res_;
86 }
87 
89  : params(pparams)
90  , flipx_(false)
91  , flipy_(false)
92  , map_(t_translation::ter_map(params.width_ + 2 * gamemap::default_border, params.height_ + 2 * gamemap::default_border/*, params.wall_*/))
93  , starting_positions_()
94  , chamber_ids_()
95  , chambers_()
96  , passages_()
97  , res_(params.cfg_.child_or_empty("settings"))
98  , rng_() //initialises with rand()
99 {
100  res_.add_child("event", config {
101  "name", "start",
102  "deprecated_message", config {
103  "what", "scenario_generation=cave",
104  "level", 1,
105  "message", "Use the Lua cave generator instead, with scenario_generation=lua and create_scenario= (see wiki for details).",
106  },
107  });
108  uint32_t seed = randomseed ? *randomseed : seed_rng::next_seed();
109  rng_.seed(seed);
110  LOG_NG << "creating random cave with seed: " << seed;
111  flipx_ = static_cast<int>(rng_() % 100) < params.flipx_chance_;
112  flipy_ = static_cast<int>(rng_() % 100) < params.flipy_chance_;
113 
114  LOG_NG << "creating scenario....";
116 
117  LOG_NG << "placing chambers...";
118  for(std::vector<chamber>::const_iterator c = chambers_.begin(); c != chambers_.end(); ++c) {
119  place_chamber(*c);
120  }
121 
122  LOG_NG << "placing passages...";
123 
124  for(std::vector<passage>::const_iterator p = passages_.begin(); p != passages_.end(); ++p) {
125  place_passage(*p);
126  }
127  LOG_NG << "outputting map....";
128 
130 }
131 
132 void cave_map_generator::cave_map_generator_job::build_chamber(map_location loc, std::set<map_location>& locs, std::size_t size, std::size_t jagged)
133 {
134  if(size == 0 || locs.count(loc) != 0 || !params.on_board(loc))
135  return;
136 
137  locs.insert(loc);
138 
139  for(const map_location& adj : get_adjacent_tiles(loc)) {
140  if(static_cast<int>(rng_() % 100) < (100l - static_cast<long>(jagged))) {
141  build_chamber(adj,locs,size-1,jagged);
142  }
143  }
144 }
145 
147 {
148  for (const config &ch : params.cfg_.child_range("chamber"))
149  {
150  // If there is only a chance of the chamber appearing, deal with that here.
151  if (ch.has_attribute("chance") && static_cast<int>(rng_() % 100) < ch["chance"].to_int()) {
152  continue;
153  }
154 
155  const std::string &xpos = ch["x"];
156  const std::string &ypos = ch["y"];
157 
158  std::size_t min_xpos = 0, min_ypos = 0, max_xpos = params.width_, max_ypos = params.height_;
159 
160  if (!xpos.empty()) {
161  const std::vector<std::string>& items = utils::split(xpos, '-');
162  if(items.empty() == false) {
163  try {
164  min_xpos = std::stoi(items.front()) - 1;
165  max_xpos = std::stoi(items.back());
166  } catch(const std::invalid_argument&) {
167  lg::log_to_chat() << "Invalid min/max coordinates in cave_map_generator: " << items.front() << ", " << items.back() << "\n";
168  ERR_WML << "Invalid min/max coordinates in cave_map_generator: " << items.front() << ", " << items.back();
169  continue;
170  }
171  }
172  }
173 
174  if (!ypos.empty()) {
175  const std::vector<std::string>& items = utils::split(ypos, '-');
176  if(items.empty() == false) {
177  try {
178  min_ypos = std::stoi(items.front()) - 1;
179  max_ypos = std::stoi(items.back());
180  } catch(const std::invalid_argument&) {
181  lg::log_to_chat() << "Invalid min/max coordinates in cave_map_generator: " << items.front() << ", " << items.back() << "\n";
182  ERR_WML << "Invalid min/max coordinates in cave_map_generator: " << items.front() << ", " << items.back();
183  }
184  }
185  }
186  const std::size_t x = translate_x(min_xpos + (rng_()%(max_xpos-min_xpos)));
187  const std::size_t y = translate_y(min_ypos + (rng_()%(max_ypos-min_ypos)));
188 
189  int chamber_size = ch["size"].to_int(3);
190  int jagged_edges = ch["jagged"];
191 
192  chamber new_chamber;
193  new_chamber.center = map_location(x,y);
194  build_chamber(new_chamber.center,new_chamber.locs,chamber_size,jagged_edges);
195 
196  auto items = ch.optional_child("items");
197  new_chamber.items = items ? &*items : nullptr;
198 
199  const std::string &id = ch["id"];
200  if (!id.empty()) {
201  chamber_ids_[id] = chambers_.size();
202  }
203 
204  chambers_.push_back(new_chamber);
205 
206  for(const config &p : ch.child_range("passage"))
207  {
208  const std::string &dst = p["destination"];
209 
210  // Find the destination of this passage
211  const std::map<std::string,std::size_t>::const_iterator itor = chamber_ids_.find(dst);
212  if(itor == chamber_ids_.end())
213  continue;
214 
215  assert(itor->second < chambers_.size());
216 
217  passages_.emplace_back(new_chamber.center, chambers_[itor->second].center, p);
218  }
219  }
220 }
221 
223 {
224  for(std::set<map_location>::const_iterator i = c.locs.begin(); i != c.locs.end(); ++i) {
225  set_terrain(*i,params.clear_);
226  }
227 
228  if (c.items == nullptr || c.locs.empty()) return;
229 
230  std::size_t index = 0;
231  for (const config::any_child it : c.items->all_children_range())
232  {
233  config cfg = it.cfg;
234  auto filter = cfg.optional_child("filter");
235  config* object_filter = nullptr;
236  if (auto object = cfg.optional_child("object")) {
237  if (auto of = object->optional_child("filter")) {
238  object_filter = &*of;
239  }
240  }
241 
242  if (!it.cfg["same_location_as_previous"].to_bool()) {
243  index = rng_()%c.locs.size();
244  }
245  std::string loc_var = it.cfg["store_location_as"];
246 
247  std::set<map_location>::const_iterator loc = c.locs.begin();
248  std::advance(loc,index);
249 
250  cfg["x"] = loc->x + 1;
251  cfg["y"] = loc->y + 1;
252 
253  if (filter) {
254  filter["x"] = loc->x + 1;
255  filter["y"] = loc->y + 1;
256  }
257 
258  if (object_filter) {
259  (*object_filter)["x"] = loc->x + 1;
260  (*object_filter)["y"] = loc->y + 1;
261  }
262 
263  // If this is a side, place a castle for the side
264  if (it.key == "side" && !it.cfg["no_castle"].to_bool()) {
265  place_castle(it.cfg["side"].to_int(-1), *loc);
266  }
267 
268  res_.add_child(it.key, cfg);
269 
270  if(!loc_var.empty()) {
271  config &temp = res_.add_child("event");
272  temp["name"] = "prestart";
273  config &xcfg = temp.add_child("set_variable");
274  xcfg["name"] = loc_var + "_x";
275  xcfg["value"] = loc->x + 1;
276  config &ycfg = temp.add_child("set_variable");
277  ycfg["name"] = loc_var + "_y";
278  ycfg["value"] = loc->y + 1;
279  }
280  }
281 }
282 
284 {
286  const t_translation::terrain_code & wall,
287  double laziness, std::size_t windiness,
288  std::mt19937& rng) :
289  map_(mapdata), wall_(wall), laziness_(laziness), windiness_(windiness), rng_(rng)
290  {}
291 
292  virtual double cost(const map_location& loc, const double so_far) const;
293 private:
296  double laziness_;
297  std::size_t windiness_;
298  std::mt19937& rng_;
299 };
300 
301 double passage_path_calculator::cost(const map_location& loc, const double) const
302 {
303  double res = 1.0;
304  if (map_.get(loc.x + gamemap::default_border, loc.y + gamemap::default_border) == wall_) {
305  res = laziness_;
306  }
307 
308  if(windiness_ > 1) {
309  res *= static_cast<double>(rng_()%windiness_);
310  }
311 
312  return res;
313 }
314 
316 {
317  const std::string& chance = p.cfg["chance"];
318  if(!chance.empty() && static_cast<int>(rng_()%100) < std::stoi(chance)) {
319  return;
320  }
321 
322 
323  int windiness = p.cfg["windiness"];
324  double laziness = std::max<double>(1.0, p.cfg["laziness"].to_double());
325 
326  passage_path_calculator calc(map_, params.wall_, laziness, windiness, rng_);
327 
328  pathfind::plain_route rt = a_star_search(p.src, p.dst, 10000.0, calc, params.width_, params.height_);
329 
330  int width = std::max<int>(1, p.cfg["width"].to_int());
331  int jagged = p.cfg["jagged"];
332 
333  for(std::vector<map_location>::const_iterator i = rt.steps.begin(); i != rt.steps.end(); ++i) {
334  std::set<map_location> locs;
335  build_chamber(*i,locs,width,jagged);
336  for(std::set<map_location>::const_iterator j = locs.begin(); j != locs.end(); ++j) {
337  set_terrain(*j, params.clear_);
338  }
339  }
340 }
341 
343 {
344  if (params.on_board(loc)) {
346 
347  if(c == params.clear_ || c == params.wall_ || c == params.village_) {
348  // Change this terrain.
349  if ( t == params.clear_ && static_cast<int>(rng_() % 1000) < params.village_density_ )
350  // Override with a village.
351  c = params.village_;
352  else
353  c = t;
354  }
355  }
356 }
357 
359 {
360  if (starting_position != -1) {
361  set_terrain(loc, params.keep_);
362 
365  , loc.y + gamemap::default_border);
366  starting_positions_.insert(t_translation::starting_positions::value_type(std::to_string(starting_position), coord));
367  }
368 
369  for(const map_location& adj : get_adjacent_tiles(loc)) {
370  set_terrain(adj, params.castle_);
371  }
372 }
double t
Definition: astarsearch.cpp:63
static lg::log_domain log_engine("engine")
#define ERR_WML
static lg::log_domain log_wml("wml")
#define LOG_NG
cave_map_generator(const config &game_config)
std::string create_map(std::optional< uint32_t > randomseed={})
Creates a new map and returns it.
config create_scenario(std::optional< uint32_t > randomseed={})
std::string config_name() const
Return a friendly name for the generator used to differentiate between different configs of the same ...
t_translation::terrain_code wall_
A config object defines a single node in a WML file, with access to child nodes.
Definition: config.hpp:159
child_itors child_range(config_key_type key)
Definition: config.cpp:273
optional_config_impl< config > optional_child(config_key_type key, int n=0)
Euivalent to mandatory_child, but returns an empty optional if the nth child was not found.
Definition: config.cpp:385
config & add_child(config_key_type key)
Definition: config.cpp:441
static const int default_border
The default border style for a map.
Definition: map.hpp:37
Encapsulates the map of the game.
Definition: map.hpp:172
std::size_t i
Definition: function.cpp:968
std::string id
Text to match against addon_info.tags()
Definition: manager.cpp:207
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
Standard logging facilities (interface).
std::stringstream & log_to_chat()
Use this to show WML errors in the ingame chat.
Definition: log.cpp:544
const std::vector< std::string > items
plain_route a_star_search(const map_location &src, const map_location &dst, double stop_at, const cost_calculator &calc, const std::size_t width, const std::size_t height, const teleport_map *teleports, bool border)
uint32_t next_seed()
Definition: seed_rng.cpp:32
const terrain_code CAVE_WALL
std::string write_game_map(const ter_map &map, const starting_positions &starting_positions, coordinate border_offset)
Write a gamemap in to a vector string.
const terrain_code DWARVEN_KEEP
const terrain_code UNDERGROUND_VILLAGE
const terrain_code DWARVEN_CASTLE
const terrain_code CAVE
std::size_t index(const std::string &str, const std::size_t index)
Codepoint index corresponding to the nth character in a UTF-8 string.
Definition: unicode.cpp:70
std::size_t size(const std::string &str)
Length in characters of a UTF-8 string.
Definition: unicode.cpp:85
std::vector< std::string > split(const config_attribute_value &val)
This module contains various pathfinding functions and utilities.
void set_terrain(map_location loc, const t_translation::terrain_code &t)
cave_map_generator_job(const cave_map_generator &params, std::optional< uint32_t > randomseed={})
void build_chamber(map_location loc, std::set< map_location > &locs, std::size_t size, std::size_t jagged)
std::size_t translate_x(std::size_t x) const
t_translation::starting_positions starting_positions_
std::size_t translate_y(std::size_t y) const
void place_castle(int starting_position, const map_location &loc)
Encapsulates the map of the game.
Definition: location.hpp:38
const t_translation::ter_map & map_
virtual double cost(const map_location &loc, const double so_far) const
t_translation::terrain_code wall_
passage_path_calculator(const t_translation::ter_map &mapdata, const t_translation::terrain_code &wall, double laziness, std::size_t windiness, std::mt19937 &rng)
Structure which holds a single route between one location and another.
Definition: pathfind.hpp:133
std::vector< map_location > steps
Definition: pathfind.hpp:135
A terrain string which is converted to a terrain is a string with 1 or 2 layers the layers are separa...
Definition: translation.hpp:49
mock_char c
mock_party p