Logo Search packages:      
Sourcecode: wesnoth-1.9 version File versions  Download package

attack_prediction.cpp

Go to the documentation of this file.
/* $Id: attack_prediction.cpp 46186 2010-09-01 21:12:38Z silene $ */
/*
   Copyright (C) 2006 - 2010 by Rusty Russell <rusty@rustcorp.com.au>
   Part of the Battle for Wesnoth Project http://www.wesnoth.org/

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY.

   See the COPYING file for more details.

   Full algorithm by Yogin.  Typing and optimization by Rusty.

   This code has lots of debugging.  It is there for a reason:
   this code is kinda tricky.  Do not remove it.
*/

/**
 * @file
 * Simulate combat to calculate attacks. Standalone program, benchmark.
 */

#include "attack_prediction.hpp"

#include "actions.hpp"
#include "game_config.hpp"

// Compile with -O3 -DBENCHMARK for speed testing,
// -DCHECK for testing correctness
// (run tools/wesnoth-attack-sim.c --check on output)
#if defined(BENCHMARK) || defined(CHECK)
#include <time.h>
#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>
#endif

#ifdef ATTACK_PREDICTION_DEBUG
#define debug(x) printf x
#else
#define debug(x)
#endif

namespace
{
/** A matrix of A's hitpoints vs B's hitpoints. */
struct prob_matrix
{
      // Simple matrix, both known HP.
      prob_matrix(unsigned int a_max_hp, unsigned int b_max_hp,
                        bool a_slows, bool b_slows,
                        unsigned int a_hp, unsigned int b_hp,
                        const std::vector<double> a_summary[2],
                        const std::vector<double> b_summary[2]);

      ~prob_matrix();

      // A hits B.
      void receive_blow_b(unsigned damage, unsigned slow_damage, double hit_chance,
                                    bool a_slows, bool a_drains);

      // B hits A.  Why can't they just get along?
      void receive_blow_a(unsigned damage, unsigned slow_damage, double hit_chance,
                                    bool b_slows, bool b_drains);

      void forced_levelup_a();
      void conditional_levelup_a();

      void forced_levelup_b();
      void conditional_levelup_b();

      // We lied: actually did less damage, adjust matrix.
      void remove_petrify_distortion_a(unsigned damage, unsigned slow_damage, unsigned b_hp);
      void remove_petrify_distortion_b(unsigned damage, unsigned slow_damage, unsigned a_hp);

      // Its over, and here's the bill.
      void extract_results(std::vector<double> summary_a[2],
                                     std::vector<double> summary_b[2]);

      // What's the chance one is dead?
      double dead_prob() const;

      void dump() const;

      // We need four matrices, or "planes", reflecting the possible
      // "slowed" states (neither slowed, A slowed, B slowed, both slowed).
      enum {
            NEITHER_SLOWED,
            A_SLOWED,
            B_SLOWED,
            BOTH_SLOWED
      };

private:
      // This gives me 10% speed improvement over std::vector<> (g++4.0.3 x86)
      double *new_arr(unsigned int size);

      double &val(unsigned plane, unsigned row, unsigned col);
      const double &val(unsigned plane, unsigned row, unsigned col) const;

      // Move this much from src to dst.  Returns true if anything transferred.
      void xfer(unsigned dst_plane, unsigned src_plane,
                    unsigned row_dst, unsigned col_dst,
                    unsigned row_src, unsigned col_src,
                    double prob);

      // Shift columns on this plane (b taking damage).  Returns min col.
      void shift_cols(unsigned dst, unsigned src,
                              unsigned damage, double prob, bool drain);

      // Shift rows on this plane (a taking damage).  Returns new min row.
      void shift_rows(unsigned dst, unsigned src,
                              unsigned damage, double prob, bool drain);

      /** @todo FIXME: rename using _ at end. */
00119       unsigned int rows_, cols_;
      double *plane_[4];

      // For optimization, we keep track of the lower row/col we need to consider
      unsigned int min_row_[4], min_col_[4];
};

prob_matrix::prob_matrix(unsigned int a_max_hp, unsigned int b_max_hp,
                                     bool a_slows, bool b_slows,
                                     unsigned int a_hp, unsigned int b_hp,
                                     const std::vector<double> a_summary[2],
                                     const std::vector<double> b_summary[2])
      : rows_(a_max_hp+1), cols_(b_max_hp+1)
{
      if (!a_summary[0].empty()) {
            // A has fought before.  Do we need a slow plane for it?
            if (!a_summary[1].empty())
                  b_slows = true;
            // Don't handle both being reused.
            assert(b_summary[0].empty());
      }
      if (!b_summary[0].empty()) {
            // B has fought before.  Do we need a slow plane for it?
            if (!b_summary[1].empty())
                  a_slows = true;
      }

      plane_[NEITHER_SLOWED] = new_arr(rows_*cols_);
      if (b_slows)
            plane_[A_SLOWED] = new_arr(rows_*cols_);
      else
            plane_[A_SLOWED] = NULL;
      if (a_slows)
            plane_[B_SLOWED] = new_arr(rows_*cols_);
      else
            plane_[B_SLOWED] = NULL;
      if (a_slows && b_slows)
            plane_[BOTH_SLOWED] = new_arr(rows_*cols_);
      else
            plane_[BOTH_SLOWED] = NULL;

      min_row_[NEITHER_SLOWED] = a_hp - 1;
      min_col_[NEITHER_SLOWED] = b_hp - 1;
      min_row_[A_SLOWED] = min_row_[B_SLOWED] = min_row_[BOTH_SLOWED] = rows_;
      min_col_[A_SLOWED] = min_col_[B_SLOWED] = min_col_[BOTH_SLOWED] = cols_;

      // Transfer HP distribution from A?
      if (!a_summary[0].empty()) {
            // @todo FIXME: Can optimize here.
            min_row_[NEITHER_SLOWED] = 0;
            min_row_[A_SLOWED] = 0;
            min_col_[A_SLOWED] = b_hp - 1;
            for (unsigned int row = 0; row < a_summary[0].size(); ++row)
                  val(NEITHER_SLOWED, row, b_hp) = a_summary[0][row];
            if (!a_summary[1].empty()) {
                  for (unsigned int row = 0; row < a_summary[1].size(); ++row)
                        val(A_SLOWED, row, b_hp) = a_summary[1][row];
            }
            debug(("A has fought before\n"));
            dump();
      } else if (!b_summary[0].empty()) {
            min_col_[NEITHER_SLOWED] = 0;
            min_col_[B_SLOWED] = 0;
            min_row_[B_SLOWED] = a_hp - 1;
            for (unsigned int col = 0; col < b_summary[0].size(); ++col)
                  val(NEITHER_SLOWED, a_hp, col) = b_summary[0][col];
            if (!b_summary[1].empty()) {
                  for (unsigned int col = 0; col < b_summary[1].size(); ++col)
                        val(B_SLOWED, a_hp, col) = b_summary[1][col];
            }
            debug(("B has fought before\n"));
            dump();
      } else {
            // If a unit has drain it might end with more HP than before.
            // Make sure we don't access the matrix in invalid positions.
            a_hp = std::min<unsigned int>(a_hp, rows_ - 1);
            b_hp = std::min<unsigned int>(b_hp, cols_ - 1);
            val(NEITHER_SLOWED, a_hp, b_hp) = 1.0;
      }
}

prob_matrix::~prob_matrix()
{
      delete[] plane_[NEITHER_SLOWED];
      delete[] plane_[A_SLOWED];
      delete[] plane_[B_SLOWED];
      delete[] plane_[BOTH_SLOWED];
}

// Allocate a new probability array, initialized to 0.
double *prob_matrix::new_arr(unsigned int size)
{
      double *arr = new double[size];
      memset(arr, 0, sizeof(double) * size);
      return arr;
}

double &prob_matrix::val(unsigned p, unsigned row, unsigned col)
{
      assert(row < rows_);
      assert(col < cols_);
      return plane_[p][row * cols_ + col];
}

const double &prob_matrix::val(unsigned p, unsigned row, unsigned col) const
{
      assert(row < rows_);
      assert(col < cols_);
      return plane_[p][row * cols_ + col];
}

#ifdef CHECK
void prob_matrix::dump() const
{
      unsigned int row, col, m;
      const char *names[]
            = { "NEITHER_SLOWED", "A_SLOWED", "B_SLOWED", "BOTH_SLOWED" };

      for (m = 0; m < 4; ++m) {
            if (!plane_[m])
                  continue;
            debug(("%s:\n", names[m]));
            for (row = 0; row < rows_; ++row) {
                  debug(("  "));
                  for (col = 0; col < cols_; ++col)
                        debug(("%4.3g ", val(m, row, col)*100));
                  debug(("\n"));
            }
      }
}
#else
void prob_matrix::dump() const
{
}
#endif

// xfer, shift_cols and shift_rows use up most of our time.  Careful!
void prob_matrix::xfer(unsigned dst_plane, unsigned src_plane,
                                 unsigned row_dst, unsigned col_dst,
                                 unsigned row_src, unsigned col_src,
                                 double prob)
{
      double &src = val(src_plane, row_src, col_src);
      if (src != 0.0) {
            double diff = src * prob;
            src -= diff;

            // This is here for drain.
            if (col_dst >= cols_)
                  col_dst = cols_ - 1;
            if (row_dst >= rows_)
                  row_dst = rows_ - 1;

            val(dst_plane, row_dst, col_dst) += diff;

            debug(("Shifted %4.3g from %s(%u,%u) to %s(%u,%u)\n",
                     diff, src_plane == NEITHER_SLOWED ? ""
                     : src_plane == A_SLOWED ? "[A_SLOWED]"
                     : src_plane == B_SLOWED ? "[B_SLOWED]"
                     : src_plane == BOTH_SLOWED ? "[BOTH_SLOWED]" : "INVALID",
                     row_src, col_src,
                     dst_plane == NEITHER_SLOWED ? ""
                     : dst_plane == A_SLOWED ? "[A_SLOWED]"
                     : dst_plane == B_SLOWED ? "[B_SLOWED]"
                     : dst_plane == BOTH_SLOWED ? "[BOTH_SLOWED]" : "INVALID",
                     row_dst, col_dst));
      }
}

void prob_matrix::shift_cols(unsigned dst, unsigned src,
                                           unsigned damage, double prob, bool drain)
{
      unsigned int row, col;
      unsigned int shift = drain ? 1 : 31; // Avoids a branch.

      if (damage >= cols_)
            damage = cols_ - 1;

      // Loop backwards so we write drain behind us, for when src == dst.
      for (row = rows_ - 1; row > min_row_[src]; row--) {
            // These are all going to die (move to col 0).
            for (col = 1; col <= damage; ++col)
                  xfer(dst, src, row+(col>>shift), 0, row, col, prob);
            for (col = damage+1; col < cols_; ++col)
                  xfer(dst, src, row+(damage>>shift), col - damage, row, col, prob);
      }
}

void prob_matrix::shift_rows(unsigned dst, unsigned src,
                                           unsigned damage, double prob, bool drain)
{
      unsigned int row, col;
      unsigned int shift = drain ? 1 : 31; // Avoids a branch.

      if (damage >= rows_)
            damage = rows_ - 1;

      // Loop downwards so if we drain, we write behind us.
      for (col = cols_ - 1; col > min_col_[src]; col--) {
            // These are all going to die (move to row 0).
            for (row = 1; row <= damage; ++row)
                  xfer(dst, src, 0, col+(row>>shift), row, col, prob);
            for (row = damage+1; row < rows_; ++row)
                  xfer(dst, src, row - damage, col+(damage>>shift), row, col, prob);
      }
}

// Shift prob_matrix to reflect probability 'hit_chance'
// that damage (up to) 'damage' is done to 'b'.
void prob_matrix::receive_blow_b(unsigned damage, unsigned slow_damage, double hit_chance,
                                                 bool a_slows, bool a_drains)
{
      int src, dst;

      // Walk backwards so we don't copy already-copied matrix planes.
      for (src = 3; src >=0; src--) {
            unsigned int actual_damage;

            if (!plane_[src])
                  continue;

            // If A slows us, we go from 0=>2, 1=>3, 2=>2 3=>3.
            if (a_slows)
                  dst = (src|2);
            else
                  dst = src;

            // A is slow in planes 1 and 3.
            if (src & 1)
                  actual_damage = slow_damage;
            else
                  actual_damage = damage;

            shift_cols(dst, src, actual_damage, hit_chance, a_drains);
            if (min_col_[src] < damage)
                  min_col_[dst] = 0;
            else if (min_col_[src] - damage < min_col_[dst])
                  min_col_[dst] = min_col_[src] - damage;
            if (min_row_[src] < min_row_[dst])
                  min_row_[dst] = min_row_[src];
      }
}

// We lied: actually did less damage, adjust matrix.
void prob_matrix::remove_petrify_distortion_a(unsigned damage, unsigned slow_damage,
                                                                  unsigned b_hp)
{
      for (int p = 0; p < 4; ++p) {
            if (!plane_[p])
                  continue;

            // A is slow in planes 1 and 3.
            if (p & 1) {
                  if (b_hp > slow_damage)
                        for (unsigned int row = 0; row < rows_; ++row)
                              xfer(p, p, row, b_hp - slow_damage, row, 0, 1.0);
            } else {
                  if (b_hp > damage)
                        for (unsigned int row = 0; row < rows_; ++row)
                              xfer(p, p, row, b_hp - damage, row, 0, 1.0);
            }
      }
}

void prob_matrix::remove_petrify_distortion_b(unsigned damage, unsigned slow_damage,
                                                                  unsigned a_hp)
{
      for (int p = 0; p < 4; ++p) {
            if (!plane_[p])
                  continue;

            // B is slow in planes 2 and 3.
            if (p & 2) {
                  if (a_hp > slow_damage)
                        for (unsigned int col = 0; col < cols_; ++col)
                              xfer(p, p, a_hp - slow_damage, col, 0, col, 1.0);
            } else {
                  if (a_hp > damage)
                        for (unsigned int col = 0; col < cols_; ++col)
                              xfer(p, p, a_hp - damage, col, 0, col, 1.0);
            }
      }
}

void prob_matrix::extract_results(std::vector<double> summary_a[2],
                                                  std::vector<double> summary_b[2])
{
      unsigned int p, row, col;

      summary_a[0] = std::vector<double>(rows_);
      summary_b[0] = std::vector<double>(cols_);

      if (plane_[A_SLOWED])
            summary_a[1] = std::vector<double>(rows_);
      if (plane_[B_SLOWED])
            summary_b[1] = std::vector<double>(cols_);

      for (p = 0; p < 4; ++p) {
            int dst_a, dst_b;
            if (!plane_[p])
                  continue;

            // A is slow in planes 1 and 3.
            dst_a = (p & 1);
            // B is slow in planes 2 and 3.
            dst_b = !!(p & 2);
            for (row = 0; row < rows_; ++row) {
                  for (col = 0; col < cols_; ++col) {
                        summary_a[dst_a][row] += val(p, row, col);
                        summary_b[dst_b][col] += val(p, row, col);
                  }
            }
      }
}

// What's the chance one is dead?
double prob_matrix::dead_prob() const
{
      unsigned int p, row, col;
      double prob = 0.0;

      for (p = 0; p < 4; ++p) {
            if (!plane_[p])
                  continue;
            // We might count 0,0 twice, but that is always 0 anyway.
            for (row = min_row_[p]; row < rows_; ++row)
                  prob += val(p, row, 0);
            for (col = min_col_[p]; col < cols_; ++col)
                  prob += val(p, 0, col);
      }
      return prob;
}

// Shift matrix to reflect probability 'hit_chance'
// that damage (up to) 'damage' is done to 'a'.
void prob_matrix::receive_blow_a(unsigned damage, unsigned slow_damage, double hit_chance,
                                                 bool b_slows, bool b_drains)
{
      int src, dst;

      // Walk backwards so we don't copy already-copied matrix planes.
      for (src = 3; src >=0; src--) {
            unsigned actual_damage;

            if (!plane_[src])
                  continue;

            // If B slows us, we go from 0=>1, 1=>1, 2=>3 3=>3.
            if (b_slows)
                  dst = (src|1);
            else
                  dst = src;

            // B is slow in planes 2 and 3.
            if (src & 2)
                  actual_damage = slow_damage;
            else
                  actual_damage = damage;

            shift_rows(dst, src, actual_damage, hit_chance, b_drains);
            if (min_row_[src] < damage)
                  min_row_[dst] = 0;
            else if (min_row_[src] - damage < min_row_[dst])
                  min_row_[dst] = min_row_[src] - damage;
            if (min_col_[src] < min_col_[dst])
                  min_col_[dst] = min_col_[src];
      }
}

void prob_matrix::forced_levelup_a()
{
      /* Move all the values (except 0hp) of all the planes to the last
         row of the planes unslowed for A. */
      for (int p = 0; p < 4; ++p) {
            if (!plane_[p]) continue;
            for (unsigned row = std::max(min_row_[p], 1u); row < rows_; ++row) {
                  for (unsigned col = min_col_[p]; col < cols_; ++col) {
                        double v = val(p, row, col);
                        val(p, row, col) = 0;
                        val(p & -2, rows_ - 1, col) += v;
                  }
            }
      }
}

void prob_matrix::forced_levelup_b()
{
      /* Move all the values (except 0hp) of all the planes to the last
         column of planes unslowed for B. */
      for (int p = 0; p < 4; ++p) {
            if (!plane_[p]) continue;
            for (unsigned row = min_row_[p]; row < rows_; ++row) {
                  for (unsigned col = std::max(min_col_[p], 1u); col < cols_; ++col) {
                        double v = val(p, row, col);
                        val(p, row, col) = 0;
                        val(p & -3, row, cols_ - 1) += v;
                  }
            }
      }
}

void prob_matrix::conditional_levelup_a()
{
      /* Move the values of the first column (except 0hp) of all the
         planes to the last row of the planes unslowed for A. */
      for (int p = 0; p < 4; ++p) {
            if (!plane_[p]) continue;
            for (unsigned row = std::max(min_row_[p], 1u); row < rows_; ++row) {
                  double v = val(p, row, 0);
                  val(p, row, 0) = 0;
                  val(p & -2, rows_ - 1, 0) += v;
            }
      }
}

void prob_matrix::conditional_levelup_b()
{
      /* Move the values of the first row (except 0hp) of all the
         planes to the last column of the planes unslowed for B. */
      for (int p = 0; p < 4; ++p) {
            if (!plane_[p]) continue;
            for (unsigned col = std::max(min_col_[p], 1u); col < cols_; ++col) {
                  double v = val(p, 0, col);
                  val(p, 0, col) = 0;
                  val(p & -3, 0, cols_ - 1) += v;
            }
      }
}

} // end anon namespace

00550 unsigned combatant::hp_dist_size(const battle_context_unit_stats &u, const combatant *prev)
{
      // Our summary must be as big as previous one.
      if (prev) {
            return prev->hp_dist.size();
      }

      // If this unit drains, HP can increase, so alloc full array.
      // Do this anyway in case we level up.
      return u.max_hp + 1;
}

00562 combatant::combatant(const battle_context_unit_stats &u, const combatant *prev)
      : hp_dist(hp_dist_size(u, prev)),
        untouched(0.0),
        poisoned(0.0),
        slowed(0.0),
        u_(u),
        hit_chances_(u.num_blows, u.chance_to_hit / 100.0)
{
      // We inherit current state from previous combatant.
      if (prev) {
            summary[0] = prev->summary[0];
            summary[1] = prev->summary[1];
            poisoned = prev->poisoned;
            untouched = prev->untouched;
            slowed = prev->slowed;
      } else {
            untouched = 1.0;
            poisoned = u.is_poisoned ? 1.0 : 0.0;
            slowed = u.is_slowed ? 1.0 : 0.0;
      }
}

// Copy constructor (except use this copy of battle_context_unit_stats)
00585 combatant::combatant(const combatant &that, const battle_context_unit_stats &u)
      : hp_dist(that.hp_dist), untouched(that.untouched), poisoned(that.poisoned), slowed(that.slowed), u_(u), hit_chances_(that.hit_chances_)
{
            summary[0] = that.summary[0];
            summary[1] = that.summary[1];
}



// For swarm, whether we get an attack depends on HP distribution
// from previous combat.  So we roll this into our P(hitting),
// since no attack is equivalent to missing.
00597 void combatant::adjust_hitchance()
{
      if (summary[0].empty() || u_.swarm_min == u_.swarm_max)
            return;

      hit_chances_ = std::vector<double>(u_.swarm_max);
      double alive_prob;

      if (summary[1].empty())
            alive_prob = 1 - summary[0][0];
      else
            alive_prob = 1 - summary[0][0] - summary[1][0];

      unsigned int i;
      for (i = 1; i <= u_.max_hp; ++i) {
            double prob = 0.0;
            if(i < summary[0].size()) {
                  prob = summary[0][i];
            }
            if (!summary[1].empty())
                  prob += summary[1][i];
            for (unsigned int j = 0; j < u_.swarm_min + (u_.swarm_max -
                static_cast<double>(u_.swarm_min)) * u_.hp / u_.max_hp; ++j)

                  hit_chances_[j] += prob * u_.chance_to_hit / 100.0 / alive_prob;
      }

      debug(("\nhit_chances_ (base %u%%):", u_.chance_to_hit));
      for (i = 0; i < u_.swarm_max; ++i)
            debug((" %.2f", hit_chances_[i] * 100.0 + 0.5));
      debug(("\n"));
}

// Minimum HP we could possibly have.
00631 unsigned combatant::min_hp() const
{
      if (summary[0].empty())
            return u_.hp;

      // We don't handle this (yet).
      assert(summary[1].empty());

      unsigned int i;
      for (i = 0; summary[0][i] == 0; ++i) {};
      return i;
}

static void forced_levelup(std::vector<double> &hp_dist)
{
      /* If we survive the combat, we will level up. So the probability
         of death is unchanged, but all other cases get merged into the
         fully healed case. */
      std::vector<double>::iterator i = hp_dist.begin();
      ++i; // Skip to the second value.
      for (; i != hp_dist.end(); ++i) *i = 0;
      // Full heal unless dead.
      hp_dist.back() = 1 - hp_dist.front();
}

static void conditional_levelup(std::vector<double> &hp_dist, double kill_prob)
{
      /* If we kill, we will level up. So then the damage we had becomes
         less probable since it's now conditional on us not levelling up.
         This doesn't apply to the probability of us dying, of course. */
      double scalefactor = 1 - kill_prob / (1 - hp_dist.front());
      std::vector<double>::iterator i = hp_dist.begin();
      ++i; // Skip to the second value.
      for (; i != hp_dist.end(); ++i) *i *= scalefactor;
      // Full heal if leveled up.
      hp_dist.back() += kill_prob;
}

// Combat without chance of death, berserk, slow or drain is simple.
00670 void combatant::no_death_fight(combatant &opp, bool levelup_considered)
{
      if (summary[0].empty()) {
            // Starts with a known HP, so Pascal's triangle.
            summary[0] = std::vector<double>(u_.max_hp+1);
            summary[0][u_.hp] = 1.0;
            for (unsigned int i = 0; i < opp.hit_chances_.size(); ++i) {
                  for (int j = i; j >= 0; j--) {
                        double move = summary[0][u_.hp - j * opp.u_.damage] * opp.hit_chances_[i];
                        summary[0][u_.hp - j * opp.u_.damage] -= move;
                        summary[0][u_.hp - (j+1) * opp.u_.damage] += move;
                  }
            }
      } else {
            // HP could be spread anywhere, iterate through whole thing.
            for (unsigned int i = 0; i < opp.hit_chances_.size(); ++i) {
                  for (unsigned int j = opp.u_.damage; j <= u_.hp; ++j) {
                        double move = summary[0][j] * opp.hit_chances_[i];
                        summary[0][j] -= move;
                        summary[0][j - opp.u_.damage] += move;
                  }
            }
      }

      if (opp.summary[0].empty()) {
            // Starts with a known HP, so Pascal's triangle.
            opp.summary[0] = std::vector<double>(opp.u_.max_hp+1);
            opp.summary[0][opp.u_.hp] = 1.0;
            for (unsigned int i = 0; i < hit_chances_.size(); ++i) {
                  for (int j = i; j >= 0; j--) {
                        double move = opp.summary[0][opp.u_.hp - j * u_.damage] * hit_chances_[i];
                        opp.summary[0][opp.u_.hp - j * u_.damage] -= move;
                        opp.summary[0][opp.u_.hp - (j+1) * u_.damage] += move;
                  }
            }
      } else {
            // HP could be spread anywhere, iterate through whole thing.
            for (unsigned int i = 0; i < hit_chances_.size(); ++i) {
                  for (unsigned int j = u_.damage; j <= opp.u_.hp; ++j) {
                        double move = opp.summary[0][j] * hit_chances_[i];
                        opp.summary[0][j] -= move;
                        opp.summary[0][j - u_.damage] += move;
                  }
            }
      }

      if (!levelup_considered) return;

      if (u_.experience + opp.u_.level >= u_.max_experience) {
            forced_levelup(summary[0]);
      }

      if (opp.u_.experience + u_.level >= opp.u_.max_experience) {
            forced_levelup(opp.summary[0]);
      }
}

// Combat with <= 1 strike each is simple, too.
00728 void combatant::one_strike_fight(combatant &opp, bool levelup_considered)
{
      if (opp.summary[0].empty()) {
            opp.summary[0] = std::vector<double>(opp.u_.max_hp+1);
            if (hit_chances_.size() == 1) {
                  opp.summary[0][opp.u_.hp] = 1.0 - hit_chances_[0];
                  opp.summary[0][std::max<int>(opp.u_.hp - u_.damage, 0)] = hit_chances_[0];
            } else {
                  assert(hit_chances_.size() == 0);
                  opp.summary[0][opp.u_.hp] = 1.0;
            }
      } else {
            if (hit_chances_.size() == 1) {
                  for (unsigned int i = 1; i < opp.summary[0].size(); ++i) {
                        double move = opp.summary[0][i] * hit_chances_[0];
                        opp.summary[0][i] -= move;
                        opp.summary[0][std::max<int>(i - u_.damage, 0)] += move;
                  }
            }
      }

      // If we killed opponent, it won't attack us.
      double opp_alive_prob = 1.0 - opp.summary[0][0];
      if (summary[0].empty()) {
            summary[0] = std::vector<double>(u_.max_hp+1);
            if (opp.hit_chances_.size() == 1) {
                  summary[0][u_.hp] = 1.0 - opp.hit_chances_[0] * opp_alive_prob;
                  summary[0][std::max<int>(u_.hp - opp.u_.damage, 0)] = opp.hit_chances_[0] * opp_alive_prob;
            } else {
                  assert(opp.hit_chances_.size() == 0);
                  summary[0][u_.hp] = 1.0;
            }
      } else {
            if (opp.hit_chances_.size() == 1) {
                  for (unsigned int i = 1; i < summary[0].size(); ++i) {
                        double move = summary[0][i] * opp.hit_chances_[0] * opp_alive_prob;
                        summary[0][i] -= move;
                        summary[0][std::max<int>(i - opp.u_.damage, 0)] += move;
                  }
            }
      }

      if (!levelup_considered) return;

      if (u_.experience + opp.u_.level >= u_.max_experience) {
            forced_levelup(summary[0]);
      } else if (u_.experience + game_config::kill_xp(opp.u_.level) >= u_.max_experience) {
            conditional_levelup(summary[0], opp.summary[0][0]);
      }

      if (opp.u_.experience + u_.level >= opp.u_.max_experience) {
            forced_levelup(opp.summary[0]);
      } else if (opp.u_.experience + game_config::kill_xp(u_.level) >= opp.u_.max_experience) {
            conditional_levelup(opp.summary[0], summary[0][0]);
      }
}

00785 void combatant::complex_fight(combatant &opp, unsigned rounds, bool levelup_considered)
{
      prob_matrix m(hp_dist.size()-1, opp.hp_dist.size()-1,
                          u_.slows && !opp.u_.is_slowed, opp.u_.slows && !u_.is_slowed,
                          u_.hp, opp.u_.hp, summary, opp.summary);

      unsigned max_attacks = std::max(hit_chances_.size(), opp.hit_chances_.size());

      debug(("A gets %u attacks, B %u\n", hit_chances_.size(), opp.hit_chances_.size()));

      unsigned int a_damage = u_.damage, a_slow_damage = u_.slow_damage;
      unsigned int b_damage = opp.u_.damage, b_slow_damage = opp.u_.slow_damage;

      // To simulate stoning, we set to amount which kills, and re-adjust after.
      /** @todo FIXME: This doesn't work for rolling calculations, just first battle. */
      if (u_.petrifies)
            a_damage = a_slow_damage = opp.u_.max_hp;
      if (opp.u_.petrifies)
            b_damage = b_slow_damage = u_.max_hp;

      do {
            for (unsigned int i = 0; i < max_attacks; ++i) {
                  if (i < hit_chances_.size()) {
                        debug(("A strikes\n"));
                        m.receive_blow_b(a_damage, a_slow_damage, hit_chances_[i],
                                                 u_.slows && !opp.u_.is_slowed, u_.drains);
                        m.dump();
                  }
                  if (i < opp.hit_chances_.size()) {
                        debug(("B strikes\n"));
                        m.receive_blow_a(b_damage, b_slow_damage, opp.hit_chances_[i],
                                                 opp.u_.slows && !u_.is_slowed, opp.u_.drains);
                        m.dump();
                  }
            }

            debug(("Combat ends:\n"));
            m.dump();
      } while (--rounds && m.dead_prob() < 0.99);

      if (u_.petrifies)
            m.remove_petrify_distortion_a(u_.damage, u_.slow_damage, opp.u_.hp);
      if (opp.u_.petrifies)
            m.remove_petrify_distortion_b(opp.u_.damage, opp.u_.slow_damage, u_.hp);

      if (levelup_considered) {
            if (u_.experience + opp.u_.level >= u_.max_experience) {
                  m.forced_levelup_a();
            } else if (u_.experience + game_config::kill_xp(opp.u_.level) >= u_.max_experience) {
                  m.conditional_levelup_a();
            }

            if (opp.u_.experience + u_.level >= opp.u_.max_experience) {
                  m.forced_levelup_b();
            } else if (opp.u_.experience + game_config::kill_xp(u_.level) >= opp.u_.max_experience) {
                  m.conditional_levelup_b();
            }
      }

      // We extract results separately, then combine.
      m.extract_results(summary, opp.summary);
}

// Two man enter.  One man leave!
// ... Or maybe two.  But definitely not three.
// Of course, one could be a woman.  Or both.
// And neither could be human, too.
// Um, ok, it was a stupid thing to say.
00853 void combatant::fight(combatant &opp, bool levelup_considered)
{
      unsigned int rounds = std::max<unsigned int>(u_.rounds, opp.u_.rounds);

      // If defender has firststrike and we don't, reverse.
      if (opp.u_.firststrike && !u_.firststrike) {
            opp.fight(*this, levelup_considered);
            return;
      }

#ifdef ATTACK_PREDICTION_DEBUG
      printf("A:\n");
      u_.dump();
      printf("B:\n");
      opp.u_.dump();
#endif

      // If we've fought before and we have swarm, we must adjust cth array.
      adjust_hitchance();
      opp.adjust_hitchance();

#if 0
      std::vector<double> prev = summary[0], opp_prev = opp.summary[0];
      complex_fight(opp, 1);
      std::vector<double> res = summary[0], opp_res = opp.summary[0];
      summary[0] = prev;
      opp.summary[0] = opp_prev;
#endif

      // Optimize the simple cases.
      if (rounds == 1 && !u_.slows && !opp.u_.slows &&
            !u_.drains && !opp.u_.drains && !u_.petrifies && !opp.u_.petrifies &&
            summary[1].empty() && opp.summary[1].empty()) {
            if (hit_chances_.size() <= 1 && opp.hit_chances_.size() <= 1) {
                  one_strike_fight(opp, levelup_considered);
            } else if (hit_chances_.size() * u_.damage < opp.min_hp() &&
                  opp.hit_chances_.size() * opp.u_.damage < min_hp()) {
                  no_death_fight(opp, levelup_considered);
            } else {
                  complex_fight(opp, rounds, levelup_considered);
            }
      } else {
                  complex_fight(opp, rounds, levelup_considered);
      }

#if 0
      assert(summary[0].size() == res.size());
      assert(opp.summary[0].size() == opp_res.size());
      for (unsigned int i = 0; i < summary[0].size(); ++i) {
            if (fabs(summary[0][i] - res[i]) > 0.000001) {
                  std::cerr << "Mismatch for " << i << " hp: " << summary[0][i] << " should have been " << res[i] << "\n";
                  assert(0);
            }
      }
      for (unsigned int i = 0; i < opp.summary[0].size(); ++i) {
            if (fabs(opp.summary[0][i] - opp_res[i])> 0.000001) {
                  std::cerr << "Mismatch for " << i << " hp: " << opp.summary[0][i] << " should have been " << opp_res[i] << "\n";
                  assert(0);
            }
      }
#endif

      // Combine summary into distribution.
      if (summary[1].empty())
            hp_dist = summary[0];
      else {
            for (unsigned int i = 0; i < hp_dist.size(); ++i)
                  hp_dist[i] = summary[0][i] + summary[1][i];
      }
      if (opp.summary[1].empty())
            opp.hp_dist = opp.summary[0];
      else {
            for (unsigned int i = 0; i < opp.hp_dist.size(); ++i)
                  opp.hp_dist[i] = opp.summary[0][i] + opp.summary[1][i];
      }

      // Make sure we don't try to access the vectors out of bounds,
      // drain increases HPs so we determine the number of HP here
      // and make sure it stays within bounds
      const unsigned int hp = std::min<unsigned int>(u_.hp, hp_dist.size() - 1);
      const unsigned int opp_hp = std::min<unsigned int>(opp.u_.hp, opp.hp_dist.size() - 1);

      // Chance that we / they were touched this time.
      double touched = untouched - hp_dist[hp];
      double opp_touched = opp.untouched - opp.hp_dist[opp_hp];
      if (opp.u_.poisons)
            poisoned += (1 - poisoned) * touched;
      if (u_.poisons)
            opp.poisoned += (1 - opp.poisoned) * opp_touched;

      if (opp.u_.slows)
            slowed += (1 - slowed) * touched;
      if (u_.slows)
            opp.slowed += (1 - opp.slowed) * opp_touched;

      /** @todo FIXME: This is approximate: we could drain, then get hit. */
      untouched = hp_dist[hp];
      opp.untouched = opp.hp_dist[opp_hp];
}

00953 double combatant::average_hp(unsigned int healing) const
{
      double total = 0;

      // Since sum of probabilities is 1.0, we can just tally weights.
      for (unsigned int i = 1; i < hp_dist.size(); ++i) {
            total += hp_dist[i] * std::min<unsigned int>(i + healing, u_.max_hp);
      }
      return total;
}

#if defined(BENCHMARK) || defined(CHECK)
// We create a significant number of nasty-to-calculate units,
// and test each one against the others.
#define NUM_UNITS 50

// Stolen from glibc headers sys/time.h
#define timer_sub(a, b, result)                                         \
  do {                                                            \
    (result)->tv_sec = (a)->tv_sec - (b)->tv_sec;                       \
    (result)->tv_usec = (a)->tv_usec - (b)->tv_usec;                    \
    if ((result)->tv_usec < 0) {                                  \
      --(result)->tv_sec;                                         \
      (result)->tv_usec += 1000000;                               \
    }                                                       \
  } while (0)

#ifdef CHECK
void combatant::print(const char label[], unsigned int battle) const
{
      printf("#%u: %s: %u %u %u %2g%% ", battle,
               label, damage_, base_num_attacks_, hp_, base_hit_chance_*100.0);
      if (drains_)
            printf("drains,");
      if (slows_)
            printf("slows,");
      if (berserk_)
            printf("berserk,");
      if (swarm_)
            printf("swarm,");
      if (firststrike_)
            printf("firststrike,");
      printf("maxhp=%u ", hp_dist.size()-1);
      printf(" %.2f", untouched);
      for (unsigned int i = 0; i < hp_dist.size(); ++i)
            printf(" %.2f", hp_dist[i] * 100);
      printf("\n");
}
#else  // ... BENCHMARK
void combatant::print(const char label[], unsigned int battle) const
{
}
#endif

static void run(unsigned specific_battle)
{
      // N^2 battles
      struct combatant *u[NUM_UNITS];
      unsigned int i, j, k, battle = 0;
      struct timeval start, end, total;

      for (i = 0; i < NUM_UNITS; ++i) {
            unsigned hp = 1 + ((i*3)%23);
            u[i] = new combatant(hp, hp + (i+7)%17, false);
            u[i]->set_weapon((i % 4) + 1, (i % 9) == 0, (i % 5) == 0,
                                     ((i+4) % 4) == 0,
                                     ((i+3) % 5) == 0);
            u[i]->set_effectiveness((i % 7) + 2, 0.3 + (i % 6)*0.1, (i % 8) == 0);
      }

      gettimeofday(&start, NULL);
      for (i = 0; i < NUM_UNITS; ++i) {
            for (j = 0; j < NUM_UNITS; ++j) {
                  if (i == j)
                        continue;
                  for (k = 0; k < NUM_UNITS; ++k) {
                        if (i == k || j == k)
                              continue;
                        ++battle;
                        if (specific_battle && battle != specific_battle)
                              continue;
                        u[j]->fight(*u[i]);
                        // We need this here, because swarm means
                        // out num hits can change.
                        u[i]->set_effectiveness((i % 7) + 2, 0.3 + (i % 6)*0.1,
                                                            (i % 8) == 0);
                        u[k]->fight(*u[i]);
                        u[i]->print("Defender", battle);
                        u[j]->print("Attacker #1", battle);
                        u[k]->print("Attacker #2", battle);
                        u[i]->reset();
                        u[j]->reset();
                        u[k]->reset();
                  }
            }
      }
      gettimeofday(&end, NULL);

      timer_sub(&end, &start, &total);

#ifdef BENCHMARK
      printf("Total time for %i combats was %lu.%06lu\n",
             NUM_UNITS*(NUM_UNITS-1)*(NUM_UNITS-2), total.tv_sec, total.tv_usec);
      printf("Time per calc = %li us\n",
             ((end.tv_sec-start.tv_sec)*1000000 + (end.tv_usec-start.tv_usec))
               / (NUM_UNITS*(NUM_UNITS-1)*(NUM_UNITS-2)));
#else
      printf("Total combats: %i\n", NUM_UNITS*(NUM_UNITS-1)*(NUM_UNITS-2));
#endif

      for (i = 0; i < NUM_UNITS; ++i) {
            delete u[i];
      }

      exit(0);
}

static combatant *parse_unit(char ***argv,
                                           unsigned *damagep = NULL,
                                           double *hit_chancep = NULL,
                                           bool *slowsp = NULL)
{
      unsigned damage, num_attacks, hp, max_hp, hit_chance;
      bool slows, slowed, drains, berserk, swarm, firststrike;
      combatant *u;

      damage = atoi((*argv)[1]);
      num_attacks = atoi((*argv)[2]);
      hp = max_hp = atoi((*argv)[3]);
      hit_chance = atoi((*argv)[4]);
      slows = false;
      slowed = false;
      drains = false;
      berserk = false;
      swarm = false;
      firststrike = false;

      if (damagep)
            *damagep = damage;
      if (hit_chancep)
            *hit_chancep = hit_chance/100.0;
      if (slowsp)
            *slowsp = slows;

      if ((*argv)[5] && atoi((*argv)[5]) == 0) {
            char *max = strstr((*argv)[5], "maxhp=");

            if (max) {
                  max_hp = atoi(max + strlen("maxhp="));
                  if (max_hp < hp) {
                        fprintf(stderr, "maxhp must be > hitpoints");
                        exit(1);
                  }
            }
            if (strstr((*argv)[5], "drain")) {
                  if (!max) {
                        fprintf(stderr, "drain needs maxhp set");
                        exit(1);
                  }
                  drains = true;
            }
            if (strstr((*argv)[5], "slows"))
                  slows = true;
            if (strstr((*argv)[5], "slowed"))
                  slowed = true;
            if (strstr((*argv)[5], "berserk"))
                  berserk = true;
            if (strstr((*argv)[5], "firststrike"))
                  firststrike = true;
            if (strstr((*argv)[5], "swarm")) {
                  if (!max) {
                        fprintf(stderr, "swarm needs maxhp set");
                        exit(1);
                  }
                  swarm = true;
            }
            *argv += 5;
      } else {
            *argv += 4;
      }
      u = new combatant(hp, max_hp, slowed, true);
      u->set_weapon(num_attacks, drains, berserk, swarm, firststrike);
      u->set_effectiveness(damage, hit_chance/100.0, slows);
      return u;
}

int main(int argc, char *argv[])
{
      combatant *def, *att[20];
      double hit_chance;
      unsigned damage;
      bool slows;
      unsigned int i;

      if (argc < 3)
            run(argv[1] ? atoi(argv[1]) : 0);

      if (argc < 9) {
            fprintf(stderr,"Usage: %s <damage> <attacks> <hp> <hitprob> [drain,slows,slowed,swarm,firststrike,berserk,maxhp=<num>] <damage> <attacks> <hp> <hitprob> [drain,slows,slowed,berserk,firststrike,swarm,maxhp=<num>] ...",
                        argv[0]);
            exit(1);
      }

      def = parse_unit(&argv, &damage, &hit_chance, &slows);
      for (i = 0; argv[1]; ++i)
            att[i] = parse_unit(&argv);
      att[i] = NULL;

      for (i = 0; att[i]; ++i) {
            // In case defender has swarm, effectiveness changes.
            debug(("Fighting next attacker\n"));
            def->set_effectiveness(damage, hit_chance, slows);
            att[i]->fight(*def);
      }

      def->print("Defender", 0);
      for (i = 0; att[i]; ++i)
            att[i]->print("Attacker", 0);

      delete def;
      for (i = 0; att[i]; ++i)
            delete att[i];

      return 0;
}
#endif // Standalone program

Generated by  Doxygen 1.6.0   Back to index