The Battle for Wesnoth  1.17.17+dev
attack_prediction.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2006 - 2023
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  // In the a_initial vector, a_initial[x] is the chance of having exactly x hp.
1505  // Thus the index returned by get_random_element corresponds directly to an amount of hp.
1506  auto a_hp = static_cast<unsigned int>(rng.get_random_element(a_initial.begin(), a_initial.end()));
1507  auto b_hp = static_cast<unsigned int>(rng.get_random_element(b_initial.begin(), b_initial.end()));
1508  unsigned int a_strikes = calc_blows_a(a_hp);
1509  unsigned int b_strikes = calc_blows_b(b_hp);
1510 
1511  for(unsigned int j = 0u; j < rounds_ && a_hp > 0u && b_hp > 0u; ++j) {
1512  for(unsigned int k = 0u; k < std::max(a_strikes, b_strikes); ++k) {
1513  if(k < a_strikes) {
1514  if(rng.get_random_bool(a_hit_chance_)) {
1515  // A hits B
1516  unsigned int damage = a_slowed ? a_slow_damage_ : a_damage_;
1517  damage = std::min(damage, b_hp);
1518  b_hit = true;
1519  b_slowed |= a_slows_;
1520 
1521  int drain_amount = (a_drain_percent_ * static_cast<signed>(damage) / 100 + a_drain_constant_);
1522  a_hp = std::clamp(a_hp + drain_amount, 1u, a_max_hp_);
1523 
1524  b_hp -= damage;
1525 
1526  if(b_hp == 0u) {
1527  // A killed B
1528  break;
1529  }
1530  }
1531  }
1532 
1533  if(k < b_strikes) {
1534  if(rng.get_random_bool(b_hit_chance_)) {
1535  // B hits A
1536  unsigned int damage = b_slowed ? b_slow_damage_ : b_damage_;
1537  damage = std::min(damage, a_hp);
1538  a_hit = true;
1539  a_slowed |= b_slows_;
1540 
1541  int drain_amount = (b_drain_percent_ * static_cast<signed>(damage) / 100 + b_drain_constant_);
1542  b_hp = std::clamp(b_hp + drain_amount, 1u, b_max_hp_);
1543 
1544  a_hp -= damage;
1545 
1546  if(a_hp == 0u) {
1547  // B killed A
1548  break;
1549  }
1550  }
1551  }
1552  }
1553  }
1554 
1555  iterations_a_hit_ += a_hit ? 1 : 0;
1556  iterations_b_hit_ += b_hit ? 1 : 0;
1557 
1558  record_monte_carlo_result(a_hp, b_hp, a_slowed, b_slowed);
1559  }
1560 }
1561 
1562 /**
1563  * Otherwise the same as in probability_combat_matrix, but this needs to divide the values
1564  * by the number of iterations.
1565  */
1566 void monte_carlo_combat_matrix::extract_results(
1567  summary_t& summary_a, summary_t& summary_b)
1568 {
1569  // Reset the summaries.
1570  summary_a[0] = std::vector<double>(num_rows());
1571  summary_b[0] = std::vector<double>(num_cols());
1572 
1573  if(plane_used(A_SLOWED)) {
1574  summary_a[1] = std::vector<double>(num_rows());
1575  }
1576 
1577  if(plane_used(B_SLOWED)) {
1578  summary_b[1] = std::vector<double>(num_cols());
1579  }
1580 
1581  for(unsigned p = 0; p < NUM_PLANES; ++p) {
1582  if(!plane_used(p)) {
1583  continue;
1584  }
1585 
1586  // A is slow in planes 1 and 3.
1587  unsigned dst_a = (p & 1) ? 1u : 0u;
1588  // B is slow in planes 2 and 3.
1589  unsigned dst_b = (p & 2) ? 1u : 0u;
1590  sum(p, summary_a[dst_a], summary_b[dst_b]);
1591  }
1592 
1593  divide_all_elements(summary_a[0], static_cast<double>(NUM_ITERATIONS));
1594  divide_all_elements(summary_b[0], static_cast<double>(NUM_ITERATIONS));
1595 
1596  if(plane_used(A_SLOWED)) {
1597  divide_all_elements(summary_a[1], static_cast<double>(NUM_ITERATIONS));
1598  }
1599 
1600  if(plane_used(B_SLOWED)) {
1601  divide_all_elements(summary_b[1], static_cast<double>(NUM_ITERATIONS));
1602  }
1603 }
1604 
1605 double monte_carlo_combat_matrix::get_a_hit_probability() const
1606 {
1607  return static_cast<double>(iterations_a_hit_) / static_cast<double>(NUM_ITERATIONS);
1608 }
1609 
1610 double monte_carlo_combat_matrix::get_b_hit_probability() const
1611 {
1612  return static_cast<double>(iterations_b_hit_) / static_cast<double>(NUM_ITERATIONS);
1613 }
1614 
1615 unsigned int monte_carlo_combat_matrix::calc_blows_a(unsigned int a_hp) const
1616 {
1617  auto it = a_split_.begin();
1618  while(it != a_split_.end() && it->end_hp <= a_hp) {
1619  ++it;
1620  }
1621 
1622  if(it == a_split_.end()) {
1623  --it;
1624  }
1625 
1626  return it->strikes;
1627 }
1628 
1629 unsigned int monte_carlo_combat_matrix::calc_blows_b(unsigned int b_hp) const
1630 {
1631  auto it = b_split_.begin();
1632  while(it != b_split_.end() && it->end_hp <= b_hp) {
1633  ++it;
1634  }
1635 
1636  if(it == b_split_.end()) {
1637  --it;
1638  }
1639 
1640  return it->strikes;
1641 }
1642 
1643 void monte_carlo_combat_matrix::scale_probabilities(
1644  const std::vector<double>& source, std::vector<double>& target, double divisor, unsigned int singular_hp)
1645 {
1646  if(divisor == 0.0) {
1647  // Happens if the "target" HP distribution vector isn't used,
1648  // in which case it's not necessary to scale the probabilities.
1649  return;
1650  }
1651 
1652  if(source.empty()) {
1653  target.resize(singular_hp + 1u, 0.0);
1654  target[singular_hp] = 1.0;
1655  } else {
1656  std::transform(
1657  source.begin(), source.end(), std::back_inserter(target), [=](double prob) { return prob / divisor; });
1658  }
1659 
1660  assert(std::abs(std::accumulate(target.begin(), target.end(), 0.0) - 1.0) < 0.001);
1661 }
1662 
1663 void monte_carlo_combat_matrix::divide_all_elements(std::vector<double>& vec, double divisor)
1664 {
1665  for(double& e : vec) {
1666  e /= divisor;
1667  }
1668 }
1669 
1670 } // end anon namespace
1671 
1673  : hp_dist(u.max_hp + 1, 0.0)
1674  , untouched(0.0)
1675  , poisoned(0.0)
1676  , slowed(0.0)
1677  , u_(u)
1678 {
1679  // We inherit current state from previous combatant.
1680  if(prev) {
1681  summary[0] = prev->summary[0];
1682  summary[1] = prev->summary[1];
1683  hp_dist = prev->hp_dist;
1684  untouched = prev->untouched;
1685  poisoned = prev->poisoned;
1686  slowed = prev->slowed;
1687  } else {
1688  hp_dist[std::min(u.hp, u.max_hp)] = 1.0;
1689  untouched = 1.0;
1690  poisoned = u.is_poisoned ? 1.0 : 0.0;
1691  slowed = u.is_slowed ? 1.0 : 0.0;
1692 
1693  // If we're already slowed, create summary[1] so that probability calculation code
1694  // knows that we're slowed.
1695  if(u.is_slowed) {
1696  summary[0].resize(u.max_hp + 1, 0.0);
1697  summary[1] = hp_dist;
1698  }
1699  }
1700 }
1701 
1702 // Copy constructor (except use this copy of battle_context_unit_stats)
1704  : hp_dist(that.hp_dist)
1705  , untouched(that.untouched)
1706  , poisoned(that.poisoned)
1707  , slowed(that.slowed)
1708  , u_(u)
1709 {
1710  summary[0] = that.summary[0];
1711  summary[1] = that.summary[1];
1712 }
1713 
1714 namespace
1715 {
1716 enum class attack_prediction_mode { probability_calculation, monte_carlo_simulation };
1717 
1718 void forced_levelup(std::vector<double>& hp_dist)
1719 {
1720  /* If we survive the combat, we will level up. So the probability
1721  of death is unchanged, but all other cases get merged into the
1722  fully healed case. */
1723  auto i = hp_dist.begin();
1724  // Skip to the second value.
1725  for(++i; i != hp_dist.end(); ++i) {
1726  *i = 0;
1727  }
1728 
1729  // Full heal unless dead.
1730  hp_dist.back() = 1 - hp_dist.front();
1731 }
1732 
1733 void conditional_levelup(std::vector<double>& hp_dist, double kill_prob)
1734 {
1735  /* If we kill, we will level up. So then the damage we had becomes
1736  less probable since it's now conditional on us not leveling up.
1737  This doesn't apply to the probability of us dying, of course. */
1738  double scalefactor = 0;
1739  const double chance_to_survive = 1 - hp_dist.front();
1740  if(chance_to_survive > DBL_MIN) {
1741  scalefactor = 1 - kill_prob / chance_to_survive;
1742  }
1743 
1744  auto i = hp_dist.begin();
1745  // Skip to the second value.
1746  for(++i; i != hp_dist.end(); ++i) {
1747  *i *= scalefactor;
1748  }
1749 
1750  // Full heal if leveled up.
1751  hp_dist.back() += kill_prob;
1752 }
1753 
1754 /* Calculates the probability that we will be poisoned after the fight. Parameters:
1755  * initial_prob: how likely we are to be poisoned before the fight.
1756  * enemy_gives: true if the enemy poisons us.
1757  * prob_touched: probability the enemy touches us.
1758  * prob_stay_alive: probability we survive the fight alive.
1759  * kill_heals: true if killing the enemy heals the poison (in other words, we get a level-up).
1760  * prob_kill: probability we kill the enemy.
1761  */
1762 double calculate_probability_of_debuff(double initial_prob, bool enemy_gives, double prob_touched, double prob_stay_alive, bool kill_heals, double prob_kill)
1763 {
1764  assert(initial_prob >= 0.0 && initial_prob <= 1.0);
1765  /* In the add-on "Legend of the Invincibles", the "distant attack" ability sets the probability of being touched to zero.
1766  With some optimizing compilers, the probability can somehow get slightly negative, see bug #2342.
1767  Ensure that it gets non-negative. */
1768  prob_touched = std::max(prob_touched, 0.0);
1769  // Prob_stay_alive can get slightly negative because of a rounding error, so ensure that it gets non-negative.
1770  prob_stay_alive = std::max(prob_stay_alive, 0.0);
1771  // 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.
1772  // Likewise, it can get slightly negative if the unit already has negative HP.
1773  // Simply limit it to suitable range.
1774  prob_kill = std::clamp(prob_kill, 0.0, 1.0);
1775 
1776  // Probability we are already debuffed and the enemy doesn't hit us.
1777  const double prob_already_debuffed_not_touched = initial_prob * (1.0 - prob_touched);
1778  // Probability we are already debuffed and the enemy hits us.
1779  const double prob_already_debuffed_touched = initial_prob * prob_touched;
1780  // Probability we aren't debuffed and the enemy doesn't hit us.
1781  // const double prob_initially_healthy_not_touched = (1.0 - initial_prob) * (1.0 - prob_touched);
1782  // Probability we aren't debuffed and the enemy hits us.
1783  const double prob_initially_healthy_touched = (1.0 - initial_prob) * prob_touched;
1784 
1785  // Probability to survive if the enemy doesn't hit us.
1786  const double prob_survive_if_not_hit = 1.0;
1787  // Probability to survive if the enemy hits us.
1788  const double prob_survive_if_hit = prob_touched > 0.0 ? (prob_stay_alive - (1.0 - prob_touched)) / prob_touched : 1.0;
1789 
1790  // Probability to kill if we don't survive the fight.
1791  // const double prob_kill_if_not_survive = 0.0;
1792  // Probability to kill if we survive the fight.
1793  const double prob_kill_if_survive = prob_stay_alive > 0.0 ? prob_kill / prob_stay_alive : 0.0;
1794 
1795  // Probability to be debuffed after the fight, calculated in multiple stages.
1796  double prob_debuff = 0.0;
1797 
1798  if(!kill_heals) {
1799  prob_debuff += prob_already_debuffed_not_touched;
1800  } else {
1801  prob_debuff += prob_already_debuffed_not_touched * (1.0 - prob_survive_if_not_hit * prob_kill_if_survive);
1802  }
1803 
1804  if(!kill_heals) {
1805  prob_debuff += prob_already_debuffed_touched;
1806  } else {
1807  prob_debuff += prob_already_debuffed_touched * (1.0 - prob_survive_if_hit * prob_kill_if_survive);
1808  }
1809 
1810  // "Originally not debuffed, not hit" situation never results in us getting debuffed. Skipping.
1811 
1812  if(!enemy_gives) {
1813  // Do nothing.
1814  } else if(!kill_heals) {
1815  prob_debuff += prob_initially_healthy_touched;
1816  } else {
1817  prob_debuff += prob_initially_healthy_touched * (1.0 - prob_survive_if_hit * prob_kill_if_survive);
1818  }
1819 
1820  return prob_debuff;
1821 }
1822 
1823 // Rounds a probability that's extremely close to 0 or 1 to exactly 0 or 1.
1824 void round_prob_if_close_to_sure(double& prob)
1825 {
1826  if(prob < 1.0e-9) {
1827  prob = 0.0;
1828  } else if(prob > 1.0 - 1.0e-9) {
1829  prob = 1.0;
1830  }
1831 }
1832 
1833 /**
1834  * Returns the smallest HP we could possibly have based on the provided
1835  * hit point distribution.
1836  */
1837 unsigned min_hp(const std::vector<double>& hp_dist, unsigned def)
1838 {
1839  const unsigned size = hp_dist.size();
1840 
1841  // Look for a nonzero entry.
1842  for(unsigned i = 0; i != size; ++i) {
1843  if(hp_dist[i] != 0.0) {
1844  return i;
1845  }
1846  }
1847 
1848  // Either the distribution is empty or is full of zeros, so
1849  // return the default.
1850  return def;
1851 }
1852 
1853 /**
1854  * Returns a number that approximates the complexity of the fight,
1855  * for the purpose of determining if it's faster to calculate exact
1856  * probabilities or to run a Monte Carlo simulation.
1857  * Ignores the numbers of rounds and strikes because these slow down
1858  * both calculation modes.
1859  */
1860 unsigned int fight_complexity(unsigned int num_slices,
1861  unsigned int opp_num_slices,
1862  const battle_context_unit_stats& stats,
1863  const battle_context_unit_stats& opp_stats)
1864 {
1865  return num_slices * opp_num_slices * ((stats.slows || opp_stats.is_slowed) ? 2 : 1)
1866  * ((opp_stats.slows || stats.is_slowed) ? 2 : 1) * stats.max_hp * opp_stats.max_hp;
1867 }
1868 
1869 /**
1870  * Returns the plane index for the slow/no-slow state of the combatants.
1871  */
1872 unsigned int plane_index(const battle_context_unit_stats& stats,
1873  const battle_context_unit_stats& opp_stats)
1874 {
1875  return (stats.is_slowed ? 1 : 0) | (opp_stats.is_slowed ? 2 : 0);
1876 }
1877 
1878 // Combat without chance of death, berserk, slow or drain is simple.
1879 void no_death_fight(const battle_context_unit_stats& stats,
1880  const battle_context_unit_stats& opp_stats,
1881  unsigned strikes,
1882  unsigned opp_strikes,
1883  std::vector<double>& hp_dist,
1884  std::vector<double>& opp_hp_dist,
1885  double& self_not_hit,
1886  double& opp_not_hit,
1887  bool levelup_considered)
1888 {
1889  // Our strikes.
1890  // If we were killed in an earlier fight, we don't get to attack.
1891  // (Most likely case: we are a first striking defender subject to a series
1892  // of attacks.)
1893  const double alive_prob = hp_dist.empty() ? 1.0 : 1.0 - hp_dist[0];
1894  const double hit_chance = (stats.chance_to_hit / 100.0) * alive_prob;
1895 
1896  if(opp_hp_dist.empty()) {
1897  // Starts with a known HP, so Pascal's triangle.
1898  opp_hp_dist = std::vector<double>(opp_stats.max_hp + 1);
1899  opp_hp_dist[opp_stats.hp] = 1.0;
1900 
1901  for(unsigned int i = 0; i < strikes; ++i) {
1902  for(int j = i; j >= 0; j--) {
1903  unsigned src_index = opp_stats.hp - j * stats.damage;
1904  double move = opp_hp_dist[src_index] * hit_chance;
1905  opp_hp_dist[src_index] -= move;
1906  opp_hp_dist[src_index - stats.damage] += move;
1907  }
1908 
1909  opp_not_hit *= 1.0 - hit_chance;
1910  }
1911  } else {
1912  // HP could be spread anywhere, iterate through whole thing.
1913  for(unsigned int i = 0; i < strikes; ++i) {
1914  for(unsigned int j = stats.damage; j < opp_hp_dist.size(); ++j) {
1915  double move = opp_hp_dist[j] * hit_chance;
1916  opp_hp_dist[j] -= move;
1917  opp_hp_dist[j - stats.damage] += move;
1918  }
1919  opp_not_hit *= 1.0 - hit_chance;
1920  }
1921  }
1922 
1923  // Opponent's strikes
1924  // If opponent was killed in an earlier fight, they don't get to attack.
1925  const double opp_alive_prob = opp_hp_dist.empty() ? 1.0 : 1.0 - opp_hp_dist[0];
1926  const double opp_hit_chance = (opp_stats.chance_to_hit / 100.0) * opp_alive_prob;
1927 
1928  if(hp_dist.empty()) {
1929  // Starts with a known HP, so Pascal's triangle.
1930  hp_dist = std::vector<double>(stats.max_hp + 1);
1931  hp_dist[stats.hp] = 1.0;
1932  for(unsigned int i = 0; i < opp_strikes; ++i) {
1933  for(int j = i; j >= 0; j--) {
1934  unsigned src_index = stats.hp - j * opp_stats.damage;
1935  double move = hp_dist[src_index] * opp_hit_chance;
1936  hp_dist[src_index] -= move;
1937  hp_dist[src_index - opp_stats.damage] += move;
1938  }
1939 
1940  self_not_hit *= 1.0 - opp_hit_chance;
1941  }
1942  } else {
1943  // HP could be spread anywhere, iterate through whole thing.
1944  for(unsigned int i = 0; i < opp_strikes; ++i) {
1945  for(unsigned int j = opp_stats.damage; j < hp_dist.size(); ++j) {
1946  double move = hp_dist[j] * opp_hit_chance;
1947  hp_dist[j] -= move;
1948  hp_dist[j - opp_stats.damage] += move;
1949  }
1950 
1951  self_not_hit *= 1.0 - opp_hit_chance;
1952  }
1953  }
1954 
1955  if(!levelup_considered) {
1956  return;
1957  }
1958 
1959  if(stats.experience + opp_stats.level >= stats.max_experience) {
1960  forced_levelup(hp_dist);
1961  }
1962 
1963  if(opp_stats.experience + stats.level >= opp_stats.max_experience) {
1964  forced_levelup(opp_hp_dist);
1965  }
1966 }
1967 
1968 // Combat with <= 1 strike each is simple, too.
1969 void one_strike_fight(const battle_context_unit_stats& stats,
1970  const battle_context_unit_stats& opp_stats,
1971  unsigned strikes,
1972  unsigned opp_strikes,
1973  std::vector<double>& hp_dist,
1974  std::vector<double>& opp_hp_dist,
1975  double& self_not_hit,
1976  double& opp_not_hit,
1977  bool levelup_considered)
1978 {
1979  // If we were killed in an earlier fight, we don't get to attack.
1980  // (Most likely case: we are a first striking defender subject to a series
1981  // of attacks.)
1982  double alive_prob = hp_dist.empty() ? 1.0 : 1.0 - hp_dist[0];
1983  if(stats.hp == 0) {
1984  alive_prob = 0.0;
1985  }
1986  const double hit_chance = (stats.chance_to_hit / 100.0) * alive_prob;
1987 
1988  if(opp_hp_dist.empty()) {
1989  opp_hp_dist = std::vector<double>(opp_stats.max_hp + 1);
1990  if(strikes == 1 && opp_stats.hp > 0) {
1991  opp_hp_dist[opp_stats.hp] = 1.0 - hit_chance;
1992  opp_hp_dist[std::max<int>(opp_stats.hp - stats.damage, 0)] = hit_chance;
1993  opp_not_hit *= 1.0 - hit_chance;
1994  } else {
1995  opp_hp_dist[opp_stats.hp] = 1.0;
1996  }
1997  } else {
1998  if(strikes == 1) {
1999  for(unsigned int i = 1; i < opp_hp_dist.size(); ++i) {
2000  double move = opp_hp_dist[i] * hit_chance;
2001  opp_hp_dist[i] -= move;
2002  opp_hp_dist[std::max<int>(i - stats.damage, 0)] += move;
2003  }
2004 
2005  opp_not_hit *= 1.0 - hit_chance;
2006  }
2007  }
2008 
2009  // If we killed opponent, it won't attack us.
2010  const double opp_attack_prob = (1.0 - opp_hp_dist[0]) * alive_prob;
2011  const double opp_hit_chance = (opp_stats.chance_to_hit / 100.0) * opp_attack_prob;
2012 
2013  if(hp_dist.empty()) {
2014  hp_dist = std::vector<double>(stats.max_hp + 1);
2015  if(opp_strikes == 1 && stats.hp > 0) {
2016  hp_dist[stats.hp] = 1.0 - opp_hit_chance;
2017  hp_dist[std::max<int>(stats.hp - opp_stats.damage, 0)] = opp_hit_chance;
2018  self_not_hit *= 1.0 - opp_hit_chance;
2019  } else {
2020  hp_dist[stats.hp] = 1.0;
2021  }
2022  } else {
2023  if(opp_strikes == 1) {
2024  for(unsigned int i = 1; i < hp_dist.size(); ++i) {
2025  double move = hp_dist[i] * opp_hit_chance;
2026  hp_dist[i] -= move;
2027  hp_dist[std::max<int>(i - opp_stats.damage, 0)] += move;
2028  }
2029 
2030  self_not_hit *= 1.0 - opp_hit_chance;
2031  }
2032  }
2033 
2034  if(!levelup_considered) {
2035  return;
2036  }
2037 
2038  if(stats.experience + game_config::combat_xp(opp_stats.level) >= stats.max_experience) {
2039  forced_levelup(hp_dist);
2040  } else if(stats.experience + game_config::kill_xp(opp_stats.level) >= stats.max_experience) {
2041  conditional_levelup(hp_dist, opp_hp_dist[0]);
2042  }
2043 
2044  if(opp_stats.experience + game_config::combat_xp(stats.level) >= opp_stats.max_experience) {
2045  forced_levelup(opp_hp_dist);
2046  } else if(opp_stats.experience + game_config::kill_xp(stats.level) >= opp_stats.max_experience) {
2047  conditional_levelup(opp_hp_dist, hp_dist[0]);
2048  }
2049 }
2050 
2051 /* The parameters "split", "opp_split", "initially_slowed_chance" and
2052 "opp_initially_slowed_chance" are ignored in the probability calculation mode. */
2053 void complex_fight(attack_prediction_mode mode,
2054  const battle_context_unit_stats& stats,
2055  const battle_context_unit_stats& opp_stats,
2056  unsigned strikes,
2057  unsigned opp_strikes,
2058  summary_t& summary,
2059  summary_t& opp_summary,
2060  double& self_not_hit,
2061  double& opp_not_hit,
2062  bool levelup_considered,
2063  std::vector<combat_slice> split,
2064  std::vector<combat_slice> opp_split,
2065  double initially_slowed_chance,
2066  double opp_initially_slowed_chance)
2067 {
2068  unsigned int rounds = std::max<unsigned int>(stats.rounds, opp_stats.rounds);
2069  unsigned max_attacks = std::max(strikes, opp_strikes);
2070 
2071  debug(("A gets %u attacks, B %u.\n", strikes, opp_strikes));
2072 
2073  unsigned int a_damage = stats.damage, a_slow_damage = stats.slow_damage;
2074  unsigned int b_damage = opp_stats.damage, b_slow_damage = opp_stats.slow_damage;
2075 
2076  // To simulate stoning, we set to amount which kills, and re-adjust after.
2077  /** @todo FIXME: This doesn't work for rolling calculations, just first battle.
2078  It also does not work if combined with (percentage) drain. */
2079  if(stats.petrifies) {
2080  a_damage = a_slow_damage = opp_stats.max_hp;
2081  }
2082 
2083  if(opp_stats.petrifies) {
2084  b_damage = b_slow_damage = stats.max_hp;
2085  }
2086 
2087  const double original_self_not_hit = self_not_hit;
2088  const double original_opp_not_hit = opp_not_hit;
2089  const double hit_chance = stats.chance_to_hit / 100.0;
2090  const double opp_hit_chance = opp_stats.chance_to_hit / 100.0;
2091  double self_hit = 0.0;
2092  double opp_hit = 0.0;
2093  double self_hit_unknown = 1.0; // Probability we don't yet know if A will be hit or not
2094  double opp_hit_unknown = 1.0; // Ditto for B
2095 
2096  // Prepare the matrix that will do our calculations.
2097  std::unique_ptr<combat_matrix> m;
2098  if(mode == attack_prediction_mode::probability_calculation) {
2099  debug(("Using exact probability calculations.\n"));
2100 
2101  probability_combat_matrix* pm = new probability_combat_matrix(stats.max_hp, opp_stats.max_hp, stats.hp,
2102  opp_stats.hp, summary, opp_summary, stats.slows, opp_stats.slows,
2103  a_damage, b_damage, a_slow_damage, b_slow_damage,
2104  stats.drain_percent, opp_stats.drain_percent, stats.drain_constant, opp_stats.drain_constant);
2105  m.reset(pm);
2106 
2107  do {
2108  for(unsigned int i = 0; i < max_attacks; ++i) {
2109  if(i < strikes) {
2110  debug(("A strikes\n"));
2111  double b_already_dead = pm->dead_prob_b();
2112  pm->receive_blow_b(hit_chance);
2113  pm->dump();
2114 
2115  double first_hit = hit_chance * opp_hit_unknown;
2116  opp_hit += first_hit;
2117  opp_hit_unknown -= first_hit;
2118  double both_were_alive = 1.0 - b_already_dead - pm->dead_prob_a();
2119  double this_hit_killed_b = both_were_alive != 0.0 ? (pm->dead_prob_b() - b_already_dead) / both_were_alive : 1.0;
2120  self_hit_unknown *= (1.0 - this_hit_killed_b);
2121  }
2122  if(i < opp_strikes) {
2123  debug(("B strikes\n"));
2124  double a_already_dead = pm->dead_prob_a();
2125  pm->receive_blow_a(opp_hit_chance);
2126  pm->dump();
2127 
2128  double first_hit = opp_hit_chance * self_hit_unknown;
2129  self_hit += first_hit;
2130  self_hit_unknown -= first_hit;
2131  double both_were_alive = 1.0 - a_already_dead - pm->dead_prob_b();
2132  double this_hit_killed_a = both_were_alive != 0.0 ? (pm->dead_prob_a() - a_already_dead) / both_were_alive : 1.0;
2133  opp_hit_unknown *= (1.0 - this_hit_killed_a);
2134  }
2135  }
2136 
2137  debug(("Combat ends:\n"));
2138  pm->dump();
2139  } while(--rounds && pm->dead_prob() < 0.99);
2140 
2141  self_hit = std::min(self_hit, 1.0);
2142  opp_hit = std::min(opp_hit, 1.0);
2143 
2144  self_not_hit = original_self_not_hit * (1.0 - self_hit);
2145  opp_not_hit = original_opp_not_hit * (1.0 - opp_hit);
2146 
2147  if(stats.slows) {
2148  /* The calculation method for the "not hit" probability above is incorrect if either unit can slow.
2149  * Because a slowed unit deals less damage, it is more likely for the slowing unit to be alive if it
2150  * has hit the other unit. In that situation, the "not hit" probability can no longer be calculated
2151  * with simple addition.
2152  * Instead, just fetch the probability from the combat matrix.
2153  */
2154  unsigned int plane = plane_index(stats, opp_stats);
2155  double not_hit = pm->col_sum(plane, opp_stats.hp) + ((plane & 1) ? 0.0 : pm->col_sum(plane | 1, opp_stats.hp));
2156  opp_not_hit = original_opp_not_hit * not_hit;
2157  }
2158  if(opp_stats.slows) {
2159  unsigned int plane = plane_index(stats, opp_stats);
2160  double not_hit = pm->row_sum(plane, stats.hp) + ((plane & 2) ? 0.0 : pm->row_sum(plane | 2, stats.hp));
2161  self_not_hit = original_self_not_hit * not_hit;
2162  }
2163  } else {
2164  debug(("Using Monte Carlo simulation.\n"));
2165 
2166  monte_carlo_combat_matrix* mcm = new monte_carlo_combat_matrix(stats.max_hp, opp_stats.max_hp, stats.hp,
2167  opp_stats.hp, summary, opp_summary, stats.slows, opp_stats.slows,
2168  a_damage, b_damage, a_slow_damage, b_slow_damage,
2169  stats.drain_percent, opp_stats.drain_percent, stats.drain_constant, opp_stats.drain_constant, rounds,
2170  hit_chance, opp_hit_chance, split, opp_split, initially_slowed_chance, opp_initially_slowed_chance);
2171  m.reset(mcm);
2172 
2173  mcm->simulate();
2174  debug(("Combat ends:\n"));
2175  mcm->dump();
2176 
2177  self_not_hit = 1.0 - mcm->get_a_hit_probability();
2178  opp_not_hit = 1.0 - mcm->get_b_hit_probability();
2179  }
2180 
2181  if(stats.petrifies) {
2182  m->remove_petrify_distortion_a(stats.damage, stats.slow_damage, opp_stats.hp);
2183  }
2184 
2185  if(opp_stats.petrifies) {
2186  m->remove_petrify_distortion_b(opp_stats.damage, opp_stats.slow_damage, stats.hp);
2187  }
2188 
2189  if(levelup_considered) {
2190  if(stats.experience + game_config::combat_xp(opp_stats.level) >= stats.max_experience) {
2191  m->forced_levelup_a();
2192  } else if(stats.experience + game_config::kill_xp(opp_stats.level) >= stats.max_experience) {
2193  m->conditional_levelup_a();
2194  }
2195 
2196  if(opp_stats.experience + game_config::combat_xp(stats.level) >= opp_stats.max_experience) {
2197  m->forced_levelup_b();
2198  } else if(opp_stats.experience + game_config::kill_xp(stats.level) >= opp_stats.max_experience) {
2199  m->conditional_levelup_b();
2200  }
2201  }
2202 
2203  // We extract results separately, then combine.
2204  m->extract_results(summary, opp_summary);
2205 }
2206 
2207 /**
2208  * Chooses the best of the various known combat calculations for the current
2209  * situation.
2210  */
2211 void do_fight(const battle_context_unit_stats& stats,
2212  const battle_context_unit_stats& opp_stats,
2213  unsigned strikes,
2214  unsigned opp_strikes,
2215  summary_t& summary,
2216  summary_t& opp_summary,
2217  double& self_not_hit,
2218  double& opp_not_hit,
2219  bool levelup_considered)
2220 {
2221  // Optimization only works in the simple cases (no slow, no drain,
2222  // no petrify, no berserk, and no slowed results from an earlier combat).
2223  if(!stats.slows && !opp_stats.slows && !stats.drains && !opp_stats.drains && !stats.petrifies
2224  && !opp_stats.petrifies && stats.rounds == 1 && opp_stats.rounds == 1 && summary[1].empty()
2225  && opp_summary[1].empty())
2226  {
2227  if(strikes <= 1 && opp_strikes <= 1) {
2228  one_strike_fight(stats, opp_stats, strikes, opp_strikes, summary[0], opp_summary[0], self_not_hit,
2229  opp_not_hit, levelup_considered);
2230  } else if(strikes * stats.damage < min_hp(opp_summary[0], opp_stats.hp)
2231  && opp_strikes * opp_stats.damage < min_hp(summary[0], stats.hp)) {
2232  no_death_fight(stats, opp_stats, strikes, opp_strikes, summary[0], opp_summary[0], self_not_hit,
2233  opp_not_hit, levelup_considered);
2234  } else {
2235  complex_fight(attack_prediction_mode::probability_calculation, stats, opp_stats, strikes, opp_strikes,
2236  summary, opp_summary, self_not_hit, opp_not_hit, levelup_considered, std::vector<combat_slice>(),
2237  std::vector<combat_slice>(), 0.0, 0.0);
2238  }
2239  } else {
2240  complex_fight(attack_prediction_mode::probability_calculation, stats, opp_stats, strikes, opp_strikes, summary,
2241  opp_summary, self_not_hit, opp_not_hit, levelup_considered, std::vector<combat_slice>(),
2242  std::vector<combat_slice>(), 0.0, 0.0);
2243  }
2244 }
2245 
2246 /**
2247  * Initializes a hit point summary (assumed empty) based on the source.
2248  * Only the part of the source from begin_hp up to (not including) end_hp
2249  * is kept, and all values get scaled by prob.
2250  */
2251 void init_slice_summary(
2252  std::vector<double>& dst, const std::vector<double>& src, unsigned begin_hp, unsigned end_hp, double prob)
2253 {
2254  if(src.empty()) {
2255  // Nothing to do.
2256  return;
2257  }
2258 
2259  const unsigned size = src.size();
2260  // Avoid going over the end of the vector.
2261  if(end_hp > size) {
2262  end_hp = size;
2263  }
2264 
2265  // Initialize the destination.
2266  dst.resize(size, 0.0);
2267  for(unsigned i = begin_hp; i < end_hp; ++i) {
2268  dst[i] = src[i] / prob;
2269  }
2270 }
2271 
2272 /**
2273  * Merges the summary results of simulation into an overall summary.
2274  * This uses prob to reverse the scaling that was done in init_slice_summary().
2275  */
2276 void merge_slice_summary(std::vector<double>& dst, const std::vector<double>& src, double prob)
2277 {
2278  const unsigned size = src.size();
2279 
2280  // Make sure we have enough space.
2281  if(dst.size() < size) {
2282  dst.resize(size, 0.0);
2283  }
2284 
2285  // Merge the data.
2286  for(unsigned i = 0; i != size; ++i) {
2287  dst[i] += src[i] * prob;
2288  }
2289 }
2290 
2291 } // end anon namespace
2292 
2293 // Two man enter. One man leave!
2294 // ... Or maybe two. But definitely not three.
2295 // Of course, one could be a woman. Or both.
2296 // And either could be non-human, too.
2297 // Um, ok, it was a stupid thing to say.
2298 void combatant::fight(combatant& opponent, bool levelup_considered)
2299 {
2300  // If defender has firststrike and we don't, reverse.
2301  if(opponent.u_.firststrike && !u_.firststrike) {
2302  opponent.fight(*this, levelup_considered);
2303  return;
2304  }
2305 
2306 #ifdef ATTACK_PREDICTION_DEBUG
2307  printf("A:\n");
2308  dump(u_);
2309  printf("B:\n");
2310  dump(opponent.u_);
2311 #endif
2312 
2313 #if 0
2314  std::vector<double> prev = summary[0], opp_prev = opponent.summary[0];
2315  complex_fight(opponent, 1);
2316  std::vector<double> res = summary[0], opp_res = opponent.summary[0];
2317  summary[0] = prev;
2318  opponent.summary[0] = opp_prev;
2319 #endif
2320 
2321  // The chance so far of not being hit this combat:
2322  double self_not_hit = 1.0;
2323  double opp_not_hit = 1.0;
2324 
2325  // The probability of being already dead before the fight begins:
2326  double self_already_dead = hp_dist[0];
2327  double opp_already_dead = opponent.hp_dist[0];
2328 
2329  // If incoming slow probabilities are extremely close to 0 or 1, round them to exactly 0 or 1 (bug #3321)
2330  round_prob_if_close_to_sure(slowed);
2331  round_prob_if_close_to_sure(opponent.slowed);
2332 
2333  // If we've fought before and we have swarm, we might have to split the
2334  // calculation by number of attacks.
2335  const std::vector<combat_slice> split = split_summary(u_, summary);
2336  const std::vector<combat_slice> opp_split = split_summary(opponent.u_, opponent.summary);
2337 
2338  bool use_monte_carlo_simulation =
2339  fight_complexity(split.size(), opp_split.size(), u_, opponent.u_) > MONTE_CARLO_SIMULATION_THRESHOLD
2341 
2342  if(use_monte_carlo_simulation) {
2343  // A very complex fight. Use Monte Carlo simulation instead of exact
2344  // probability calculations.
2345  complex_fight(attack_prediction_mode::monte_carlo_simulation, u_, opponent.u_, u_.num_blows,
2346  opponent.u_.num_blows, summary, opponent.summary, self_not_hit, opp_not_hit, levelup_considered, split,
2347  opp_split, slowed, opponent.slowed);
2348  } else if(split.size() == 1 && opp_split.size() == 1) {
2349  // No special treatment due to swarm is needed. Ignore the split.
2350  do_fight(u_, opponent.u_, u_.num_blows, opponent.u_.num_blows, summary, opponent.summary, self_not_hit,
2351  opp_not_hit, levelup_considered);
2352  } else {
2353  // Storage for the accumulated hit point distributions.
2354  summary_t summary_result, opp_summary_result;
2355  // The chance of not being hit becomes an accumulated chance:
2356  self_not_hit = 0.0;
2357  opp_not_hit = 0.0;
2358 
2359  // Loop through all the potential combat situations.
2360  for(unsigned s = 0; s != split.size(); ++s) {
2361  for(unsigned t = 0; t != opp_split.size(); ++t) {
2362  const double sit_prob = split[s].prob * opp_split[t].prob;
2363 
2364  // Create summaries for this potential combat situation.
2365  summary_t sit_summary, sit_opp_summary;
2366  init_slice_summary(sit_summary[0], summary[0], split[s].begin_hp, split[s].end_hp, split[s].prob);
2367  init_slice_summary(sit_summary[1], summary[1], split[s].begin_hp, split[s].end_hp, split[s].prob);
2368  init_slice_summary(sit_opp_summary[0], opponent.summary[0], opp_split[t].begin_hp, opp_split[t].end_hp,
2369  opp_split[t].prob);
2370  init_slice_summary(sit_opp_summary[1], opponent.summary[1], opp_split[t].begin_hp, opp_split[t].end_hp,
2371  opp_split[t].prob);
2372 
2373  // Scale the "not hit" chance for this situation by the chance that
2374  // this situation applies.
2375  double sit_self_not_hit = sit_prob;
2376  double sit_opp_not_hit = sit_prob;
2377 
2378  do_fight(u_, opponent.u_, split[s].strikes, opp_split[t].strikes, sit_summary, sit_opp_summary,
2379  sit_self_not_hit, sit_opp_not_hit, levelup_considered);
2380 
2381  // Collect the results.
2382  self_not_hit += sit_self_not_hit;
2383  opp_not_hit += sit_opp_not_hit;
2384  merge_slice_summary(summary_result[0], sit_summary[0], sit_prob);
2385  merge_slice_summary(summary_result[1], sit_summary[1], sit_prob);
2386  merge_slice_summary(opp_summary_result[0], sit_opp_summary[0], sit_prob);
2387  merge_slice_summary(opp_summary_result[1], sit_opp_summary[1], sit_prob);
2388  }
2389  }
2390 
2391  // Swap in the results.
2392  summary[0].swap(summary_result[0]);
2393  summary[1].swap(summary_result[1]);
2394  opponent.summary[0].swap(opp_summary_result[0]);
2395  opponent.summary[1].swap(opp_summary_result[1]);
2396  }
2397 
2398 #if 0
2399  assert(summary[0].size() == res.size());
2400  assert(opponent.summary[0].size() == opp_res.size());
2401  for(unsigned int i = 0; i < summary[0].size(); ++i) {
2402  if(std::fabs(summary[0][i] - res[i]) > 0.000001) {
2403  PLAIN_LOG << "Mismatch for " << i << " hp: " << summary[0][i] << " should have been " << res[i];
2404  assert(false);
2405  }
2406  }
2407  for(unsigned int i = 0; i < opponent.summary[0].size(); ++i) {
2408  if(std::fabs(opponent.summary[0][i] - opp_res[i]) > 0.000001) {
2409  PLAIN_LOG << "Mismatch for " << i << " hp: " << opponent.summary[0][i] << " should have been " << opp_res[i];
2410  assert(false);
2411  }
2412  }
2413 #endif
2414 
2415  // Combine summary into distribution.
2416  if(summary[1].empty()) {
2417  hp_dist = summary[0];
2418  } else {
2419  const unsigned size = summary[0].size();
2420  hp_dist.resize(size);
2421  for(unsigned int i = 0; i < size; ++i)
2422  hp_dist[i] = summary[0][i] + summary[1][i];
2423  }
2424 
2425  if(opponent.summary[1].empty()) {
2426  opponent.hp_dist = opponent.summary[0];
2427  } else {
2428  const unsigned size = opponent.summary[0].size();
2429  opponent.hp_dist.resize(size);
2430  for(unsigned int i = 0; i < size; ++i)
2431  opponent.hp_dist[i] = opponent.summary[0][i] + opponent.summary[1][i];
2432  }
2433 
2434  // Chance that we / they were touched this time.
2435  double touched = 1.0 - self_not_hit;
2436  double opp_touched = 1.0 - opp_not_hit;
2437 
2438  poisoned = calculate_probability_of_debuff(poisoned, opponent.u_.poisons, touched, 1.0 - hp_dist[0],
2439  u_.experience + game_config::kill_xp(opponent.u_.level) >= u_.max_experience, opponent.hp_dist[0] - opp_already_dead);
2440  opponent.poisoned = calculate_probability_of_debuff(opponent.poisoned, u_.poisons, opp_touched, 1.0 - opponent.hp_dist[0],
2441  opponent.u_.experience + game_config::kill_xp(u_.level) >= opponent.u_.max_experience, hp_dist[0] - self_already_dead);
2442 
2443  /* The slowed probability depends on in how many rounds
2444  * the combatant happened to be slowed.
2445  * We need to recalculate it based on the HP distribution.
2446  */
2447  slowed = std::min(std::accumulate(summary[1].begin(), summary[1].end(), 0.0), 1.0);
2448  opponent.slowed = std::min(std::accumulate(opponent.summary[1].begin(), opponent.summary[1].end(), 0.0), 1.0);
2449 
2451  // We'll level up after the battle -> slow/poison will go away
2452  poisoned = 0.0;
2453  slowed = 0.0;
2454  }
2455  if(opponent.u_.experience + game_config::combat_xp(u_.level) >= opponent.u_.max_experience) {
2456  opponent.poisoned = 0.0;
2457  opponent.slowed = 0.0;
2458  }
2459 
2460  untouched *= self_not_hit;
2461  opponent.untouched *= opp_not_hit;
2462 }
2463 
2464 double combatant::average_hp(unsigned int healing) const
2465 {
2466  double total = 0;
2467 
2468  // Since sum of probabilities is 1.0, we can just tally weights.
2469  for(unsigned int i = 1; i < hp_dist.size(); ++i) {
2470  total += hp_dist[i] * std::min<unsigned int>(i + healing, u_.max_hp);
2471  }
2472 
2473  return total;
2474 }
2475 
2476 /* ** The stand-alone program ** */
2477 
2478 #if defined(BENCHMARK) || defined(CHECK)
2479 // We create a significant number of nasty-to-calculate units,
2480 // and test each one against the others.
2481 static const unsigned int NUM_UNITS = 50;
2482 
2483 #ifdef ATTACK_PREDICTION_DEBUG
2484 void list_combatant(const battle_context_unit_stats& stats, unsigned fighter)
2485 {
2486  std::ostringstream ss;
2487 
2488  // TODO: swarm_max? not strikes?
2489  ss << "#" << fighter << ": " << stats.swarm_max << "-" << stats.damage << "; "
2490  << stats.chance_to_hit << "% chance to hit; ";
2491 
2492  if(stats.drains) {
2493  ss << "drains, ";
2494  }
2495 
2496  if(stats.slows) {
2497  ss << "slows, ";
2498  }
2499 
2500  if(stats.rounds > 1) {
2501  ss << "berserk, ";
2502  }
2503 
2504  if(stats.swarm) {
2505  ss << "swarm(" << stats.num_blows << "), ";
2506  }
2507 
2508  if(stats.firststrike) {
2509  ss << "firststrike, ";
2510  }
2511 
2512  ss << "max hp = " << stats.max_hp << "\n";
2513 
2514  std::cout << ss.rdbuf() << std::endl;
2515 }
2516 #else
2517 void list_combatant(const battle_context_unit_stats&, unsigned)
2518 {
2519 }
2520 #endif
2521 
2522 #ifdef HUMAN_READABLE
2523 void combatant::print(const char label[], unsigned int battle, unsigned int fighter) const
2524 {
2525  std::ostringstream ss;
2526 
2527  // TODO: add this to the stream... no idea how to convert it properly...
2528  printf("#%06u: (%02u) %s%*c %u-%d; %uhp; %02u%% to hit; %.2f%% unscathed; ", battle, fighter, label,
2529  static_cast<int>(strlen(label)) - 12, ':', u_.swarm_max, u_.damage, u_.hp, u_.chance_to_hit, untouched * 100.0);
2530 
2531  if(u_.drains) {
2532  ss << "drains, ";
2533  }
2534 
2535  if(u_.slows) {
2536  ss << "slows, ";
2537  }
2538 
2539  if(u_.rounds > 1) {
2540  ss << "berserk, ";
2541  }
2542 
2543  if(u_.swarm) {
2544  ss << "swarm, ";
2545  }
2546 
2547  if(u_.firststrike) {
2548  ss << "firststrike, ";
2549  }
2550 
2551  std::cout << ss.rdbuf() << std::endl;
2552 
2553  // TODO: add to stream
2554  printf("maxhp=%zu ", hp_dist.size() - 1);
2555 
2556  int num_outputs = 0;
2557  for(unsigned int i = 0; i < hp_dist.size(); ++i) {
2558  if(hp_dist[i] != 0.0) {
2559  if(num_outputs++ % 6 == 0) {
2560  printf("\n\t");
2561  } else {
2562  printf(" ");
2563  }
2564 
2565  printf("%2u: %5.2f", i, hp_dist[i] * 100);
2566  }
2567  }
2568 
2569  printf("\n");
2570 }
2571 #elif defined(CHECK)
2572 void combatant::print(const char label[], unsigned int battle, unsigned int /*fighter*/) const
2573 {
2574  std::ostringstream ss;
2575 
2576  printf("#%u: %s: %d %u %u %2g%% ", battle, label, u_.damage, u_.swarm_max, u_.hp,
2577  static_cast<float>(u_.chance_to_hit));
2578 
2579  if(u_.drains) {
2580  ss << "drains, ";
2581  }
2582 
2583  if(u_.slows) {
2584  ss << "slows, ";
2585  }
2586 
2587  if(u_.rounds > 1) {
2588  ss << "berserk, ";
2589  }
2590 
2591  if(u_.swarm) {
2592  ss << "swarm, ";
2593  }
2594 
2595  if(u_.firststrike) {
2596  ss << "firststrike, ";
2597  }
2598 
2599  std::cout << ss.rdbuf() << std::endl;
2600 
2601  // TODO: add to stream
2602  printf("maxhp=%zu ", hp_dist.size() - 1);
2603  printf(" %.2f", untouched);
2604  for(unsigned int i = 0; i < hp_dist.size(); ++i) {
2605  printf(" %.2f", hp_dist[i] * 100);
2606  }
2607 
2608  printf("\n");
2609 }
2610 #else // ... BENCHMARK
2611 void combatant::print(const char /*label*/[], unsigned int /*battle*/, unsigned int /*fighter*/) const
2612 {
2613 }
2614 #endif
2615 
2616 void combatant::reset()
2617 {
2618  for(unsigned int i = 0; i < hp_dist.size(); ++i) {
2619  hp_dist[i] = 0.0;
2620  }
2621 
2622  untouched = 1.0;
2623  poisoned = u_.is_poisoned ? 1.0 : 0.0;
2624  slowed = u_.is_slowed ? 1.0 : 0.0;
2625  summary[0] = std::vector<double>();
2626  summary[1] = std::vector<double>();
2627 }
2628 
2629 static void run(unsigned specific_battle)
2630 {
2631  using std::chrono::duration_cast;
2632  using std::chrono::microseconds;
2633 
2634  // N^2 battles
2635  struct battle_context_unit_stats* stats[NUM_UNITS];
2636  struct combatant* u[NUM_UNITS];
2637  unsigned int i, j, k, battle = 0;
2638  std::chrono::high_resolution_clock::time_point start, end;
2639 
2640  for(i = 0; i < NUM_UNITS; ++i) {
2641  unsigned alt = i + 74; // To offset some cycles.
2642  // To get somewhat realistic performance data, try to approximate
2643  // hit point ranges for mainline units (say 25-60 max hitpoints?)
2644  unsigned max_hp = (i * 2) % 23 + (i * 3) % 14 + 25;
2645  unsigned hp = (alt * 5) % max_hp + 1;
2646  stats[i] = new battle_context_unit_stats(alt % 8 + 2, // damage
2647  (alt % 19 + 3) / 4, // number of strikes
2648  hp, max_hp,
2649  (i % 6) * 10 + 30, // hit chance
2650  (i % 13) % 4 == 0, // drains
2651  (i % 11) % 3 == 0, // slows
2652  false, // slowed
2653  i % 7 == 0, // berserk
2654  (i % 17) / 2 == 0, // firststrike
2655  i % 5 == 0); // swarm
2656  u[i] = new combatant(*stats[i]);
2657  list_combatant(*stats[i], i + 1);
2658  }
2659 
2660  start = std::chrono::high_resolution_clock::now();
2661  // Go through all fights with two attackers (j and k attacking i).
2662  for(i = 0; i < NUM_UNITS; ++i) {
2663  for(j = 0; j < NUM_UNITS; ++j) {
2664  if(i == j) {
2665  continue;
2666  }
2667 
2668  for(k = 0; k < NUM_UNITS; ++k) {
2669  if(i == k || j == k) {
2670  continue;
2671  }
2672 
2673  ++battle;
2674  if(specific_battle && battle != specific_battle) {
2675  continue;
2676  }
2677 
2678  // Fight!
2679  u[j]->fight(*u[i]);
2680  u[k]->fight(*u[i]);
2681  // Results.
2682  u[i]->print("Defender", battle, i + 1);
2683  u[j]->print("Attacker #1", battle, j + 1);
2684  u[k]->print("Attacker #2", battle, k + 1);
2685  // Start the next fight fresh.
2686  u[i]->reset();
2687  u[j]->reset();
2688  u[k]->reset();
2689  }
2690  }
2691  }
2692 
2693  end = std::chrono::high_resolution_clock::now();
2694 
2695  auto total = end - start;
2696 
2697 #ifdef BENCHMARK
2698  printf("Total time for %u combats was %lf\n", NUM_UNITS * (NUM_UNITS - 1) * (NUM_UNITS - 2),
2699  static_cast<double>(duration_cast<microseconds>(total).count()) / 1000000.0);
2700  printf("Time per calc = %li us\n", static_cast<long>(duration_cast<microseconds>(total).count())
2701  / (NUM_UNITS * (NUM_UNITS - 1) * (NUM_UNITS - 2)));
2702 #else
2703  printf("Total combats: %u\n", NUM_UNITS * (NUM_UNITS - 1) * (NUM_UNITS - 2));
2704 #endif
2705 
2706  for(i = 0; i < NUM_UNITS; ++i) {
2707  delete u[i];
2708  delete stats[i];
2709  }
2710 
2711  exit(0);
2712 }
2713 
2714 static battle_context_unit_stats* parse_unit(char*** argv)
2715 {
2716  // There are four required parameters.
2717  int add_to_argv = 4;
2718  int damage = atoi((*argv)[1]);
2719  int num_attacks = atoi((*argv)[2]);
2720  int hitpoints = atoi((*argv)[3]), max_hp = hitpoints;
2721  int hit_chance = atoi((*argv)[4]);
2722 
2723  // Parse the optional (fifth) parameter.
2724  bool drains = false, slows = false, slowed = false, berserk = false, firststrike = false, swarm = false;
2725  if((*argv)[5] && atoi((*argv)[5]) == 0) {
2726  // Optional parameter is present.
2727  ++add_to_argv;
2728 
2729  char* max = strstr((*argv)[5], "maxhp=");
2730  if(max) {
2731  max_hp = atoi(max + strlen("maxhp="));
2732  if(max_hp < hitpoints) {
2733  PLAIN_LOG << "maxhp must be at least hitpoints.";
2734  exit(1);
2735  }
2736  }
2737 
2738  if(strstr((*argv)[5], "drain")) {
2739  if(!max) {
2740  PLAIN_LOG << "WARNING: drain specified without maxhp; assuming uninjured.";
2741  }
2742 
2743  drains = true;
2744  }
2745 
2746  if(strstr((*argv)[5], "slows")) {
2747  slows = true;
2748  }
2749 
2750  if(strstr((*argv)[5], "slowed")) {
2751  slowed = true;
2752  }
2753 
2754  if(strstr((*argv)[5], "berserk")) {
2755  berserk = true;
2756  }
2757 
2758  if(strstr((*argv)[5], "firststrike")) {
2759  firststrike = true;
2760  }
2761 
2762  if(strstr((*argv)[5], "swarm")) {
2763  if(!max) {
2764  PLAIN_LOG << "WARNING: swarm specified without maxhp; assuming uninjured.";
2765  }
2766 
2767  swarm = true;
2768  }
2769  }
2770 
2771  // Update argv.
2772  *argv += add_to_argv;
2773 
2774  // Construct the stats and return.
2775  return new battle_context_unit_stats(
2776  damage, num_attacks, hitpoints, max_hp, hit_chance, drains, slows, slowed, berserk, firststrike, swarm);
2777 }
2778 
2779 int main(int argc, char* argv[])
2780 {
2781  battle_context_unit_stats *def_stats, *att_stats[20];
2782  combatant *def, *att[20];
2783  unsigned int i;
2784 
2785  if(argc < 3)
2786  run(argv[1] ? atoi(argv[1]) : 0);
2787 
2788  if(argc < 9) {
2789  PLAIN_LOG
2790  << "Usage: " << argv[0] << " [<battle>]\n\t" << argv[0] << " "
2791  << "<damage> <attacks> <hp> <hitprob> [drain,slows,slowed,swarm,firststrike,berserk,maxhp=<num>] "
2792  << "<damage> <attacks> <hp> <hitprob> [drain,slows,slowed,berserk,firststrike,swarm,maxhp=<num>] ...";
2793  exit(1);
2794  }
2795 
2796  def_stats = parse_unit(&argv);
2797  def = new combatant(*def_stats);
2798  for(i = 0; argv[1] && i < 19; ++i) {
2799  att_stats[i] = parse_unit(&argv);
2800  att[i] = new combatant(*att_stats[i]);
2801  }
2802 
2803  att[i] = nullptr;
2804 
2805  for(i = 0; att[i]; ++i) {
2806  debug(("Fighting next attacker\n"));
2807  att[i]->fight(*def);
2808  }
2809 
2810  def->print("Defender", 0, 0);
2811  for(i = 0; att[i]; ++i) {
2812  att[i]->print("Attacker", 0, i + 1);
2813  }
2814 
2815  for(i = 0; att[i]; ++i) {
2816  delete att[i];
2817  delete att_stats[i];
2818  }
2819 
2820  delete def;
2821  delete def_stats;
2822 
2823  return 0;
2824 }
2825 
2826 #endif // Standalone program
Various functions that implement attacks and attack calculations.
double t
Definition: astarsearch.cpp:65
map_location prev
Definition: astarsearch.cpp:66
#define debug(x)
std::vector< std::string > names
Definition: build_info.cpp:69
this class does not give synced random results derived classes might do.
Definition: random.hpp:29
static rng & default_instance()
Definition: random.cpp:74
T::difference_type 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
bool get_random_bool(double probability)
This helper method returns true with the probability supplied as a parameter.
Definition: random.cpp:137
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:968
std::string label
What to show in the filter's drop-down list.
Definition: manager.cpp:217
T end(const std::pair< T, T > &p)
T begin(const std::pair< T, T > &p)
Standard logging facilities (interface).
#define PLAIN_LOG
Definition: log.hpp:261
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
int kill_xp(int level)
Definition: game_config.hpp:48
int combat_xp(int level)
Definition: game_config.hpp:53
void clear(const std::string &key)
Definition: general.cpp:190
bool damage_prediction_allow_monte_carlo_simulation()
Definition: general.cpp:989
std::size_t size(const std::string &str)
Length in characters of a UTF-8 string.
Definition: unicode.cpp:87
std::vector< std::string > split(const config_attribute_value &val)
int main(int, char **argv)
Definition: sdl2.cpp:19
Structure describing the statistics of a unit involved in the battle.
Definition: attack.hpp:52
bool slows
Attack slows opponent when it hits.
Definition: attack.hpp:58
unsigned int num_blows
Effective number of blows, takes swarm into account.
Definition: attack.hpp:77
bool petrifies
Attack petrifies opponent when it hits.
Definition: attack.hpp:60
int drain_percent
Percentage of damage recovered as health.
Definition: attack.hpp:75
unsigned int hp
Hitpoints of the unit at the beginning of the battle.
Definition: attack.hpp:70
unsigned int level
Definition: attack.hpp:67
int slow_damage
Effective damage if unit becomes slowed (== damage, if already slowed)
Definition: attack.hpp:74
unsigned int max_experience
Definition: attack.hpp:66
bool drains
Attack drains opponent when it hits.
Definition: attack.hpp:59
unsigned int swarm_min
Minimum number of blows with swarm (equal to num_blows if swarm isn't used).
Definition: attack.hpp:78
bool swarm
Attack has swarm special.
Definition: attack.hpp:63
bool is_attacker
True if the unit is the attacker.
Definition: attack.hpp:55
bool is_poisoned
True if the unit is poisoned at the beginning of the battle.
Definition: attack.hpp:56
bool is_slowed
True if the unit is slowed at the beginning of the battle.
Definition: attack.hpp:57
unsigned int rounds
Berserk special can force us to fight more than one round.
Definition: attack.hpp:69
unsigned int swarm_max
Maximum number of blows with swarm (equal to num_blows if swarm isn't used).
Definition: attack.hpp:79
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
unsigned int max_hp
Maximum hitpoints of the unit.
Definition: attack.hpp:71
int damage
Effective damage of the weapon (all factors accounted for).
Definition: attack.hpp:73
bool poisons
Attack poisons opponent when it hits.
Definition: attack.hpp:62
unsigned int chance_to_hit
Effective chance to hit as a percentage (all factors accounted for).
Definition: attack.hpp:72
int drain_constant
Base HP drained regardless of damage dealt.
Definition: attack.hpp:76
bool firststrike
Attack has firststrike special.
Definition: attack.hpp:64
unsigned int experience
Definition: attack.hpp:66
All combat-related info.
double slowed
Resulting chance we are slowed.
std::vector< double > hp_dist
Resulting probability distribution (might be not as large as max_hp)
double poisoned
Resulting chance we are poisoned.
static const unsigned int MONTE_CARLO_SIMULATION_THRESHOLD
const battle_context_unit_stats & u_
std::array< std::vector< double >, 2 > summary
Summary of matrix used to calculate last battle (unslowed & slowed).
double average_hp(unsigned int healing=0) const
What's the average hp (weighted average of hp_dist).
void fight(combatant &opponent, bool levelup_considered=true)
Simulate a fight! Can be called multiple times for cumulative calculations.
combatant(const battle_context_unit_stats &u, const combatant *prev=nullptr)
Construct a combatant.
double untouched
Resulting chance we were not hit by this opponent (important if it poisons)
mock_char c
mock_party p
static map_location::DIRECTION s
#define e