The Battle for Wesnoth  1.17.0-dev
markov_generator.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2003 - 2021
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  * Generate race-specific unit-names.
19  */
20 
22 
24 #include "random.hpp"
25 
26 static void add_prefixes(const std::u32string& str, std::size_t length, markov_prefix_map& res)
27 {
28  for(std::size_t i = 0; i <= str.size(); ++i) {
29  const std::size_t start = i > length ? i - length : 0;
30  const std::u32string key(str.begin() + start, str.begin() + i);
31  const char32_t c = i != str.size() ? str[i] : 0;
32  res[key].push_back(c);
33  }
34 }
35 
36 static markov_prefix_map markov_prefixes(const std::vector<std::string>& items, std::size_t length)
37 {
39 
40  for(std::vector<std::string>::const_iterator i = items.begin(); i != items.end(); ++i) {
41  add_prefixes(unicode_cast<std::u32string>(*i),length,res);
42  }
43 
44  return res;
45 }
46 
47 static std::u32string markov_generate_name(const markov_prefix_map& prefixes,
48  std::size_t chain_size, std::size_t max_len)
49 {
50  if(prefixes.empty() || chain_size == 0) {
51  return std::u32string();
52  }
53 
54  std::u32string prefix, res;
55 
56  // Since this function is called in the name description in a MP game it
57  // uses the local locale. The locale between players can be different and
58  // thus the markov_prefix_map can be different. This resulted in
59  // get_random() getting called a different number of times for the
60  // generation in different locales (due to the bail out at 'if(c == 0)').
61  //
62  // This causes a problem since the random state is no longer in sync. The
63  // following calls to get_random() return different results, which caused
64  // traits to be different. To avoid that problem we call get_random()
65  // the maximum number of times and store the result in a lookup table.
66  std::vector<int> random(max_len);
67  std::size_t j = 0;
68  for(; j < max_len; ++j) {
69  random[j] = randomness::generator->next_random();
70  }
71 
72  j = 0;
73  while(res.size() < max_len) {
74  const markov_prefix_map::const_iterator i = prefixes.find(prefix);
75  if(i == prefixes.end() || i->second.empty()) {
76  return res;
77  }
78 
79  const char32_t c = i->second[random[j++]%i->second.size()];
80  if(c == 0) {
81  return res;
82  }
83 
84  res.resize(res.size()+1);
85  res.back() = c;
86  prefix.resize(prefix.size()+1);
87  prefix.back() = c;
88  while(prefix.size() > chain_size) {
89  prefix.erase(prefix.begin());
90  }
91  }
92 
93  // Getting here means that the maximum length was reached when
94  // generating the name, hence the ending of the name has to be
95  // made valid. Otherwise weird names like UnĂ¡rierini- and
96  // Thramboril-G may occur.
97 
98  // Strip characters from the end until the last prefix of the
99  // name has end-of-string as a possible next character in the
100  // markov prefix map. If no valid ending is found, use the
101  // originally generated name.
102  std::u32string originalRes = res;
103  while(!res.empty()) {
104  const int prefixLen = chain_size < res.size() ? chain_size : res.size();
105  prefix = std::u32string(res.end() - prefixLen, res.end());
106 
107  const markov_prefix_map::const_iterator i = prefixes.find(prefix);
108  if (i == prefixes.end() || i->second.empty()) {
109  return res;
110  }
111  if (std::find(i->second.begin(), i->second.end(), static_cast<char32_t>(0))
112  != i->second.end()) {
113  // This ending is valid.
114  return res;
115  }
116  // The current ending is invalid, remove the last character
117  // and retry.
118  res.pop_back();
119  }
120  // No valid ending at all could be found. This generally should
121  // not happen, unless the chain length is very long or the
122  // maximum length is very small. Return the originally generated
123  // name, it's not much we can do about it.
124  return originalRes;
125 }
126 
127 markov_generator::markov_generator(const std::vector<std::string>& items, std::size_t chain_size, std::size_t max_len)
128  : prefixes_(markov_prefixes(items, chain_size))
129  , chain_size_(chain_size)
130  , max_len_(max_len)
131 {
132 }
133 
134 std::string markov_generator::generate() const
135 {
136  std::u32string name = markov_generate_name(prefixes_, chain_size_, max_len_);
137  return unicode_cast<std::string>(name);
138 }
markov_generator(const std::vector< std::string > &items, std::size_t chain_size, std::size_t max_len)
ucs4_convert_impl::enableif< TD, typename TS::value_type >::type unicode_cast(const TS &source)
static void add_prefixes(const std::u32string &str, std::size_t length, markov_prefix_map &res)
static std::u32string markov_generate_name(const markov_prefix_map &prefixes, std::size_t chain_size, std::size_t max_len)
const std::vector< std::string > items
static markov_prefix_map markov_prefixes(const std::vector< std::string > &items, std::size_t length)
std::size_t chain_size_
std::size_t i
Definition: function.cpp:967
markov_prefix_map prefixes_
rng * generator
This generator is automatically synced during synced context.
Definition: random.cpp:61
std::map< std::u32string, std::u32string > markov_prefix_map
std::string generate() const override
uint32_t next_random()
Provides the next random draw.
Definition: random.cpp:85
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:30
mock_char c