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