The Battle for Wesnoth  1.17.0-dev
attack_prediction.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2006 - 2021
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 <iostream>
44 #include <memory>
45 #include <numeric>
46 #include <sstream>
47 
48 #if defined(BENCHMARK) || defined(CHECK)
49 #include <chrono>
50 #include <cstdio>
51 #include <cstdlib>
52 #endif
53 
54 #ifdef ATTACK_PREDICTION_DEBUG
55 #define debug(x) printf x
56 #else
57 #define debug(x)
58 #endif
59 
60 #ifdef ATTACK_PREDICTION_DEBUG
61 namespace
62 {
63 /** Prints the attack statistics of a unit to cout. */
64 void dump(const battle_context_unit_stats& stats)
65 {
66  std::ostringstream ss;
67 
68  ss << "==================================";
69  << std::boolalpha
70  << "\n" << "is_attacker: " << stats.is_attacker
71  << "\n" << "is_poisoned: " << stats.is_poisoned
72  << "\n" << "is_slowed: " << stats.is_slowed
73  << "\n" << "slows: " << stats.slows
74  << "\n" << "drains: " << stats.drains
75  << "\n" << "petrifies: " << stats.petrifies
76  << "\n" << "poisons: " << stats.poisons
77  << "\n" << "backstab_pos: " << stats.backstab_pos
78  << "\n" << "swarm: " << stats.swarm
79  << "\n" << "firststrike: " << stats.firststrike
80  << std::noboolalpha
81  << "\n" << "rounds: " << stats.rounds
82  << "\n\n"
83  << "\n" << "hp: " << stats.hp
84  << "\n" << "max_hp: " << stats.max_hp
85  << "\n" << "chance_to_hit: " << stats.chance_to_hit
86  << "\n" << "damage: " << stats.damage
87  << "\n" << "slow_damage: " << stats.slow_damage
88  << "\n" << "drain_percent: " << stats.drain_percent
89  << "\n" << "drain_constant: " << stats.drain_constant
90  << "\n" << "num_blows: " << stats.num_blows
91  << "\n" << "swarm_min: " << stats.swarm_min
92  << "\n" << "swarm_max: " << stats.swarm_max
93  << "\n\n";
94 
95  std::cout << ss.rdbuf() << std::endl;
96 }
97 }
98 #endif
99 
100 namespace
101 {
102 using summary_t = std::array<std::vector<double>, 2>;
103 
104 /**
105 * A struct to describe one possible combat scenario.
106 * (Needed when the number of attacks can vary due to swarm.)
107 */
108 struct combat_slice
109 {
110  // The hit point range this slice covers.
111  unsigned begin_hp; // included in the range.
112  unsigned end_hp; // excluded from the range.
113 
114  // The probability of this slice.
115  double prob;
116 
117  // The number of strikes applicable with this slice.
118  unsigned strikes;
119 
120  combat_slice(
121  const summary_t& src_summary, unsigned begin, unsigned end, unsigned num_strikes);
122  combat_slice(const summary_t& src_summary, unsigned num_strikes);
123 };
124 
125 /**
126 * Creates a slice from a summary, and associates a number of strikes.
127 */
128 combat_slice::combat_slice(
129  const summary_t& src_summary, unsigned begin, unsigned end, unsigned num_strikes)
130  : begin_hp(begin)
131  , end_hp(end)
132  , prob(0.0)
133  , strikes(num_strikes)
134 {
135  if(src_summary[0].empty()) {
136  // No summary; this should be the only slice.
137  prob = 1.0;
138  return;
139  }
140 
141  // Avoid accessing beyond the end of the vectors.
142  if(end > src_summary[0].size()) {
143  end = src_summary[0].size();
144  }
145 
146  // Sum the probabilities in the slice.
147  for(unsigned i = begin; i < end; ++i) {
148  prob += src_summary[0][i];
149  }
150 
151  if(!src_summary[1].empty()) {
152  for(unsigned i = begin; i < end; ++i) {
153  prob += src_summary[1][i];
154  }
155  }
156 }
157 
158 /**
159 * Creates a slice from the summaries, and associates a number of strikes.
160 * This version of the constructor creates a slice consisting of everything.
161 */
162 combat_slice::combat_slice(const summary_t& src_summary, unsigned num_strikes)
163  : begin_hp(0)
164  , end_hp(src_summary[0].size())
165  , prob(1.0)
166  , strikes(num_strikes)
167 {
168 }
169 
170 /**
171 * Returns the number of hit points greater than cur_hp, and at most
172 * stats.max_hp+1, at which the unit would get another attack because
173 * of swarm.
174 * Helper function for split_summary().
175 */
176 unsigned hp_for_next_attack(unsigned cur_hp, const battle_context_unit_stats& stats)
177 {
178  unsigned old_strikes = stats.calc_blows(cur_hp);
179 
180  // A formula would have to deal with rounding issues; instead
181  // loop until we find more strikes.
182  while(++cur_hp <= stats.max_hp) {
183  if(stats.calc_blows(cur_hp) != old_strikes) {
184  break;
185  }
186  }
187 
188  return cur_hp;
189 }
190 
191 /**
192 * Split the combat by number of attacks per combatant (for swarm).
193 * This also clears the current summaries.
194 */
195 std::vector<combat_slice> split_summary(
196  const battle_context_unit_stats& unit_stats, summary_t& summary)
197 {
198  std::vector<combat_slice> result;
199 
200  if(unit_stats.swarm_min == unit_stats.swarm_max || summary[0].empty()) {
201  // We use the same number of blows for all possibilities.
202  result.emplace_back(summary, unit_stats.num_blows);
203  return result;
204  }
205 
206  debug(("Slicing:\n"));
207  // Loop through our slices.
208  unsigned cur_end = 0;
209  do {
210  // Advance to the next slice.
211  const unsigned cur_begin = cur_end;
212  cur_end = hp_for_next_attack(cur_begin, unit_stats);
213 
214  // Add this slice.
215  combat_slice slice(summary, cur_begin, cur_end, unit_stats.calc_blows(cur_begin));
216  if(slice.prob != 0.0) {
217  result.push_back(slice);
218  debug(("\t%2u-%2u hp; strikes: %u; probability: %6.2f\n", cur_begin, cur_end, slice.strikes,
219  slice.prob * 100.0));
220  }
221  } while(cur_end <= unit_stats.max_hp);
222 
223  return result;
224 }
225 
226 /**
227  * A matrix of A's hitpoints vs B's hitpoints vs. their slowed states.
228  * This class is concerned only with the matrix implementation and
229  * implements functionality for shifting and retrieving probabilities
230  * (i.e. low-level stuff).
231  */
232 class prob_matrix
233 {
234  // Since this gets used very often (especially by the AI), it has
235  // been optimized for speed as a sparse matrix.
236 public:
237  prob_matrix(unsigned int a_max,
238  unsigned int b_max,
239  bool need_a_slowed,
240  bool need_b_slowed,
241  unsigned int a_cur,
242  unsigned int b_cur,
243  const summary_t& a_initial,
244  const summary_t& b_initial);
245 
246  // Shift columns on this plane (b taking damage).
247  void shift_cols(unsigned dst, unsigned src, unsigned damage, double prob, int drain_constant, int drain_percent);
248  // Shift rows on this plane (a taking damage).
249  void shift_rows(unsigned dst, unsigned src, unsigned damage, double prob, int drain_constant, int drain_percent);
250 
251  /** Move a column (adding it to the destination). */
252  void move_column(unsigned d_plane, unsigned s_plane, unsigned d_col, unsigned s_col);
253  /** Move a row (adding it to the destination). */
254  void move_row(unsigned d_plane, unsigned s_plane, unsigned d_row, unsigned s_row);
255 
256  // Move values within a row (or column) to a specified column (or row).
257  void merge_col(unsigned d_plane, unsigned s_plane, unsigned col, unsigned d_row);
258  void merge_cols(unsigned d_plane, unsigned s_plane, unsigned d_row);
259  void merge_row(unsigned d_plane, unsigned s_plane, unsigned row, unsigned d_col);
260  void merge_rows(unsigned d_plane, unsigned s_plane, unsigned d_col);
261 
262  // Set all values to zero and clear the lists of used columns/rows.
263  void clear();
264 
265  // Record the result of a single Monte Carlo simulation iteration.
266  void record_monte_carlo_result(unsigned int a_hp, unsigned int b_hp, bool a_slowed, bool b_slowed);
267 
268  // Returns the index of the plane with the given slow statuses.
269  static unsigned int plane_index(bool a_slowed, bool b_slowed)
270  {
271  return (a_slowed ? 1 : 0) + (b_slowed ? 2 : 0);
272  }
273 
274  /** What is the chance that an indicated combatant (one of them) is at zero? */
275  double prob_of_zero(bool check_a, bool check_b) const;
276  /** Sums the values in the specified row. */
277  double row_sum(unsigned plane, unsigned row) const;
278  /** Sums the values in the specified column. */
279  double col_sum(unsigned plane, unsigned column) const;
280  /** Sums the values in the specified plane. */
281  void sum(unsigned plane, std::vector<double>& row_sums, std::vector<double>& col_sums) const;
282 
283  /** Returns true if the specified plane might have data in it. */
284  bool plane_used(unsigned p) const
285  {
286  return p < NUM_PLANES && plane_[p] != nullptr;
287  }
288 
289  unsigned int num_rows() const
290  {
291  return rows_;
292  }
293  unsigned int num_cols() const
294  {
295  return cols_;
296  }
297 
298  // Debugging tool.
299  void dump() const;
300 
301  // We need four matrices, or "planes", reflecting the possible
302  // "slowed" states (neither slowed, A slowed, B slowed, both slowed).
303  enum {
304  NEITHER_SLOWED,
305  A_SLOWED,
306  B_SLOWED,
307  BOTH_SLOWED,
308  NUM_PLANES // Symbolic constant for the number of planes.
309  };
310 
311 private:
312  // This gives me 10% speed improvement over std::vector<> (g++4.0.3 x86)
313  std::unique_ptr<double[]> new_plane() const;
314 
315  void initialize_plane(unsigned plane,
316  unsigned a_cur,
317  unsigned b_cur,
318  const std::vector<double>& a_initial,
319  const std::vector<double>& b_initial);
320  void initialize_row(
321  unsigned plane, unsigned row, double row_prob, unsigned b_cur, const std::vector<double>& b_initial);
322 
323  double& val(unsigned plane, unsigned row, unsigned col);
324  const double& val(unsigned plane, unsigned row, unsigned col) const;
325 
326  /** Transfers a portion (value * prob) of one value in the matrix to another. */
327  void xfer(unsigned dst_plane,
328  unsigned src_plane,
329  unsigned row_dst,
330  unsigned col_dst,
331  unsigned row_src,
332  unsigned col_src,
333  double prob);
334  /** Transfers one value in the matrix to another. */
335  void xfer(unsigned dst_plane,
336  unsigned src_plane,
337  unsigned row_dst,
338  unsigned col_dst,
339  unsigned row_src,
340  unsigned col_src);
341 
342  void shift_cols_in_row(unsigned dst,
343  unsigned src,
344  unsigned row,
345  const std::vector<unsigned>& cols,
346  unsigned damage,
347  double prob,
348  int drainmax,
349  int drain_constant,
350  int drain_percent);
351  void shift_rows_in_col(unsigned dst,
352  unsigned src,
353  unsigned col,
354  const std::vector<unsigned>& rows,
355  unsigned damage,
356  double prob,
357  int drainmax,
358  int drain_constant,
359  int drain_percent);
360 
361 private: // data
362  const unsigned int rows_, cols_;
363  std::array<std::unique_ptr<double[]>, NUM_PLANES> plane_;
364 
365  // For optimization, we keep track of the rows and columns with data.
366  // (The matrices are likely going to be rather sparse, with data on a grid.)
367  std::array<std::set<unsigned>, NUM_PLANES> used_rows_, used_cols_;
368 };
369 
370 /**
371  * Constructor.
372  * @param a_max The maximum value we will track for A.
373  * @param b_max The maximum value we will track for B.
374  * @param need_a_slowed Set to true if there might be transfers to a "slow" plane for A.
375  * @param need_b_slowed Set to true if there might be transfers to a "slow" plane for B.
376  * @param a_cur The current value for A. (Ignored if a_initial[0] is not empty.)
377  * @param b_cur The current value for B. (Ignored if b_initial[0] is not empty.)
378  * @param a_initial The initial distribution of values for A. Element [0] is for normal A. while [1] is for slowed
379  * A.
380  * @param b_initial The initial distribution of values for B. Element [0] is for normal B. while [1] is for slowed
381  * B.
382  */
383 prob_matrix::prob_matrix(unsigned int a_max,
384  unsigned int b_max,
385  bool need_a_slowed,
386  bool need_b_slowed,
387  unsigned int a_cur,
388  unsigned int b_cur,
389  const summary_t& a_initial,
390  const summary_t& b_initial)
391  : rows_(a_max + 1)
392  , cols_(b_max + 1)
393  , plane_()
394  , used_rows_()
395  , used_cols_()
396 {
397  // Make sure we do not access the matrix in invalid positions.
398  a_cur = std::min<unsigned int>(a_cur, rows_ - 1);
399  b_cur = std::min<unsigned int>(b_cur, cols_ - 1);
400 
401  // It will be convenient to always consider row/col 0 to be used.
402  for(unsigned plane = 0; plane != NUM_PLANES; ++plane) {
403  used_rows_[plane].insert(0u);
404  used_cols_[plane].insert(0u);
405  }
406 
407  // We will need slowed planes if the initial vectors have them.
408  need_a_slowed = need_a_slowed || !a_initial[1].empty();
409  need_b_slowed = need_b_slowed || !b_initial[1].empty();
410 
411  // Allocate the needed planes.
412  plane_[NEITHER_SLOWED] = new_plane();
413  plane_[A_SLOWED] = !need_a_slowed ? nullptr : new_plane();
414  plane_[B_SLOWED] = !need_b_slowed ? nullptr : new_plane();
415  plane_[BOTH_SLOWED] = !(need_a_slowed && need_b_slowed) ? nullptr : new_plane();
416 
417  // Initialize the probability distribution.
418  initialize_plane(NEITHER_SLOWED, a_cur, b_cur, a_initial[0], b_initial[0]);
419 
420  if(!a_initial[1].empty()) {
421  initialize_plane(A_SLOWED, a_cur, b_cur, a_initial[1], b_initial[0]);
422  }
423 
424  if(!b_initial[1].empty()) {
425  initialize_plane(B_SLOWED, a_cur, b_cur, a_initial[0], b_initial[1]);
426  }
427 
428  if(!a_initial[1].empty() && !b_initial[1].empty()) {
429  initialize_plane(BOTH_SLOWED, a_cur, b_cur, a_initial[1], b_initial[1]);
430  }
431 
432  // Some debugging messages.
433  if(!a_initial[0].empty()) {
434  debug(("A has fought before (or is slowed).\n"));
435  dump();
436  }
437 
438  if(!b_initial[0].empty()) {
439  debug(("B has fought before (or is slowed).\n"));
440  dump();
441  }
442 }
443 
444 /** Allocate a new probability array, initialized to 0. */
445 std::unique_ptr<double[]> prob_matrix::new_plane() const
446 {
447  const unsigned int size = rows_ * cols_;
448  std::unique_ptr<double[]> res(new double[size]);
449  std::fill_n(res.get(), size, 0);
450  return res;
451 }
452 
453 /**
454  * Fills the indicated plane with its initial (non-zero) values.
455  * (Part of construction)
456  * @param plane The plane to initialize.
457  * @param a_cur The current value for A. (Ignored if a_initial is not empty.)
458  * @param b_cur The current value for B. (Ignored if b_initial is not empty.)
459  * @param a_initial The initial distribution of values for A for this plane.
460  * @param b_initial The initial distribution of values for B for this plane.
461  */
462 void prob_matrix::initialize_plane(unsigned plane,
463  unsigned a_cur,
464  unsigned b_cur,
465  const std::vector<double>& a_initial,
466  const std::vector<double>& b_initial)
467 {
468  if(!a_initial.empty()) {
469  unsigned row_count = std::min<unsigned>(a_initial.size(), rows_);
470  // The probabilities for each row are contained in a_initial.
471  for(unsigned row = 0; row < row_count; ++row) {
472  if(a_initial[row] != 0.0) {
473  used_rows_[plane].insert(row);
474  initialize_row(plane, row, a_initial[row], b_cur, b_initial);
475  }
476  }
477  } else {
478  used_rows_[plane].insert(a_cur);
479  // Only the row indicated by a_cur is a possibility.
480  initialize_row(plane, a_cur, 1.0, b_cur, b_initial);
481  }
482 }
483 
484 /**
485  * Fills the indicated row with its initial (non-zero) values.
486  * (Part of construction)
487  * @param plane The plane containing the row to initialize.
488  * @param row The row to initialize.
489  * @param row_prob The probability of A having the value for this row.
490  * @param b_cur The current value for B. (Ignored if b_initial is not empty.)
491  * @param b_initial The initial distribution of values for B for this plane.
492  */
493 void prob_matrix::initialize_row(
494  unsigned plane, unsigned row, double row_prob, unsigned b_cur, const std::vector<double>& b_initial)
495 {
496  if(!b_initial.empty()) {
497  unsigned col_count = std::min<unsigned>(b_initial.size(), cols_);
498  // The probabilities for each column are contained in b_initial.
499  for(unsigned col = 0; col < col_count; ++col) {
500  if(b_initial[col] != 0.0) {
501  used_cols_[plane].insert(col);
502  val(plane, row, col) = row_prob * b_initial[col];
503  }
504  }
505  } else {
506  // Only the column indicated by b_cur is a possibility.
507  used_cols_[plane].insert(b_cur);
508  val(plane, row, b_cur) = row_prob;
509  }
510 }
511 
512 double& prob_matrix::val(unsigned plane, unsigned row, unsigned col)
513 {
514  assert(row < rows_);
515  assert(col < cols_);
516  return plane_[plane][row * cols_ + col];
517 }
518 
519 const double& prob_matrix::val(unsigned plane, unsigned row, unsigned col) const
520 {
521  assert(row < rows_);
522  assert(col < cols_);
523  return plane_[plane][row * cols_ + col];
524 }
525 
526 // xfer, shift_cols and shift_rows use up most of our time. Careful!
527 /**
528  * Transfers a portion (value * prob) of one value in the matrix to another.
529  */
530 void prob_matrix::xfer(unsigned dst_plane,
531  unsigned src_plane,
532  unsigned row_dst,
533  unsigned col_dst,
534  unsigned row_src,
535  unsigned col_src,
536  double prob)
537 {
538  double& src = val(src_plane, row_src, col_src);
539  if(src != 0.0) {
540  double diff = src * prob;
541  src -= diff;
542 
543  double& dst = val(dst_plane, row_dst, col_dst);
544  if(dst == 0.0) {
545  // Track that this entry is now used.
546  used_rows_[dst_plane].insert(row_dst);
547  used_cols_[dst_plane].insert(col_dst);
548  }
549  dst += diff;
550 
551  debug(("Shifted %4.3g from %s(%u,%u) to %s(%u,%u).\n", diff,
552  src_plane == NEITHER_SLOWED
553  ? ""
554  : src_plane == A_SLOWED
555  ? "[A_SLOWED]"
556  : src_plane == B_SLOWED
557  ? "[B_SLOWED]"
558  : src_plane == BOTH_SLOWED
559  ? "[BOTH_SLOWED]"
560  : "INVALID",
561 
562  row_src, col_src,
563  dst_plane == NEITHER_SLOWED
564  ? ""
565  : dst_plane == A_SLOWED
566  ? "[A_SLOWED]"
567  : dst_plane == B_SLOWED
568  ? "[B_SLOWED]"
569  : dst_plane == BOTH_SLOWED
570  ? "[BOTH_SLOWED]"
571  : "INVALID",
572  row_dst, col_dst)
573  );
574  }
575 }
576 
577 /**
578  * Transfers one value in the matrix to another.
579  */
580 void prob_matrix::xfer(
581  unsigned dst_plane, unsigned src_plane, unsigned row_dst, unsigned col_dst, unsigned row_src, unsigned col_src)
582 {
583  if(dst_plane == src_plane && row_dst == row_src && col_dst == col_src)
584  // Transferring to itself. Nothing to do.
585  return;
586 
587  double& src = val(src_plane, row_src, col_src);
588  if(src != 0.0) {
589  debug(("Shifting %4.3g from %s(%u,%u) to %s(%u,%u).\n", src,
590  src_plane == NEITHER_SLOWED
591  ? ""
592  : src_plane == A_SLOWED
593  ? "[A_SLOWED]"
594  : src_plane == B_SLOWED
595  ? "[B_SLOWED]"
596  : src_plane == BOTH_SLOWED
597  ? "[BOTH_SLOWED]"
598  : "INVALID",
599  row_src, col_src,
600  dst_plane == NEITHER_SLOWED
601  ? ""
602  : dst_plane == A_SLOWED
603  ? "[A_SLOWED]"
604  : dst_plane == B_SLOWED
605  ? "[B_SLOWED]"
606  : dst_plane == BOTH_SLOWED
607  ? "[BOTH_SLOWED]"
608  : "INVALID",
609  row_dst, col_dst)
610  );
611 
612  double& dst = val(dst_plane, row_dst, col_dst);
613  if(dst == 0.0) {
614  // Track that this entry is now used.
615  used_rows_[dst_plane].insert(row_dst);
616  used_cols_[dst_plane].insert(col_dst);
617  }
618 
619  dst += src;
620  src = 0.0;
621  }
622 }
623 
624 /**
625  * Transfers a portion (value * prob) of the values in a row to another.
626  * Part of shift_cols().
627  */
628 void prob_matrix::shift_cols_in_row(unsigned dst,
629  unsigned src,
630  unsigned row,
631  const std::vector<unsigned>& cols,
632  unsigned damage,
633  double prob,
634  int drainmax,
635  int drain_constant,
636  int drain_percent)
637 {
638  // Some conversions to (signed) int.
639  int row_i = static_cast<int>(row);
640  int max_row = static_cast<int>(rows_) - 1;
641 
642  // cols[0] is excluded since that should be 0, representing already dead.
643  unsigned col_x = 1;
644 
645  // Killing blows can have different drain amounts, so handle them first
646  for(; col_x < cols.size() && cols[col_x] < damage; ++col_x) {
647  // These variables are not strictly necessary, but they make the
648  // calculation easier to parse.
649  int col_i = static_cast<int>(cols[col_x]);
650  int drain_amount = col_i * drain_percent / 100 + drain_constant;
651  unsigned newrow = std::clamp(row_i + drain_amount, 1, max_row);
652  xfer(dst, src, newrow, 0, row, cols[col_x], prob);
653  }
654 
655  // The remaining columns use the specified drainmax.
656  unsigned newrow = std::clamp(row_i + drainmax, 1, max_row);
657  for(; col_x < cols.size(); ++col_x) {
658  xfer(dst, src, newrow, cols[col_x] - damage, row, cols[col_x], prob);
659  }
660 }
661 
662 /**
663  * Transfers a portion (value * prob) of each column in a plane to another.
664  * Each column in the @a src plane gets shifted @a damage columns towards 0, and
665  * also shifted into the @a dst plane. In addition, the rows can shift if
666  * @a drain constant or @a drain_percent is nonzero.
667  */
668 void prob_matrix::shift_cols(
669  unsigned dst, unsigned src, unsigned damage, double prob, int drain_constant, int drain_percent)
670 {
671  int drainmax = (drain_percent * (static_cast<signed>(damage)) / 100 + drain_constant);
672 
673  if(drain_constant || drain_percent) {
674  debug(("Drains %i (%i%% of %u plus %i)\n", drainmax, drain_percent, damage, drain_constant));
675  }
676 
677  // Get lists of indices currently used in the source plane.
678  // (This needs to be cached since we might add indices while shifting.)
679  const std::vector<unsigned> rows(used_rows_[src].begin(), used_rows_[src].end());
680  const std::vector<unsigned> cols(used_cols_[src].begin(), used_cols_[src].end());
681 
682  // Loop downwards if we drain positive, but upwards if we drain negative,
683  // so we write behind us (for when src == dst).
684  if(drainmax > 0) {
685  // rows[0] is excluded since that should be 0, representing already dead.
686  for(unsigned row_x = rows.size() - 1; row_x != 0; --row_x) {
687  shift_cols_in_row(dst, src, rows[row_x], cols, damage, prob, drainmax, drain_constant, drain_percent);
688  }
689  } else {
690  // rows[0] is excluded since that should be 0, representing already dead.
691  for(unsigned row_x = 1; row_x != rows.size(); ++row_x) {
692  shift_cols_in_row(dst, src, rows[row_x], cols, damage, prob, drainmax, drain_constant, drain_percent);
693  }
694  }
695 }
696 
697 /**
698  * Transfers a portion (value * prob) of the values in a column to another.
699  * Part of shift_rows().
700  */
701 void prob_matrix::shift_rows_in_col(unsigned dst,
702  unsigned src,
703  unsigned col,
704  const std::vector<unsigned>& rows,
705  unsigned damage,
706  double prob,
707  int drainmax,
708  int drain_constant,
709  int drain_percent)
710 {
711  // Some conversions to (signed) int.
712  int col_i = static_cast<int>(col);
713  int max_col = static_cast<int>(cols_) - 1;
714 
715  // rows[0] is excluded since that should be 0, representing already dead.
716  unsigned row_x = 1;
717 
718  // Killing blows can have different drain amounts, so handle them first
719  for(; row_x < rows.size() && rows[row_x] < damage; ++row_x) {
720  // These variables are not strictly necessary, but they make the
721  // calculation easier to parse.
722  int row_i = static_cast<int>(rows[row_x]);
723  int drain_amount = row_i * drain_percent / 100 + drain_constant;
724  unsigned newcol = std::clamp(col_i + drain_amount, 1, max_col);
725  xfer(dst, src, 0, newcol, rows[row_x], col, prob);
726  }
727 
728  // The remaining rows use the specified drainmax.
729  unsigned newcol = std::clamp(col_i + drainmax, 1, max_col);
730  for(; row_x < rows.size(); ++row_x) {
731  xfer(dst, src, rows[row_x] - damage, newcol, rows[row_x], col, prob);
732  }
733 }
734 
735 /**
736  * Transfers a portion (value * prob) of each row in a plane to another.
737  * Each row in the @a src plane gets shifted @a damage columns towards 0, and
738  * also shifted into the @a dst plane. In addition, the columns can shift if
739  * @a drain constant or @a drain_percent is nonzero.
740  */
741 void prob_matrix::shift_rows(
742  unsigned dst, unsigned src, unsigned damage, double prob, int drain_constant, int drain_percent)
743 {
744  int drainmax = (drain_percent * (static_cast<signed>(damage)) / 100 + drain_constant);
745 
746  if(drain_constant || drain_percent) {
747  debug(("Drains %i (%i%% of %u plus %i)\n", drainmax, drain_percent, damage, drain_constant));
748  }
749 
750  // Get lists of indices currently used in the source plane.
751  // (This needs to be cached since we might add indices while shifting.)
752  const std::vector<unsigned> rows(used_rows_[src].begin(), used_rows_[src].end());
753  const std::vector<unsigned> cols(used_cols_[src].begin(), used_cols_[src].end());
754 
755  // Loop downwards if we drain positive, but upwards if we drain negative,
756  // so we write behind us (for when src == dst).
757  if(drainmax > 0) {
758  // cols[0] is excluded since that should be 0, representing already dead.
759  for(unsigned col_x = cols.size() - 1; col_x != 0; --col_x)
760  shift_rows_in_col(dst, src, cols[col_x], rows, damage, prob, drainmax, drain_constant, drain_percent);
761  } else {
762  // cols[0] is excluded since that should be 0, representing already dead.
763  for(unsigned col_x = 1; col_x != cols.size(); ++col_x) {
764  shift_rows_in_col(dst, src, cols[col_x], rows, damage, prob, drainmax, drain_constant, drain_percent);
765  }
766  }
767 }
768 
769 /**
770  * Move a column (adding it to the destination).
771  */
772 void prob_matrix::move_column(unsigned d_plane, unsigned s_plane, unsigned d_col, unsigned s_col)
773 {
774  // Transfer the data.
775  for(const unsigned& row : used_rows_[s_plane]) {
776  xfer(d_plane, s_plane, row, d_col, row, s_col);
777  }
778 }
779 
780 /**
781  * Move a row (adding it to the destination).
782  */
783 void prob_matrix::move_row(unsigned d_plane, unsigned s_plane, unsigned d_row, unsigned s_row)
784 {
785  // Transfer the data.
786  for(const unsigned& col : used_cols_[s_plane]) {
787  xfer(d_plane, s_plane, d_row, col, s_row, col);
788  }
789 }
790 
791 /**
792  * Move values in the specified column -- excluding row zero -- to the
793  * specified row in that column (possibly shifting planes in the process).
794  */
795 void prob_matrix::merge_col(unsigned d_plane, unsigned s_plane, unsigned col, unsigned d_row)
796 {
797  auto rows_end = used_rows_[s_plane].end();
798  auto row_it = used_rows_[s_plane].begin();
799 
800  // Transfer the data, excluding row zero.
801  for(++row_it; row_it != rows_end; ++row_it) {
802  xfer(d_plane, s_plane, d_row, col, *row_it, col);
803  }
804 }
805 
806 /**
807  * Move values within columns in the specified plane -- excluding row zero --
808  * to the specified row (possibly shifting planes in the process).
809  */
810 void prob_matrix::merge_cols(unsigned d_plane, unsigned s_plane, unsigned d_row)
811 {
812  auto rows_end = used_rows_[s_plane].end();
813  auto row_it = used_rows_[s_plane].begin();
814 
815  // Transfer the data, excluding row zero.
816  for(++row_it; row_it != rows_end; ++row_it) {
817  for(const unsigned& col : used_cols_[s_plane]) {
818  xfer(d_plane, s_plane, d_row, col, *row_it, col);
819  }
820  }
821 }
822 
823 /**
824  * Move values in the specified row -- excluding column zero -- to the
825  * specified column in that row (possibly shifting planes in the process).
826  */
827 void prob_matrix::merge_row(unsigned d_plane, unsigned s_plane, unsigned row, unsigned d_col)
828 {
829  auto cols_end = used_cols_[s_plane].end();
830  auto col_it = used_cols_[s_plane].begin();
831 
832  // Transfer the data, excluding column zero.
833  for(++col_it; col_it != cols_end; ++col_it) {
834  xfer(d_plane, s_plane, row, d_col, row, *col_it);
835  }
836 }
837 
838 /**
839  * Move values within rows in the specified plane -- excluding column zero --
840  * to the specified column (possibly shifting planes in the process).
841  */
842 void prob_matrix::merge_rows(unsigned d_plane, unsigned s_plane, unsigned d_col)
843 {
844  auto cols_end = used_cols_[s_plane].end();
845  // Exclude column zero.
846  auto cols_begin = std::next(used_cols_[s_plane].begin());
847 
848  // Transfer the data, excluding column zero.
849  for(const unsigned row : used_rows_[s_plane]) {
850  for(auto col_it = cols_begin; col_it != cols_end; ++col_it) {
851  xfer(d_plane, s_plane, row, d_col, row, *col_it);
852  }
853  }
854 }
855 
856 /**
857  * Set all values to zero and clear the lists of used columns/rows.
858  */
859 void prob_matrix::clear()
860 {
861  for(unsigned int p = 0u; p < NUM_PLANES; ++p) {
862  if(!plane_used(p)) {
863  continue;
864  }
865 
866  if(used_rows_[p].empty()) {
867  // Nothing to do
868  continue;
869  }
870 
871  auto [first_row, last_row] = std::minmax_element(used_rows_[p].begin(), used_rows_[p].end());
872  for(unsigned int r = *first_row; r <= *last_row; ++r) {
873  for(unsigned int c = 0u; c < cols_; ++c) {
874  plane_[p][r * cols_ + c] = 0.0;
875  }
876  }
877 
878  used_rows_[p].clear();
879  used_cols_[p].clear();
880 
881  /* Row and column 0 are always considered to be used.
882  Functions like merge_col() access *used_rows_[plane].begin() without checking if there are
883  any used rows: thus, ensuring that there are used rows and columns is necessary to avoid
884  memory corruption. */
885  used_rows_[p].insert(0u);
886  used_cols_[p].insert(0u);
887  }
888 }
889 
890 /**
891  * Record the result of a single Monte Carlo simulation iteration.
892  */
893 void prob_matrix::record_monte_carlo_result(unsigned int a_hp, unsigned int b_hp, bool a_slowed, bool b_slowed)
894 {
895  assert(a_hp <= rows_);
896  assert(b_hp <= cols_);
897  unsigned int plane = plane_index(a_slowed, b_slowed);
898  ++val(plane, a_hp, b_hp);
899  used_rows_[plane].insert(a_hp);
900  used_cols_[plane].insert(b_hp);
901 }
902 
903 /**
904  * What is the chance that an indicated combatant (one of them) is at zero?
905  */
906 double prob_matrix::prob_of_zero(bool check_a, bool check_b) const
907 {
908  double prob = 0.0;
909 
910  for(unsigned p = 0; p < NUM_PLANES; ++p) {
911  if(!plane_used(p)) {
912  continue;
913  }
914 
915  // Column 0 is where b is at zero.
916  if(check_b) {
917  for(const unsigned& row : used_rows_[p]) {
918  prob += val(p, row, 0);
919  }
920  }
921 
922  // Row 0 is where a is at zero.
923  if(check_a) {
924  for(const unsigned& col : used_cols_[p]) {
925  prob += val(p, 0, col);
926  }
927  }
928  // Theoretically, if checking both, we should subtract the chance that
929  // both are dead, but that chance is zero, so don't worry about it.
930  }
931 
932  return prob;
933 }
934 
935 /**
936  * Sums the values in the specified row.
937  */
938 double prob_matrix::row_sum(unsigned plane, unsigned row) const
939 {
940  if(!plane_used(plane)) {
941  return 0.0;
942  }
943 
944  double sum = 0.0;
945  for(unsigned col : used_cols_[plane]) {
946  sum += val(plane, row, col);
947  }
948  return sum;
949 }
950 
951 /**
952  * Sums the values in the specified column.
953  */
954 double prob_matrix::col_sum(unsigned plane, unsigned column) const
955 {
956  if(!plane_used(plane)) {
957  return 0.0;
958  }
959 
960  double sum = 0.0;
961  for(unsigned row : used_rows_[plane]) {
962  sum += val(plane, row, column);
963  }
964  return sum;
965 }
966 
967 /**
968  * Sums the values in the specified plane.
969  * The sum of each row is added to the corresponding entry in row_sums.
970  * The sum of each column is added to the corresponding entry in col_sums.
971  */
972 void prob_matrix::sum(unsigned plane, std::vector<double>& row_sums, std::vector<double>& col_sums) const
973 {
974  for(const unsigned& row : used_rows_[plane]) {
975  for(const unsigned& col : used_cols_[plane]) {
976  const double& prob = val(plane, row, col);
977  row_sums[row] += prob;
978  col_sums[col] += prob;
979  }
980  }
981 }
982 
983 #if defined(CHECK) && defined(ATTACK_PREDICTION_DEBUG)
984 void prob_matrix::dump() const
985 {
986  unsigned int row, col, m;
987  const char* names[] {"NEITHER_SLOWED", "A_SLOWED", "B_SLOWED", "BOTH_SLOWED"};
988 
989  for(m = 0; m < NUM_PLANES; ++m) {
990  if(!plane_used(m)) {
991  continue;
992  }
993 
994  debug(("%s:\n", names[m]));
995  for(row = 0; row < rows_; ++row) {
996  debug((" "));
997  for(col = 0; col < cols_; ++col) {
998  debug(("%4.3g ", val(m, row, col) * 100));
999  }
1000 
1001  debug(("\n"));
1002  }
1003  }
1004 }
1005 #else
1006 void prob_matrix::dump() const
1007 {
1008 }
1009 #endif
1010 
1011 /**
1012  * A matrix for calculating the outcome of combat.
1013  * This class specifies the interface and functionality shared between
1014  * probability_combat_matrix and monte_carlo_combat_matrix.
1015  */
1016 class combat_matrix : protected prob_matrix
1017 {
1018 public:
1019  combat_matrix(unsigned int a_max_hp,
1020  unsigned int b_max_hp,
1021  unsigned int a_hp,
1022  unsigned int b_hp,
1023  const summary_t& a_summary,
1024  const summary_t& b_summary,
1025  bool a_slows,
1026  bool b_slows,
1027  unsigned int a_damage,
1028  unsigned int b_damage,
1029  unsigned int a_slow_damage,
1030  unsigned int b_slow_damage,
1031  int a_drain_percent,
1032  int b_drain_percent,
1033  int a_drain_constant,
1034  int b_drain_constant);
1035 
1036  virtual ~combat_matrix()
1037  {
1038  }
1039 
1040  // We lied: actually did less damage, adjust matrix.
1041  void remove_petrify_distortion_a(unsigned damage, unsigned slow_damage, unsigned b_hp);
1042  void remove_petrify_distortion_b(unsigned damage, unsigned slow_damage, unsigned a_hp);
1043 
1044  void forced_levelup_a();
1045  void conditional_levelup_a();
1046 
1047  void forced_levelup_b();
1048  void conditional_levelup_b();
1049 
1050  using prob_matrix::row_sum;
1051  using prob_matrix::col_sum;
1052 
1053  // Its over, and here's the bill.
1054  virtual void extract_results(
1055  summary_t& summary_a, summary_t& summary_b)
1056  = 0;
1057 
1058  void dump() const
1059  {
1060  prob_matrix::dump();
1061  }
1062 
1063 protected:
1064  unsigned a_max_hp_;
1065  bool a_slows_;
1066  unsigned a_damage_;
1067  unsigned a_slow_damage_;
1068  int a_drain_percent_;
1069  int a_drain_constant_;
1070 
1071  unsigned b_max_hp_;
1072  bool b_slows_;
1073  unsigned b_damage_;
1074  unsigned b_slow_damage_;
1075  int b_drain_percent_;
1076  int b_drain_constant_;
1077 };
1078 
1079 /**
1080  * Constructor.
1081  * @param a_max_hp The maximum hit points for A.
1082  * @param b_max_hp The maximum hit points for B.
1083  * @param a_slows Set to true if A slows B when A hits B.
1084  * @param b_slows Set to true if B slows A when B hits A.
1085  * @param a_hp The current hit points for A. (Ignored if a_summary[0] is not empty.)
1086  * @param b_hp The current hit points for B. (Ignored if b_summary[0] is not empty.)
1087  * @param a_summary The hit point distribution for A (from previous combats). Element [0] is for normal A. while
1088  * [1] is for slowed A.
1089  * @param b_summary The hit point distribution for B (from previous combats). Element [0] is for normal B. while
1090  * [1] is for slowed B.
1091  */
1092 
1093 combat_matrix::combat_matrix(unsigned int a_max_hp,
1094  unsigned int b_max_hp,
1095  unsigned int a_hp,
1096  unsigned int b_hp,
1097  const summary_t& a_summary,
1098  const summary_t& b_summary,
1099  bool a_slows,
1100  bool b_slows,
1101  unsigned int a_damage,
1102  unsigned int b_damage,
1103  unsigned int a_slow_damage,
1104  unsigned int b_slow_damage,
1105  int a_drain_percent,
1106  int b_drain_percent,
1107  int a_drain_constant,
1108  int b_drain_constant)
1109  // The inversion of the order of the *_slows parameters here is intentional.
1110  : prob_matrix(a_max_hp, b_max_hp, b_slows, a_slows, a_hp, b_hp, a_summary, b_summary)
1111  , a_max_hp_(a_max_hp)
1112  , a_slows_(a_slows)
1113  , a_damage_(a_damage)
1114  , a_slow_damage_(a_slow_damage)
1115  , a_drain_percent_(a_drain_percent)
1116  , a_drain_constant_(a_drain_constant)
1117  , b_max_hp_(b_max_hp)
1118  , b_slows_(b_slows)
1119  , b_damage_(b_damage)
1120  , b_slow_damage_(b_slow_damage)
1121  , b_drain_percent_(b_drain_percent)
1122  , b_drain_constant_(b_drain_constant)
1123 {
1124 }
1125 
1126 // We lied: actually did less damage, adjust matrix.
1127 void combat_matrix::remove_petrify_distortion_a(unsigned damage, unsigned slow_damage, unsigned b_hp)
1128 {
1129  for(int p = 0; p < NUM_PLANES; ++p) {
1130  if(!plane_used(p)) {
1131  continue;
1132  }
1133 
1134  // A is slow in planes 1 and 3.
1135  unsigned actual_damage = (p & 1) ? slow_damage : damage;
1136  if(b_hp > actual_damage) {
1137  // B was actually petrified, not killed.
1138  move_column(p, p, b_hp - actual_damage, 0);
1139  }
1140  }
1141 }
1142 
1143 void combat_matrix::remove_petrify_distortion_b(unsigned damage, unsigned slow_damage, unsigned a_hp)
1144 {
1145  for(int p = 0; p < NUM_PLANES; ++p) {
1146  if(!plane_used(p)) {
1147  continue;
1148  }
1149 
1150  // B is slow in planes 2 and 3.
1151  unsigned actual_damage = (p & 2) ? slow_damage : damage;
1152  if(a_hp > actual_damage) {
1153  // A was actually petrified, not killed.
1154  move_row(p, p, a_hp - actual_damage, 0);
1155  }
1156  }
1157 }
1158 
1159 void combat_matrix::forced_levelup_a()
1160 {
1161  /* Move all the values (except 0hp) of all the planes to the "fully healed"
1162  row of the planes unslowed for A. */
1163  for(int p = 0; p < NUM_PLANES; ++p) {
1164  if(plane_used(p)) {
1165  merge_cols(p & -2, p, a_max_hp_);
1166  }
1167  }
1168 }
1169 
1170 void combat_matrix::forced_levelup_b()
1171 {
1172  /* Move all the values (except 0hp) of all the planes to the "fully healed"
1173  column of planes unslowed for B. */
1174  for(int p = 0; p < NUM_PLANES; ++p) {
1175  if(plane_used(p)) {
1176  merge_rows(p & -3, p, b_max_hp_);
1177  }
1178  }
1179 }
1180 
1181 void combat_matrix::conditional_levelup_a()
1182 {
1183  /* Move the values of the first column (except 0hp) of all the
1184  planes to the "fully healed" row of the planes unslowed for A. */
1185  for(int p = 0; p < NUM_PLANES; ++p) {
1186  if(plane_used(p)) {
1187  merge_col(p & -2, p, 0, a_max_hp_);
1188  }
1189  }
1190 }
1191 
1192 void combat_matrix::conditional_levelup_b()
1193 {
1194  /* Move the values of the first row (except 0hp) of all the
1195  planes to the last column of the planes unslowed for B. */
1196  for(int p = 0; p < NUM_PLANES; ++p) {
1197  if(plane_used(p)) {
1198  merge_row(p & -3, p, 0, b_max_hp_);
1199  }
1200  }
1201 }
1202 
1203 /**
1204  * Implementation of combat_matrix that calculates exact probabilities of events.
1205  * Fast in "simple" fights (low number of strikes, low HP, and preferably no slow
1206  * or swarm effect), but can be unusably expensive in extremely complex situations.
1207  */
1208 class probability_combat_matrix : public combat_matrix
1209 {
1210 public:
1211  probability_combat_matrix(unsigned int a_max_hp,
1212  unsigned int b_max_hp,
1213  unsigned int a_hp,
1214  unsigned int b_hp,
1215  const summary_t& a_summary,
1216  const summary_t& b_summary,
1217  bool a_slows,
1218  bool b_slows,
1219  unsigned int a_damage,
1220  unsigned int b_damage,
1221  unsigned int a_slow_damage,
1222  unsigned int b_slow_damage,
1223  int a_drain_percent,
1224  int b_drain_percent,
1225  int a_drain_constant,
1226  int b_drain_constant);
1227 
1228  // A hits B.
1229  void receive_blow_b(double hit_chance);
1230  // B hits A. Why can't they just get along?
1231  void receive_blow_a(double hit_chance);
1232 
1233  /** What is the chance that one of the combatants is dead? */
1234  double dead_prob() const
1235  {
1236  return prob_of_zero(true, true);
1237  }
1238 
1239  /** What is the chance that combatant 'a' is dead? */
1240  double dead_prob_a() const
1241  {
1242  return prob_of_zero(true, false);
1243  }
1244 
1245  /** What is the chance that combatant 'b' is dead? */
1246  double dead_prob_b() const
1247  {
1248  return prob_of_zero(false, true);
1249  }
1250 
1251  void extract_results(
1252  summary_t& summary_a, summary_t& summary_b) override;
1253 };
1254 
1255 /**
1256  * Constructor.
1257  * @param a_max_hp The maximum hit points for A.
1258  * @param b_max_hp The maximum hit points for B.
1259  * @param a_slows Set to true if A slows B when A hits B.
1260  * @param b_slows Set to true if B slows A when B hits A.
1261  * @param a_hp The current hit points for A. (Ignored if a_summary[0] is not empty.)
1262  * @param b_hp The current hit points for B. (Ignored if b_summary[0] is not empty.)
1263  * @param a_summary The hit point distribution for A (from previous combats). Element [0] is for normal A. while
1264  * [1] is for slowed A.
1265  * @param b_summary The hit point distribution for B (from previous combats). Element [0] is for normal B. while
1266  * [1] is for slowed B.
1267  */
1268 probability_combat_matrix::probability_combat_matrix(unsigned int a_max_hp,
1269  unsigned int b_max_hp,
1270  unsigned int a_hp,
1271  unsigned int b_hp,
1272  const summary_t& a_summary,
1273  const summary_t& b_summary,
1274  bool a_slows,
1275  bool b_slows,
1276  unsigned int a_damage,
1277  unsigned int b_damage,
1278  unsigned int a_slow_damage,
1279  unsigned int b_slow_damage,
1280  int a_drain_percent,
1281  int b_drain_percent,
1282  int a_drain_constant,
1283  int b_drain_constant)
1284  : combat_matrix(a_max_hp,
1285  b_max_hp,
1286  a_hp,
1287  b_hp,
1288  a_summary,
1289  b_summary,
1290  a_slows,
1291  b_slows,
1292  a_damage,
1293  b_damage,
1294  a_slow_damage,
1295  b_slow_damage,
1296  a_drain_percent,
1297  b_drain_percent,
1298  a_drain_constant,
1299  b_drain_constant)
1300 {
1301 }
1302 
1303 // Shift combat_matrix to reflect the probability 'hit_chance' that damage
1304 // is done to 'b'.
1305 void probability_combat_matrix::receive_blow_b(double hit_chance)
1306 {
1307  // Walk backwards so we don't copy already-copied matrix planes.
1308  unsigned src = NUM_PLANES;
1309  while(src-- != 0) {
1310  if(!plane_used(src)) {
1311  continue;
1312  }
1313 
1314  // If A slows us, we go from 0=>2, 1=>3, 2=>2 3=>3.
1315  int dst = a_slows_ ? src | 2 : src;
1316 
1317  // A is slow in planes 1 and 3.
1318  unsigned damage = (src & 1) ? a_slow_damage_ : a_damage_;
1319 
1320  shift_cols(dst, src, damage, hit_chance, a_drain_constant_, a_drain_percent_);
1321  }
1322 }
1323 
1324 // Shift matrix to reflect probability 'hit_chance'
1325 // that damage (up to) 'damage' is done to 'a'.
1326 void probability_combat_matrix::receive_blow_a(double hit_chance)
1327 {
1328  // Walk backwards so we don't copy already-copied matrix planes.
1329  unsigned src = NUM_PLANES;
1330  while(src-- != 0) {
1331  if(!plane_used(src)) {
1332  continue;
1333  }
1334 
1335  // If B slows us, we go from 0=>1, 1=>1, 2=>3 3=>3.
1336  int dst = b_slows_ ? src | 1 : src;
1337 
1338  // B is slow in planes 2 and 3.
1339  unsigned damage = (src & 2) ? b_slow_damage_ : b_damage_;
1340 
1341  shift_rows(dst, src, damage, hit_chance, b_drain_constant_, b_drain_percent_);
1342  }
1343 }
1344 
1345 void probability_combat_matrix::extract_results(
1346  summary_t& summary_a, summary_t& summary_b)
1347 {
1348  // Reset the summaries.
1349  summary_a[0] = std::vector<double>(num_rows());
1350  summary_b[0] = std::vector<double>(num_cols());
1351 
1352  if(plane_used(A_SLOWED)) {
1353  summary_a[1] = std::vector<double>(num_rows());
1354  }
1355 
1356  if(plane_used(B_SLOWED)) {
1357  summary_b[1] = std::vector<double>(num_cols());
1358  }
1359 
1360  for(unsigned p = 0; p < NUM_PLANES; ++p) {
1361  if(!plane_used(p)) {
1362  continue;
1363  }
1364 
1365  // A is slow in planes 1 and 3.
1366  unsigned dst_a = (p & 1) ? 1u : 0u;
1367  // B is slow in planes 2 and 3.
1368  unsigned dst_b = (p & 2) ? 1u : 0u;
1369  sum(p, summary_a[dst_a], summary_b[dst_b]);
1370  }
1371 }
1372 
1373 /**
1374  * Implementation of combat_matrix based on Monte Carlo simulation.
1375  * This does not give exact results, but the error should be small
1376  * thanks to the law of large numbers. Probably more important is that
1377  * the simulation time doesn't depend on anything other than the number
1378  * of strikes, which makes this method much faster if the combatants
1379  * have a lot of HP.
1380  */
1381 class monte_carlo_combat_matrix : public combat_matrix
1382 {
1383 public:
1384  monte_carlo_combat_matrix(unsigned int a_max_hp,
1385  unsigned int b_max_hp,
1386  unsigned int a_hp,
1387  unsigned int b_hp,
1388  const summary_t& a_summary,
1389  const summary_t& b_summary,
1390  bool a_slows,
1391  bool b_slows,
1392  unsigned int a_damage,
1393  unsigned int b_damage,
1394  unsigned int a_slow_damage,
1395  unsigned int b_slow_damage,
1396  int a_drain_percent,
1397  int b_drain_percent,
1398  int a_drain_constant,
1399  int b_drain_constant,
1400  unsigned int rounds,
1401  double a_hit_chance,
1402  double b_hit_chance,
1403  const std::vector<combat_slice>& a_split,
1404  const std::vector<combat_slice>& b_split,
1405  double a_initially_slowed_chance,
1406  double b_initially_slowed_chance);
1407 
1408  void simulate();
1409 
1410  void extract_results(
1411  summary_t& summary_a, summary_t& summary_b) override;
1412 
1413  double get_a_hit_probability() const;
1414  double get_b_hit_probability() const;
1415 
1416 private:
1417  static const unsigned int NUM_ITERATIONS = 5000u;
1418 
1419  std::vector<double> a_initial_;
1420  std::vector<double> b_initial_;
1421  std::vector<double> a_initial_slowed_;
1422  std::vector<double> b_initial_slowed_;
1423  std::vector<combat_slice> a_split_;
1424  std::vector<combat_slice> b_split_;
1425  unsigned int rounds_;
1426  double a_hit_chance_;
1427  double b_hit_chance_;
1428  double a_initially_slowed_chance_;
1429  double b_initially_slowed_chance_;
1430  unsigned int iterations_a_hit_ = 0u;
1431  unsigned int iterations_b_hit_ = 0u;
1432 
1433  unsigned int calc_blows_a(unsigned int a_hp) const;
1434  unsigned int calc_blows_b(unsigned int b_hp) const;
1435  static void divide_all_elements(std::vector<double>& vec, double divisor);
1436  static void scale_probabilities(
1437  const std::vector<double>& source, std::vector<double>& target, double divisor, unsigned int singular_hp);
1438 };
1439 
1440 monte_carlo_combat_matrix::monte_carlo_combat_matrix(unsigned int a_max_hp,
1441  unsigned int b_max_hp,
1442  unsigned int a_hp,
1443  unsigned int b_hp,
1444  const summary_t& a_summary,
1445  const summary_t& b_summary,
1446  bool a_slows,
1447  bool b_slows,
1448  unsigned int a_damage,
1449  unsigned int b_damage,
1450  unsigned int a_slow_damage,
1451  unsigned int b_slow_damage,
1452  int a_drain_percent,
1453  int b_drain_percent,
1454  int a_drain_constant,
1455  int b_drain_constant,
1456  unsigned int rounds,
1457  double a_hit_chance,
1458  double b_hit_chance,
1459  const std::vector<combat_slice>& a_split,
1460  const std::vector<combat_slice>& b_split,
1461  double a_initially_slowed_chance,
1462  double b_initially_slowed_chance)
1463  : combat_matrix(a_max_hp,
1464  b_max_hp,
1465  a_hp,
1466  b_hp,
1467  a_summary,
1468  b_summary,
1469  a_slows,
1470  b_slows,
1471  a_damage,
1472  b_damage,
1473  a_slow_damage,
1474  b_slow_damage,
1475  a_drain_percent,
1476  b_drain_percent,
1477  a_drain_constant,
1478  b_drain_constant)
1479  , a_split_(a_split)
1480  , b_split_(b_split)
1481  , rounds_(rounds)
1482  , a_hit_chance_(a_hit_chance)
1483  , b_hit_chance_(b_hit_chance)
1484  , a_initially_slowed_chance_(a_initially_slowed_chance)
1485  , b_initially_slowed_chance_(b_initially_slowed_chance)
1486 {
1487  scale_probabilities(a_summary[0], a_initial_, 1.0 - a_initially_slowed_chance, a_hp);
1488  scale_probabilities(a_summary[1], a_initial_slowed_, a_initially_slowed_chance, a_hp);
1489  scale_probabilities(b_summary[0], b_initial_, 1.0 - b_initially_slowed_chance, b_hp);
1490  scale_probabilities(b_summary[1], b_initial_slowed_, b_initially_slowed_chance, b_hp);
1491 
1492  clear();
1493 }
1494 
1495 void monte_carlo_combat_matrix::simulate()
1496 {
1498 
1499  for(unsigned int i = 0u; i < NUM_ITERATIONS; ++i) {
1500  bool a_hit = false;
1501  bool b_hit = false;
1502  bool a_slowed = rng.get_random_bool(a_initially_slowed_chance_);
1503  bool b_slowed = rng.get_random_bool(b_initially_slowed_chance_);
1504  const std::vector<double>& a_initial = a_slowed ? a_initial_slowed_ : a_initial_;
1505  const std::vector<double>& b_initial = b_slowed ? b_initial_slowed_ : b_initial_;
1506  unsigned int a_hp = rng.get_random_element(a_initial.begin(), a_initial.end());
1507  unsigned int b_hp = 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) * (1.0 - 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) * (1.0 - 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  std::cerr << "Mismatch for " << i << " hp: " << summary[0][i] << " should have been " << res[i] << "\n";
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  std::cerr << "Mismatch for " << i << " hp: " << opponent.summary[0][i] << " should have been " << opp_res[i] << "\n";
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  std::cerr << "maxhp must be at least hitpoints." << std::endl;
2734  exit(1);
2735  }
2736  }
2737 
2738  if(strstr((*argv)[5], "drain")) {
2739  if(!max) {
2740  std::cerr << "WARNING: drain specified without maxhp; assuming uninjured." << std::endl;
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  std::cerr << "WARNING: swarm specified without maxhp; assuming uninjured." << std::endl;
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  std::cerr
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  << std::endl;
2794  exit(1);
2795  }
2796 
2797  def_stats = parse_unit(&argv);
2798  def = new combatant(*def_stats);
2799  for(i = 0; argv[1] && i < 19; ++i) {
2800  att_stats[i] = parse_unit(&argv);
2801  att[i] = new combatant(*att_stats[i]);
2802  }
2803 
2804  att[i] = nullptr;
2805 
2806  for(i = 0; att[i]; ++i) {
2807  debug(("Fighting next attacker\n"));
2808  att[i]->fight(*def);
2809  }
2810 
2811  def->print("Defender", 0, 0);
2812  for(i = 0; att[i]; ++i) {
2813  att[i]->print("Attacker", 0, i + 1);
2814  }
2815 
2816  for(i = 0; att[i]; ++i) {
2817  delete att[i];
2818  delete att_stats[i];
2819  }
2820 
2821  delete def;
2822  delete def_stats;
2823 
2824  return 0;
2825 }
2826 
2827 #endif // Standalone program
int kill_xp(int level)
Definition: game_config.hpp:48
unsigned int calc_blows(unsigned new_hp) const
Calculates the number of blows we would have if we had new_hp instead of the recorded hp...
Definition: attack.hpp:110
int combat_xp(int level)
Definition: game_config.hpp:53
double untouched
Resulting chance we were not hit by this opponent (important if it poisons)
std::vector< double > hp_dist
Resulting probability distribution (might be not as large as max_hp)
std::array< std::vector< double >, 2 > summary
Summary of matrix used to calculate last battle (unslowed & slowed).
unsigned int hp
Hitpoints of the unit at the beginning of the battle.
Definition: attack.hpp:74
Various functions that implement attacks and attack calculations.
double average_hp(unsigned int healing=0) const
What&#39;s the average hp (weighted average of hp_dist).
void clear(const std::string &key)
Definition: general.cpp:186
bool is_slowed
True if the unit is slowed at the beginning of the battle.
Definition: attack.hpp:57
bool slows
Attack slows opponent when it hits.
Definition: attack.hpp:58
int drain_constant
Base HP drained regardless of damage dealt.
Definition: attack.hpp:80
unsigned int chance_to_hit
Effective chance to hit as a percentage (all factors accounted for).
Definition: attack.hpp:76
int main(int argc, char **argv)
Definition: SDLMain.mm:115
bool poisons
Attack poisons opponent when it hits.
Definition: attack.hpp:62
bool backstab_pos
True if the attacker is in position to backstab the defender (this is used to determine whether to ap...
Definition: attack.hpp:63
int damage
Effective damage of the weapon (all factors accounted for).
Definition: attack.hpp:77
std::size_t size(const std::string &str)
Length in characters of a UTF-8 string.
Definition: unicode.cpp:87
std::string label
What to show in the filter&#39;s drop-down list.
Definition: manager.cpp:217
unsigned int level
Definition: attack.hpp:71
const battle_context_unit_stats & u_
unsigned int rounds
Berserk special can force us to fight more than one round.
Definition: attack.hpp:73
unsigned int swarm_min
Minimum number of blows with swarm (equal to num_blows if swarm isn&#39;t used).
Definition: attack.hpp:82
attack_prediction_mode
unsigned int get_random_element(T first, T last)
This helper method selects a random element from a container of floating-point numbers.
Definition: random.hpp:112
combatant(const battle_context_unit_stats &u, const combatant *prev=nullptr)
Construct a combatant.
void fight(combatant &opponent, bool levelup_considered=true)
Simulate a fight! Can be called multiple times for cumulative calculations.
Structure describing the statistics of a unit involved in the battle.
Definition: attack.hpp:51
bool damage_prediction_allow_monte_carlo_simulation()
Definition: general.cpp:949
bool get_random_bool(double probability)
This helper method returns true with the probability supplied as a parameter.
Definition: random.cpp:137
double slowed
Resulting chance we are slowed.
All combat-related info.
bool swarm
Attack has swarm special.
Definition: attack.hpp:67
int slow_damage
Effective damage if unit becomes slowed (== damage, if already slowed)
Definition: attack.hpp:78
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:941
mock_party p
static map_location::DIRECTION s
unsigned int experience
Definition: attack.hpp:70
std::vector< std::string > names
Definition: build_info.cpp:66
static const unsigned int MONTE_CARLO_SIMULATION_THRESHOLD
bool firststrike
Attack has firststrike special.
Definition: attack.hpp:68
bool is_poisoned
True if the unit is poisoned at the beginning of the battle.
Definition: attack.hpp:56
#define debug(x)
int drain_percent
Percentage of damage recovered as health.
Definition: attack.hpp:79
#define next(ls)
Definition: llex.cpp:32
double t
Definition: astarsearch.cpp:65
std::vector< std::string > split(const config_attribute_value &val)
map_location prev
Definition: astarsearch.cpp:66
Standard logging facilities (interface).
EXIT_STATUS start(const std::string &filename, bool take_screenshot, const std::string &screenshot_filename)
Main interface for launching the editor from the title screen.
Definition: editor_main.cpp:30
unsigned int num_blows
Effective number of blows, takes swarm into account.
Definition: attack.hpp:81
unsigned int max_hp
Maximum hitpoints of the unit.
Definition: attack.hpp:75
bool is_attacker
True if the unit is the attacker.
Definition: attack.hpp:55
#define e
unsigned int max_experience
Definition: attack.hpp:70
bool petrifies
Attack petrifies opponent when it hits.
Definition: attack.hpp:60
mock_char c
static rng & default_instance()
Definition: random.cpp:74
bool drains
Attack drains opponent when it hits.
Definition: attack.hpp:59
double poisoned
Resulting chance we are poisoned.
unsigned int swarm_max
Maximum number of blows with swarm (equal to num_blows if swarm isn&#39;t used).
Definition: attack.hpp:83
this class does not give synced random results derived classes might do.
Definition: random.hpp:28