The Battle for Wesnoth  1.17.10+dev
attack_prediction.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2006 - 2022
3  by Rusty Russell <rusty@rustcorp.com.au>
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  * Simulate combat to calculate attacks.
19  * This can be compiled as a stand-alone program to either verify
20  * correctness or to benchmark performance.
21  *
22  * Compile with -O3 -DBENCHMARK for speed testing, and with -DCHECK for
23  * testing correctness (redirect the output to a file, then compile
24  * utils/wesnoth-attack-sim.c and run that with the arguments
25  * --check <file name>).
26  * For either option, use -DHUMAN_READABLE if you want to see the results
27  * from each combat displayed in a prettier format (but no longer suitable
28  * for wesnoth-attack-sim.c).
29  */
30 
31 #include "attack_prediction.hpp"
32 
33 #include "actions/attack.hpp"
34 #include "game_config.hpp"
35 #include "log.hpp"
36 #include "preferences/general.hpp"
37 #include "random.hpp"
39 
40 #include <array>
41 #include <cfloat>
42 #include <cmath>
43 #include <memory>
44 #include <numeric>
45 #include <sstream>
46 
47 #if defined(BENCHMARK) || defined(CHECK)
48 #include <chrono>
49 #include <cstdio>
50 #include <cstdlib>
51 #endif
52 
53 #ifdef ATTACK_PREDICTION_DEBUG
54 #define debug(x) printf x
55 #else
56 #define debug(x)
57 #endif
58 
59 #ifdef ATTACK_PREDICTION_DEBUG
60 namespace
61 {
62 /** Prints the attack statistics of a unit to cout. */
63 void dump(const battle_context_unit_stats& stats)
64 {
65  std::ostringstream ss;
66 
67  ss << "==================================";
68  << std::boolalpha
69  << "\n" << "is_attacker: " << stats.is_attacker
70  << "\n" << "is_poisoned: " << stats.is_poisoned
71  << "\n" << "is_slowed: " << stats.is_slowed
72  << "\n" << "slows: " << stats.slows
73  << "\n" << "drains: " << stats.drains
74  << "\n" << "petrifies: " << stats.petrifies
75  << "\n" << "poisons: " << stats.poisons
76  << "\n" << "swarm: " << stats.swarm
77  << "\n" << "firststrike: " << stats.firststrike
78  << std::noboolalpha
79  << "\n" << "rounds: " << stats.rounds
80  << "\n\n"
81  << "\n" << "hp: " << stats.hp
82  << "\n" << "max_hp: " << stats.max_hp
83  << "\n" << "chance_to_hit: " << stats.chance_to_hit
84  << "\n" << "damage: " << stats.damage
85  << "\n" << "slow_damage: " << stats.slow_damage
86  << "\n" << "drain_percent: " << stats.drain_percent
87  << "\n" << "drain_constant: " << stats.drain_constant
88  << "\n" << "num_blows: " << stats.num_blows
89  << "\n" << "swarm_min: " << stats.swarm_min
90  << "\n" << "swarm_max: " << stats.swarm_max
91  << "\n\n";
92 
93  std::cout << ss.rdbuf() << std::endl;
94 }
95 }
96 #endif
97 
98 namespace
99 {
100 using summary_t = std::array<std::vector<double>, 2>;
101 
102 /**
103 * A struct to describe one possible combat scenario.
104 * (Needed when the number of attacks can vary due to swarm.)
105 */
106 struct combat_slice
107 {
108  // The hit point range this slice covers.
109  unsigned begin_hp; // included in the range.
110  unsigned end_hp; // excluded from the range.
111 
112  // The probability of this slice.
113  double prob;
114 
115  // The number of strikes applicable with this slice.
116  unsigned strikes;
117 
118  combat_slice(
119  const summary_t& src_summary, unsigned begin, unsigned end, unsigned num_strikes);
120  combat_slice(const summary_t& src_summary, unsigned num_strikes);
121 };
122 
123 /**
124 * Creates a slice from a summary, and associates a number of strikes.
125 */
126 combat_slice::combat_slice(
127  const summary_t& src_summary, unsigned begin, unsigned end, unsigned num_strikes)
128  : begin_hp(begin)
129  , end_hp(end)
130  , prob(0.0)
131  , strikes(num_strikes)
132 {
133  if(src_summary[0].empty()) {
134  // No summary; this should be the only slice.
135  prob = 1.0;
136  return;
137  }
138 
139  // Avoid accessing beyond the end of the vectors.
140  if(end > src_summary[0].size()) {
141  end = src_summary[0].size();
142  }
143 
144  // Sum the probabilities in the slice.
145  for(unsigned i = begin; i < end; ++i) {
146  prob += src_summary[0][i];
147  }
148 
149  if(!src_summary[1].empty()) {
150  for(unsigned i = begin; i < end; ++i) {
151  prob += src_summary[1][i];
152  }
153  }
154 }
155 
156 /**
157 * Creates a slice from the summaries, and associates a number of strikes.
158 * This version of the constructor creates a slice consisting of everything.
159 */
160 combat_slice::combat_slice(const summary_t& src_summary, unsigned num_strikes)
161  : begin_hp(0)
162  , end_hp(src_summary[0].size())
163  , prob(1.0)
164  , strikes(num_strikes)
165 {
166 }
167 
168 /**
169 * Returns the number of hit points greater than cur_hp, and at most
170 * stats.max_hp+1, at which the unit would get another attack because
171 * of swarm.
172 * Helper function for split_summary().
173 */
174 unsigned hp_for_next_attack(unsigned cur_hp, const battle_context_unit_stats& stats)
175 {
176  unsigned old_strikes = stats.calc_blows(cur_hp);
177 
178  // A formula would have to deal with rounding issues; instead
179  // loop until we find more strikes.
180  while(++cur_hp <= stats.max_hp) {
181  if(stats.calc_blows(cur_hp) != old_strikes) {
182  break;
183  }
184  }
185 
186  return cur_hp;
187 }
188 
189 /**
190 * Split the combat by number of attacks per combatant (for swarm).
191 * This also clears the current summaries.
192 */
193 std::vector<combat_slice> split_summary(
194  const battle_context_unit_stats& unit_stats, summary_t& summary)
195 {
196  std::vector<combat_slice> result;
197 
198  if(unit_stats.swarm_min == unit_stats.swarm_max || summary[0].empty()) {
199  // We use the same number of blows for all possibilities.
200  result.emplace_back(summary, unit_stats.num_blows);
201  return result;
202  }
203 
204  debug(("Slicing:\n"));
205  // Loop through our slices.
206  unsigned cur_end = 0;
207  do {
208  // Advance to the next slice.
209  const unsigned cur_begin = cur_end;
210  cur_end = hp_for_next_attack(cur_begin, unit_stats);
211 
212  // Add this slice.
213  combat_slice slice(summary, cur_begin, cur_end, unit_stats.calc_blows(cur_begin));
214  if(slice.prob != 0.0) {
215  result.push_back(slice);
216  debug(("\t%2u-%2u hp; strikes: %u; probability: %6.2f\n", cur_begin, cur_end, slice.strikes,
217  slice.prob * 100.0));
218  }
219  } while(cur_end <= unit_stats.max_hp);
220 
221  return result;
222 }
223 
224 /**
225  * A matrix of A's hitpoints vs B's hitpoints vs. their slowed states.
226  * This class is concerned only with the matrix implementation and
227  * implements functionality for shifting and retrieving probabilities
228  * (i.e. low-level stuff).
229  */
230 class prob_matrix
231 {
232  // Since this gets used very often (especially by the AI), it has
233  // been optimized for speed as a sparse matrix.
234 public:
235  prob_matrix(unsigned int a_max,
236  unsigned int b_max,
237  bool need_a_slowed,
238  bool need_b_slowed,
239  unsigned int a_cur,
240  unsigned int b_cur,
241  const summary_t& a_initial,
242  const summary_t& b_initial);
243 
244  // Shift columns on this plane (b taking damage).
245  void shift_cols(unsigned dst, unsigned src, unsigned damage, double prob, int drain_constant, int drain_percent);
246  // Shift rows on this plane (a taking damage).
247  void shift_rows(unsigned dst, unsigned src, unsigned damage, double prob, int drain_constant, int drain_percent);
248 
249  /** Move a column (adding it to the destination). */
250  void move_column(unsigned d_plane, unsigned s_plane, unsigned d_col, unsigned s_col);
251  /** Move a row (adding it to the destination). */
252  void move_row(unsigned d_plane, unsigned s_plane, unsigned d_row, unsigned s_row);
253 
254  // Move values within a row (or column) to a specified column (or row).
255  void merge_col(unsigned d_plane, unsigned s_plane, unsigned col, unsigned d_row);
256  void merge_cols(unsigned d_plane, unsigned s_plane, unsigned d_row);
257  void merge_row(unsigned d_plane, unsigned s_plane, unsigned row, unsigned d_col);
258  void merge_rows(unsigned d_plane, unsigned s_plane, unsigned d_col);
259 
260  // Set all values to zero and clear the lists of used columns/rows.
261  void clear();
262 
263  // Record the result of a single Monte Carlo simulation iteration.
264  void record_monte_carlo_result(unsigned int a_hp, unsigned int b_hp, bool a_slowed, bool b_slowed);
265 
266  // Returns the index of the plane with the given slow statuses.
267  static unsigned int plane_index(bool a_slowed, bool b_slowed)
268  {
269  return (a_slowed ? 1 : 0) + (b_slowed ? 2 : 0);
270  }
271 
272  /** What is the chance that an indicated combatant (one of them) is at zero? */
273  double prob_of_zero(bool check_a, bool check_b) const;
274  /** Sums the values in the specified row. */
275  double row_sum(unsigned plane, unsigned row) const;
276  /** Sums the values in the specified column. */
277  double col_sum(unsigned plane, unsigned column) const;
278  /** Sums the values in the specified plane. */
279  void sum(unsigned plane, std::vector<double>& row_sums, std::vector<double>& col_sums) const;
280 
281  /** Returns true if the specified plane might have data in it. */
282  bool plane_used(unsigned p) const
283  {
284  return p < NUM_PLANES && plane_[p] != nullptr;
285  }
286 
287  unsigned int num_rows() const
288  {
289  return rows_;
290  }
291  unsigned int num_cols() const
292  {
293  return cols_;
294  }
295 
296  // Debugging tool.
297  void dump() const;
298 
299  // We need four matrices, or "planes", reflecting the possible
300  // "slowed" states (neither slowed, A slowed, B slowed, both slowed).
301  enum {
302  NEITHER_SLOWED,
303  A_SLOWED,
304  B_SLOWED,
305  BOTH_SLOWED,
306  NUM_PLANES // Symbolic constant for the number of planes.
307  };
308 
309 private:
310  // This gives me 10% speed improvement over std::vector<> (g++4.0.3 x86)
311  std::unique_ptr<double[]> new_plane() const;
312 
313  void initialize_plane(unsigned plane,
314  unsigned a_cur,
315  unsigned b_cur,
316  const std::vector<double>& a_initial,
317  const std::vector<double>& b_initial);
318  void initialize_row(
319  unsigned plane, unsigned row, double row_prob, unsigned b_cur, const std::vector<double>& b_initial);
320 
321  double& val(unsigned plane, unsigned row, unsigned col);
322  const double& val(unsigned plane, unsigned row, unsigned col) const;
323 
324  /** Transfers a portion (value * prob) of one value in the matrix to another. */
325  void xfer(unsigned dst_plane,
326  unsigned src_plane,
327  unsigned row_dst,
328  unsigned col_dst,
329  unsigned row_src,
330  unsigned col_src,
331  double prob);
332  /** Transfers one value in the matrix to another. */
333  void xfer(unsigned dst_plane,
334  unsigned src_plane,
335  unsigned row_dst,
336  unsigned col_dst,
337  unsigned row_src,
338  unsigned col_src);
339 
340  void shift_cols_in_row(unsigned dst,
341  unsigned src,
342  unsigned row,
343  const std::vector<unsigned>& cols,
344  unsigned damage,
345  double prob,
346  int drainmax,
347  int drain_constant,
348  int drain_percent);
349  void shift_rows_in_col(unsigned dst,
350  unsigned src,
351  unsigned col,
352  const std::vector<unsigned>& rows,
353  unsigned damage,
354  double prob,
355  int drainmax,
356  int drain_constant,
357  int drain_percent);
358 
359 private: // data
360  const unsigned int rows_, cols_;
361  std::array<std::unique_ptr<double[]>, NUM_PLANES> plane_;
362 
363  // For optimization, we keep track of the rows and columns with data.
364  // (The matrices are likely going to be rather sparse, with data on a grid.)
365  std::array<std::set<unsigned>, NUM_PLANES> used_rows_, used_cols_;
366 };
367 
368 /**
369  * Constructor.
370  * @param a_max The maximum value we will track for A.
371  * @param b_max The maximum value we will track for B.
372  * @param need_a_slowed Set to true if there might be transfers to a "slow" plane for A.
373  * @param need_b_slowed Set to true if there might be transfers to a "slow" plane for B.
374  * @param a_cur The current value for A. (Ignored if a_initial[0] is not empty.)
375  * @param b_cur The current value for B. (Ignored if b_initial[0] is not empty.)
376  * @param a_initial The initial distribution of values for A. Element [0] is for normal A. while [1] is for slowed
377  * A.
378  * @param b_initial The initial distribution of values for B. Element [0] is for normal B. while [1] is for slowed
379  * B.
380  */
381 prob_matrix::prob_matrix(unsigned int a_max,
382  unsigned int b_max,
383  bool need_a_slowed,
384  bool need_b_slowed,
385  unsigned int a_cur,
386  unsigned int b_cur,
387  const summary_t& a_initial,
388  const summary_t& b_initial)
389  : rows_(a_max + 1)
390  , cols_(b_max + 1)
391  , plane_()
392  , used_rows_()
393  , used_cols_()
394 {
395  // Make sure we do not access the matrix in invalid positions.
396  a_cur = std::min<unsigned int>(a_cur, rows_ - 1);
397  b_cur = std::min<unsigned int>(b_cur, cols_ - 1);
398 
399  // It will be convenient to always consider row/col 0 to be used.
400  for(unsigned plane = 0; plane != NUM_PLANES; ++plane) {
401  used_rows_[plane].insert(0u);
402  used_cols_[plane].insert(0u);
403  }
404 
405  // We will need slowed planes if the initial vectors have them.
406  need_a_slowed = need_a_slowed || !a_initial[1].empty();
407  need_b_slowed = need_b_slowed || !b_initial[1].empty();
408 
409  // Allocate the needed planes.
410  plane_[NEITHER_SLOWED] = new_plane();
411  plane_[A_SLOWED] = !need_a_slowed ? nullptr : new_plane();
412  plane_[B_SLOWED] = !need_b_slowed ? nullptr : new_plane();
413  plane_[BOTH_SLOWED] = !(need_a_slowed && need_b_slowed) ? nullptr : new_plane();
414 
415  // Initialize the probability distribution.
416  initialize_plane(NEITHER_SLOWED, a_cur, b_cur, a_initial[0], b_initial[0]);
417 
418  if(!a_initial[1].empty()) {
419  initialize_plane(A_SLOWED, a_cur, b_cur, a_initial[1], b_initial[0]);
420  }
421 
422  if(!b_initial[1].empty()) {
423  initialize_plane(B_SLOWED, a_cur, b_cur, a_initial[0], b_initial[1]);
424  }
425 
426  if(!a_initial[1].empty() && !b_initial[1].empty()) {
427  initialize_plane(BOTH_SLOWED, a_cur, b_cur, a_initial[1], b_initial[1]);
428  }
429 
430  // Some debugging messages.
431  if(!a_initial[0].empty()) {
432  debug(("A has fought before (or is slowed).\n"));
433  dump();
434  }
435 
436  if(!b_initial[0].empty()) {
437  debug(("B has fought before (or is slowed).\n"));
438  dump();
439  }
440 }
441 
442 /** Allocate a new probability array, initialized to 0. */
443 std::unique_ptr<double[]> prob_matrix::new_plane() const
444 {
445  const unsigned int size = rows_ * cols_;
446  std::unique_ptr<double[]> res(new double[size]);
447  std::fill_n(res.get(), size, 0);
448  return res;
449 }
450 
451 /**
452  * Fills the indicated plane with its initial (non-zero) values.
453  * (Part of construction)
454  * @param plane The plane to initialize.
455  * @param a_cur The current value for A. (Ignored if a_initial is not empty.)
456  * @param b_cur The current value for B. (Ignored if b_initial is not empty.)
457  * @param a_initial The initial distribution of values for A for this plane.
458  * @param b_initial The initial distribution of values for B for this plane.
459  */
460 void prob_matrix::initialize_plane(unsigned plane,
461  unsigned a_cur,
462  unsigned b_cur,
463  const std::vector<double>& a_initial,
464  const std::vector<double>& b_initial)
465 {
466  if(!a_initial.empty()) {
467  unsigned row_count = std::min<unsigned>(a_initial.size(), rows_);
468  // The probabilities for each row are contained in a_initial.
469  for(unsigned row = 0; row < row_count; ++row) {
470  if(a_initial[row] != 0.0) {
471  used_rows_[plane].insert(row);
472  initialize_row(plane, row, a_initial[row], b_cur, b_initial);
473  }
474  }
475  } else {
476  used_rows_[plane].insert(a_cur);
477  // Only the row indicated by a_cur is a possibility.
478  initialize_row(plane, a_cur, 1.0, b_cur, b_initial);
479  }
480 }
481 
482 /**
483  * Fills the indicated row with its initial (non-zero) values.
484  * (Part of construction)
485  * @param plane The plane containing the row to initialize.
486  * @param row The row to initialize.
487  * @param row_prob The probability of A having the value for this row.
488  * @param b_cur The current value for B. (Ignored if b_initial is not empty.)
489  * @param b_initial The initial distribution of values for B for this plane.
490  */
491 void prob_matrix::initialize_row(
492  unsigned plane, unsigned row, double row_prob, unsigned b_cur, const std::vector<double>& b_initial)
493 {
494  if(!b_initial.empty()) {
495  unsigned col_count = std::min<unsigned>(b_initial.size(), cols_);
496  // The probabilities for each column are contained in b_initial.
497  for(unsigned col = 0; col < col_count; ++col) {
498  if(b_initial[col] != 0.0) {
499  used_cols_[plane].insert(col);
500  val(plane, row, col) = row_prob * b_initial[col];
501  }
502  }
503  } else {
504  // Only the column indicated by b_cur is a possibility.
505  used_cols_[plane].insert(b_cur);
506  val(plane, row, b_cur) = row_prob;
507  }
508 }
509 
510 double& prob_matrix::val(unsigned plane, unsigned row, unsigned col)
511 {
512  assert(row < rows_);
513  assert(col < cols_);
514  return plane_[plane][row * cols_ + col];
515 }
516 
517 const double& prob_matrix::val(unsigned plane, unsigned row, unsigned col) const
518 {
519  assert(row < rows_);
520  assert(col < cols_);
521  return plane_[plane][row * cols_ + col];
522 }
523 
524 // xfer, shift_cols and shift_rows use up most of our time. Careful!
525 /**
526  * Transfers a portion (value * prob) of one value in the matrix to another.
527  */
528 void prob_matrix::xfer(unsigned dst_plane,
529  unsigned src_plane,
530  unsigned row_dst,
531  unsigned col_dst,
532  unsigned row_src,
533  unsigned col_src,
534  double prob)
535 {
536  double& src = val(src_plane, row_src, col_src);
537  if(src != 0.0) {
538  double diff = src * prob;
539  src -= diff;
540 
541  double& dst = val(dst_plane, row_dst, col_dst);
542  if(dst == 0.0) {
543  // Track that this entry is now used.
544  used_rows_[dst_plane].insert(row_dst);
545  used_cols_[dst_plane].insert(col_dst);
546  }
547  dst += diff;
548 
549  debug(("Shifted %4.3g from %s(%u,%u) to %s(%u,%u).\n", diff,
550  src_plane == NEITHER_SLOWED
551  ? ""
552  : src_plane == A_SLOWED
553  ? "[A_SLOWED]"
554  : src_plane == B_SLOWED
555  ? "[B_SLOWED]"
556  : src_plane == BOTH_SLOWED
557  ? "[BOTH_SLOWED]"
558  : "INVALID",
559 
560  row_src, col_src,
561  dst_plane == NEITHER_SLOWED
562  ? ""
563  : dst_plane == A_SLOWED
564  ? "[A_SLOWED]"
565  : dst_plane == B_SLOWED
566  ? "[B_SLOWED]"
567  : dst_plane == BOTH_SLOWED
568  ? "[BOTH_SLOWED]"
569  : "INVALID",
570  row_dst, col_dst)
571  );
572  }
573 }
574 
575 /**
576  * Transfers one value in the matrix to another.
577  */
578 void prob_matrix::xfer(
579  unsigned dst_plane, unsigned src_plane, unsigned row_dst, unsigned col_dst, unsigned row_src, unsigned col_src)
580 {
581  if(dst_plane == src_plane && row_dst == row_src && col_dst == col_src)
582  // Transferring to itself. Nothing to do.
583  return;
584 
585  double& src = val(src_plane, row_src, col_src);
586  if(src != 0.0) {
587  debug(("Shifting %4.3g from %s(%u,%u) to %s(%u,%u).\n", src,
588  src_plane == NEITHER_SLOWED
589  ? ""
590  : src_plane == A_SLOWED
591  ? "[A_SLOWED]"
592  : src_plane == B_SLOWED
593  ? "[B_SLOWED]"
594  : src_plane == BOTH_SLOWED
595  ? "[BOTH_SLOWED]"
596  : "INVALID",
597  row_src, col_src,
598  dst_plane == NEITHER_SLOWED
599  ? ""
600  : dst_plane == A_SLOWED
601  ? "[A_SLOWED]"
602  : dst_plane == B_SLOWED
603  ? "[B_SLOWED]"
604  : dst_plane == BOTH_SLOWED
605  ? "[BOTH_SLOWED]"
606  : "INVALID",
607  row_dst, col_dst)
608  );
609 
610  double& dst = val(dst_plane, row_dst, col_dst);
611  if(dst == 0.0) {
612  // Track that this entry is now used.
613  used_rows_[dst_plane].insert(row_dst);
614  used_cols_[dst_plane].insert(col_dst);
615  }
616 
617  dst += src;
618  src = 0.0;
619  }
620 }
621 
622 /**
623  * Transfers a portion (value * prob) of the values in a row to another.
624  * Part of shift_cols().
625  */
626 void prob_matrix::shift_cols_in_row(unsigned dst,
627  unsigned src,
628  unsigned row,
629  const std::vector<unsigned>& cols,
630  unsigned damage,
631  double prob,
632  int drainmax,
633  int drain_constant,
634  int drain_percent)
635 {
636  // Some conversions to (signed) int.
637  int row_i = static_cast<int>(row);
638  int max_row = static_cast<int>(rows_) - 1;
639 
640  // cols[0] is excluded since that should be 0, representing already dead.
641  unsigned col_x = 1;
642 
643  // Killing blows can have different drain amounts, so handle them first
644  for(; col_x < cols.size() && cols[col_x] < damage; ++col_x) {
645  // These variables are not strictly necessary, but they make the
646  // calculation easier to parse.
647  int col_i = static_cast<int>(cols[col_x]);
648  int drain_amount = col_i * drain_percent / 100 + drain_constant;
649  unsigned newrow = std::clamp(row_i + drain_amount, 1, max_row);
650  xfer(dst, src, newrow, 0, row, cols[col_x], prob);
651  }
652 
653  // The remaining columns use the specified drainmax.
654  unsigned newrow = std::clamp(row_i + drainmax, 1, max_row);
655  for(; col_x < cols.size(); ++col_x) {
656  xfer(dst, src, newrow, cols[col_x] - damage, row, cols[col_x], prob);
657  }
658 }
659 
660 /**
661  * Transfers a portion (value * prob) of each column in a plane to another.
662  * Each column in the @a src plane gets shifted @a damage columns towards 0, and
663  * also shifted into the @a dst plane. In addition, the rows can shift if
664  * @a drain constant or @a drain_percent is nonzero.
665  */
666 void prob_matrix::shift_cols(
667  unsigned dst, unsigned src, unsigned damage, double prob, int drain_constant, int drain_percent)
668 {
669  int drainmax = (drain_percent * (static_cast<signed>(damage)) / 100 + drain_constant);
670 
671  if(drain_constant || drain_percent) {
672  debug(("Drains %i (%i%% of %u plus %i)\n", drainmax, drain_percent, damage, drain_constant));
673  }
674 
675  // Get lists of indices currently used in the source plane.
676  // (This needs to be cached since we might add indices while shifting.)
677  const std::vector<unsigned> rows(used_rows_[src].begin(), used_rows_[src].end());
678  const std::vector<unsigned> cols(used_cols_[src].begin(), used_cols_[src].end());
679 
680  // Loop downwards if we drain positive, but upwards if we drain negative,
681  // so we write behind us (for when src == dst).
682  if(drainmax > 0) {
683  // rows[0] is excluded since that should be 0, representing already dead.
684  for(unsigned row_x = rows.size() - 1; row_x != 0; --row_x) {
685  shift_cols_in_row(dst, src, rows[row_x], cols, damage, prob, drainmax, drain_constant, drain_percent);
686  }
687  } else {
688  // rows[0] is excluded since that should be 0, representing already dead.
689  for(unsigned row_x = 1; row_x != rows.size(); ++row_x) {
690  shift_cols_in_row(dst, src, rows[row_x], cols, damage, prob, drainmax, drain_constant, drain_percent);
691  }
692  }
693 }
694 
695 /**
696  * Transfers a portion (value * prob) of the values in a column to another.
697  * Part of shift_rows().
698  */
699 void prob_matrix::shift_rows_in_col(unsigned dst,
700  unsigned src,
701  unsigned col,
702  const std::vector<unsigned>& rows,
703  unsigned damage,
704  double prob,
705  int drainmax,
706  int drain_constant,
707  int drain_percent)
708 {
709  // Some conversions to (signed) int.
710  int col_i = static_cast<int>(col);
711  int max_col = static_cast<int>(cols_) - 1;
712 
713  // rows[0] is excluded since that should be 0, representing already dead.
714  unsigned row_x = 1;
715 
716  // Killing blows can have different drain amounts, so handle them first
717  for(; row_x < rows.size() && rows[row_x] < damage; ++row_x) {
718  // These variables are not strictly necessary, but they make the
719  // calculation easier to parse.
720  int row_i = static_cast<int>(rows[row_x]);
721  int drain_amount = row_i * drain_percent / 100 + drain_constant;
722  unsigned newcol = std::clamp(col_i + drain_amount, 1, max_col);
723  xfer(dst, src, 0, newcol, rows[row_x], col, prob);
724  }
725 
726  // The remaining rows use the specified drainmax.
727  unsigned newcol = std::clamp(col_i + drainmax, 1, max_col);
728  for(; row_x < rows.size(); ++row_x) {
729  xfer(dst, src, rows[row_x] - damage, newcol, rows[row_x], col, prob);
730  }
731 }
732 
733 /**
734  * Transfers a portion (value * prob) of each row in a plane to another.
735  * Each row in the @a src plane gets shifted @a damage columns towards 0, and
736  * also shifted into the @a dst plane. In addition, the columns can shift if
737  * @a drain constant or @a drain_percent is nonzero.
738  */
739 void prob_matrix::shift_rows(
740  unsigned dst, unsigned src, unsigned damage, double prob, int drain_constant, int drain_percent)
741 {
742  int drainmax = (drain_percent * (static_cast<signed>(damage)) / 100 + drain_constant);
743 
744  if(drain_constant || drain_percent) {
745  debug(("Drains %i (%i%% of %u plus %i)\n", drainmax, drain_percent, damage, drain_constant));
746  }
747 
748  // Get lists of indices currently used in the source plane.
749  // (This needs to be cached since we might add indices while shifting.)
750  const std::vector<unsigned> rows(used_rows_[src].begin(), used_rows_[src].end());
751  const std::vector<unsigned> cols(used_cols_[src].begin(), used_cols_[src].end());
752 
753  // Loop downwards if we drain positive, but upwards if we drain negative,
754  // so we write behind us (for when src == dst).
755  if(drainmax > 0) {
756  // cols[0] is excluded since that should be 0, representing already dead.
757  for(unsigned col_x = cols.size() - 1; col_x != 0; --col_x)
758  shift_rows_in_col(dst, src, cols[col_x], rows, damage, prob, drainmax, drain_constant, drain_percent);
759  } else {
760  // cols[0] is excluded since that should be 0, representing already dead.
761  for(unsigned col_x = 1; col_x != cols.size(); ++col_x) {
762  shift_rows_in_col(dst, src, cols[col_x], rows, damage, prob, drainmax, drain_constant, drain_percent);
763  }
764  }
765 }
766 
767 /**
768  * Move a column (adding it to the destination).
769  */
770 void prob_matrix::move_column(unsigned d_plane, unsigned s_plane, unsigned d_col, unsigned s_col)
771 {
772  // Transfer the data.
773  for(const unsigned& row : used_rows_[s_plane]) {
774  xfer(d_plane, s_plane, row, d_col, row, s_col);
775  }
776 }
777 
778 /**
779  * Move a row (adding it to the destination).
780  */
781 void prob_matrix::move_row(unsigned d_plane, unsigned s_plane, unsigned d_row, unsigned s_row)
782 {
783  // Transfer the data.
784  for(const unsigned& col : used_cols_[s_plane]) {
785  xfer(d_plane, s_plane, d_row, col, s_row, col);
786  }
787 }
788 
789 /**
790  * Move values in the specified column -- excluding row zero -- to the
791  * specified row in that column (possibly shifting planes in the process).
792  */
793 void prob_matrix::merge_col(unsigned d_plane, unsigned s_plane, unsigned col, unsigned d_row)
794 {
795  auto rows_end = used_rows_[s_plane].end();
796  auto row_it = used_rows_[s_plane].begin();
797 
798  // Transfer the data, excluding row zero.
799  for(++row_it; row_it != rows_end; ++row_it) {
800  xfer(d_plane, s_plane, d_row, col, *row_it, col);
801  }
802 }
803 
804 /**
805  * Move values within columns in the specified plane -- excluding row zero --
806  * to the specified row (possibly shifting planes in the process).
807  */
808 void prob_matrix::merge_cols(unsigned d_plane, unsigned s_plane, unsigned d_row)
809 {
810  auto rows_end = used_rows_[s_plane].end();
811  auto row_it = used_rows_[s_plane].begin();
812 
813  // Transfer the data, excluding row zero.
814  for(++row_it; row_it != rows_end; ++row_it) {
815  for(const unsigned& col : used_cols_[s_plane]) {
816  xfer(d_plane, s_plane, d_row, col, *row_it, col);
817  }
818  }
819 }
820 
821 /**
822  * Move values in the specified row -- excluding column zero -- to the
823  * specified column in that row (possibly shifting planes in the process).
824  */
825 void prob_matrix::merge_row(unsigned d_plane, unsigned s_plane, unsigned row, unsigned d_col)
826 {
827  auto cols_end = used_cols_[s_plane].end();
828  auto col_it = used_cols_[s_plane].begin();
829 
830  // Transfer the data, excluding column zero.
831  for(++col_it; col_it != cols_end; ++col_it) {
832  xfer(d_plane, s_plane, row, d_col, row, *col_it);
833  }
834 }
835 
836 /**
837  * Move values within rows in the specified plane -- excluding column zero --
838  * to the specified column (possibly shifting planes in the process).
839  */
840 void prob_matrix::merge_rows(unsigned d_plane, unsigned s_plane, unsigned d_col)
841 {
842  auto cols_end = used_cols_[s_plane].end();
843  // Exclude column zero.
844  auto cols_begin = std::next(used_cols_[s_plane].begin());
845 
846  // Transfer the data, excluding column zero.
847  for(const unsigned row : used_rows_[s_plane]) {
848  for(auto col_it = cols_begin; col_it != cols_end; ++col_it) {
849  xfer(d_plane, s_plane, row, d_col, row, *col_it);
850  }
851  }
852 }
853 
854 /**
855  * Set all values to zero and clear the lists of used columns/rows.
856  */
857 void prob_matrix::clear()
858 {
859  for(unsigned int p = 0u; p < NUM_PLANES; ++p) {
860  if(!plane_used(p)) {
861  continue;
862  }
863 
864  if(used_rows_[p].empty()) {
865  // Nothing to do
866  continue;
867  }
868 
869  auto [first_row, last_row] = std::minmax_element(used_rows_[p].begin(), used_rows_[p].end());
870  for(unsigned int r = *first_row; r <= *last_row; ++r) {
871  for(unsigned int c = 0u; c < cols_; ++c) {
872  plane_[p][r * cols_ + c] = 0.0;
873  }
874  }
875 
876  used_rows_[p].clear();
877  used_cols_[p].clear();
878 
879  /* Row and column 0 are always considered to be used.
880  Functions like merge_col() access *used_rows_[plane].begin() without checking if there are
881  any used rows: thus, ensuring that there are used rows and columns is necessary to avoid
882  memory corruption. */
883  used_rows_[p].insert(0u);
884  used_cols_[p].insert(0u);
885  }
886 }
887 
888 /**
889  * Record the result of a single Monte Carlo simulation iteration.
890  */
891 void prob_matrix::record_monte_carlo_result(unsigned int a_hp, unsigned int b_hp, bool a_slowed, bool b_slowed)
892 {
893  assert(a_hp <= rows_);
894  assert(b_hp <= cols_);
895  unsigned int plane = plane_index(a_slowed, b_slowed);
896  ++val(plane, a_hp, b_hp);
897  used_rows_[plane].insert(a_hp);
898  used_cols_[plane].insert(b_hp);
899 }
900 
901 /**
902  * What is the chance that an indicated combatant (one of them) is at zero?
903  */
904 double prob_matrix::prob_of_zero(bool check_a, bool check_b) const
905 {
906  double prob = 0.0;
907 
908  for(unsigned p = 0; p < NUM_PLANES; ++p) {
909  if(!plane_used(p)) {
910  continue;
911  }
912 
913  // Column 0 is where b is at zero.
914  if(check_b) {
915  for(const unsigned& row : used_rows_[p]) {
916  prob += val(p, row, 0);
917  }
918  }
919 
920  // Row 0 is where a is at zero.
921  if(check_a) {
922  for(const unsigned& col : used_cols_[p]) {
923  prob += val(p, 0, col);
924  }
925  }
926  // Theoretically, if checking both, we should subtract the chance that
927  // both are dead, but that chance is zero, so don't worry about it.
928  }
929 
930  return prob;
931 }
932 
933 /**
934  * Sums the values in the specified row.
935  */
936 double prob_matrix::row_sum(unsigned plane, unsigned row) const
937 {
938  if(!plane_used(plane)) {
939  return 0.0;
940  }
941 
942  double sum = 0.0;
943  for(unsigned col : used_cols_[plane]) {
944  sum += val(plane, row, col);
945  }
946  return sum;
947 }
948 
949 /**
950  * Sums the values in the specified column.
951  */
952 double prob_matrix::col_sum(unsigned plane, unsigned column) const
953 {
954  if(!plane_used(plane)) {
955  return 0.0;
956  }
957 
958  double sum = 0.0;
959  for(unsigned row : used_rows_[plane]) {
960  sum += val(plane, row, column);
961  }
962  return sum;
963 }
964 
965 /**
966  * Sums the values in the specified plane.
967  * The sum of each row is added to the corresponding entry in row_sums.
968  * The sum of each column is added to the corresponding entry in col_sums.
969  */
970 void prob_matrix::sum(unsigned plane, std::vector<double>& row_sums, std::vector<double>& col_sums) const
971 {
972  for(const unsigned& row : used_rows_[plane]) {
973  for(const unsigned& col : used_cols_[plane]) {
974  const double& prob = val(plane, row, col);
975  row_sums[row] += prob;
976  col_sums[col] += prob;
977  }
978  }
979 }
980 
981 #if defined(CHECK) && defined(ATTACK_PREDICTION_DEBUG)
982 void prob_matrix::dump() const
983 {
984  unsigned int row, col, m;
985  const char* names[] {"NEITHER_SLOWED", "A_SLOWED", "B_SLOWED", "BOTH_SLOWED"};
986 
987  for(m = 0; m < NUM_PLANES; ++m) {
988  if(!plane_used(m)) {
989  continue;
990  }
991 
992  debug(("%s:\n", names[m]));
993  for(row = 0; row < rows_; ++row) {
994  debug((" "));
995  for(col = 0; col < cols_; ++col) {
996  debug(("%4.3g ", val(m, row, col) * 100));
997  }
998 
999  debug(("\n"));
1000  }
1001  }
1002 }
1003 #else
1004 void prob_matrix::dump() const
1005 {
1006 }
1007 #endif
1008 
1009 /**
1010  * A matrix for calculating the outcome of combat.
1011  * This class specifies the interface and functionality shared between
1012  * probability_combat_matrix and monte_carlo_combat_matrix.
1013  */
1014 class combat_matrix : protected prob_matrix
1015 {
1016 public:
1017  combat_matrix(unsigned int a_max_hp,
1018  unsigned int b_max_hp,
1019  unsigned int a_hp,
1020  unsigned int b_hp,
1021  const summary_t& a_summary,
1022  const summary_t& b_summary,
1023  bool a_slows,
1024  bool b_slows,
1025  unsigned int a_damage,
1026  unsigned int b_damage,
1027  unsigned int a_slow_damage,
1028  unsigned int b_slow_damage,
1029  int a_drain_percent,
1030  int b_drain_percent,
1031  int a_drain_constant,
1032  int b_drain_constant);
1033 
1034  virtual ~combat_matrix()
1035  {
1036  }
1037 
1038  // We lied: actually did less damage, adjust matrix.
1039  void remove_petrify_distortion_a(unsigned damage, unsigned slow_damage, unsigned b_hp);
1040  void remove_petrify_distortion_b(unsigned damage, unsigned slow_damage, unsigned a_hp);
1041 
1042  void forced_levelup_a();
1043  void conditional_levelup_a();
1044 
1045  void forced_levelup_b();
1046  void conditional_levelup_b();
1047 
1048  using prob_matrix::row_sum;
1049  using prob_matrix::col_sum;
1050 
1051  // Its over, and here's the bill.
1052  virtual void extract_results(
1053  summary_t& summary_a, summary_t& summary_b)
1054  = 0;
1055 
1056  void dump() const
1057  {
1058  prob_matrix::dump();
1059  }
1060 
1061 protected:
1062  unsigned a_max_hp_;
1063  bool a_slows_;
1064  unsigned a_damage_;
1065  unsigned a_slow_damage_;
1066  int a_drain_percent_;
1067  int a_drain_constant_;
1068 
1069  unsigned b_max_hp_;
1070  bool b_slows_;
1071  unsigned b_damage_;
1072  unsigned b_slow_damage_;
1073  int b_drain_percent_;
1074  int b_drain_constant_;
1075 };
1076 
1077 /**
1078  * Constructor.
1079  * @param a_max_hp The maximum hit points for A.
1080  * @param b_max_hp The maximum hit points for B.
1081  * @param a_slows Set to true if A slows B when A hits B.
1082  * @param b_slows Set to true if B slows A when B hits A.
1083  * @param a_hp The current hit points for A. (Ignored if a_summary[0] is not empty.)
1084  * @param b_hp The current hit points for B. (Ignored if b_summary[0] is not empty.)
1085  * @param a_summary The hit point distribution for A (from previous combats). Element [0] is for normal A. while
1086  * [1] is for slowed A.
1087  * @param b_summary The hit point distribution for B (from previous combats). Element [0] is for normal B. while
1088  * [1] is for slowed B.
1089  */
1090 
1091 combat_matrix::combat_matrix(unsigned int a_max_hp,
1092  unsigned int b_max_hp,
1093  unsigned int a_hp,
1094  unsigned int b_hp,
1095  const summary_t& a_summary,
1096  const summary_t& b_summary,
1097  bool a_slows,
1098  bool b_slows,
1099  unsigned int a_damage,
1100  unsigned int b_damage,
1101  unsigned int a_slow_damage,
1102  unsigned int b_slow_damage,
1103  int a_drain_percent,
1104  int b_drain_percent,
1105  int a_drain_constant,
1106  int b_drain_constant)
1107  // The inversion of the order of the *_slows parameters here is intentional.
1108  : prob_matrix(a_max_hp, b_max_hp, b_slows, a_slows, a_hp, b_hp, a_summary, b_summary)
1109  , a_max_hp_(a_max_hp)
1110  , a_slows_(a_slows)
1111  , a_damage_(a_damage)
1112  , a_slow_damage_(a_slow_damage)
1113  , a_drain_percent_(a_drain_percent)
1114  , a_drain_constant_(a_drain_constant)
1115  , b_max_hp_(b_max_hp)
1116  , b_slows_(b_slows)
1117  , b_damage_(b_damage)
1118  , b_slow_damage_(b_slow_damage)
1119  , b_drain_percent_(b_drain_percent)
1120  , b_drain_constant_(b_drain_constant)
1121 {
1122 }
1123 
1124 // We lied: actually did less damage, adjust matrix.
1125 void combat_matrix::remove_petrify_distortion_a(unsigned damage, unsigned slow_damage, unsigned b_hp)
1126 {
1127  for(int p = 0; p < NUM_PLANES; ++p) {
1128  if(!plane_used(p)) {
1129  continue;
1130  }
1131 
1132  // A is slow in planes 1 and 3.
1133  unsigned actual_damage = (p & 1) ? slow_damage : damage;
1134  if(b_hp > actual_damage) {
1135  // B was actually petrified, not killed.
1136  move_column(p, p, b_hp - actual_damage, 0);
1137  }
1138  }
1139 }
1140 
1141 void combat_matrix::remove_petrify_distortion_b(unsigned damage, unsigned slow_damage, unsigned a_hp)
1142 {
1143  for(int p = 0; p < NUM_PLANES; ++p) {
1144  if(!plane_used(p)) {
1145  continue;
1146  }
1147 
1148  // B is slow in planes 2 and 3.
1149  unsigned actual_damage = (p & 2) ? slow_damage : damage;
1150  if(a_hp > actual_damage) {
1151  // A was actually petrified, not killed.
1152  move_row(p, p, a_hp - actual_damage, 0);
1153  }
1154  }
1155 }
1156 
1157 void combat_matrix::forced_levelup_a()
1158 {
1159  /* Move all the values (except 0hp) of all the planes to the "fully healed"
1160  row of the planes unslowed for A. */
1161  for(int p = 0; p < NUM_PLANES; ++p) {
1162  if(plane_used(p)) {
1163  merge_cols(p & -2, p, a_max_hp_);
1164  }
1165  }
1166 }
1167 
1168 void combat_matrix::forced_levelup_b()
1169 {
1170  /* Move all the values (except 0hp) of all the planes to the "fully healed"
1171  column of planes unslowed for B. */
1172  for(int p = 0; p < NUM_PLANES; ++p) {
1173  if(plane_used(p)) {
1174  merge_rows(p & -3, p, b_max_hp_);
1175  }
1176  }
1177 }
1178 
1179 void combat_matrix::conditional_levelup_a()
1180 {
1181  /* Move the values of the first column (except 0hp) of all the
1182  planes to the "fully healed" row of the planes unslowed for A. */
1183  for(int p = 0; p < NUM_PLANES; ++p) {
1184  if(plane_used(p)) {
1185  merge_col(p & -2, p, 0, a_max_hp_);
1186  }
1187  }
1188 }
1189 
1190 void combat_matrix::conditional_levelup_b()
1191 {
1192  /* Move the values of the first row (except 0hp) of all the
1193  planes to the last column of the planes unslowed for B. */
1194  for(int p = 0; p < NUM_PLANES; ++p) {
1195  if(plane_used(p)) {
1196  merge_row(p & -3, p, 0, b_max_hp_);
1197  }
1198  }
1199 }
1200 
1201 /**
1202  * Implementation of combat_matrix that calculates exact probabilities of events.
1203  * Fast in "simple" fights (low number of strikes, low HP, and preferably no slow
1204  * or swarm effect), but can be unusably expensive in extremely complex situations.
1205  */
1206 class probability_combat_matrix : public combat_matrix
1207 {
1208 public:
1209  probability_combat_matrix(unsigned int a_max_hp,
1210  unsigned int b_max_hp,
1211  unsigned int a_hp,
1212  unsigned int b_hp,
1213  const summary_t& a_summary,
1214  const summary_t& b_summary,
1215  bool a_slows,
1216  bool b_slows,
1217  unsigned int a_damage,
1218  unsigned int b_damage,
1219  unsigned int a_slow_damage,
1220  unsigned int b_slow_damage,
1221  int a_drain_percent,
1222  int b_drain_percent,
1223  int a_drain_constant,
1224  int b_drain_constant);
1225 
1226  // A hits B.
1227  void receive_blow_b(double hit_chance);
1228  // B hits A. Why can't they just get along?
1229  void receive_blow_a(double hit_chance);
1230 
1231  /** What is the chance that one of the combatants is dead? */
1232  double dead_prob() const
1233  {
1234  return prob_of_zero(true, true);
1235  }
1236 
1237  /** What is the chance that combatant 'a' is dead? */
1238  double dead_prob_a() const
1239  {
1240  return prob_of_zero(true, false);
1241  }
1242 
1243  /** What is the chance that combatant 'b' is dead? */
1244  double dead_prob_b() const
1245  {
1246  return prob_of_zero(false, true);
1247  }
1248 
1249  void extract_results(
1250  summary_t& summary_a, summary_t& summary_b) override;
1251 };
1252 
1253 /**
1254  * Constructor.
1255  * @param a_max_hp The maximum hit points for A.
1256  * @param b_max_hp The maximum hit points for B.
1257  * @param a_slows Set to true if A slows B when A hits B.
1258  * @param b_slows Set to true if B slows A when B hits A.
1259  * @param a_hp The current hit points for A. (Ignored if a_summary[0] is not empty.)
1260  * @param b_hp The current hit points for B. (Ignored if b_summary[0] is not empty.)
1261  * @param a_summary The hit point distribution for A (from previous combats). Element [0] is for normal A. while
1262  * [1] is for slowed A.
1263  * @param b_summary The hit point distribution for B (from previous combats). Element [0] is for normal B. while
1264  * [1] is for slowed B.
1265  */
1266 probability_combat_matrix::probability_combat_matrix(unsigned int a_max_hp,
1267  unsigned int b_max_hp,
1268  unsigned int a_hp,
1269  unsigned int b_hp,
1270  const summary_t& a_summary,
1271  const summary_t& b_summary,
1272  bool a_slows,
1273  bool b_slows,
1274  unsigned int a_damage,
1275  unsigned int b_damage,
1276  unsigned int a_slow_damage,
1277  unsigned int b_slow_damage,
1278  int a_drain_percent,
1279  int b_drain_percent,
1280  int a_drain_constant,
1281  int b_drain_constant)
1282  : combat_matrix(a_max_hp,
1283  b_max_hp,
1284  a_hp,
1285  b_hp,
1286  a_summary,
1287  b_summary,
1288  a_slows,
1289  b_slows,
1290  a_damage,
1291  b_damage,
1292  a_slow_damage,
1293  b_slow_damage,
1294  a_drain_percent,
1295  b_drain_percent,
1296  a_drain_constant,
1297  b_drain_constant)
1298 {
1299 }
1300 
1301 // Shift combat_matrix to reflect the probability 'hit_chance' that damage
1302 // is done to 'b'.
1303 void probability_combat_matrix::receive_blow_b(double hit_chance)
1304 {
1305  // Walk backwards so we don't copy already-copied matrix planes.
1306  unsigned src = NUM_PLANES;
1307  while(src-- != 0) {
1308  if(!plane_used(src)) {
1309  continue;
1310  }
1311 
1312  // If A slows us, we go from 0=>2, 1=>3, 2=>2 3=>3.
1313  int dst = a_slows_ ? src | 2 : src;
1314 
1315  // A is slow in planes 1 and 3.
1316  unsigned damage = (src & 1) ? a_slow_damage_ : a_damage_;
1317 
1318  shift_cols(dst, src, damage, hit_chance, a_drain_constant_, a_drain_percent_);
1319  }
1320 }
1321 
1322 // Shift matrix to reflect probability 'hit_chance'
1323 // that damage (up to) 'damage' is done to 'a'.
1324 void probability_combat_matrix::receive_blow_a(double hit_chance)
1325 {
1326  // Walk backwards so we don't copy already-copied matrix planes.
1327  unsigned src = NUM_PLANES;
1328  while(src-- != 0) {
1329  if(!plane_used(src)) {
1330  continue;
1331  }
1332 
1333  // If B slows us, we go from 0=>1, 1=>1, 2=>3 3=>3.
1334  int dst = b_slows_ ? src | 1 : src;
1335 
1336  // B is slow in planes 2 and 3.
1337  unsigned damage = (src & 2) ? b_slow_damage_ : b_damage_;
1338 
1339  shift_rows(dst, src, damage, hit_chance, b_drain_constant_, b_drain_percent_);
1340  }
1341 }
1342 
1343 void probability_combat_matrix::extract_results(
1344  summary_t& summary_a, summary_t& summary_b)
1345 {
1346  // Reset the summaries.
1347  summary_a[0] = std::vector<double>(num_rows());
1348  summary_b[0] = std::vector<double>(num_cols());
1349 
1350  if(plane_used(A_SLOWED)) {
1351  summary_a[1] = std::vector<double>(num_rows());
1352  }
1353 
1354  if(plane_used(B_SLOWED)) {
1355  summary_b[1] = std::vector<double>(num_cols());
1356  }
1357 
1358  for(unsigned p = 0; p < NUM_PLANES; ++p) {
1359  if(!plane_used(p)) {
1360  continue;
1361  }
1362 
1363  // A is slow in planes 1 and 3.
1364  unsigned dst_a = (p & 1) ? 1u : 0u;
1365  // B is slow in planes 2 and 3.
1366  unsigned dst_b = (p & 2) ? 1u : 0u;
1367  sum(p, summary_a[dst_a], summary_b[dst_b]);
1368  }
1369 }
1370 
1371 /**
1372  * Implementation of combat_matrix based on Monte Carlo simulation.
1373  * This does not give exact results, but the error should be small
1374  * thanks to the law of large numbers. Probably more important is that
1375  * the simulation time doesn't depend on anything other than the number
1376  * of strikes, which makes this method much faster if the combatants
1377  * have a lot of HP.
1378  */
1379 class monte_carlo_combat_matrix : public combat_matrix
1380 {
1381 public:
1382  monte_carlo_combat_matrix(unsigned int a_max_hp,
1383  unsigned int b_max_hp,
1384  unsigned int a_hp,
1385  unsigned int b_hp,
1386  const summary_t& a_summary,
1387  const summary_t& b_summary,
1388  bool a_slows,
1389  bool b_slows,
1390  unsigned int a_damage,
1391  unsigned int b_damage,
1392  unsigned int a_slow_damage,
1393  unsigned int b_slow_damage,
1394  int a_drain_percent,
1395  int b_drain_percent,
1396  int a_drain_constant,
1397  int b_drain_constant,
1398  unsigned int rounds,
1399  double a_hit_chance,
1400  double b_hit_chance,
1401  const std::vector<combat_slice>& a_split,
1402  const std::vector<combat_slice>& b_split,
1403  double a_initially_slowed_chance,
1404  double b_initially_slowed_chance);
1405 
1406  void simulate();
1407 
1408  void extract_results(
1409  summary_t& summary_a, summary_t& summary_b) override;
1410 
1411  double get_a_hit_probability() const;
1412  double get_b_hit_probability() const;
1413 
1414 private:
1415  static const unsigned int NUM_ITERATIONS = 5000u;
1416 
1417  std::vector<double> a_initial_;
1418  std::vector<double> b_initial_;
1419  std::vector<double> a_initial_slowed_;
1420  std::vector<double> b_initial_slowed_;
1421  std::vector<combat_slice> a_split_;
1422  std::vector<combat_slice> b_split_;
1423  unsigned int rounds_;
1424  double a_hit_chance_;
1425  double b_hit_chance_;
1426  double a_initially_slowed_chance_;
1427  double b_initially_slowed_chance_;
1428  unsigned int iterations_a_hit_ = 0u;
1429  unsigned int iterations_b_hit_ = 0u;
1430 
1431  unsigned int calc_blows_a(unsigned int a_hp) const;
1432  unsigned int calc_blows_b(unsigned int b_hp) const;
1433  static void divide_all_elements(std::vector<double>& vec, double divisor);
1434  static void scale_probabilities(
1435  const std::vector<double>& source, std::vector<double>& target, double divisor, unsigned int singular_hp);
1436 };
1437 
1438 monte_carlo_combat_matrix::monte_carlo_combat_matrix(unsigned int a_max_hp,
1439  unsigned int b_max_hp,
1440  unsigned int a_hp,
1441  unsigned int b_hp,
1442  const summary_t& a_summary,
1443  const summary_t& b_summary,
1444  bool a_slows,
1445  bool b_slows,
1446  unsigned int a_damage,
1447  unsigned int b_damage,
1448  unsigned int a_slow_damage,
1449  unsigned int b_slow_damage,
1450  int a_drain_percent,
1451  int b_drain_percent,
1452  int a_drain_constant,
1453  int b_drain_constant,
1454  unsigned int rounds,
1455  double a_hit_chance,
1456  double b_hit_chance,
1457  const std::vector<combat_slice>& a_split,
1458  const std::vector<combat_slice>& b_split,
1459  double a_initially_slowed_chance,
1460  double b_initially_slowed_chance)
1461  : combat_matrix(a_max_hp,
1462  b_max_hp,
1463  a_hp,
1464  b_hp,
1465  a_summary,
1466  b_summary,
1467  a_slows,
1468  b_slows,
1469  a_damage,
1470  b_damage,
1471  a_slow_damage,
1472  b_slow_damage,
1473  a_drain_percent,
1474  b_drain_percent,
1475  a_drain_constant,
1476  b_drain_constant)
1477  , a_split_(a_split)
1478  , b_split_(b_split)
1479  , rounds_(rounds)
1480  , a_hit_chance_(a_hit_chance)
1481  , b_hit_chance_(b_hit_chance)
1482  , a_initially_slowed_chance_(a_initially_slowed_chance)
1483  , b_initially_slowed_chance_(b_initially_slowed_chance)
1484 {
1485  scale_probabilities(a_summary[0], a_initial_, 1.0 - a_initially_slowed_chance, a_hp);
1486  scale_probabilities(a_summary[1], a_initial_slowed_, a_initially_slowed_chance, a_hp);
1487  scale_probabilities(b_summary[0], b_initial_, 1.0 - b_initially_slowed_chance, b_hp);
1488  scale_probabilities(b_summary[1], b_initial_slowed_, b_initially_slowed_chance, b_hp);
1489 
1490  clear();
1491 }
1492 
1493 void monte_carlo_combat_matrix::simulate()
1494 {
1496 
1497  for(unsigned int i = 0u; i < NUM_ITERATIONS; ++i) {
1498  bool a_hit = false;
1499  bool b_hit = false;
1500  bool a_slowed = rng.get_random_bool(a_initially_slowed_chance_);
1501  bool b_slowed = rng.get_random_bool(b_initially_slowed_chance_);
1502  const std::vector<double>& a_initial = a_slowed ? a_initial_slowed_ : a_initial_;
1503  const std::vector<double>& b_initial = b_slowed ? b_initial_slowed_ : b_initial_;
1504  unsigned int a_hp = rng.get_random_element(a_initial.begin(), a_initial.end());
1505  unsigned int b_hp = rng.get_random_element(b_initial.begin(), b_initial.end());
1506  unsigned int a_strikes = calc_blows_a(a_hp);
1507  unsigned int b_strikes = calc_blows_b(b_hp);
1508 
1509  for(unsigned int j = 0u; j < rounds_ && a_hp > 0u && b_hp > 0u; ++j) {
1510  for(unsigned int k = 0u; k < std::max(a_strikes, b_strikes); ++k) {
1511  if(k < a_strikes) {
1512  if(rng.get_random_bool(a_hit_chance_)) {
1513  // A hits B
1514  unsigned int damage = a_slowed ? a_slow_damage_ : a_damage_;
1515  damage = std::min(damage, b_hp);
1516  b_hit = true;
1517  b_slowed |= a_slows_;
1518 
1519  int drain_amount = (a_drain_percent_ * static_cast<signed>(damage) / 100 + a_drain_constant_);
1520  a_hp = std::clamp(a_hp + drain_amount, 1u, a_max_hp_);
1521 
1522  b_hp -= damage;
1523 
1524  if(b_hp == 0u) {
1525  // A killed B
1526  break;
1527  }
1528  }
1529  }
1530 
1531  if(k < b_strikes) {
1532  if(rng.get_random_bool(b_hit_chance_)) {
1533  // B hits A
1534  unsigned int damage = b_slowed ? b_slow_damage_ : b_damage_;
1535  damage = std::min(damage, a_hp);
1536  a_hit = true;
1537  a_slowed |= b_slows_;
1538 
1539  int drain_amount = (b_drain_percent_ * static_cast<signed>(damage) / 100 + b_drain_constant_);
1540  b_hp = std::clamp(b_hp + drain_amount, 1u, b_max_hp_);
1541 
1542  a_hp -= damage;
1543 
1544  if(a_hp == 0u) {
1545  // B killed A
1546  break;
1547  }
1548  }
1549  }
1550  }
1551  }
1552 
1553  iterations_a_hit_ += a_hit ? 1 : 0;
1554  iterations_b_hit_ += b_hit ? 1 : 0;
1555 
1556  record_monte_carlo_result(a_hp, b_hp, a_slowed, b_slowed);
1557  }
1558 }
1559 
1560 /**
1561  * Otherwise the same as in probability_combat_matrix, but this needs to divide the values
1562  * by the number of iterations.
1563  */
1564 void monte_carlo_combat_matrix::extract_results(
1565  summary_t& summary_a, summary_t& summary_b)
1566 {
1567  // Reset the summaries.
1568  summary_a[0] = std::vector<double>(num_rows());
1569  summary_b[0] = std::vector<double>(num_cols());
1570 
1571  if(plane_used(A_SLOWED)) {
1572  summary_a[1] = std::vector<double>(num_rows());
1573  }
1574 
1575  if(plane_used(B_SLOWED)) {
1576  summary_b[1] = std::vector<double>(num_cols());
1577  }
1578 
1579  for(unsigned p = 0; p < NUM_PLANES; ++p) {
1580  if(!plane_used(p)) {
1581  continue;
1582  }
1583 
1584  // A is slow in planes 1 and 3.
1585  unsigned dst_a = (p & 1) ? 1u : 0u;
1586  // B is slow in planes 2 and 3.
1587  unsigned dst_b = (p & 2) ? 1u : 0u;
1588  sum(p, summary_a[dst_a], summary_b[dst_b]);
1589  }
1590 
1591  divide_all_elements(summary_a[0], static_cast<double>(NUM_ITERATIONS));
1592  divide_all_elements(summary_b[0], static_cast<double>(NUM_ITERATIONS));
1593 
1594  if(plane_used(A_SLOWED)) {
1595  divide_all_elements(summary_a[1], static_cast<double>(NUM_ITERATIONS));
1596  }
1597 
1598  if(plane_used(B_SLOWED)) {
1599  divide_all_elements(summary_b[1], static_cast<double>(NUM_ITERATIONS));
1600  }
1601 }
1602 
1603 double monte_carlo_combat_matrix::get_a_hit_probability() const
1604 {
1605  return static_cast<double>(iterations_a_hit_) / static_cast<double>(NUM_ITERATIONS);
1606 }
1607 
1608 double monte_carlo_combat_matrix::get_b_hit_probability() const
1609 {
1610  return static_cast<double>(iterations_b_hit_) / static_cast<double>(NUM_ITERATIONS);
1611 }
1612 
1613 unsigned int monte_carlo_combat_matrix::calc_blows_a(unsigned int a_hp) const
1614 {
1615  auto it = a_split_.begin();
1616  while(it != a_split_.end() && it->end_hp <= a_hp) {
1617  ++it;
1618  }
1619 
1620  if(it == a_split_.end()) {
1621  --it;
1622  }
1623 
1624  return it->strikes;
1625 }
1626 
1627 unsigned int monte_carlo_combat_matrix::calc_blows_b(unsigned int b_hp) const
1628 {
1629  auto it = b_split_.begin();
1630  while(it != b_split_.end() && it->end_hp <= b_hp) {
1631  ++it;
1632  }
1633 
1634  if(it == b_split_.end()) {
1635  --it;
1636  }
1637 
1638  return it->strikes;
1639 }
1640 
1641 void monte_carlo_combat_matrix::scale_probabilities(
1642  const std::vector<double>& source, std::vector<double>& target, double divisor, unsigned int singular_hp)
1643 {
1644  if(divisor == 0.0) {
1645  // Happens if the "target" HP distribution vector isn't used,
1646  // in which case it's not necessary to scale the probabilities.
1647  return;
1648  }
1649 
1650  if(source.empty()) {
1651  target.resize(singular_hp + 1u, 0.0);
1652  target[singular_hp] = 1.0;
1653  } else {
1654  std::transform(
1655  source.begin(), source.end(), std::back_inserter(target), [=](double prob) { return prob / divisor; });
1656  }
1657 
1658  assert(std::abs(std::accumulate(target.begin(), target.end(), 0.0) - 1.0) < 0.001);
1659 }
1660 
1661 void monte_carlo_combat_matrix::divide_all_elements(std::vector<double>& vec, double divisor)
1662 {
1663  for(double& e : vec) {
1664  e /= divisor;
1665  }
1666 }
1667 
1668 } // end anon namespace
1669 
1671  : hp_dist(u.max_hp + 1, 0.0)
1672  , untouched(0.0)
1673  , poisoned(0.0)
1674  , slowed(0.0)
1675  , u_(u)
1676 {
1677  // We inherit current state from previous combatant.
1678  if(prev) {
1679  summary[0] = prev->summary[0];
1680  summary[1] = prev->summary[1];
1681  hp_dist = prev->hp_dist;
1682  untouched = prev->untouched;
1683  poisoned = prev->poisoned;
1684  slowed = prev->slowed;
1685  } else {
1686  hp_dist[std::min(u.hp, u.max_hp)] = 1.0;
1687  untouched = 1.0;
1688  poisoned = u.is_poisoned ? 1.0 : 0.0;
1689  slowed = u.is_slowed ? 1.0 : 0.0;
1690 
1691  // If we're already slowed, create summary[1] so that probability calculation code
1692  // knows that we're slowed.
1693  if(u.is_slowed) {
1694  summary[0].resize(u.max_hp + 1, 0.0);
1695  summary[1] = hp_dist;
1696  }
1697  }
1698 }
1699 
1700 // Copy constructor (except use this copy of battle_context_unit_stats)
1702  : hp_dist(that.hp_dist)
1703  , untouched(that.untouched)
1704  , poisoned(that.poisoned)
1705  , slowed(that.slowed)
1706  , u_(u)
1707 {
1708  summary[0] = that.summary[0];
1709  summary[1] = that.summary[1];
1710 }
1711 
1712 namespace
1713 {
1714 enum class attack_prediction_mode { probability_calculation, monte_carlo_simulation };
1715 
1716 void forced_levelup(std::vector<double>& hp_dist)
1717 {
1718  /* If we survive the combat, we will level up. So the probability
1719  of death is unchanged, but all other cases get merged into the
1720  fully healed case. */
1721  auto i = hp_dist.begin();
1722  // Skip to the second value.
1723  for(++i; i != hp_dist.end(); ++i) {
1724  *i = 0;
1725  }
1726 
1727  // Full heal unless dead.
1728  hp_dist.back() = 1 - hp_dist.front();
1729 }
1730 
1731 void conditional_levelup(std::vector<double>& hp_dist, double kill_prob)
1732 {
1733  /* If we kill, we will level up. So then the damage we had becomes
1734  less probable since it's now conditional on us not leveling up.
1735  This doesn't apply to the probability of us dying, of course. */
1736  double scalefactor = 0;
1737  const double chance_to_survive = 1 - hp_dist.front();
1738  if(chance_to_survive > DBL_MIN) {
1739  scalefactor = 1 - kill_prob / chance_to_survive;
1740  }
1741 
1742  auto i = hp_dist.begin();
1743  // Skip to the second value.
1744  for(++i; i != hp_dist.end(); ++i) {
1745  *i *= scalefactor;
1746  }
1747 
1748  // Full heal if leveled up.
1749  hp_dist.back() += kill_prob;
1750 }
1751 
1752 /* Calculates the probability that we will be poisoned after the fight. Parameters:
1753  * initial_prob: how likely we are to be poisoned before the fight.
1754  * enemy_gives: true if the enemy poisons us.
1755  * prob_touched: probability the enemy touches us.
1756  * prob_stay_alive: probability we survive the fight alive.
1757  * kill_heals: true if killing the enemy heals the poison (in other words, we get a level-up).
1758  * prob_kill: probability we kill the enemy.
1759  */
1760 double calculate_probability_of_debuff(double initial_prob, bool enemy_gives, double prob_touched, double prob_stay_alive, bool kill_heals, double prob_kill)
1761 {
1762  assert(initial_prob >= 0.0 && initial_prob <= 1.0);
1763  /* In the add-on "Legend of the Invincibles", the "distant attack" ability sets the probability of being touched to zero.
1764  With some optimizing compilers, the probability can somehow get slightly negative, see bug #2342.
1765  Ensure that it gets non-negative. */
1766  prob_touched = std::max(prob_touched, 0.0);
1767  // Prob_stay_alive can get slightly negative because of a rounding error, so ensure that it gets non-negative.
1768  prob_stay_alive = std::max(prob_stay_alive, 0.0);
1769  // Prob_kill can creep a bit above 100 % if the AI simulates an unit being attacked by multiple units in a row, due to rounding error.
1770  // Likewise, it can get slightly negative if the unit already has negative HP.
1771  // Simply limit it to suitable range.
1772  prob_kill = std::clamp(prob_kill, 0.0, 1.0);
1773 
1774  // Probability we are already debuffed and the enemy doesn't hit us.
1775  const double prob_already_debuffed_not_touched = initial_prob * (1.0 - prob_touched);
1776  // Probability we are already debuffed and the enemy hits us.
1777  const double prob_already_debuffed_touched = initial_prob * prob_touched;
1778  // Probability we aren't debuffed and the enemy doesn't hit us.
1779  // const double prob_initially_healthy_not_touched = (1.0 - initial_prob) * (1.0 - prob_touched);
1780  // Probability we aren't debuffed and the enemy hits us.
1781  const double prob_initially_healthy_touched = (1.0 - initial_prob) * prob_touched;
1782 
1783  // Probability to survive if the enemy doesn't hit us.
1784  const double prob_survive_if_not_hit = 1.0;
1785  // Probability to survive if the enemy hits us.
1786  const double prob_survive_if_hit = prob_touched > 0.0 ? (prob_stay_alive - (1.0 - prob_touched)) / prob_touched : 1.0;
1787 
1788  // Probability to kill if we don't survive the fight.
1789  // const double prob_kill_if_not_survive = 0.0;
1790  // Probability to kill if we survive the fight.
1791  const double prob_kill_if_survive = prob_stay_alive > 0.0 ? prob_kill / prob_stay_alive : 0.0;
1792 
1793  // Probability to be debuffed after the fight, calculated in multiple stages.
1794  double prob_debuff = 0.0;
1795 
1796  if(!kill_heals) {
1797  prob_debuff += prob_already_debuffed_not_touched;
1798  } else {
1799  prob_debuff += prob_already_debuffed_not_touched * (1.0 - prob_survive_if_not_hit * prob_kill_if_survive);
1800  }
1801 
1802  if(!kill_heals) {
1803  prob_debuff += prob_already_debuffed_touched;
1804  } else {
1805  prob_debuff += prob_already_debuffed_touched * (1.0 - prob_survive_if_hit * prob_kill_if_survive);
1806  }
1807 
1808  // "Originally not debuffed, not hit" situation never results in us getting debuffed. Skipping.
1809 
1810  if(!enemy_gives) {
1811  // Do nothing.
1812  } else if(!kill_heals) {
1813  prob_debuff += prob_initially_healthy_touched;
1814  } else {
1815  prob_debuff += prob_initially_healthy_touched * (1.0 - prob_survive_if_hit * prob_kill_if_survive);
1816  }
1817 
1818  return prob_debuff;
1819 }
1820 
1821 // Rounds a probability that's extremely close to 0 or 1 to exactly 0 or 1.
1822 void round_prob_if_close_to_sure(double& prob)
1823 {
1824  if(prob < 1.0e-9) {
1825  prob = 0.0;
1826  } else if(prob > 1.0 - 1.0e-9) {
1827  prob = 1.0;
1828  }
1829 }
1830 
1831 /**
1832  * Returns the smallest HP we could possibly have based on the provided
1833  * hit point distribution.
1834  */
1835 unsigned min_hp(const std::vector<double>& hp_dist, unsigned def)
1836 {
1837  const unsigned size = hp_dist.size();
1838 
1839  // Look for a nonzero entry.
1840  for(unsigned i = 0; i != size; ++i) {
1841  if(hp_dist[i] != 0.0) {
1842  return i;
1843  }
1844  }
1845 
1846  // Either the distribution is empty or is full of zeros, so
1847  // return the default.
1848  return def;
1849 }
1850 
1851 /**
1852  * Returns a number that approximates the complexity of the fight,
1853  * for the purpose of determining if it's faster to calculate exact
1854  * probabilities or to run a Monte Carlo simulation.
1855  * Ignores the numbers of rounds and strikes because these slow down
1856  * both calculation modes.
1857  */
1858 unsigned int fight_complexity(unsigned int num_slices,
1859  unsigned int opp_num_slices,
1860  const battle_context_unit_stats& stats,
1861  const battle_context_unit_stats& opp_stats)
1862 {
1863  return num_slices * opp_num_slices * ((stats.slows || opp_stats.is_slowed) ? 2 : 1)
1864  * ((opp_stats.slows || stats.is_slowed) ? 2 : 1) * stats.max_hp * opp_stats.max_hp;
1865 }
1866 
1867 /**
1868  * Returns the plane index for the slow/no-slow state of the combatants.
1869  */
1870 unsigned int plane_index(const battle_context_unit_stats& stats,
1871  const battle_context_unit_stats& opp_stats)
1872 {
1873  return (stats.is_slowed ? 1 : 0) | (opp_stats.is_slowed ? 2 : 0);
1874 }
1875 
1876 // Combat without chance of death, berserk, slow or drain is simple.
1877 void no_death_fight(const battle_context_unit_stats& stats,
1878  const battle_context_unit_stats& opp_stats,
1879  unsigned strikes,
1880  unsigned opp_strikes,
1881  std::vector<double>& hp_dist,
1882  std::vector<double>& opp_hp_dist,
1883  double& self_not_hit,
1884  double& opp_not_hit,
1885  bool levelup_considered)
1886 {
1887  // Our strikes.
1888  // If we were killed in an earlier fight, we don't get to attack.
1889  // (Most likely case: we are a first striking defender subject to a series
1890  // of attacks.)
1891  const double alive_prob = hp_dist.empty() ? 1.0 : 1.0 - hp_dist[0];
1892  const double hit_chance = (stats.chance_to_hit / 100.0) * alive_prob;
1893 
1894  if(opp_hp_dist.empty()) {
1895  // Starts with a known HP, so Pascal's triangle.
1896  opp_hp_dist = std::vector<double>(opp_stats.max_hp + 1);
1897  opp_hp_dist[opp_stats.hp] = 1.0;
1898 
1899  for(unsigned int i = 0; i < strikes; ++i) {
1900  for(int j = i; j >= 0; j--) {
1901  unsigned src_index = opp_stats.hp - j * stats.damage;
1902  double move = opp_hp_dist[src_index] * hit_chance;
1903  opp_hp_dist[src_index] -= move;
1904  opp_hp_dist[src_index - stats.damage] += move;
1905  }
1906 
1907  opp_not_hit *= 1.0 - hit_chance;
1908  }
1909  } else {
1910  // HP could be spread anywhere, iterate through whole thing.
1911  for(unsigned int i = 0; i < strikes; ++i) {
1912  for(unsigned int j = stats.damage; j < opp_hp_dist.size(); ++j) {
1913  double move = opp_hp_dist[j] * hit_chance;
1914  opp_hp_dist[j] -= move;
1915  opp_hp_dist[j - stats.damage] += move;
1916  }
1917  opp_not_hit *= 1.0 - hit_chance;
1918  }
1919  }
1920 
1921  // Opponent's strikes
1922  // If opponent was killed in an earlier fight, they don't get to attack.
1923  const double opp_alive_prob = opp_hp_dist.empty() ? 1.0 : 1.0 - opp_hp_dist[0];
1924  const double opp_hit_chance = (opp_stats.chance_to_hit / 100.0) * opp_alive_prob;
1925 
1926  if(hp_dist.empty()) {
1927  // Starts with a known HP, so Pascal's triangle.
1928  hp_dist = std::vector<double>(stats.max_hp + 1);
1929  hp_dist[stats.hp] = 1.0;
1930  for(unsigned int i = 0; i < opp_strikes; ++i) {
1931  for(int j = i; j >= 0; j--) {
1932  unsigned src_index = stats.hp - j * opp_stats.damage;
1933  double move = hp_dist[src_index] * opp_hit_chance;
1934  hp_dist[src_index] -= move;
1935  hp_dist[src_index - opp_stats.damage] += move;
1936  }
1937 
1938  self_not_hit *= 1.0 - opp_hit_chance;
1939  }
1940  } else {
1941  // HP could be spread anywhere, iterate through whole thing.
1942  for(unsigned int i = 0; i < opp_strikes; ++i) {
1943  for(unsigned int j = opp_stats.damage; j < hp_dist.size(); ++j) {
1944  double move = hp_dist[j] * opp_hit_chance;
1945  hp_dist[j] -= move;
1946  hp_dist[j - opp_stats.damage] += move;
1947  }
1948 
1949  self_not_hit *= 1.0 - opp_hit_chance;
1950  }
1951  }
1952 
1953  if(!levelup_considered) {
1954  return;
1955  }
1956 
1957  if(stats.experience + opp_stats.level >= stats.max_experience) {
1958  forced_levelup(hp_dist);
1959  }
1960 
1961  if(opp_stats.experience + stats.level >= opp_stats.max_experience) {
1962  forced_levelup(opp_hp_dist);
1963  }
1964 }
1965 
1966 // Combat with <= 1 strike each is simple, too.
1967 void one_strike_fight(const battle_context_unit_stats& stats,
1968  const battle_context_unit_stats& opp_stats,
1969  unsigned strikes,
1970  unsigned opp_strikes,
1971  std::vector<double>& hp_dist,
1972  std::vector<double>& opp_hp_dist,
1973  double& self_not_hit,
1974  double& opp_not_hit,
1975  bool levelup_considered)
1976 {
1977  // If we were killed in an earlier fight, we don't get to attack.
1978  // (Most likely case: we are a first striking defender subject to a series
1979  // of attacks.)
1980  double alive_prob = hp_dist.empty() ? 1.0 : 1.0 - hp_dist[0];
1981  if(stats.hp == 0) {
1982  alive_prob = 0.0;
1983  }
1984  const double hit_chance = (stats.chance_to_hit / 100.0) * alive_prob;
1985 
1986  if(opp_hp_dist.empty()) {
1987  opp_hp_dist = std::vector<double>(opp_stats.max_hp + 1);
1988  if(strikes == 1 && opp_stats.hp > 0) {
1989  opp_hp_dist[opp_stats.hp] = 1.0 - hit_chance;
1990  opp_hp_dist[std::max<int>(opp_stats.hp - stats.damage, 0)] = hit_chance;
1991  opp_not_hit *= 1.0 - hit_chance;
1992  } else {
1993  opp_hp_dist[opp_stats.hp] = 1.0;
1994  }
1995  } else {
1996  if(strikes == 1) {
1997  for(unsigned int i = 1; i < opp_hp_dist.size(); ++i) {
1998  double move = opp_hp_dist[i] * hit_chance;
1999  opp_hp_dist[i] -= move;
2000  opp_hp_dist[std::max<int>(i - stats.damage, 0)] += move;
2001  }
2002 
2003  opp_not_hit *= 1.0 - hit_chance;
2004  }
2005  }
2006 
2007  // If we killed opponent, it won't attack us.
2008  const double opp_attack_prob = (1.0 - opp_hp_dist[0]) * alive_prob;
2009  const double opp_hit_chance = (opp_stats.chance_to_hit / 100.0) * opp_attack_prob;
2010 
2011  if(hp_dist.empty()) {
2012  hp_dist = std::vector<double>(stats.max_hp + 1);
2013  if(opp_strikes == 1 && stats.hp > 0) {
2014  hp_dist[stats.hp] = 1.0 - opp_hit_chance;
2015  hp_dist[std::max<int>(stats.hp - opp_stats.damage, 0)] = opp_hit_chance;
2016  self_not_hit *= 1.0 - opp_hit_chance;
2017  } else {
2018  hp_dist[stats.hp] = 1.0;
2019  }
2020  } else {
2021  if(opp_strikes == 1) {
2022  for(unsigned int i = 1; i < hp_dist.size(); ++i) {
2023  double move = hp_dist[i] * opp_hit_chance;
2024  hp_dist[i] -= move;
2025  hp_dist[std::max<int>(i - opp_stats.damage, 0)] += move;
2026  }
2027 
2028  self_not_hit *= 1.0 - opp_hit_chance;
2029  }
2030  }
2031 
2032  if(!levelup_considered) {
2033  return;
2034  }
2035 
2036  if(stats.experience + game_config::combat_xp(opp_stats.level) >= stats.max_experience) {
2037  forced_levelup(hp_dist);
2038  } else if(stats.experience + game_config::kill_xp(opp_stats.level) >= stats.max_experience) {
2039  conditional_levelup(hp_dist, opp_hp_dist[0]);
2040  }
2041 
2042  if(opp_stats.experience + game_config::combat_xp(stats.level) >= opp_stats.max_experience) {
2043  forced_levelup(opp_hp_dist);
2044  } else if(opp_stats.experience + game_config::kill_xp(stats.level) >= opp_stats.max_experience) {
2045  conditional_levelup(opp_hp_dist, hp_dist[0]);
2046  }
2047 }
2048 
2049 /* The parameters "split", "opp_split", "initially_slowed_chance" and
2050 "opp_initially_slowed_chance" are ignored in the probability calculation mode. */
2051 void complex_fight(attack_prediction_mode mode,
2052  const battle_context_unit_stats& stats,
2053  const battle_context_unit_stats& opp_stats,
2054  unsigned strikes,
2055  unsigned opp_strikes,
2056  summary_t& summary,
2057  summary_t& opp_summary,
2058  double& self_not_hit,
2059  double& opp_not_hit,
2060  bool levelup_considered,
2061  std::vector<combat_slice> split,
2062  std::vector<combat_slice> opp_split,
2063  double initially_slowed_chance,
2064  double opp_initially_slowed_chance)
2065 {
2066  unsigned int rounds = std::max<unsigned int>(stats.rounds, opp_stats.rounds);
2067  unsigned max_attacks = std::max(strikes, opp_strikes);
2068 
2069  debug(("A gets %u attacks, B %u.\n", strikes, opp_strikes));
2070 
2071  unsigned int a_damage = stats.damage, a_slow_damage = stats.slow_damage;
2072  unsigned int b_damage = opp_stats.damage, b_slow_damage = opp_stats.slow_damage;
2073 
2074  // To simulate stoning, we set to amount which kills, and re-adjust after.
2075  /** @todo FIXME: This doesn't work for rolling calculations, just first battle.
2076  It also does not work if combined with (percentage) drain. */
2077  if(stats.petrifies) {
2078  a_damage = a_slow_damage = opp_stats.max_hp;
2079  }
2080 
2081  if(opp_stats.petrifies) {
2082  b_damage = b_slow_damage = stats.max_hp;
2083  }
2084 
2085  const double original_self_not_hit = self_not_hit;
2086  const double original_opp_not_hit = opp_not_hit;
2087  const double hit_chance = stats.chance_to_hit / 100.0;
2088  const double opp_hit_chance = opp_stats.chance_to_hit / 100.0;
2089  double self_hit = 0.0;
2090  double opp_hit = 0.0;
2091  double self_hit_unknown = 1.0; // Probability we don't yet know if A will be hit or not
2092  double opp_hit_unknown = 1.0; // Ditto for B
2093 
2094  // Prepare the matrix that will do our calculations.
2095  std::unique_ptr<combat_matrix> m;
2096  if(mode == attack_prediction_mode::probability_calculation) {
2097  debug(("Using exact probability calculations.\n"));
2098 
2099  probability_combat_matrix* pm = new probability_combat_matrix(stats.max_hp, opp_stats.max_hp, stats.hp,
2100  opp_stats.hp, summary, opp_summary, stats.slows, opp_stats.slows,
2101  a_damage, b_damage, a_slow_damage, b_slow_damage,
2102  stats.drain_percent, opp_stats.drain_percent, stats.drain_constant, opp_stats.drain_constant);
2103  m.reset(pm);
2104 
2105  do {
2106  for(unsigned int i = 0; i < max_attacks; ++i) {
2107  if(i < strikes) {
2108  debug(("A strikes\n"));
2109  double b_already_dead = pm->dead_prob_b();
2110  pm->receive_blow_b(hit_chance);
2111  pm->dump();
2112 
2113  double first_hit = hit_chance * opp_hit_unknown;
2114  opp_hit += first_hit;
2115  opp_hit_unknown -= first_hit;
2116  double both_were_alive = 1.0 - b_already_dead - pm->dead_prob_a();
2117  double this_hit_killed_b = both_were_alive != 0.0 ? (pm->dead_prob_b() - b_already_dead) / both_were_alive : 1.0;
2118  self_hit_unknown *= (1.0 - this_hit_killed_b);
2119  }
2120  if(i < opp_strikes) {
2121  debug(("B strikes\n"));
2122  double a_already_dead = pm->dead_prob_a();
2123  pm->receive_blow_a(opp_hit_chance);
2124  pm->dump();
2125 
2126  double first_hit = opp_hit_chance * self_hit_unknown;
2127  self_hit += first_hit;
2128  self_hit_unknown -= first_hit;
2129  double both_were_alive = 1.0 - a_already_dead - pm->dead_prob_b();
2130  double this_hit_killed_a = both_were_alive != 0.0 ? (pm->dead_prob_a() - a_already_dead) / both_were_alive : 1.0;
2131  opp_hit_unknown *= (1.0 - this_hit_killed_a);
2132  }
2133  }
2134 
2135  debug(("Combat ends:\n"));
2136  pm->dump();
2137  } while(--rounds && pm->dead_prob() < 0.99);
2138 
2139  self_hit = std::min(self_hit, 1.0);
2140  opp_hit = std::min(opp_hit, 1.0);
2141 
2142  self_not_hit = original_self_not_hit * (1.0 - self_hit);
2143  opp_not_hit = original_opp_not_hit * (1.0 - opp_hit);
2144 
2145  if(stats.slows) {
2146  /* The calculation method for the "not hit" probability above is incorrect if either unit can slow.
2147  * Because a slowed unit deals less damage, it is more likely for the slowing unit to be alive if it
2148  * has hit the other unit. In that situation, the "not hit" probability can no longer be calculated
2149  * with simple addition.
2150  * Instead, just fetch the probability from the combat matrix.
2151  */
2152  unsigned int plane = plane_index(stats, opp_stats);
2153  double not_hit = pm->col_sum(plane, opp_stats.hp) + ((plane & 1) ? 0.0 : pm->col_sum(plane | 1, opp_stats.hp));
2154  opp_not_hit = original_opp_not_hit * not_hit;
2155  }
2156  if(opp_stats.slows) {
2157  unsigned int plane = plane_index(stats, opp_stats);
2158  double not_hit = pm->row_sum(plane, stats.hp) + ((plane & 2) ? 0.0 : pm->row_sum(plane | 2, stats.hp));
2159  self_not_hit = original_self_not_hit * not_hit;
2160  }
2161  } else {
2162  debug(("Using Monte Carlo simulation.\n"));
2163 
2164  monte_carlo_combat_matrix* mcm = new monte_carlo_combat_matrix(stats.max_hp, opp_stats.max_hp, stats.hp,
2165  opp_stats.hp, summary, opp_summary, stats.slows, opp_stats.slows,
2166  a_damage, b_damage, a_slow_damage, b_slow_damage,
2167  stats.drain_percent, opp_stats.drain_percent, stats.drain_constant, opp_stats.drain_constant, rounds,
2168  hit_chance, opp_hit_chance, split, opp_split, initially_slowed_chance, opp_initially_slowed_chance);
2169  m.reset(mcm);
2170 
2171  mcm->simulate();
2172  debug(("Combat ends:\n"));
2173  mcm->dump();
2174 
2175  self_not_hit = 1.0 - mcm->get_a_hit_probability();
2176  opp_not_hit = 1.0 - mcm->get_b_hit_probability();
2177  }
2178 
2179  if(stats.petrifies) {
2180  m->remove_petrify_distortion_a(stats.damage, stats.slow_damage, opp_stats.hp);
2181  }
2182 
2183  if(opp_stats.petrifies) {
2184  m->remove_petrify_distortion_b(opp_stats.damage, opp_stats.slow_damage, stats.hp);
2185  }
2186 
2187  if(levelup_considered) {
2188  if(stats.experience + game_config::combat_xp(opp_stats.level) >= stats.max_experience) {
2189  m->forced_levelup_a();
2190  } else if(stats.experience + game_config::kill_xp(opp_stats.level) >= stats.max_experience) {
2191  m->conditional_levelup_a();
2192  }
2193 
2194  if(opp_stats.experience + game_config::combat_xp(stats.level) >= opp_stats.max_experience) {
2195  m->forced_levelup_b();
2196  } else if(opp_stats.experience + game_config::kill_xp(stats.level) >= opp_stats.max_experience) {
2197  m->conditional_levelup_b();
2198  }
2199  }
2200 
2201  // We extract results separately, then combine.
2202  m->extract_results(summary, opp_summary);
2203 }
2204 
2205 /**
2206  * Chooses the best of the various known combat calculations for the current
2207  * situation.
2208  */
2209 void do_fight(const battle_context_unit_stats& stats,
2210  const battle_context_unit_stats& opp_stats,
2211  unsigned strikes,
2212  unsigned opp_strikes,
2213  summary_t& summary,
2214  summary_t& opp_summary,
2215  double& self_not_hit,
2216  double& opp_not_hit,
2217  bool levelup_considered)
2218 {
2219  // Optimization only works in the simple cases (no slow, no drain,
2220  // no petrify, no berserk, and no slowed results from an earlier combat).
2221  if(!stats.slows && !opp_stats.slows && !stats.drains && !opp_stats.drains && !stats.petrifies
2222  && !opp_stats.petrifies && stats.rounds == 1 && opp_stats.rounds == 1 && summary[1].empty()
2223  && opp_summary[1].empty())
2224  {
2225  if(strikes <= 1 && opp_strikes <= 1) {
2226  one_strike_fight(stats, opp_stats, strikes, opp_strikes, summary[0], opp_summary[0], self_not_hit,
2227  opp_not_hit, levelup_considered);
2228  } else if(strikes * stats.damage < min_hp(opp_summary[0], opp_stats.hp)
2229  && opp_strikes * opp_stats.damage < min_hp(summary[0], stats.hp)) {
2230  no_death_fight(stats, opp_stats, strikes, opp_strikes, summary[0], opp_summary[0], self_not_hit,
2231  opp_not_hit, levelup_considered);
2232  } else {
2233  complex_fight(attack_prediction_mode::probability_calculation, stats, opp_stats, strikes, opp_strikes,
2234  summary, opp_summary, self_not_hit, opp_not_hit, levelup_considered, std::vector<combat_slice>(),
2235  std::vector<combat_slice>(), 0.0, 0.0);
2236  }
2237  } else {
2238  complex_fight(attack_prediction_mode::probability_calculation, stats, opp_stats, strikes, opp_strikes, summary,
2239  opp_summary, self_not_hit, opp_not_hit, levelup_considered, std::vector<combat_slice>(),
2240  std::vector<combat_slice>(), 0.0, 0.0);
2241  }
2242 }
2243 
2244 /**
2245  * Initializes a hit point summary (assumed empty) based on the source.
2246  * Only the part of the source from begin_hp up to (not including) end_hp
2247  * is kept, and all values get scaled by prob.
2248  */
2249 void init_slice_summary(
2250  std::vector<double>& dst, const std::vector<double>& src, unsigned begin_hp, unsigned end_hp, double prob)
2251 {
2252  if(src.empty()) {
2253  // Nothing to do.
2254  return;
2255  }
2256 
2257  const unsigned size = src.size();
2258  // Avoid going over the end of the vector.
2259  if(end_hp > size) {
2260  end_hp = size;
2261  }
2262 
2263  // Initialize the destination.
2264  dst.resize(size, 0.0);
2265  for(unsigned i = begin_hp; i < end_hp; ++i) {
2266  dst[i] = src[i] / prob;
2267  }
2268 }
2269 
2270 /**
2271  * Merges the summary results of simulation into an overall summary.
2272  * This uses prob to reverse the scaling that was done in init_slice_summary().
2273  */
2274 void merge_slice_summary(std::vector<double>& dst, const std::vector<double>& src, double prob)
2275 {
2276  const unsigned size = src.size();
2277 
2278  // Make sure we have enough space.
2279  if(dst.size() < size) {
2280  dst.resize(size, 0.0);
2281  }
2282 
2283  // Merge the data.
2284  for(unsigned i = 0; i != size; ++i) {
2285  dst[i] += src[i] * prob;
2286  }
2287 }
2288 
2289 } // end anon namespace
2290 
2291 // Two man enter. One man leave!
2292 // ... Or maybe two. But definitely not three.
2293 // Of course, one could be a woman. Or both.
2294 // And either could be non-human, too.
2295 // Um, ok, it was a stupid thing to say.
2296 void combatant::fight(combatant& opponent, bool levelup_considered)
2297 {
2298  // If defender has firststrike and we don't, reverse.
2299  if(opponent.u_.firststrike && !u_.firststrike) {
2300  opponent.fight(*this, levelup_considered);
2301  return;
2302  }
2303 
2304 #ifdef ATTACK_PREDICTION_DEBUG
2305  printf("A:\n");
2306  dump(u_);
2307  printf("B:\n");
2308  dump(opponent.u_);
2309 #endif
2310 
2311 #if 0
2312  std::vector<double> prev = summary[0], opp_prev = opponent.summary[0];
2313  complex_fight(opponent, 1);
2314  std::vector<double> res = summary[0], opp_res = opponent.summary[0];
2315  summary[0] = prev;
2316  opponent.summary[0] = opp_prev;
2317 #endif
2318 
2319  // The chance so far of not being hit this combat:
2320  double self_not_hit = 1.0;
2321  double opp_not_hit = 1.0;
2322 
2323  // The probability of being already dead before the fight begins:
2324  double self_already_dead = hp_dist[0];
2325  double opp_already_dead = opponent.hp_dist[0];
2326 
2327  // If incoming slow probabilities are extremely close to 0 or 1, round them to exactly 0 or 1 (bug #3321)
2328  round_prob_if_close_to_sure(slowed);
2329  round_prob_if_close_to_sure(opponent.slowed);
2330 
2331  // If we've fought before and we have swarm, we might have to split the
2332  // calculation by number of attacks.
2333  const std::vector<combat_slice> split = split_summary(u_, summary);
2334  const std::vector<combat_slice> opp_split = split_summary(opponent.u_, opponent.summary);
2335 
2336  bool use_monte_carlo_simulation =
2337  fight_complexity(split.size(), opp_split.size(), u_, opponent.u_) > MONTE_CARLO_SIMULATION_THRESHOLD
2339 
2340  if(use_monte_carlo_simulation) {
2341  // A very complex fight. Use Monte Carlo simulation instead of exact
2342  // probability calculations.
2343  complex_fight(attack_prediction_mode::monte_carlo_simulation, u_, opponent.u_, u_.num_blows,
2344  opponent.u_.num_blows, summary, opponent.summary, self_not_hit, opp_not_hit, levelup_considered, split,
2345  opp_split, slowed, opponent.slowed);
2346  } else if(split.size() == 1 && opp_split.size() == 1) {
2347  // No special treatment due to swarm is needed. Ignore the split.
2348  do_fight(u_, opponent.u_, u_.num_blows, opponent.u_.num_blows, summary, opponent.summary, self_not_hit,
2349  opp_not_hit, levelup_considered);
2350  } else {
2351  // Storage for the accumulated hit point distributions.
2352  summary_t summary_result, opp_summary_result;
2353  // The chance of not being hit becomes an accumulated chance:
2354  self_not_hit = 0.0;
2355  opp_not_hit = 0.0;
2356 
2357  // Loop through all the potential combat situations.
2358  for(unsigned s = 0; s != split.size(); ++s) {
2359  for(unsigned t = 0; t != opp_split.size(); ++t) {
2360  const double sit_prob = split[s].prob * opp_split[t].prob;
2361 
2362  // Create summaries for this potential combat situation.
2363  summary_t sit_summary, sit_opp_summary;
2364  init_slice_summary(sit_summary[0], summary[0], split[s].begin_hp, split[s].end_hp, split[s].prob);
2365  init_slice_summary(sit_summary[1], summary[1], split[s].begin_hp, split[s].end_hp, split[s].prob);
2366  init_slice_summary(sit_opp_summary[0], opponent.summary[0], opp_split[t].begin_hp, opp_split[t].end_hp,
2367  opp_split[t].prob);
2368  init_slice_summary(sit_opp_summary[1], opponent.summary[1], opp_split[t].begin_hp, opp_split[t].end_hp,
2369  opp_split[t].prob);
2370 
2371  // Scale the "not hit" chance for this situation by the chance that
2372  // this situation applies.
2373  double sit_self_not_hit = sit_prob;
2374  double sit_opp_not_hit = sit_prob;
2375 
2376  do_fight(u_, opponent.u_, split[s].strikes, opp_split[t].strikes, sit_summary, sit_opp_summary,
2377  sit_self_not_hit, sit_opp_not_hit, levelup_considered);
2378 
2379  // Collect the results.
2380  self_not_hit += sit_self_not_hit;
2381  opp_not_hit += sit_opp_not_hit;
2382  merge_slice_summary(summary_result[0], sit_summary[0], sit_prob);
2383  merge_slice_summary(summary_result[1], sit_summary[1], sit_prob);
2384  merge_slice_summary(opp_summary_result[0], sit_opp_summary[0], sit_prob);
2385  merge_slice_summary(opp_summary_result[1], sit_opp_summary[1], sit_prob);
2386  }
2387  }
2388 
2389  // Swap in the results.
2390  summary[0].swap(summary_result[0]);
2391  summary[1].swap(summary_result[1]);
2392  opponent.summary[0].swap(opp_summary_result[0]);
2393  opponent.summary[1].swap(opp_summary_result[1]);
2394  }
2395 
2396 #if 0
2397  assert(summary[0].size() == res.size());
2398  assert(opponent.summary[0].size() == opp_res.size());
2399  for(unsigned int i = 0; i < summary[0].size(); ++i) {
2400  if(std::fabs(summary[0][i] - res[i]) > 0.000001) {
2401  PLAIN_LOG << "Mismatch for " << i << " hp: " << summary[0][i] << " should have been " << res[i];
2402  assert(false);
2403  }
2404  }
2405  for(unsigned int i = 0; i < opponent.summary[0].size(); ++i) {
2406  if(std::fabs(opponent.summary[0][i] - opp_res[i]) > 0.000001) {
2407  PLAIN_LOG << "Mismatch for " << i << " hp: " << opponent.summary[0][i] << " should have been " << opp_res[i];
2408  assert(false);
2409  }
2410  }
2411 #endif
2412 
2413  // Combine summary into distribution.
2414  if(summary[1].empty()) {
2415  hp_dist = summary[0];
2416  } else {
2417  const unsigned size = summary[0].size();
2418  hp_dist.resize(size);
2419  for(unsigned int i = 0; i < size; ++i)
2420  hp_dist[i] = summary[0][i] + summary[1][i];
2421  }
2422 
2423  if(opponent.summary[1].empty()) {
2424  opponent.hp_dist = opponent.summary[0];
2425  } else {
2426  const unsigned size = opponent.summary[0].size();
2427  opponent.hp_dist.resize(size);
2428  for(unsigned int i = 0; i < size; ++i)
2429  opponent.hp_dist[i] = opponent.summary[0][i] + opponent.summary[1][i];
2430  }
2431 
2432  // Chance that we / they were touched this time.
2433  double touched = 1.0 - self_not_hit;
2434  double opp_touched = 1.0 - opp_not_hit;
2435 
2436  poisoned = calculate_probability_of_debuff(poisoned, opponent.u_.poisons, touched, 1.0 - hp_dist[0],
2437  u_.experience + game_config::kill_xp(opponent.u_.level) >= u_.max_experience, opponent.hp_dist[0] - opp_already_dead);
2438  opponent.poisoned = calculate_probability_of_debuff(opponent.poisoned, u_.poisons, opp_touched, 1.0 - opponent.hp_dist[0],
2439  opponent.u_.experience + game_config::kill_xp(u_.level) >= opponent.u_.max_experience, hp_dist[0] - self_already_dead);
2440 
2441  /* The slowed probability depends on in how many rounds
2442  * the combatant happened to be slowed.
2443  * We need to recalculate it based on the HP distribution.
2444  */
2445  slowed = std::min(std::accumulate(summary[1].begin(), summary[1].end(), 0.0), 1.0);
2446  opponent.slowed = std::min(std::accumulate(opponent.summary[1].begin(), opponent.summary[1].end(), 0.0), 1.0);
2447 
2449  // We'll level up after the battle -> slow/poison will go away
2450  poisoned = 0.0;
2451  slowed = 0.0;
2452  }
2453  if(opponent.u_.experience + game_config::combat_xp(u_.level) >= opponent.u_.max_experience) {
2454  opponent.poisoned = 0.0;
2455  opponent.slowed = 0.0;
2456  }
2457 
2458  untouched *= self_not_hit;
2459  opponent.untouched *= opp_not_hit;
2460 }
2461 
2462 double combatant::average_hp(unsigned int healing) const
2463 {
2464  double total = 0;
2465 
2466  // Since sum of probabilities is 1.0, we can just tally weights.
2467  for(unsigned int i = 1; i < hp_dist.size(); ++i) {
2468  total += hp_dist[i] * std::min<unsigned int>(i + healing, u_.max_hp);
2469  }
2470 
2471  return total;
2472 }
2473 
2474 /* ** The stand-alone program ** */
2475 
2476 #if defined(BENCHMARK) || defined(CHECK)
2477 // We create a significant number of nasty-to-calculate units,
2478 // and test each one against the others.
2479 static const unsigned int NUM_UNITS = 50;
2480 
2481 #ifdef ATTACK_PREDICTION_DEBUG
2482 void list_combatant(const battle_context_unit_stats& stats, unsigned fighter)
2483 {
2484  std::ostringstream ss;
2485 
2486  // TODO: swarm_max? not strikes?
2487  ss << "#" << fighter << ": " << stats.swarm_max << "-" << stats.damage << "; "
2488  << stats.chance_to_hit << "% chance to hit; ";
2489 
2490  if(stats.drains) {
2491  ss << "drains, ";
2492  }
2493 
2494  if(stats.slows) {
2495  ss << "slows, ";
2496  }
2497 
2498  if(stats.rounds > 1) {
2499  ss << "berserk, ";
2500  }
2501 
2502  if(stats.swarm) {
2503  ss << "swarm(" << stats.num_blows << "), ";
2504  }
2505 
2506  if(stats.firststrike) {
2507  ss << "firststrike, ";
2508  }
2509 
2510  ss << "max hp = " << stats.max_hp << "\n";
2511 
2512  std::cout << ss.rdbuf() << std::endl;
2513 }
2514 #else
2515 void list_combatant(const battle_context_unit_stats&, unsigned)
2516 {
2517 }
2518 #endif
2519 
2520 #ifdef HUMAN_READABLE
2521 void combatant::print(const char label[], unsigned int battle, unsigned int fighter) const
2522 {
2523  std::ostringstream ss;
2524 
2525  // TODO: add this to the stream... no idea how to convert it properly...
2526  printf("#%06u: (%02u) %s%*c %u-%d; %uhp; %02u%% to hit; %.2f%% unscathed; ", battle, fighter, label,
2527  static_cast<int>(strlen(label)) - 12, ':', u_.swarm_max, u_.damage, u_.hp, u_.chance_to_hit, untouched * 100.0);
2528 
2529  if(u_.drains) {
2530  ss << "drains, ";
2531  }
2532 
2533  if(u_.slows) {
2534  ss << "slows, ";
2535  }
2536 
2537  if(u_.rounds > 1) {
2538  ss << "berserk, ";
2539  }
2540 
2541  if(u_.swarm) {
2542  ss << "swarm, ";
2543  }
2544 
2545  if(u_.firststrike) {
2546  ss << "firststrike, ";
2547  }
2548 
2549  std::cout << ss.rdbuf() << std::endl;
2550 
2551  // TODO: add to stream
2552  printf("maxhp=%zu ", hp_dist.size() - 1);
2553 
2554  int num_outputs = 0;
2555  for(unsigned int i = 0; i < hp_dist.size(); ++i) {
2556  if(hp_dist[i] != 0.0) {
2557  if(num_outputs++ % 6 == 0) {
2558  printf("\n\t");
2559  } else {
2560  printf(" ");
2561  }
2562 
2563  printf("%2u: %5.2f", i, hp_dist[i] * 100);
2564  }
2565  }
2566 
2567  printf("\n");
2568 }
2569 #elif defined(CHECK)
2570 void combatant::print(const char label[], unsigned int battle, unsigned int /*fighter*/) const
2571 {
2572  std::ostringstream ss;
2573 
2574  printf("#%u: %s: %d %u %u %2g%% ", battle, label, u_.damage, u_.swarm_max, u_.hp,
2575  static_cast<float>(u_.chance_to_hit));
2576 
2577  if(u_.drains) {
2578  ss << "drains, ";
2579  }
2580 
2581  if(u_.slows) {
2582  ss << "slows, ";
2583  }
2584 
2585  if(u_.rounds > 1) {
2586  ss << "berserk, ";
2587  }
2588 
2589  if(u_.swarm) {
2590  ss << "swarm, ";
2591  }
2592 
2593  if(u_.firststrike) {
2594  ss << "firststrike, ";
2595  }
2596 
2597  std::cout << ss.rdbuf() << std::endl;
2598 
2599  // TODO: add to stream
2600  printf("maxhp=%zu ", hp_dist.size() - 1);
2601  printf(" %.2f", untouched);
2602  for(unsigned int i = 0; i < hp_dist.size(); ++i) {
2603  printf(" %.2f", hp_dist[i] * 100);
2604  }
2605 
2606  printf("\n");
2607 }
2608 #else // ... BENCHMARK
2609 void combatant::print(const char /*label*/[], unsigned int /*battle*/, unsigned int /*fighter*/) const
2610 {
2611 }
2612 #endif
2613 
2614 void combatant::reset()
2615 {
2616  for(unsigned int i = 0; i < hp_dist.size(); ++i) {
2617  hp_dist[i] = 0.0;
2618  }
2619 
2620  untouched = 1.0;
2621  poisoned = u_.is_poisoned ? 1.0 : 0.0;
2622  slowed = u_.is_slowed ? 1.0 : 0.0;
2623  summary[0] = std::vector<double>();
2624  summary[1] = std::vector<double>();
2625 }
2626 
2627 static void run(unsigned specific_battle)
2628 {
2629  using std::chrono::duration_cast;
2630  using std::chrono::microseconds;
2631 
2632  // N^2 battles
2633  struct battle_context_unit_stats* stats[NUM_UNITS];
2634  struct combatant* u[NUM_UNITS];
2635  unsigned int i, j, k, battle = 0;
2636  std::chrono::high_resolution_clock::time_point start, end;
2637 
2638  for(i = 0; i < NUM_UNITS; ++i) {
2639  unsigned alt = i + 74; // To offset some cycles.
2640  // To get somewhat realistic performance data, try to approximate
2641  // hit point ranges for mainline units (say 25-60 max hitpoints?)
2642  unsigned max_hp = (i * 2) % 23 + (i * 3) % 14 + 25;
2643  unsigned hp = (alt * 5) % max_hp + 1;
2644  stats[i] = new battle_context_unit_stats(alt % 8 + 2, // damage
2645  (alt % 19 + 3) / 4, // number of strikes
2646  hp, max_hp,
2647  (i % 6) * 10 + 30, // hit chance
2648  (i % 13) % 4 == 0, // drains
2649  (i % 11) % 3 == 0, // slows
2650  false, // slowed
2651  i % 7 == 0, // berserk
2652  (i % 17) / 2 == 0, // firststrike
2653  i % 5 == 0); // swarm
2654  u[i] = new combatant(*stats[i]);
2655  list_combatant(*stats[i], i + 1);
2656  }
2657 
2658  start = std::chrono::high_resolution_clock::now();
2659  // Go through all fights with two attackers (j and k attacking i).
2660  for(i = 0; i < NUM_UNITS; ++i) {
2661  for(j = 0; j < NUM_UNITS; ++j) {
2662  if(i == j) {
2663  continue;
2664  }
2665 
2666  for(k = 0; k < NUM_UNITS; ++k) {
2667  if(i == k || j == k) {
2668  continue;
2669  }
2670 
2671  ++battle;
2672  if(specific_battle && battle != specific_battle) {
2673  continue;
2674  }
2675 
2676  // Fight!
2677  u[j]->fight(*u[i]);
2678  u[k]->fight(*u[i]);
2679  // Results.
2680  u[i]->print("Defender", battle, i + 1);
2681  u[j]->print("Attacker #1", battle, j + 1);
2682  u[k]->print("Attacker #2", battle, k + 1);
2683  // Start the next fight fresh.
2684  u[i]->reset();
2685  u[j]->reset();
2686  u[k]->reset();
2687  }
2688  }
2689  }
2690 
2691  end = std::chrono::high_resolution_clock::now();
2692 
2693  auto total = end - start;
2694 
2695 #ifdef BENCHMARK
2696  printf("Total time for %u combats was %lf\n", NUM_UNITS * (NUM_UNITS - 1) * (NUM_UNITS - 2),
2697  static_cast<double>(duration_cast<microseconds>(total).count()) / 1000000.0);
2698  printf("Time per calc = %li us\n", static_cast<long>(duration_cast<microseconds>(total).count())
2699  / (NUM_UNITS * (NUM_UNITS - 1) * (NUM_UNITS - 2)));
2700 #else
2701  printf("Total combats: %u\n", NUM_UNITS * (NUM_UNITS - 1) * (NUM_UNITS - 2));
2702 #endif
2703 
2704  for(i = 0; i < NUM_UNITS; ++i) {
2705  delete u[i];
2706  delete stats[i];
2707  }
2708 
2709  exit(0);
2710 }
2711 
2712 static battle_context_unit_stats* parse_unit(char*** argv)
2713 {
2714  // There are four required parameters.
2715  int add_to_argv = 4;
2716  int damage = atoi((*argv)[1]);
2717  int num_attacks = atoi((*argv)[2]);
2718  int hitpoints = atoi((*argv)[3]), max_hp = hitpoints;
2719  int hit_chance = atoi((*argv)[4]);
2720 
2721  // Parse the optional (fifth) parameter.
2722  bool drains = false, slows = false, slowed = false, berserk = false, firststrike = false, swarm = false;
2723  if((*argv)[5] && atoi((*argv)[5]) == 0) {
2724  // Optional parameter is present.
2725  ++add_to_argv;
2726 
2727  char* max = strstr((*argv)[5], "maxhp=");
2728  if(max) {
2729  max_hp = atoi(max + strlen("maxhp="));
2730  if(max_hp < hitpoints) {
2731  PLAIN_LOG << "maxhp must be at least hitpoints.";
2732  exit(1);
2733  }
2734  }
2735 
2736  if(strstr((*argv)[5], "drain")) {
2737  if(!max) {
2738  PLAIN_LOG << "WARNING: drain specified without maxhp; assuming uninjured.";
2739  }
2740 
2741  drains = true;
2742  }
2743 
2744  if(strstr((*argv)[5], "slows")) {
2745  slows = true;
2746  }
2747 
2748  if(strstr((*argv)[5], "slowed")) {
2749  slowed = true;
2750  }
2751 
2752  if(strstr((*argv)[5], "berserk")) {
2753  berserk = true;
2754  }
2755 
2756  if(strstr((*argv)[5], "firststrike")) {
2757  firststrike = true;
2758  }
2759 
2760  if(strstr((*argv)[5], "swarm")) {
2761  if(!max) {
2762  PLAIN_LOG << "WARNING: swarm specified without maxhp; assuming uninjured.";
2763  }
2764 
2765  swarm = true;
2766  }
2767  }
2768 
2769  // Update argv.
2770  *argv += add_to_argv;
2771 
2772  // Construct the stats and return.
2773  return new battle_context_unit_stats(
2774  damage, num_attacks, hitpoints, max_hp, hit_chance, drains, slows, slowed, berserk, firststrike, swarm);
2775 }
2776 
2777 int main(int argc, char* argv[])
2778 {
2779  battle_context_unit_stats *def_stats, *att_stats[20];
2780  combatant *def, *att[20];
2781  unsigned int i;
2782 
2783  if(argc < 3)
2784  run(argv[1] ? atoi(argv[1]) : 0);
2785 
2786  if(argc < 9) {
2787  PLAIN_LOG
2788  << "Usage: " << argv[0] << " [<battle>]\n\t" << argv[0] << " "
2789  << "<damage> <attacks> <hp> <hitprob> [drain,slows,slowed,swarm,firststrike,berserk,maxhp=<num>] "
2790  << "<damage> <attacks> <hp> <hitprob> [drain,slows,slowed,berserk,firststrike,swarm,maxhp=<num>] ...";
2791  exit(1);
2792  }
2793 
2794  def_stats = parse_unit(&argv);
2795  def = new combatant(*def_stats);
2796  for(i = 0; argv[1] && i < 19; ++i) {
2797  att_stats[i] = parse_unit(&argv);
2798  att[i] = new combatant(*att_stats[i]);
2799  }
2800 
2801  att[i] = nullptr;
2802 
2803  for(i = 0; att[i]; ++i) {
2804  debug(("Fighting next attacker\n"));
2805  att[i]->fight(*def);
2806  }
2807 
2808  def->print("Defender", 0, 0);
2809  for(i = 0; att[i]; ++i) {
2810  att[i]->print("Attacker", 0, i + 1);
2811  }
2812 
2813  for(i = 0; att[i]; ++i) {
2814  delete att[i];
2815  delete att_stats[i];
2816  }
2817 
2818  delete def;
2819  delete def_stats;
2820 
2821  return 0;
2822 }
2823 
2824 #endif // Standalone program
int kill_xp(int level)
Definition: game_config.hpp:48
unsigned int calc_blows(unsigned new_hp) const
Calculates the number of blows we would have if we had new_hp instead of the recorded hp...
Definition: attack.hpp:105
int combat_xp(int level)
Definition: game_config.hpp:53
#define PLAIN_LOG
Definition: log.hpp:258
double untouched
Resulting chance we were not hit by this opponent (important if it poisons)
std::vector< double > hp_dist
Resulting probability distribution (might be not as large as max_hp)
std::array< std::vector< double >, 2 > summary
Summary of matrix used to calculate last battle (unslowed & slowed).
int main(int, char **argv)
Definition: sdl2.cpp:5
unsigned int hp
Hitpoints of the unit at the beginning of the battle.
Definition: attack.hpp:70
Various functions that implement attacks and attack calculations.
double average_hp(unsigned int healing=0) const
What&#39;s the average hp (weighted average of hp_dist).
void clear(const std::string &key)
Definition: general.cpp:190
bool is_slowed
True if the unit is slowed at the beginning of the battle.
Definition: attack.hpp:57
bool slows
Attack slows opponent when it hits.
Definition: attack.hpp:58
int drain_constant
Base HP drained regardless of damage dealt.
Definition: attack.hpp:76
unsigned int chance_to_hit
Effective chance to hit as a percentage (all factors accounted for).
Definition: attack.hpp:72
bool poisons
Attack poisons opponent when it hits.
Definition: attack.hpp:62
int damage
Effective damage of the weapon (all factors accounted for).
Definition: attack.hpp:73
std::size_t size(const std::string &str)
Length in characters of a UTF-8 string.
Definition: unicode.cpp:87
std::string label
What to show in the filter&#39;s drop-down list.
Definition: manager.cpp:217
unsigned int level
Definition: attack.hpp:67
const battle_context_unit_stats & u_
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
unsigned int rounds
Berserk special can force us to fight more than one round.
Definition: attack.hpp:69
unsigned int swarm_min
Minimum number of blows with swarm (equal to num_blows if swarm isn&#39;t used).
Definition: attack.hpp:78
attack_prediction_mode
unsigned int get_random_element(T first, T last)
This helper method selects a random element from a container of floating-point numbers.
Definition: random.hpp:112
combatant(const battle_context_unit_stats &u, const combatant *prev=nullptr)
Construct a combatant.
void fight(combatant &opponent, bool levelup_considered=true)
Simulate a fight! Can be called multiple times for cumulative calculations.
Structure describing the statistics of a unit involved in the battle.
Definition: attack.hpp:51
bool damage_prediction_allow_monte_carlo_simulation()
Definition: general.cpp:992
bool get_random_bool(double probability)
This helper method returns true with the probability supplied as a parameter.
Definition: random.cpp:137
double slowed
Resulting chance we are slowed.
All combat-related info.
bool swarm
Attack has swarm special.
Definition: attack.hpp:63
int slow_damage
Effective damage if unit becomes slowed (== damage, if already slowed)
Definition: attack.hpp:74
static void print(std::stringstream &sstr, const std::string &queue, const std::string &id)
Definition: fire_event.cpp:30
std::size_t i
Definition: function.cpp:967
mock_party p
static map_location::DIRECTION s
unsigned int experience
Definition: attack.hpp:66
std::vector< std::string > names
Definition: build_info.cpp:67
static const unsigned int MONTE_CARLO_SIMULATION_THRESHOLD
bool firststrike
Attack has firststrike special.
Definition: attack.hpp:64
bool is_poisoned
True if the unit is poisoned at the beginning of the battle.
Definition: attack.hpp:56
#define debug(x)
int drain_percent
Percentage of damage recovered as health.
Definition: attack.hpp:75
double t
Definition: astarsearch.cpp:65
std::vector< std::string > split(const config_attribute_value &val)
map_location prev
Definition: astarsearch.cpp:66
Standard logging facilities (interface).
unsigned int num_blows
Effective number of blows, takes swarm into account.
Definition: attack.hpp:77
unsigned int max_hp
Maximum hitpoints of the unit.
Definition: attack.hpp:71
bool is_attacker
True if the unit is the attacker.
Definition: attack.hpp:55
#define e
unsigned int max_experience
Definition: attack.hpp:66
bool petrifies
Attack petrifies opponent when it hits.
Definition: attack.hpp:60
mock_char c
static rng & default_instance()
Definition: random.cpp:74
bool drains
Attack drains opponent when it hits.
Definition: attack.hpp:59
double poisoned
Resulting chance we are poisoned.
unsigned int swarm_max
Maximum number of blows with swarm (equal to num_blows if swarm isn&#39;t used).
Definition: attack.hpp:79
this class does not give synced random results derived classes might do.
Definition: random.hpp:28