On Sun, 2006-03-12 at 11:09 -0600, Bruno Wolff III wrote:
> On Fri, Mar 10, 2006 at 22:13:58 -0500,
> "john w. bjerk" <[EMAIL PROTECTED]> wrote:
> >
> > Reason:
> > Since currently non-obvious how healing/curing will be apportioned in
> > any but the simplest scenarios, and a number of our coders consider
> > that writing an optimal healing distribution algorithm is quite
> > difficult, and hasn't yet been done:
> >
> > Idea:
> > Healers/Curers should do a fixed amount of healing per adjacent unit,
> > no matter how many units are adjacent. Healing/Curing could stack,
> > but the Healing cap of 8HP(+2 resting) per turn per unit would not be
> > changed. The effect on poison would be unchanged.
>
> Are you going to address team healing at the same time? That is also not
> very clean in the way that works currently. But if you go to a no cap on
> healers (other than there being 6 adjacent spaces), it would be very simple
> to heal allied units at the same time.
Hi all,
I've implemented (not committed) an optimal healing algo. Patch below.
Fun problem. It's O(N^2 * P) where N is the number of healers, and P is
the average patients per healer. Healing is divided on single HP
granularity, currently on "most damaged first" priority.
Anyway, I like having a limit on how much healing a single healer can
perform: it just makes sense, and adds something to the game by forcing
user to triage units.
I agree with Bruno that allied healing is a PITA: it would be far
simpler with this new code, and more obvious, if we change healing to
happen at start of *healer's* turn, and have healer prefer own units
over allies.
Cheers,
Rusty.
Index: actions.cpp
===================================================================
--- actions.cpp (revision 10450)
+++ actions.cpp (working copy)
@@ -1366,6 +1366,245 @@
namespace {
+struct patient
+{
+ patient(const unit &u);
+
+ const unit &u;
+
+ // How much have we been healed already?
+ unsigned int healed;
+
+ // How much healing would we like?
+ unsigned int need;
+
+ // Was our poison stopped?
+ bool poison_stopped;
+
+ // Was our poison cured?
+ bool poison_cured;
+
+ // What priority is this patient? Higher gets healed first.
+ unsigned int priority() const;
+
+ // Treat poison: we do this instead of healing.
+ void patient::treat_poison(bool cure);
+
+ // Heal by some hitpoints (<= need).
+ void heal(unsigned int hp);
+};
+
+patient::patient(const unit &un)
+ : u(un), healed(0), poison_stopped(false), poison_cured(false)
+{
+ int needed = u.max_hitpoints() - u.hitpoints();
+
+ // You can do this with wierd WML, I think.
+ if (needed < 0)
+ need = 0;
+ else
+ need = needed;
+}
+
+void patient::heal(unsigned int hp)
+{
+ wassert(hp <= need);
+ healed += hp;
+ need -= hp;
+}
+
+void patient::treat_poison(bool cure)
+{
+ poison_stopped = true;
+ if (cure)
+ poison_cured = true;
+}
+
+// We use this function to rank patients. We could use
+// least hp, rather than most damage, for example.
+unsigned int patient::priority(void) const
+{
+ return need;
+}
+
+struct healer
+{
+ healer(const gamemap::location& loc, const unit &un);
+
+ // Gather patients.
+ void find_patients(std::map<gamemap::location,patient *> &patient_map,
+ const gamemap &map);
+
+ const gamemap::location& loc;
+ const unit &u;
+
+ std::list<patient *> patients;
+
+ unsigned int healing_left;
+
+ // Did we do any healing? (for graphics)
+ bool did_healing;
+
+ // Ratio of how much healing we can do to how much is needed.
+ double capacity_ratio() const;
+
+ // Perform healing on one patient.
+ void do_heal();
+
+ void treat_poison();
+
+ // Consider your patients (they might have changed).
+ // Return false if there's nothing more this healer can do.
+ void assess_patients();
+
+ bool healer::finished() const;
+
+ // Will this unit heal for us?
+ static bool will_heal(const gamemap::location& loc, const unit &un,
+ unsigned int side, const
unit_map& units,
+ const gamemap& map, const
std::vector<team>& teams);
+
+private:
+ bool can_help_unit(const gamemap::location& loc, const unit &un, const
gamemap& map);
+};
+
+bool healer::will_heal(const gamemap::location& loc,
+ const unit &un,
+ unsigned int side,
+ const unit_map& units,
+ const gamemap& map,
+ const std::vector<team>& teams)
+{
+ if (!un.type().heals() || un.incapacitated())
+ return false;
+
+ if (un.side() == side)
+ return true;
+
+ if (teams[un.side()-1].is_enemy(side))
+ return false;
+
+ // Allied healers only heal us if they have no adjacent, healable, own
units.
+ // FIXME: This would be much simplified if they did healing at start of
*healer* turn.
+ gamemap::location adjacent[6];
+ get_adjacent_tiles(loc, adjacent);
+ for (unsigned int n = 0; n != 6U; ++n) {
+ const unit_map::const_iterator i = units.find(adjacent[n]);
+ if (i != units.end()) {
+ if (!map.gives_healing(i->first)
+ && i->second.healable()
+ && i->second.side() == un.side()
+ && (i->second.poisoned() ||
i->second.hitpoints() < i->second.max_hitpoints()))
+ return false;
+ }
+ }
+
+ return true;
+}
+
+healer::healer(const gamemap::location& location, const unit &un)
+ : loc(location), u(un), healing_left(u.type().max_unit_healing()),
did_healing(false)
+{
+}
+
+bool healer::can_help_unit(const gamemap::location& location, const unit &un,
const gamemap& map)
+{
+ // Village will do all the healing: we can add nothing.
+ if (map.gives_healing(location))
+ return false;
+
+ return un.poisoned() || un.hitpoints() < un.max_hitpoints();
+}
+
+void healer::find_patients(std::map<gamemap::location,patient *> &patient_map,
+ const gamemap &map)
+{
+ // Put all units on this side who we can into the map.
+ gamemap::location adjacent[6];
+ get_adjacent_tiles(loc, adjacent);
+
+ for (unsigned int n = 0; n != 6U; ++n) {
+ std::map<gamemap::location,patient *>::iterator p;
+ p = patient_map.find(adjacent[n]);
+ if (p != patient_map.end() && can_help_unit(p->first,
p->second->u, map)) {
+ LOG_NG << "Healer '" << u.name() << "' adding patient
'"
+ <<
patient_map.find(adjacent[n])->second->u.name() << "'\n";
+
patients.push_back(patient_map.find(adjacent[n])->second);
+ }
+ }
+}
+
+double healer::capacity_ratio() const
+{
+ unsigned int demand = 0;
+
+ // What's the most we could offer each unit?
+ for (std::list<patient *>::const_iterator i = patients.begin(); i !=
patients.end(); ++i) {
+ demand += minimum((*i)->need, u.type().heals() - (*i)->healed);
+ }
+
+ return healing_left / (double)demand;
+}
+
+void healer::do_heal()
+{
+ unsigned int prio = 0;
+ std::list<patient*>::iterator p;
+
+ // Find highest priority patient.
+ for (std::list<patient*>::iterator i = patients.begin(); i !=
patients.end(); ++i) {
+ if ((*i)->priority() >= prio) {
+ prio = (*i)->priority();
+ p = i;
+ }
+ }
+ LOG_NG << "Healer '" << u.name() << "' healing patient '"
+ << (*p)->u.name() << "'\n";
+
+ (*p)->heal(1);
+ healing_left--;
+ did_healing = true;
+}
+
+// We do this first up: we can stop/cure poison, but can't heal any more.
+void healer::treat_poison()
+{
+ for (std::list<patient*>::iterator i = patients.begin(); i !=
patients.end(); ) {
+ if ((*i)->u.poisoned()) {
+ LOG_NG << "Healer '" << u.name() << "' treating
poisoned patient '"
+ << (*i)->u.name() << "'\n";
+ (*i)->treat_poison(u.type().heals() >=
game_config::cure_amount);
+ i = patients.erase(i);
+ } else
+ i++;
+ }
+}
+
+// Trivially optimizable: only reconsider healers with patient which actually
changed.
+void healer::assess_patients()
+{
+ // Discard patients which have no need, or whom we can't help.
+ // In practice, there can only be 1 at the moment.
+ std::list<patient*>::iterator i;
+ for (i = patients.begin(); i != patients.end(); ) {
+ // FIXME: make u.type().heals() unsigned.
+ if ((*i)->need == 0
+ || (*i)->healed >= unsigned(u.type().heals())) {
+ LOG_NG << "Healer '" << u.name() << "' done with
patient '"
+ << (*i)->u.name() << "' need:" <<
lexical_cast<std::string>((*i)->need)
+ << " healed:" <<
lexical_cast<std::string>((*i)->healed) << "\n";
+ i = patients.erase(i);
+ } else
+ i++;
+ }
+}
+
+bool healer::finished() const
+{
+ return healing_left == 0 || patients.empty();
+}
+
+#if 0
//function which returns true iff the unit at 'loc' will heal a unit from side
'side'
//on this turn.
//
@@ -1424,9 +1663,11 @@
//there's no-one of higher priority nearby, so the ally will heal
return true;
}
+#endif
}
+#if 0
void calculate_healing(display& disp, const gamestatus& status, const gamemap&
map,
std::map<gamemap::location,unit>& units, int side,
const std::vector<team>& teams, bool
update_display)
@@ -1706,7 +1947,129 @@
}
}
}
+#else
+void calculate_healing(display& disp, const gamestatus& status, const gamemap&
map,
+ std::map<gamemap::location,unit>& units, unsigned int
side,
+ const std::vector<team>& teams, bool
update_display)
+{
+ std::map<gamemap::location,unit>::iterator i;
+ std::map<gamemap::location,patient *> patient_map, village_people;
+ std::map<gamemap::location,patient *>::iterator p;
+ std::list<healer> healers, done_healers;
+ std::list<healer>::iterator h;
+ // All units on this side are potential patients.
+ for (i = units.begin(); i != units.end(); ++i) {
+ if (i->second.side() == side && i->second.healable()) {
+ patient *p = new patient(i->second);
+ patient_map.insert(std::pair<gamemap::location,patient
*>(i->first, p));
+
+ // Track units in villages (ignored by healers)
+ if (map.gives_healing(i->first))
+
village_people.insert(std::pair<gamemap::location,patient *>
+
(i->first, p));
+ }
+
+ // Is this a healer which will help us?
+ if (healer::will_heal(i->first, i->second, side, units, map,
teams))
+ healers.push_back(healer(i->first, i->second));
+ }
+
+ // Now we have complete patient map, have healers find their patients.
+ for (h = healers.begin(); h != healers.end(); h++)
+ h->find_patients(patient_map, map);
+
+ // Deal with the Village People first!
+ for (p = village_people.begin(); p != village_people.end(); p++) {
+ if (p->second->u.poisoned()) {
+ LOG_NG << "Village curing poison '" <<
p->second->u.name() << "'\n";
+ p->second->treat_poison(true);
+ } else {
+ LOG_NG << "Village healing '" << p->second->u.name()
<< "'\n";
+ p->second->heal(game_config::cure_amount);
+ }
+ }
+
+ // Cure/delay poison first.
+ for (h = healers.begin(); h != healers.end(); ) {
+ h->treat_poison();
+
+ // This also weeds out any healers who had no patients to begin
with.
+ if (h->finished()) {
+ done_healers.push_back(*h);
+ h = healers.erase(h);
+ } else
+ h++;
+ }
+
+ while (!healers.empty()) {
+ double best_capacity_ratio = -1;
+ std::list<healer>::iterator best;
+
+ // Find least stressed healer.
+ for (h = healers.begin(); h != healers.end(); h++) {
+ if (h->capacity_ratio() > best_capacity_ratio) {
+ best = h;
+ best_capacity_ratio = h->capacity_ratio();
+ }
+ }
+
+ LOG_NG << "Best healer chosen was '" << best->u.name() << "'\n";
+ best->do_heal();
+
+ // Weed out any healers now spent (could be others, if they
+ // share same patient as this healer).
+ for (h = healers.begin(); h != healers.end(); ) {
+ h->assess_patients();
+ if (h->finished()) {
+ LOG_NG << "Healer '" << h->u.name() << "' is
finished\n";
+ done_healers.push_back(*h);
+ h = healers.erase(h);
+ } else
+ h++;
+ }
+ }
+
+ // Apply bonus to rested units.
+ for (p = patient_map.begin(); p != patient_map.end(); p++) {
+ if (p->second->u.is_resting()) {
+ // FIXME: BUG compatible, only give resting bonus if
poison untreated.
+ if (!p->second->u.poisoned() ||
!p->second->poison_stopped) {
+ p->second->healed +=
minimum<int>(game_config::rest_heal_amount,
+
p->second->need);
+ }
+ }
+ }
+
+ // FIXME: Draw results.
+ // Now, apply the results.
+ for (p = patient_map.begin(); p != patient_map.end(); p++) {
+ unit &u = units.find(p->first)->second;
+
+ if (p->second->u.poisoned()) {
+ if (p->second->poison_cured)
+ u.remove_flag("poisoned");
+ else if (!p->second->poison_stopped) {
+ int damage = minimum<int>(u.hitpoints() - 1,
game_config::cure_amount);
+ // FIXME: BUG compatible: can get resting bonus
when poisoned.
+ u.gets_hit(damage - p->second->healed);
+ }
+ // No healer should have wasted effort on this.
+ // FIXME: rest_heal_amount should be unsigned.
+ wassert(p->second->healed <=
unsigned(game_config::rest_heal_amount));
+ } else {
+ if (p->second->healed)
+ u.heal(p->second->healed);
+ }
+
+ // Reset all units' resting state while we're looping anyway.
+ u.set_resting(true);
+
+ delete(p->second);
+ }
+}
+#endif
+
unit get_advanced_unit(const game_data& info,
std::map<gamemap::location,unit>& units,
const gamemap::location& loc, const std::string& advance_to)
Index: actions.hpp
===================================================================
--- actions.hpp (revision 10450)
+++ actions.hpp (working copy)
@@ -123,7 +123,7 @@
//calculates healing for all units for the given side. Should be called
//at the beginning of a side's turn.
void calculate_healing(display& disp, const gamestatus& status, const gamemap&
map,
- std::map<gamemap::location,unit>& units, int side,
+ std::map<gamemap::location,unit>& units, unsigned int
side,
const std::vector<team>& teams, bool
update_display);
//function which, given the location of a unit that is advancing, and the
--
ccontrol: http://ozlabs.org/~rusty/ccontrol
_______________________________________________
Wesnoth-dev mailing list
[email protected]
https://mail.gna.org/listinfo/wesnoth-dev
