1 #include "ResearchQueue.h"
2
3 #include "Empire.h"
4 #include "../universe/Enums.h"
5 #include "../universe/Tech.h"
6 #include "../util/AppInterface.h"
7
8 namespace {
9 const float EPSILON = 0.01f;
10
11 /** sets the .allocated_rp, value for each Tech in the queue. Only sets
12 * nonzero funding to a Tech if it is researchable this turn. Also
13 * determines total number of spent RP (returning by reference in
14 * total_RPs_spent) */
SetTechQueueElementSpending(float RPs,const std::map<std::string,float> & research_progress,const std::map<std::string,TechStatus> & research_status,ResearchQueue::QueueType & queue,float & total_RPs_spent,int & projects_in_progress,int empire_id)15 void SetTechQueueElementSpending(
16 float RPs, const std::map<std::string, float>& research_progress,
17 const std::map<std::string, TechStatus>& research_status,
18 ResearchQueue::QueueType& queue, float& total_RPs_spent,
19 int& projects_in_progress, int empire_id)
20 {
21 total_RPs_spent = 0.0f;
22 projects_in_progress = 0;
23
24 for (ResearchQueue::Element& elem : queue) {
25 elem.allocated_rp = 0.0f; // default, may be modified below
26
27 if (elem.paused) {
28 continue;
29 }
30
31 // get details on what is being researched...
32 const Tech* tech = GetTech(elem.name);
33 if (!tech) {
34 ErrorLogger() << "SetTechQueueElementSpending found null tech on research queue?!";
35 continue;
36 }
37 auto status_it = research_status.find(elem.name);
38 if (status_it == research_status.end()) {
39 ErrorLogger() << "SetTechQueueElementSpending couldn't find tech with name " << elem.name << " in the research status map";
40 continue;
41 }
42 bool researchable = status_it->second == TS_RESEARCHABLE;
43
44 if (researchable && !elem.paused) {
45 auto progress_it = research_progress.find(elem.name);
46 float tech_cost = tech->ResearchCost(empire_id);
47 float progress = progress_it == research_progress.end() ? 0.0f : progress_it->second;
48 float RPs_needed = tech_cost - progress*tech_cost;
49 int tech_min_turns = std::max(1, tech ? tech->ResearchTime(empire_id) : 1);
50
51 float RPs_per_turn_limit = tech ? (tech_cost / tech_min_turns) : 1.0f;
52 float RPs_to_spend = std::min(RPs_needed, RPs_per_turn_limit);
53
54 if (total_RPs_spent + RPs_to_spend <= RPs - EPSILON) {
55 elem.allocated_rp = RPs_to_spend;
56 total_RPs_spent += elem.allocated_rp;
57 ++projects_in_progress;
58 } else if (total_RPs_spent < RPs - EPSILON) {
59 elem.allocated_rp = RPs - total_RPs_spent;
60 total_RPs_spent += elem.allocated_rp;
61 ++projects_in_progress;
62 } else {
63 elem.allocated_rp = 0.0f;
64 }
65 } else {
66 // item can't be researched this turn
67 elem.allocated_rp = 0.0f;
68 }
69 }
70
71 DebugLogger() << "SetTechQueueElementSpending allocated: " << total_RPs_spent << " of " << RPs << " available";
72 }
73 }
74
75
Dump() const76 std::string ResearchQueue::Element::Dump() const {
77 std::stringstream retval;
78 retval << "ResearchQueue::Element: tech: " << name << " empire id: " << empire_id;
79 retval << " allocated: " << allocated_rp << " turns left: " << turns_left;
80 if (paused)
81 retval << " (paused)";
82 retval << "\n";
83 return retval.str();
84 }
85
InQueue(const std::string & tech_name) const86 bool ResearchQueue::InQueue(const std::string& tech_name) const {
87 return std::count_if(m_queue.begin(), m_queue.end(),
88 [tech_name](const Element& e){ return e.name == tech_name; });
89 }
90
Paused(const std::string & tech_name) const91 bool ResearchQueue::Paused(const std::string& tech_name) const {
92 auto it = find(tech_name);
93 if (it == end())
94 return false;
95 return it->paused;
96 }
97
Paused(int idx) const98 bool ResearchQueue::Paused(int idx) const {
99 if (idx >= static_cast<int>(m_queue.size()))
100 return false;
101 return std::next(begin(), idx)->paused;
102 }
103
ProjectsInProgress() const104 int ResearchQueue::ProjectsInProgress() const
105 { return m_projects_in_progress; }
106
TotalRPsSpent() const107 float ResearchQueue::TotalRPsSpent() const
108 { return m_total_RPs_spent; }
109
AllEnqueuedProjects() const110 std::vector<std::string> ResearchQueue::AllEnqueuedProjects() const {
111 std::vector<std::string> retval;
112 for (const auto& entry : m_queue)
113 retval.push_back(entry.name);
114 return retval;
115 }
116
Dump() const117 std::string ResearchQueue::Dump() const {
118 std::stringstream retval;
119 retval << "ResearchQueue:\n";
120 float spent_rp{0.0f};
121 for (const auto& entry : m_queue) {
122 retval << " ... " << entry.Dump();
123 spent_rp += entry.allocated_rp;
124 }
125 retval << "ResearchQueue Total Spent RP: " << spent_rp;
126 return retval.str();
127 }
128
empty() const129 bool ResearchQueue::empty() const
130 { return !m_queue.size(); }
131
size() const132 unsigned int ResearchQueue::size() const
133 { return m_queue.size(); }
134
begin() const135 ResearchQueue::const_iterator ResearchQueue::begin() const
136 { return m_queue.begin(); }
137
end() const138 ResearchQueue::const_iterator ResearchQueue::end() const
139 { return m_queue.end(); }
140
find(const std::string & tech_name) const141 ResearchQueue::const_iterator ResearchQueue::find(const std::string& tech_name) const {
142 for (auto it = begin(); it != end(); ++it) {
143 if (it->name == tech_name)
144 return it;
145 }
146 return end();
147 }
148
operator [](int i) const149 const ResearchQueue::Element& ResearchQueue::operator[](int i) const {
150 if (i < 0 || i >= static_cast<int>(m_queue.size()))
151 throw std::out_of_range("Tried to access ResearchQueue element out of bounds");
152 return m_queue[i];
153 }
154
Update(float RPs,const std::map<std::string,float> & research_progress)155 void ResearchQueue::Update(float RPs, const std::map<std::string, float>& research_progress) {
156 // status of all techs for this empire
157 const Empire* empire = GetEmpire(m_empire_id);
158 if (!empire) {
159 ErrorLogger() << "ResearchQueue::Update passed null empire. doing nothing.";
160 m_projects_in_progress = 0;
161 m_total_RPs_spent = 0.0f;
162 return;
163 }
164
165 std::map<std::string, TechStatus> sim_tech_status_map;
166 for (const auto& tech : GetTechManager()) {
167 const std::string& tech_name = tech->Name();
168 sim_tech_status_map[tech_name] = empire->GetTechStatus(tech_name);
169 }
170
171 SetTechQueueElementSpending(RPs, research_progress, sim_tech_status_map, m_queue,
172 m_total_RPs_spent, m_projects_in_progress, m_empire_id);
173
174 if (m_queue.empty()) {
175 ResearchQueueChangedSignal();
176 return; // nothing more to do...
177 }
178
179 const int TOO_MANY_TURNS = 500; // stop counting turns to completion after this long, to prevent seemingly endless loops
180
181 // initialize status of everything to never getting done
182 for (Element& element : m_queue)
183 element.turns_left = -1;
184
185 if (RPs <= EPSILON) {
186 ResearchQueueChangedSignal();
187 return; // nothing more to do if not enough RP...
188 }
189
190 boost::posix_time::ptime dp_time_start;
191 boost::posix_time::ptime dp_time_end;
192
193 // "Dynamic Programming" version of research queue simulator -- copy the queue simulator containers
194 // perform dynamic programming calculation of completion times, then after regular simulation is done compare results (if both enabled)
195
196 //record original order & progress
197 // will take advantage of fact that sets (& map keys) are by default kept in sorted order lowest to highest
198 std::map<std::string, float> dp_prog = research_progress;
199 std::map<std::string, int> orig_queue_order;
200 std::map<int, float> dpsim_research_progress;
201 for (unsigned int i = 0; i < m_queue.size(); ++i) {
202 std::string tname = m_queue[i].name;
203 orig_queue_order[tname] = i;
204 dpsim_research_progress[i] = dp_prog[tname];
205 }
206
207 std::map<std::string, TechStatus> dpsim_tech_status_map = std::move(sim_tech_status_map);
208
209 // initialize simulation_results with -1 for all techs, so that any techs that aren't
210 // finished in simulation by turn TOO_MANY_TURNS will be left marked as never to be finished
211 std::vector<int> dpsimulation_results(m_queue.size(), -1);
212
213 const int DP_TURNS = TOO_MANY_TURNS; // track up to this many turns
214
215 std::map<std::string, std::set<std::string>> waiting_for_prereqs;
216 std::set<int> dp_researchable_techs;
217
218 for (unsigned int i = 0; i < m_queue.size(); ++i) {
219 std::string techname = m_queue[i].name;
220 if (m_queue[i].paused)
221 continue;
222 const Tech* tech = GetTech(techname);
223 if (!tech)
224 continue;
225 if (dpsim_tech_status_map[techname] == TS_RESEARCHABLE) {
226 dp_researchable_techs.insert(i);
227 } else if (dpsim_tech_status_map[techname] == TS_UNRESEARCHABLE ||
228 dpsim_tech_status_map[techname] == TS_HAS_RESEARCHED_PREREQ)
229 {
230 std::set<std::string> these_prereqs = tech->Prerequisites();
231 for (auto ptech_it = these_prereqs.begin(); ptech_it != these_prereqs.end();) {
232 if (dpsim_tech_status_map[*ptech_it] != TS_COMPLETE) {
233 ++ptech_it;
234 } else {
235 auto erase_it = ptech_it;
236 ++ptech_it;
237 these_prereqs.erase(erase_it);
238 }
239 }
240 waiting_for_prereqs[techname] = these_prereqs;
241 }
242 }
243
244 int dp_turns = 0;
245 //pp_still_available[turn-1] gives the RP still available in this resource pool at turn "turn"
246 std::vector<float> rp_still_available(DP_TURNS, RPs); // initialize to the full RP allocation for every turn
247
248 while ((dp_turns < DP_TURNS) && !(dp_researchable_techs.empty())) {// if we haven't used up our turns and still have techs to process
249 ++dp_turns;
250 std::map<int, bool> already_processed;
251 for (int tech_id : dp_researchable_techs) {
252 already_processed[tech_id] = false;
253 }
254 auto cur_tech_it = dp_researchable_techs.begin();
255 while ((rp_still_available[dp_turns-1] > EPSILON)) { // try to use up this turns RPs
256 if (cur_tech_it == dp_researchable_techs.end()) {
257 break; //will be wasting some RP this turn
258 }
259 int cur_tech = *cur_tech_it;
260 if (already_processed[cur_tech]) {
261 ++cur_tech_it;
262 continue;
263 }
264 already_processed[cur_tech] = true;
265 const std::string& tech_name = m_queue[cur_tech].name;
266 const Tech* tech = GetTech(tech_name);
267 float progress = dpsim_research_progress[cur_tech];
268 float tech_cost = tech ? tech->ResearchCost(m_empire_id) : 0.0f;
269 int tech_min_turns = std::max(1, tech ? tech->ResearchTime(m_empire_id) : 1);
270
271 float RPs_needed = tech ? tech_cost * (1.0f - std::min(progress, 1.0f)) : 0.0f;
272 float RPs_per_turn_limit = tech ? (tech_cost / tech_min_turns) : 1.0f;
273
274 float RPs_to_spend = std::min(std::min(RPs_needed, RPs_per_turn_limit), rp_still_available[dp_turns-1]);
275 progress += RPs_to_spend / std::max(EPSILON, tech_cost);
276 dpsim_research_progress[cur_tech] = progress;
277 rp_still_available[dp_turns-1] -= RPs_to_spend;
278 auto next_res_tech_it = cur_tech_it;
279 int next_res_tech_idx;
280 if (++next_res_tech_it == dp_researchable_techs.end()) {
281 next_res_tech_idx = m_queue.size()+1;
282 } else {
283 next_res_tech_idx = *(next_res_tech_it);
284 }
285
286 if (tech_cost - EPSILON <= progress * tech_cost) {
287 dpsim_tech_status_map[tech_name] = TS_COMPLETE;
288 dpsimulation_results[cur_tech] = dp_turns;
289 #ifndef ORIG_RES_SIMULATOR
290 m_queue[cur_tech].turns_left = dp_turns;
291 #endif
292 dp_researchable_techs.erase(cur_tech_it);
293 std::set<std::string> unlocked_techs;
294 if (tech)
295 unlocked_techs = tech->UnlockedTechs();
296 for (std::string u_tech_name : unlocked_techs) {
297 auto prereq_tech_it = waiting_for_prereqs.find(u_tech_name);
298 if (prereq_tech_it != waiting_for_prereqs.end() ){
299 std::set<std::string>& these_prereqs = prereq_tech_it->second;
300 auto just_finished_it = these_prereqs.find(tech_name);
301 if (just_finished_it != these_prereqs.end() ) { //should always find it
302 these_prereqs.erase(just_finished_it);
303 if (these_prereqs.empty()) { // tech now fully unlocked
304 int this_tech_idx = orig_queue_order[u_tech_name];
305 dp_researchable_techs.insert(this_tech_idx);
306 waiting_for_prereqs.erase(prereq_tech_it);
307 already_processed[this_tech_idx] = true; //doesn't get any allocation on current turn
308 if (this_tech_idx < next_res_tech_idx ) {
309 next_res_tech_idx = this_tech_idx;
310 }
311 }
312 } else { //couldnt find tech_name in prereqs list
313 DebugLogger() << "ResearchQueue::Update tech unlocking problem:"<< tech_name << "thought it was a prereq for " << u_tech_name << "but the latter disagreed";
314 }
315 } //else { //tech_name thinks itself a prereq for ytechName, but u_tech_name not in prereqs -- not a problem so long as u_tech_name not in our queue at all
316 // DebugLogger() << "ResearchQueue::Update tech unlocking problem:"<< tech_name << "thought it was a prereq for " << u_tech_name << "but the latter disagreed";
317 //}
318 }
319 }// if (tech->ResearchCost() - EPSILON <= progress * tech_cost)
320 cur_tech_it = dp_researchable_techs.find(next_res_tech_idx);
321 }//while ((rp_still_available[dp_turns-1]> EPSILON))
322 //dp_time = dpsim_queue_timer.elapsed() * 1000;
323 // DebugLogger() << "ProductionQueue::Update queue dynamic programming sim time: " << dpsim_queue_timer.elapsed() * 1000.0;
324 } // while ((dp_turns < DP_TURNS ) && !(dp_researchable_techs.empty() ) )
325
326 ResearchQueueChangedSignal();
327 }
328
push_back(const std::string & tech_name,bool paused)329 void ResearchQueue::push_back(const std::string& tech_name, bool paused)
330 { m_queue.push_back(Element(tech_name, m_empire_id, 0.0f, -1, paused)); }
331
insert(iterator it,const std::string & tech_name,bool paused)332 void ResearchQueue::insert(iterator it, const std::string& tech_name, bool paused)
333 { m_queue.insert(it, Element(tech_name, m_empire_id, 0.0f, -1, paused)); }
334
erase(iterator it)335 void ResearchQueue::erase(iterator it) {
336 if (it == end())
337 throw std::out_of_range("Tried to erase ResearchQueue element out of bounds");
338 m_queue.erase(it);
339 }
340
find(const std::string & tech_name)341 ResearchQueue::iterator ResearchQueue::find(const std::string& tech_name) {
342 for (iterator it = begin(); it != end(); ++it) {
343 if (it->name == tech_name)
344 return it;
345 }
346 return end();
347 }
348
begin()349 ResearchQueue::iterator ResearchQueue::begin()
350 { return m_queue.begin(); }
351
end()352 ResearchQueue::iterator ResearchQueue::end()
353 { return m_queue.end(); }
354
clear()355 void ResearchQueue::clear() {
356 m_queue.clear();
357 m_projects_in_progress = 0;
358 m_total_RPs_spent = 0.0f;
359 ResearchQueueChangedSignal();
360 }
361