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