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