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