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