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