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