The Battle for Wesnoth  1.15.0-dev
ca.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2009 - 2018 by Yurii Chernyi <terraninfo@terraninfo.net>
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 
15 /**
16  * Default AI (Testing)
17  * @file
18  */
19 
20 #include "ai/default/ca.hpp"
21 #include "ai/actions.hpp"
22 #include "ai/manager.hpp"
23 #include "ai/composite/engine.hpp"
24 #include "ai/composite/rca.hpp"
25 #include "ai/composite/stage.hpp"
26 #include "game_board.hpp"
27 #include "game_classification.hpp"
28 #include "game_data.hpp"
29 #include "log.hpp"
30 #include "map/map.hpp"
31 #include "resources.hpp"
32 #include "team.hpp"
33 #include "units/unit.hpp"
34 #include "pathfind/pathfind.hpp"
35 #include "pathfind/teleport.hpp"
36 
37 #include <numeric>
38 #include <boost/dynamic_bitset.hpp>
39 
40 #include <SDL_timer.h>
41 
42 static lg::log_domain log_ai_testing_ai_default("ai/ca/testing_ai_default");
43 #define DBG_AI_TESTING_AI_DEFAULT LOG_STREAM(debug, log_ai_testing_ai_default)
44 #define LOG_AI_TESTING_AI_DEFAULT LOG_STREAM(info, log_ai_testing_ai_default)
45 #define WRN_AI_TESTING_AI_DEFAULT LOG_STREAM(warn, log_ai_testing_ai_default)
46 #define ERR_AI_TESTING_AI_DEFAULT LOG_STREAM(err, log_ai_testing_ai_default)
47 
48 
49 namespace ai {
50 
51 namespace ai_default_rca {
52 
53 //==============================================================
54 
55 goto_phase::goto_phase( rca_context &context, const config &cfg )
56  : candidate_action(context,cfg)
57  , move_()
58 {
59 }
60 
62 {
63 }
64 
66 {
67  // Execute goto-movements - first collect gotos in a list
68  std::vector<map_location> gotos;
69  unit_map &units_ = resources::gameboard->units();
70  const gamemap &map_ = resources::gameboard->map();
71 
72  for(unit_map::iterator ui = units_.begin(); ui != units_.end(); ++ui) {
73  if (ui->get_goto() == ui->get_location()) {
74  ui->set_goto(map_location());
75  } else if (ui->side() == get_side() && map_.on_board(ui->get_goto())) {
76  gotos.push_back(ui->get_location());
77  }
78  }
79 
80  for(std::vector<map_location>::const_iterator g = gotos.begin(); g != gotos.end(); ++g) {
81  unit_map::const_iterator ui = units_.find(*g);
82  // passive_leader: never moves or attacks
83  if(ui->can_recruit() && get_passive_leader() && !get_passive_leader_shares_keep()){
84  continue;//@todo: only bail out if goto is on keep
85  }
86  // end of passive_leader
87 
89 
91 
93  route = pathfind::a_star_search(ui->get_location(), ui->get_goto(), 10000.0, calc, map_.w(), map_.h(), &allowed_teleports);
94 
95  if (!route.steps.empty()){
96  move_ = check_move_action(ui->get_location(), route.steps.back(), true, true);
97  } else {
98  // there is no direct path (yet)
99  // go to the nearest hex instead.
100  // maybe a door will open later or something
101 
102  int closest_distance = -1;
103  std::pair<map_location,map_location> closest_move;
104  for(move_map::const_iterator i = get_dstsrc().begin(); i != get_dstsrc().end(); ++i) {
105  if(i->second != ui->get_location()) {
106  continue;
107  }
108  int distance = distance_between(i->first,ui->get_goto());
109  if(closest_distance == -1 || distance < closest_distance) {
110  closest_distance = distance;
111  closest_move = *i;
112  }
113  }
114  if(closest_distance != -1) {
115  move_ = check_move_action(ui->get_location(), closest_move.first);
116  } else {
117  continue;
118  }
119  }
120 
121  if (move_->is_ok()) {
122  return get_score();
123  }
124  }
125 
126  return BAD_SCORE;
127 }
128 
130 {
131  if (!move_) {
132  return;
133  }
134 
135  move_->execute();
136  if (!move_->is_ok()){
137  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok" << std::endl;
138  }
139 
140  // In some situations, a theoretically possible path is blocked by allies,
141  // resulting in the unit not moving. In this case, we remove all remaining
142  // movement from the unit in order to prevent blacklisting of the CA.
143  if (!move_->is_gamestate_changed()){
144  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute did not move unit; removing moves instead" << std::endl;
145  stopunit_result_ptr stopunit = check_stopunit_action(move_->get_unit_location(), true, false);
146  stopunit->execute();
147  }
148 }
149 
150 
151 //==============================================================
152 
154  : candidate_action(context,cfg),best_analysis_(),choice_rating_(-1000.0)
155 {
156 }
157 
159 {
160 }
161 
163 {
164  std::vector<std::string> options = get_recruitment_pattern();
165 
166  choice_rating_ = -1000.0;
167  int ticks = SDL_GetTicks();
168 
169  const std::vector<attack_analysis> analysis = get_attacks(); //passive_leader: in aspect_attacks::analyze_targets()
170 
171  int time_taken = SDL_GetTicks() - ticks;
172  LOG_AI_TESTING_AI_DEFAULT << "took " << time_taken << " ticks for " << analysis.size()
173  << " positions. Analyzing...\n";
174 
175  ticks = SDL_GetTicks();
176 
177  const int max_sims = 50000;
178  int num_sims = analysis.empty() ? 0 : max_sims/analysis.size();
179  if(num_sims < 20)
180  num_sims = 20;
181  if(num_sims > 40)
182  num_sims = 40;
183 
184  LOG_AI_TESTING_AI_DEFAULT << "simulations: " << num_sims << "\n";
185 
186  const int max_positions = 30000;
187  const int skip_num = analysis.size()/max_positions;
188 
189  std::vector<attack_analysis>::const_iterator choice_it = analysis.end();
190  for(std::vector<attack_analysis>::const_iterator it = analysis.begin();
191  it != analysis.end(); ++it) {
192 
193  if(skip_num > 0 && ((it - analysis.begin())%skip_num) && it->movements.size() > 1)
194  continue;
195 
196  const double rating = it->rating(get_aggression(),*this);
197  LOG_AI_TESTING_AI_DEFAULT << "attack option rated at " << rating << " ("
198  << (it->uses_leader ? get_leader_aggression() : get_aggression()) << ")\n";
199 
200  if(rating > choice_rating_) {
201  choice_it = it;
202  choice_rating_ = rating;
203  }
204  }
205 
206  time_taken = SDL_GetTicks() - ticks;
207  LOG_AI_TESTING_AI_DEFAULT << "analysis took " << time_taken << " ticks\n";
208 
209 
210  // suokko tested the rating against current_team().caution()
211  // Bad mistake -- the AI became extremely reluctant to attack anything.
212  // Documenting this in case someone has this bright idea again...*don't*...
213  if(choice_rating_ > 0.0) {
214  best_analysis_ = *choice_it;
215  return get_score();
216  } else {
217  return BAD_SCORE;
218  }
219 }
220 
222 {
223  assert(choice_rating_ > 0.0);
224  map_location from = best_analysis_.movements[0].first;
225  map_location to = best_analysis_.movements[0].second;
226  map_location target_loc = best_analysis_.target;
227 
228  if (from!=to) {
229  move_result_ptr move_res = execute_move_action(from,to,false);
230  if (!move_res->is_ok()) {
231  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok, move failed" << std::endl;
232  return;
233  }
234  }
235 
236  attack_result_ptr attack_res = check_attack_action(to, target_loc, -1);
237  if (!attack_res->is_ok()) {
238  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok, attack cancelled" << std::endl;
239  } else {
240  attack_res->execute();
241  if (!attack_res->is_ok()) {
242  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok, attack failed" << std::endl;
243  }
244  }
245 
246 }
247 
248 //==============================================================
249 
251  : candidate_action(context,cfg), auto_remove_(), dst_(), id_(), move_()
252 {
253 }
254 
256 {
257 }
258 
260 {
261 
262  const config &goal = get_leader_goal();
263  //passive leader can reach a goal
264  if (!goal) {
265  LOG_AI_TESTING_AI_DEFAULT << get_name() << "No goal found\n";
266  return BAD_SCORE;
267  }
268 
269  if (goal.empty()) {
270  LOG_AI_TESTING_AI_DEFAULT << get_name() << "Empty goal found\n";
271  return BAD_SCORE;
272  }
273 
274  double max_risk = goal["max_risk"].to_double(1 - get_caution());
275  auto_remove_ = goal["auto_remove"].to_bool();
276 
278  if (!dst_.valid()) {
279  ERR_AI_TESTING_AI_DEFAULT << "Invalid goal: "<<std::endl<<goal;
280  return BAD_SCORE;
281  }
282 
284  if (!leader.valid() || leader->incapacitated()) {
285  WRN_AI_TESTING_AI_DEFAULT << "Leader not found" << std::endl;
286  return BAD_SCORE;
287  }
288 
289  id_ = goal["id"].str();
290  if (leader->get_location() == dst_) {
291  //goal already reached
292  if (auto_remove_ && !id_.empty()) {
293  remove_goal(id_);
294  } else {
295  move_ = check_move_action(leader->get_location(), leader->get_location(), !auto_remove_);//we do full moves if we don't want to remove goal
296  if (move_->is_ok()) {
297  return get_score();
298  } else {
299  return BAD_SCORE;
300  }
301  }
302  }
303 
305  const pathfind::teleport_map allowed_teleports = pathfind::get_teleport_locations(*leader, current_team());
306  pathfind::plain_route route = a_star_search(leader->get_location(), dst_, 1000.0, calc,
307  resources::gameboard->map().w(), resources::gameboard->map().h(), &allowed_teleports);
308  if(route.steps.empty()) {
309  LOG_AI_TESTING_AI_DEFAULT << "route empty";
310  return BAD_SCORE;
311  }
312 
313  const pathfind::paths leader_paths(*leader, false, true, current_team());
314 
315  std::map<map_location,pathfind::paths> possible_moves;
316  possible_moves.emplace(leader->get_location(), leader_paths);
317 
318  map_location loc;
319  for (const map_location &l : route.steps)
320  {
321  if (leader_paths.destinations.contains(l) &&
322  power_projection(l, get_enemy_dstsrc()) < leader->hitpoints() * max_risk)
323  {
324  loc = l;
325  }
326  }
327 
328  if(loc.valid()) {
329  move_ = check_move_action(leader->get_location(), loc, false);
330  if (move_->is_ok()) {
331  return get_score();
332  }
333  }
334  return BAD_SCORE;
335 
336 }
337 
339 {
340  move_->execute();
341  if (!move_->is_ok()){
342  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok" << std::endl;
343  }
344  if (move_->get_unit_location()==dst_) {
345  //goal already reached
346  if (auto_remove_ && !id_.empty()) {
347  remove_goal(id_);
348  }
349  }
350 }
351 
352 void move_leader_to_goals_phase::remove_goal(const std::string &id)
353 {
354  config mod_ai;
355  mod_ai["side"] = get_side();
356  mod_ai["path"] = "aspect[leader_goal].facet["+id+"]";
357  mod_ai["action"] = "delete";
359 }
360 
361 //==============================================================
362 
364  : candidate_action(context,cfg),move_()
365 {
366 
367 }
368 
370 {
371 
372 }
373 
375 {
376  if (get_leader_ignores_keep()) {
377  return BAD_SCORE;
378  }
380  return BAD_SCORE;
381  }
382 
383  // 1. Collect all leaders in a list
384  // 2. Get the suitable_keep for each leader
385  // 3. Choose the leader with the nearest suitable_keep (and which still have moves)
386  // 4. If leader can reach this keep in 1 turn -> set move_ to there
387  // 5. If not -> Calculate the best move_ (use a-star search)
388  // 6. Save move_ for execution
389 
390  // 1.
391  const unit_map &units_ = resources::gameboard->units();
392  const std::vector<unit_map::const_iterator> leaders = units_.find_leaders(get_side());
393  if (leaders.empty()) {
394  return BAD_SCORE;
395  }
396 
397  // 2. + 3.
398  const unit* best_leader = nullptr;
399  map_location best_keep;
400  int shortest_distance = 99999;
401 
402  for (const unit_map::const_iterator& leader : leaders) {
403  if (leader->incapacitated() || leader->movement_left() == 0) {
404  continue;
405  }
406 
407  // Find where the leader can move
408  const ai::moves_map &possible_moves = get_possible_moves();
409  const ai::moves_map::const_iterator& p_it = possible_moves.find(leader->get_location());
410  if (p_it == possible_moves.end()) {
411  return BAD_SCORE;
412  }
413  const pathfind::paths leader_paths = p_it->second;
414 
415  const map_location& keep = suitable_keep(leader->get_location(), leader_paths);
416  if (keep == map_location::null_location() || keep == leader->get_location()) {
417  continue;
418  }
419 
421 
422  const pathfind::teleport_map allowed_teleports = pathfind::get_teleport_locations(*leader, current_team());
423 
424  pathfind::plain_route route;
425  route = pathfind::a_star_search(leader->get_location(), keep, 10000.0, calc, resources::gameboard->map().w(), resources::gameboard->map().h(), &allowed_teleports);
426 
427  if (!route.steps.empty() || route.move_cost < shortest_distance) {
428  best_leader = &(*leader);
429  best_keep = keep;
430  shortest_distance = route.move_cost;
431  }
432  }
433 
434  if (best_leader == nullptr) {
435  return BAD_SCORE;
436  }
437 
438  // 4.
439  const unit* leader = best_leader;
440  const map_location keep = best_keep;
441  const pathfind::paths leader_paths(*leader, false, true, current_team());
443  const pathfind::teleport_map allowed_teleports = pathfind::get_teleport_locations(*leader, current_team());
444 
445  if (leader_paths.destinations.contains(keep) && units_.count(keep) == 0) {
446  move_ = check_move_action(leader->get_location(), keep, false);
447  if (move_->is_ok()) {
448  return get_score();
449  }
450  }
451 
452  // 5.
453  // The leader can't move to his keep, try to move to the closest location
454  // to the keep where there are no enemies in range.
455  // Make a map of the possible locations the leader can move to,
456  // ordered by the distance from the keep.
457  typedef std::multimap<int, map_location> ordered_locations;
458  ordered_locations moves_toward_keep;
459 
460  pathfind::plain_route route;
461  route = pathfind::a_star_search(leader->get_location(), keep, 10000.0, calc, resources::gameboard->map().w(), resources::gameboard->map().h(), &allowed_teleports);
462 
463  // find next hop
465  int next_hop_cost = 0;
466  for (const map_location& step : route.steps) {
467  if (leader_paths.destinations.contains(step)) {
468  next_hop = step;
469  next_hop_cost += leader->movement_cost(resources::gameboard->map().get_terrain(step));
470  } else {
471  break;
472  }
473  }
474  if (next_hop == map_location::null_location()) {
475  return BAD_SCORE;
476  }
477  //define the next hop to have the lowest cost (0)
478  moves_toward_keep.emplace(0, next_hop);
479 
480  for (const pathfind::paths::step &dest : leader_paths.destinations) {
481  if (!units_.find(dest.curr).valid()) {
482  route = pathfind::a_star_search(dest.curr, next_hop, 10000.0, calc,
483  resources::gameboard->map().w(), resources::gameboard->map().h(), &allowed_teleports);
484  if (route.move_cost < next_hop_cost) {
485  moves_toward_keep.emplace(route.move_cost, dest.curr);
486  }
487  }
488  }
489 
490  // Find the first location which we can move to,
491  // without the threat of enemies.
492  for (const ordered_locations::value_type& pair : moves_toward_keep) {
493  const map_location& loc = pair.second;
494  if (get_enemy_dstsrc().count(loc) == 0) {
495  move_ = check_move_action(leader->get_location(), loc, true);
496  if (move_->is_ok()) {
497  return get_score();
498  }
499  }
500  }
501  return BAD_SCORE;
502 }
503 
505 {
506  move_->execute();
507  if (!move_->is_ok()) {
508  LOG_AI_TESTING_AI_DEFAULT << get_name() <<"::execute not ok" << std::endl;
509  }
510 }
511 
512 //==============================================================
513 
515  : candidate_action(context,cfg)
516  , keep_loc_()
517  , leader_loc_()
518  , best_leader_loc_()
519  , debug_(false)
520  , moves_()
521 {
522 }
523 
525 {
526 }
527 
529 {
530  moves_.clear();
533  if (!moves_.empty()) {
534  return get_score();
535  }
536  return BAD_SCORE;
537 }
538 
539 
541 {
542  unit_map &units_ = resources::gameboard->units();
543  unit_map::const_iterator leader = units_.find_leader(get_side());
544  // Move all the units to get villages, however move the leader last,
545  // so that the castle will be cleared if it wants to stop to recruit along the way.
546  std::pair<map_location,map_location> leader_move;
547 
548  for(tmoves::const_iterator i = moves_.begin(); i != moves_.end(); ++i) {
549 
550  if(leader != units_.end() && leader->get_location() == i->second) {
551  leader_move = *i;
552  } else {
553  if (resources::gameboard->find_visible_unit(i->first, current_team()) == units_.end()) {
554  move_result_ptr move_res = execute_move_action(i->second,i->first,true);
555  if (!move_res->is_ok()) {
556  return;
557  }
558 
559  const map_location loc = move_res->get_unit_location();
560  leader = units_.find_leader(get_side());
561  const unit_map::const_iterator new_unit = units_.find(loc);
562 
563  if (new_unit != units_.end() &&
564  power_projection(i->first, get_enemy_dstsrc()) >= new_unit->hitpoints() / 4.0)
565  {
566  LOG_AI_TESTING_AI_DEFAULT << "found support target... " << new_unit->get_location() << '\n';
567  //FIXME: suokko tweaked the constant 1.0 to the formula:
568  //25.0* current_team().caution() * power_projection(loc,enemy_dstsrc) / new_unit->second.hitpoints()
569  //Is this an improvement?
570 
571  ///@todo 1.7 check if this an improvement
572  //add_target(target(new_unit->first,1.0,target::SUPPORT));
573  }
574  }
575  }
576  }
577 
578  if(leader_move.second.valid()) {
579  if((resources::gameboard->find_visible_unit(leader_move.first , current_team()) == units_.end())
580  && resources::gameboard->map().is_village(leader_move.first)) {
581  move_result_ptr move_res = execute_move_action(leader_move.second,leader_move.first,true);
582  if (!move_res->is_ok()) {
583  return;
584  }
585  }
586  }
587 
588  return;
589 }
590 
592  const move_map& dstsrc, const move_map& enemy_dstsrc,
593  unit_map::const_iterator &leader)
594 {
595  DBG_AI_TESTING_AI_DEFAULT << "deciding which villages we want...\n";
596  unit_map &units_ = resources::gameboard->units();
597  const int ticks = SDL_GetTicks();
599  if(leader != units_.end()) {
600  keep_loc_ = nearest_keep(leader->get_location());
601  leader_loc_ = leader->get_location();
602  } else {
605  }
606 
608 
609  // Find our units who can move.
610  treachmap reachmap;
611  for(unit_map::const_iterator u_itor = units_.begin();
612  u_itor != units_.end(); ++u_itor) {
613  if(u_itor->can_recruit() && get_passive_leader()){
614  continue;
615  }
616  if(u_itor->side() == get_side() && u_itor->movement_left()) {
617  reachmap.emplace(u_itor->get_location(), std::vector<map_location>());
618  }
619  }
620 
621 
622  DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " units found who can try to capture a village.\n";
623 
624  find_villages(reachmap, moves_, dstsrc, enemy_dstsrc);
625 
626  treachmap::iterator itor = reachmap.begin();
627  while(itor != reachmap.end()) {
628  if(itor->second.empty()) {
629  itor = remove_unit(reachmap, moves_, itor);
630  } else {
631  ++itor;
632  }
633  }
634 
635  if(!reachmap.empty()) {
636  DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " units left after removing the ones who "
637  "can't reach a village, send the to the dispatcher.\n";
638 
639  dump_reachmap(reachmap);
640 
641  dispatch(reachmap, moves_);
642  } else {
643  DBG_AI_TESTING_AI_DEFAULT << "No more units left after removing the ones who can't reach a village.\n";
644  }
645 
646  LOG_AI_TESTING_AI_DEFAULT << "Village assignment done: " << (SDL_GetTicks() - ticks)
647  << " ms, resulted in " << moves_.size() << " units being dispatched.\n";
648 
649 }
650 
652  treachmap& reachmap,
653  tmoves& moves,
654  const std::multimap<map_location,map_location>& dstsrc,
655  const std::multimap<map_location,map_location>& enemy_dstsrc)
656 
657 {
658  std::map<map_location, double> vulnerability;
659 
660  const bool passive_leader = get_passive_leader();
661 
662  std::size_t min_distance = 100000;
663  const gamemap &map_ = resources::gameboard->map();
664  std::vector<team> &teams_ = resources::gameboard->teams();
665 
666  // When a unit is dispatched we need to make sure we don't
667  // dispatch this unit a second time, so store them here.
668  std::vector<map_location> dispatched_units;
669  for(std::multimap<map_location, map_location>::const_iterator
670  j = dstsrc.begin();
671  j != dstsrc.end(); ++j) {
672 
673  const map_location &current_loc = j->first;
674 
675  if(j->second == leader_loc_) {
676  if(passive_leader) {
677  continue;
678  }
679 
680  const std::size_t distance = distance_between(keep_loc_, current_loc);
681  if(distance < min_distance) {
682  min_distance = distance;
683  best_leader_loc_ = current_loc;
684  }
685  }
686 
687  if(std::find(dispatched_units.begin(), dispatched_units.end(),
688  j->second) != dispatched_units.end()) {
689  continue;
690  }
691 
692  if(map_.is_village(current_loc) == false) {
693  continue;
694  }
695 
696  bool want_village = true, owned = false;
697  for(std::size_t n = 0; n != teams_.size(); ++n) {
698  owned = teams_[n].owns_village(current_loc);
699  if(owned && !current_team().is_enemy(n+1)) {
700  want_village = false;
701  }
702 
703  if(owned) {
704  break;
705  }
706  }
707 
708  if(want_village == false) {
709  continue;
710  }
711 
712  // If it is a neutral village, and we have no leader,
713  // then the village is of no use to us, and we don't want it.
714  if(!owned && leader_loc_ == map_location::null_location()) {
715  continue;
716  }
717 
718  double threat = 0.0;
719  const std::map<map_location,double>::const_iterator vuln = vulnerability.find(current_loc);
720  if(vuln != vulnerability.end()) {
721  threat = vuln->second;
722  } else {
723  threat = power_projection(current_loc,enemy_dstsrc);
724  vulnerability.emplace(current_loc, threat);
725  }
726 
728  if (u == resources::gameboard->units().end() || u->get_state("guardian")) {
729  continue;
730  }
731 
732  const unit &un = *u;
733  //FIXME: suokko turned this 2:1 to 1.5:1.0.
734  //and dropped the second term of the multiplication. Is that better?
735  //const double threat_multipler = (current_loc == leader_loc?2:1) * current_team().caution() * 10;
736  if(un.hitpoints() < (threat*2*un.defense_modifier(map_.get_terrain(current_loc)))/100) {
737  continue;
738  }
739 
740  // If the next and previous destination differs from our current destination,
741  // we're the only one who can reach the village -> dispatch.
742  std::multimap<map_location, map_location>::const_iterator next = j;
743  ++next; // j + 1 fails
744  const bool at_begin = (j == dstsrc.begin());
745  std::multimap<map_location, map_location>::const_iterator prev = j; //FIXME seems not to work
746  if(!at_begin) {
747  --prev;
748  }
749 #if 1
750  if((next == dstsrc.end() || next->first != current_loc)
751  && (at_begin || prev->first != current_loc)) {
752 
753  move_result_ptr move_check_res = check_move_action(j->second,j->first,true);
754  if (move_check_res->is_ok()) {
755  DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << j->second << " to village " << j->first << '\n';
756  moves.emplace_back(j->first, j->second);
757  }
758  reachmap.erase(j->second);
759  dispatched_units.push_back(j->second);
760  continue;
761  }
762 #endif
763  reachmap[j->second].push_back(current_loc);
764  }
765 
766  DBG_AI_TESTING_AI_DEFAULT << moves.size() << " units already dispatched, "
767  << reachmap.size() << " left to evaluate.\n";
768 }
769 
771 {
772  DBG_AI_TESTING_AI_DEFAULT << "Starting simple dispatch.\n";
773 
774  // we now have a list with units with the villages they can reach.
775  // keep trying the following steps as long as one of them changes
776  // the state.
777  // 1. Dispatch units who can reach 1 village (if more units can reach that
778  // village only one can capture it, so use the first in the list.)
779  // 2. Villages which can only be reached by one unit get that unit dispatched
780  // to them.
781  std::size_t village_count = 0;
782  bool dispatched = true;
783  while(dispatched) {
784  dispatched = false;
785 
786  if(dispatch_unit_simple(reachmap, moves)) {
787  dispatched = true;
788  } else {
789  if(reachmap.empty()) {
790  DBG_AI_TESTING_AI_DEFAULT << "dispatch_unit_simple() found a final solution.\n";
791  break;
792  } else {
793  DBG_AI_TESTING_AI_DEFAULT << "dispatch_unit_simple() couldn't dispatch more units.\n";
794  }
795  }
796 
797  if(dispatch_village_simple(reachmap, moves, village_count)) {
798  dispatched = true;
799  } else {
800  if(reachmap.empty()) {
801  DBG_AI_TESTING_AI_DEFAULT << "dispatch_village_simple() found a final solution.\n";
802  break;
803  } else {
804  DBG_AI_TESTING_AI_DEFAULT << "dispatch_village_simple() couldn't dispatch more units.\n";
805  }
806  }
807 
808  if(!reachmap.empty() && dispatched) {
809  DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " unit(s) left restarting simple dispatching.\n";
810 
811  dump_reachmap(reachmap);
812  }
813  }
814 
815  if(reachmap.empty()) {
816  DBG_AI_TESTING_AI_DEFAULT << "No units left after simple dispatcher.\n";
817  return;
818  }
819 
820  DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " units left for complex dispatch with "
821  << village_count << " villages left.\n";
822 
823  dump_reachmap(reachmap);
824 
825  dispatch_complex(reachmap, moves, village_count);
826 }
827 
828 // Returns need further processing
829 // false Nothing has been modified or no units left
831 {
832  bool result = false;
833 
834  treachmap::iterator itor = reachmap.begin();
835  while(itor != reachmap.end()) {
836  if(itor->second.size() == 1) {
837  const map_location village = itor->second[0];
838  result = true;
839 
840  DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << itor->first << " to village " << village << '\n';
841  moves.emplace_back(village, itor->first);
842  reachmap.erase(itor++);
843 
844  if(remove_village(reachmap, moves, village)) {
845  itor = reachmap.begin();
846  }
847 
848  } else {
849  ++itor;
850  }
851  }
852 
853  // Test special cases.
854  if(reachmap.empty()) {
855  // We're done.
856  return false;
857  }
858 
859  if(reachmap.size() == 1) {
860  // One unit left.
861  DBG_AI_TESTING_AI_DEFAULT << "Dispatched _last_ unit at " << reachmap.begin()->first
862  << " to village " << reachmap.begin()->second[0] << '\n';
863 
864  moves.emplace_back(reachmap.begin()->second[0], reachmap.begin()->first);
865 
866  reachmap.clear();
867  // We're done.
868  return false;
869  }
870 
871  return result;
872 }
873 
875  treachmap& reachmap, tmoves& moves, std::size_t& village_count)
876 {
877 
878  bool result = false;
879  bool dispatched = true;
880  while(dispatched) {
881  dispatched = false;
882 
883  // build the reverse map
884  std::map<map_location /*village location*/,
885  std::vector<map_location /* units that can reach it*/>>reversemap;
886 
887  treachmap::const_iterator itor = reachmap.begin();
888  for(;itor != reachmap.end(); ++itor) {
889 
890  for(std::vector<map_location>::const_iterator
891  v_itor = itor->second.begin();
892  v_itor != itor->second.end(); ++v_itor) {
893 
894  reversemap[*v_itor].push_back(itor->first);
895 
896  }
897  }
898 
899  village_count = reversemap.size();
900 
901  itor = reversemap.begin();
902  while(itor != reversemap.end()) {
903  if(itor->second.size() == 1) {
904  // One unit can reach this village.
905  const map_location village = itor->first;
906  dispatched = true;
907  result = true;
908 
909  DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << itor->second[0] << " to village " << itor->first << '\n';
910  moves.emplace_back(itor->first, itor->second[0]);
911 
912  reachmap.erase(itor->second[0]);
913  remove_village(reachmap, moves, village);
914  // Get can go to some trouble to remove the unit from the other villages
915  // instead we abort this loop end do a full rebuild on the map.
916  break;
917  } else {
918  ++itor;
919  }
920  }
921  }
922 
923  return result;
924 }
925 
927  treachmap& reachmap, tmoves& moves, const map_location& village)
928 {
929  bool result = false;
930  treachmap::iterator itor = reachmap.begin();
931  while(itor != reachmap.end()) {
932  itor->second.erase(std::remove(itor->second.begin(), itor->second.end(), village), itor->second.end());
933  if(itor->second.empty()) {
934  result = true;
935  itor = remove_unit(reachmap, moves, itor);
936  } else {
937  ++itor;
938  }
939  }
940  return result;
941 }
942 
944  treachmap& reachmap, tmoves& moves, treachmap::iterator unit)
945 {
946  assert(unit->second.empty());
947 
948  if(unit->first == leader_loc_ && best_leader_loc_ != map_location::null_location()) {
949  DBG_AI_TESTING_AI_DEFAULT << "Dispatch leader at " << leader_loc_ << " closer to the keep at "
950  << best_leader_loc_ << '\n';
951 
952  moves.emplace_back(best_leader_loc_, leader_loc_);
953  }
954 
955  reachmap.erase(unit++);
956  return unit;
957 }
958 
960  treachmap& reachmap, tmoves& moves, const std::size_t village_count)
961 {
962  // ***** ***** Init and dispatch if every unit can reach every village.
963 
964  const std::size_t unit_count = reachmap.size();
965  // The maximum number of villages we can capture with the available units.
966  const std::size_t max_result = unit_count < village_count ? unit_count : village_count;
967 
968  assert(unit_count >= 2 && village_count >= 2);
969 
970  // Every unit can reach every village.
971  if(unit_count == 2 && village_count == 2) {
972  DBG_AI_TESTING_AI_DEFAULT << "Every unit can reach every village for 2 units, dispatch them.\n";
973  full_dispatch(reachmap, moves);
974  return;
975  }
976 
977  std::vector<map_location> units(unit_count);
978  std::vector<std::size_t> villages_per_unit(unit_count);
979  std::vector<map_location> villages;
980  std::vector<std::size_t> units_per_village(village_count);
981 
982  // We want to test the units, the ones who can reach the least
983  // villages first so this is our lookup map.
984  std::multimap<std::size_t /* villages_per_unit value*/,
985  std::size_t /*villages_per_unit index*/> unit_lookup;
986 
987  std::vector</*unit*/boost::dynamic_bitset</*village*/>> matrix(reachmap.size(), boost::dynamic_bitset<>(village_count));
988 
989  treachmap::const_iterator itor = reachmap.begin();
990  for(std::size_t u = 0; u < unit_count; ++u, ++itor) {
991  units[u] = itor->first;
992  villages_per_unit[u] = itor->second.size();
993  unit_lookup.emplace(villages_per_unit[u], u);
994 
995  assert(itor->second.size() >= 2);
996 
997  for(std::size_t v = 0; v < itor->second.size(); ++v) {
998 
999  std::size_t v_index;
1000  // find the index of the v in the villages
1001  std::vector<map_location>::const_iterator v_itor =
1002  std::find(villages.begin(), villages.end(), itor->second[v]);
1003  if(v_itor == villages.end()) {
1004  v_index = villages.size(); // will be the last element after push_back.
1005  villages.push_back(itor->second[v]);
1006  } else {
1007  v_index = v_itor - villages.begin();
1008  }
1009 
1010  units_per_village[v_index]++;
1011 
1012  matrix[u][v_index] = true;
1013  }
1014  }
1015  for(std::vector<std::size_t>::const_iterator upv_it = units_per_village.begin();
1016  upv_it != units_per_village.end(); ++upv_it) {
1017 
1018  assert(*upv_it >=2);
1019  }
1020 
1021  if(debug_) {
1022  // Print header
1023  std::cerr << "Reach matrix:\n\nvillage";
1024  std::size_t u, v;
1025  for(v = 0; v < village_count; ++v) {
1026  std::cerr << '\t' << villages[v];
1027  }
1028  std::cerr << "\ttotal\nunit\n";
1029 
1030  // Print data
1031  for(u = 0; u < unit_count; ++u) {
1032  std::cerr << units[u];
1033 
1034  for(v = 0; v < village_count; ++v) {
1035  std::cerr << '\t' << matrix[u][v];
1036  }
1037  std::cerr << "\t" << villages_per_unit[u] << '\n';
1038  }
1039 
1040  // Print footer
1041  std::cerr << "total";
1042  for(v = 0; v < village_count; ++v) {
1043  std::cerr << '\t' << units_per_village[v];
1044  }
1045  std::cerr << '\n';
1046  }
1047 
1048  // Test the special case, everybody can reach all villages
1049  const bool reach_all = ((village_count == unit_count)
1050  && (std::accumulate(villages_per_unit.begin(), villages_per_unit.end(), std::size_t())
1051  == (village_count * unit_count)));
1052 
1053  if(reach_all) {
1054  DBG_AI_TESTING_AI_DEFAULT << "Every unit can reach every village, dispatch them\n";
1055  full_dispatch(reachmap, moves);
1056  reachmap.clear();
1057  return;
1058  }
1059 
1060  // ***** ***** Find a square
1061  std::multimap<std::size_t /* villages_per_unit value*/, std::size_t /*villages_per_unit index*/>
1062  ::const_iterator src_itor = unit_lookup.begin();
1063 
1064  while(src_itor != unit_lookup.end() && src_itor->first == 2) {
1065 
1066  for(std::multimap<std::size_t, std::size_t>::const_iterator
1067  dst_itor = unit_lookup.begin();
1068  dst_itor != unit_lookup.end(); ++ dst_itor) {
1069 
1070  // avoid comparing us with ourselves.
1071  if(src_itor == dst_itor) {
1072  continue;
1073  }
1074 
1075  boost::dynamic_bitset<> result = matrix[src_itor->second] & matrix[dst_itor->second];
1076  std::size_t matched = result.count();
1077 
1078  // we found a solution, dispatch
1079  if(matched == 2) {
1080  // Collect data
1081  std::size_t first = result.find_first();
1082  std::size_t second = result.find_next(first);
1083 
1084  const map_location village1 = villages[first];
1085  const map_location village2 = villages[second];
1086 
1087  const bool perfect = (src_itor->first == 2 &&
1088  dst_itor->first == 2 &&
1089  units_per_village[first] == 2 &&
1090  units_per_village[second] == 2);
1091 
1092  // Dispatch
1093  DBG_AI_TESTING_AI_DEFAULT << "Found a square.\nDispatched unit at " << units[src_itor->second]
1094  << " to village " << village1 << '\n';
1095  moves.emplace_back(village1, units[src_itor->second]);
1096 
1097  DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << units[dst_itor->second]
1098  << " to village " << village2 << '\n';
1099  moves.emplace_back(village2, units[dst_itor->second]);
1100 
1101  // Remove the units
1102  reachmap.erase(units[src_itor->second]);
1103  reachmap.erase(units[dst_itor->second]);
1104 
1105  // Evaluate and start correct function.
1106  if(perfect) {
1107  // We did a perfect dispatch 2 units who could visit 2 villages.
1108  // This means we didn't change the assertion for this functions
1109  // so call ourselves recursively, and finish afterwards.
1110  DBG_AI_TESTING_AI_DEFAULT << "Perfect dispatch, do complex again.\n";
1111  dispatch_complex(reachmap, moves, village_count - 2);
1112  return;
1113  } else {
1114  // We did a not perfect dispatch but we did modify things
1115  // so restart dispatching.
1116  DBG_AI_TESTING_AI_DEFAULT << "NON Perfect dispatch, do dispatch again.\n";
1117  remove_village(reachmap, moves, village1);
1118  remove_village(reachmap, moves, village2);
1119  dispatch(reachmap, moves);
1120  return;
1121  }
1122  }
1123  }
1124 
1125  ++src_itor;
1126  }
1127 
1128  // ***** ***** Do all permutations.
1129  // Now walk through all possible permutations
1130  // - test whether the suggestion is possible
1131  // - does it result in max_villages
1132  // - dispatch and ready
1133  // - is it's result better as the last best
1134  // - store
1135  std::vector<std::pair<map_location, map_location>> best_result;
1136 
1137  // Bruteforcing all possible permutations can result in a slow game.
1138  // So there needs to be a balance between the best possible result and
1139  // not too slow. From the test (at the end of the file) a good number is
1140  // picked. In general we shouldn't reach this point too often if we do
1141  // there are a lot of villages which are unclaimed and a lot of units
1142  // to claim them.
1143  const std::size_t max_options = 8;
1144  if(unit_count >= max_options && village_count >= max_options) {
1145 
1146  DBG_AI_TESTING_AI_DEFAULT << "Too many units " << unit_count << " and villages "
1147  << village_count<<" found, evaluate only the first "
1148  << max_options << " options;\n";
1149 
1150  std::vector<std::size_t> perm (max_options, 0);
1151  for(std::size_t i =0; i < max_options; ++i) {
1152  perm[i] = i;
1153  }
1154  while(std::next_permutation(perm.begin(), perm.end())) {
1155 
1156  // Get result for current permutation.
1157  std::vector<std::pair<map_location,map_location>> result;
1158  for(std::size_t u = 0; u < max_options; ++u) {
1159  if(matrix[u][perm[u]]) {
1160  result.emplace_back(villages[perm[u]], units[u]);
1161 
1162  }
1163  }
1164  if(result.size() == max_result) {
1165  best_result.swap(result);
1166  break;
1167  }
1168 
1169  if(result.size() > best_result.size()) {
1170  best_result.swap(result);
1171  }
1172  }
1173  // End of loop no optimal found, assign the best
1174  moves.insert(moves.end(), best_result.begin(), best_result.end());
1175 
1176  // Clean up the reachmap for dispatched units.
1177  for(const auto& unit_village_pair : best_result) {
1178  reachmap.erase(unit_village_pair.second);
1179  }
1180 
1181  // Try to dispatch whatever is left
1182  dispatch(reachmap, moves);
1183  return;
1184 
1185  } else if(unit_count <= village_count) {
1186 
1187  DBG_AI_TESTING_AI_DEFAULT << "Unit major\n";
1188 
1189  std::vector<std::size_t> perm (unit_count, 0);
1190  for(std::size_t i =0; i < unit_count; ++i) {
1191  perm[i] = i;
1192  }
1193  while(std::next_permutation(perm.begin(), perm.end())) {
1194  // Get result for current permutation.
1195  std::vector<std::pair<map_location,map_location>> result;
1196  for(std::size_t u = 0; u < unit_count; ++u) {
1197  if(matrix[u][perm[u]]) {
1198  result.emplace_back(villages[perm[u]], units[u]);
1199 
1200  }
1201  }
1202  if(result.size() == max_result) {
1203  moves.insert(moves.end(), result.begin(), result.end());
1204  reachmap.clear();
1205  return;
1206  }
1207 
1208  if(result.size() > best_result.size()) {
1209  best_result.swap(result);
1210  }
1211  }
1212  // End of loop no optimal found, assign the best
1213  moves.insert(moves.end(), best_result.begin(), best_result.end());
1214 
1215  // clean up the reachmap we need to test whether the leader is still there
1216  // and if so remove him manually to get him dispatched.
1217  for(const auto& unit_village_pair : best_result) {
1218  reachmap.erase(unit_village_pair.second);
1219  }
1220  treachmap::iterator unit = reachmap.find(leader_loc_);
1221  if(unit != reachmap.end()) {
1222  unit->second.clear();
1223  remove_unit(reachmap, moves, unit);
1224  }
1225  reachmap.clear();
1226 
1227  } else {
1228 
1229  DBG_AI_TESTING_AI_DEFAULT << "Village major\n";
1230 
1231  std::vector<std::size_t> perm (village_count, 0);
1232  for(std::size_t i =0; i < village_count; ++i) {
1233  perm[i] = i;
1234  }
1235  while(std::next_permutation(perm.begin(), perm.end())) {
1236  // Get result for current permutation.
1237  std::vector<std::pair<map_location,map_location>> result;
1238  for(std::size_t v = 0; v < village_count; ++v) {
1239  if(matrix[perm[v]][v]) {
1240  result.emplace_back(villages[v], units[perm[v]]);
1241 
1242  }
1243  }
1244  if(result.size() == max_result) {
1245  moves.insert(moves.end(), result.begin(), result.end());
1246  reachmap.clear();
1247  return;
1248  }
1249 
1250  if(result.size() > best_result.size()) {
1251  best_result.swap(result);
1252  }
1253  }
1254  // End of loop no optimal found, assigne the best
1255  moves.insert(moves.end(), best_result.begin(), best_result.end());
1256 
1257  // clean up the reachmap we need to test whether the leader is still there
1258  // and if so remove him manually to get him dispatched.
1259  for(const auto& unit_village_pair : best_result) {
1260  reachmap.erase(unit_village_pair.second);
1261  }
1262  treachmap::iterator unit = reachmap.find(leader_loc_);
1263  if(unit != reachmap.end()) {
1264  unit->second.clear();
1265  remove_unit(reachmap, moves, unit);
1266  }
1267  reachmap.clear();
1268  }
1269 }
1270 
1272 {
1273  treachmap::const_iterator itor = reachmap.begin();
1274  for(std::size_t i = 0; i < reachmap.size(); ++i, ++itor) {
1275  DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << itor->first
1276  << " to village " << itor->second[i] << '\n';
1277  moves.emplace_back(itor->second[i], itor->first);
1278  }
1279 }
1280 
1282 {
1283  if(!debug_) {
1284  return;
1285  }
1286 
1287  for(treachmap::const_iterator itor =
1288  reachmap.begin(); itor != reachmap.end(); ++itor) {
1289 
1290  std::cerr << "Reachlist for unit at " << itor->first;
1291 
1292  if(itor->second.empty()) {
1293  std::cerr << "\tNone";
1294  }
1295 
1296  for(std::vector<map_location>::const_iterator
1297  v_itor = itor->second.begin();
1298  v_itor != itor->second.end(); ++v_itor) {
1299 
1300  std::cerr << '\t' << *v_itor;
1301  }
1302  std::cerr << '\n';
1303 
1304  }
1305 }
1306 
1307 //==============================================================
1308 
1310  : candidate_action(context,cfg),move_()
1311 {
1312 }
1313 
1315 {
1316 }
1317 
1319 {
1320  // Find units in need of healing.
1321  unit_map &units_ = resources::gameboard->units();
1322  unit_map::iterator u_it = units_.begin();
1323  for(; u_it != units_.end(); ++u_it) {
1324  unit &u = *u_it;
1325 
1326  if(u.can_recruit() && get_passive_leader()){
1327  continue;
1328  }
1329 
1330  // If the unit is on our side, has lost as many or more than
1331  // 1/2 round worth of healing, and doesn't regenerate itself,
1332  // then try to find a vacant village for it to rest in.
1333  if(u.side() == get_side() &&
1336  !u.get_ability_bool("regenerate"))
1337  {
1338  // Look for the village which is the least vulnerable to enemy attack.
1339  typedef std::multimap<map_location,map_location>::const_iterator Itor;
1340  std::pair<Itor,Itor> it = get_srcdst().equal_range(u_it->get_location());
1341  double best_vulnerability = 100000.0;
1342  // Make leader units more unlikely to move to vulnerable villages
1343  const double leader_penalty = (u.can_recruit()?2.0:1.0);
1344  Itor best_loc = it.second;
1345  while(it.first != it.second) {
1346  const map_location& dst = it.first->second;
1347  if (resources::gameboard->map().gives_healing(dst) && (units_.find(dst) == units_.end() || dst == u_it->get_location())) {
1348  const double vuln = power_projection(dst, get_enemy_dstsrc());
1349  DBG_AI_TESTING_AI_DEFAULT << "found village with vulnerability: " << vuln << "\n";
1350  if(vuln < best_vulnerability) {
1351  best_vulnerability = vuln;
1352  best_loc = it.first;
1353  DBG_AI_TESTING_AI_DEFAULT << "chose village " << dst << '\n';
1354  }
1355  }
1356 
1357  ++it.first;
1358  }
1359 
1360  // If we have found an eligible village,
1361  // and we can move there without expecting to get whacked next turn:
1362  if(best_loc != it.second && best_vulnerability*leader_penalty < u.hitpoints()) {
1363  move_ = check_move_action(best_loc->first,best_loc->second,true);
1364  if (move_->is_ok()) {
1365  return get_score();
1366  }
1367  }
1368  }
1369  }
1370 
1371  return BAD_SCORE;
1372 }
1373 
1375 {
1376  LOG_AI_TESTING_AI_DEFAULT << "moving unit to village for healing...\n";
1377  move_->execute();
1378  if (!move_->is_ok()){
1379  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok" << std::endl;
1380  }
1381 }
1382 
1383 //==============================================================
1384 
1386  : candidate_action(context,cfg), move_()
1387 {
1388 }
1389 
1391 {
1392 }
1393 
1395 {
1396 
1397 
1398  // Get versions of the move map that assume that all units are at full movement
1399  const unit_map& units_ = resources::gameboard->units();
1400 
1401  //unit_map::const_iterator leader = units_.find_leader(get_side());
1402  std::vector<unit_map::const_iterator> leaders = units_.find_leaders(get_side());
1403  std::map<map_location,pathfind::paths> dummy_possible_moves;
1404 
1405  move_map fullmove_srcdst;
1406  move_map fullmove_dstsrc;
1407  calculate_possible_moves(dummy_possible_moves, fullmove_srcdst, fullmove_dstsrc,
1408  false, true, &get_avoid());
1409 
1410  /*adjacent_loc_array_t leader_adj;
1411  if(leader != units_.end()) {
1412  get_adjacent_tiles(leader->get_location(), leader_adj.data());
1413  }*/
1414  //int leader_adj_count = 0;
1415  std::vector<map_location> leaders_adj_v;
1416  for (unit_map::const_iterator leader : leaders) {
1417  adjacent_loc_array_t tmp_leader_adj;
1418  get_adjacent_tiles(leader->get_location(), tmp_leader_adj.data());
1419  for (map_location &loc : tmp_leader_adj) {
1420  bool found = false;
1421  for (map_location &new_loc : leaders_adj_v) {
1422  if(new_loc == loc){
1423  found = true;
1424  break;
1425  }
1426  }
1427  if(!found){
1428  leaders_adj_v.push_back(loc);
1429  }
1430  }
1431  }
1432  //leader_adj_count = leaders_adj_v.size();
1433 
1434 
1435  for(unit_map::const_iterator i = units_.begin(); i != units_.end(); ++i) {
1436  if (i->side() == get_side() &&
1437  i->movement_left() == i->total_movement() &&
1438  //leaders.find(*i) == leaders.end() && //unit_map::const_iterator(i) != leader &&
1439  std::find(leaders.begin(), leaders.end(), i) == leaders.end() &&
1440  !i->incapacitated())
1441  {
1442  // This unit still has movement left, and is a candidate to retreat.
1443  // We see the amount of power of each side on the situation,
1444  // and decide whether it should retreat.
1445  if(should_retreat(i->get_location(), i, fullmove_srcdst, fullmove_dstsrc, get_caution())) {
1446 
1447  bool can_reach_leader = false;
1448 
1449  // Time to retreat. Look for the place where the power balance
1450  // is most in our favor.
1451  // If we can't find anywhere where we like the power balance,
1452  // just try to get to the best defensive hex.
1453  typedef move_map::const_iterator Itor;
1454  std::pair<Itor,Itor> itors = get_srcdst().equal_range(i->get_location());
1455  map_location best_pos, best_defensive(i->get_location());
1456 
1457  double best_rating = -1000.0;
1458  int best_defensive_rating = i->defense_modifier(resources::gameboard->map().get_terrain(i->get_location()))
1459  - (resources::gameboard->map().is_village(i->get_location()) ? 10 : 0);
1460  while(itors.first != itors.second) {
1461 
1462  //if(leader != units_.end() && std::count(leader_adj,
1463  // leader_adj + 6, itors.first->second)) {
1464  if(std::find(leaders_adj_v.begin(), leaders_adj_v.end(), itors.first->second) != leaders_adj_v.end()){
1465 
1466  can_reach_leader = true;
1467  break;
1468  }
1469 
1470  // We rate the power balance of a hex based on our power projection
1471  // compared to theirs, multiplying their power projection by their
1472  // chance to hit us on the hex we're planning to flee to.
1473  const map_location& hex = itors.first->second;
1474  const int defense = i->defense_modifier(resources::gameboard->map().get_terrain(hex));
1475  const double our_power = power_projection(hex,get_dstsrc());
1476  const double their_power = power_projection(hex,get_enemy_dstsrc()) * static_cast<double>(defense)/100.0;
1477  const double rating = our_power - their_power;
1478  if(rating > best_rating) {
1479  best_pos = hex;
1480  best_rating = rating;
1481  }
1482 
1483  // Give a bonus for getting to a village.
1484  const int modified_defense = defense - (resources::gameboard->map().is_village(hex) ? 10 : 0);
1485 
1486  if(modified_defense < best_defensive_rating) {
1487  best_defensive_rating = modified_defense;
1488  best_defensive = hex;
1489  }
1490 
1491  ++itors.first;
1492  }
1493 
1494  // If the unit is in range of its leader, it should
1495  // never retreat -- it has to defend the leader instead.
1496  if(can_reach_leader) {
1497  continue;
1498  }
1499 
1500  if(!best_pos.valid()) {
1501  best_pos = best_defensive;
1502  }
1503 
1504  if(best_pos.valid()) {
1505  move_ = check_move_action(i->get_location(), best_pos, true);
1506  if (move_->is_ok()) {
1507  return get_score();
1508  }
1509  }
1510  }
1511  }
1512  }
1513 
1514  return BAD_SCORE;
1515 }
1516 
1518 {
1519  move_->execute();
1520  if (!move_->is_ok()){
1521  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok" << std::endl;
1522  }
1523 }
1524 
1525 
1526 
1527 bool retreat_phase::should_retreat(const map_location& loc, const unit_map::const_iterator& un, const move_map &srcdst, const move_map &dstsrc, double caution)
1528 {
1529  const move_map &enemy_dstsrc = get_enemy_dstsrc();
1530 
1531  if(caution <= 0.0) {
1532  return false;
1533  }
1534 
1535  double optimal_terrain = best_defensive_position(un->get_location(), dstsrc,
1536  srcdst, enemy_dstsrc).chance_to_hit/100.0;
1537  const double proposed_terrain =
1538  un->defense_modifier(resources::gameboard->map().get_terrain(loc)) / 100.0;
1539 
1540  // The 'exposure' is the additional % chance to hit
1541  // this unit receives from being on a sub-optimal defensive terrain.
1542  const double exposure = proposed_terrain - optimal_terrain;
1543 
1544  const double our_power = power_projection(loc,dstsrc);
1545  const double their_power = power_projection(loc,enemy_dstsrc);
1546  return caution*their_power*(1.0+exposure) > our_power;
1547 }
1548 
1549 
1550 //==============================================================
1551 
1553  : candidate_action(context,cfg)
1554 {
1555 }
1556 
1557 
1559 {
1560 }
1561 
1563 {
1564  ERR_AI_TESTING_AI_DEFAULT << get_name() << ": evaluate - not yet implemented" << std::endl;
1565  return BAD_SCORE;
1566 }
1567 
1568 
1569 
1571 {
1572  ERR_AI_TESTING_AI_DEFAULT << get_name() << ": execute - not yet implemented" << std::endl;
1573 }
1574 
1575 //==============================================================
1576 
1578  :candidate_action(context, cfg)
1579 {
1580 }
1581 
1583 {
1584 }
1585 
1587 {
1589  return BAD_SCORE;
1590  }
1591  bool allied_leaders_available = false;
1592  for(team &tmp_team : resources::gameboard->teams()) {
1593  if(!current_team().is_enemy(tmp_team.side())){
1594  std::vector<unit_map::unit_iterator> allied_leaders = resources::gameboard->units().find_leaders(get_side());
1595  if (!allied_leaders.empty()){
1596  allied_leaders_available = true;
1597  break;
1598  }
1599  }
1600  }
1601  if(allied_leaders_available){
1602  return get_score();
1603  }
1604  return BAD_SCORE;
1605 }
1606 
1608 {
1609  //get all AI leaders
1610  std::vector<unit_map::unit_iterator> ai_leaders = resources::gameboard->units().find_leaders(get_side());
1611 
1612  //calculate all possible moves (AI + allies)
1613  typedef std::map<map_location, pathfind::paths> path_map;
1614  path_map possible_moves;
1615  move_map friends_srcdst, friends_dstsrc;
1616  calculate_moves(resources::gameboard->units(), possible_moves, friends_srcdst, friends_dstsrc, false, true);
1617 
1618  //check for each ai leader if he should move away from his keep
1619  for (unit_map::unit_iterator &ai_leader : ai_leaders) {
1620  if(!ai_leader.valid()) {
1621  //This can happen if wml killed or moved a leader during a movement events of another leader
1622  WRN_AI_TESTING_AI_DEFAULT << "leader_shares_keep_phase: Leader vanished.\n";
1623  continue;
1624  }
1625  //only if leader is on a keep
1626  const map_location &keep = ai_leader->get_location();
1627  if ( !resources::gameboard->map().is_keep(keep) ) {
1628  continue;
1629  }
1630  map_location recruit_loc = pathfind::find_vacant_castle(*ai_leader);
1631  if(!resources::gameboard->map().on_board(recruit_loc)){
1632  continue;
1633  }
1634  bool friend_can_reach_keep = false;
1635 
1636  //for each leader, check if he's allied and can reach our keep
1637  for(path_map::const_iterator i = possible_moves.begin(); i != possible_moves.end(); ++i){
1638  const unit_map::const_iterator itor = resources::gameboard->units().find(i->first);
1639  if(!itor.valid()) {
1640  //This can happen if wml killed or moved a unit during a movement events of another leader
1641  WRN_AI_TESTING_AI_DEFAULT << "leader_shares_keep_phase: Unit vanished.\n";
1642  continue;
1643  }
1644 
1645  team &leader_team = resources::gameboard->get_team(itor->side());
1646  if(itor != resources::gameboard->units().end() && itor->can_recruit() && itor->side() != get_side() && (leader_team.total_income() + leader_team.gold() > leader_team.minimum_recruit_price())){
1647  pathfind::paths::dest_vect::const_iterator tokeep = i->second.destinations.find(keep);
1648  if(tokeep != i->second.destinations.end()){
1649  friend_can_reach_keep = true;
1650  break;
1651  }
1652  }
1653  }
1654  //if there's no allied leader who can reach the keep, check next ai leader
1655  if(friend_can_reach_keep){
1656  //determine the best place the ai leader can move to
1657  map_location best_move;
1658  int defense_modifier = 100;
1659  for(pathfind::paths::dest_vect::const_iterator i = possible_moves[keep].destinations.begin()
1660  ; i != possible_moves[keep].destinations.end()
1661  ; ++i){
1662 
1663  //calculate_moves() above uses max. moves -> need to check movement_left of leader here
1664  if(distance_between(i->curr, keep) <= 3
1665  && static_cast<int>(distance_between(i->curr, keep)) <= ai_leader->movement_left()){
1666 
1667  int tmp_def_mod = ai_leader->defense_modifier(resources::gameboard->map().get_terrain(i->curr));
1668  if(tmp_def_mod < defense_modifier){
1669  defense_modifier = tmp_def_mod;
1670  best_move = i->curr;
1671  }
1672  }
1673  }
1674  //only move if there's a place with a good defense
1675  if(defense_modifier < 100){
1676  move_result_ptr move = check_move_action(keep, best_move, true);
1677  if(move->is_ok()){
1678  move->execute();
1679  if (!move->is_ok()){
1680  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok" << std::endl;
1681  }else{
1682  ai_leader->set_goto(keep);
1683  }
1684  //TODO: maybe we should we fix the entry in possible_moves for this move to avoid getting the 'Unit vanished' warning above.
1685  }else{
1686  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok" << std::endl;
1687  }
1688  }
1689  }
1690  ai_leader->remove_movement_ai();
1691  }
1692  for(unit_map::unit_iterator &leader : ai_leaders) {
1693  leader->remove_movement_ai();
1694  }
1695  //ERR_AI_TESTING_AI_DEFAULT << get_name() << ": evaluate - not yet implemented" << std::endl;
1696 }
1697 
1698 
1699 //==============================================================
1700 
1701 
1702 } //end of namespace testing_ai_default
1703 
1704 } //end of namespace ai
void remove()
Removes a tip.
Definition: tooltip.cpp:188
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:221
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:338
int h() const
Effective map height.
Definition: map.hpp:116
std::vector< unit_iterator > find_leaders(int side)
Definition: map.cpp:357
unit_iterator end()
Definition: map.hpp:415
move_result_ptr move_
Definition: ca.hpp:44
virtual const attacks_vector & get_attacks() const override
Definition: contexts.hpp:646
virtual const std::vector< team > & teams() const override
Definition: game_board.hpp:92
std::vector< std::pair< map_location, map_location > > tmoves
Definition: ca.hpp:133
void get_adjacent_tiles(const map_location &a, map_location *res)
Function which, given a location, will place all adjacent locations in res.
Definition: location.cpp:517
virtual const unit_map & units() const override
Definition: game_board.hpp:114
virtual const map_location & nearest_keep(const map_location &loc) const override
Definition: contexts.hpp:871
This class represents a single unit of a specific type.
Definition: unit.hpp:99
void dispatch(treachmap &reachmap, tmoves &moves)
Dispatches all units to their best location.
Definition: ca.cpp:770
int movement_cost(const t_translation::terrain_code &terrain) const
Get the unit&#39;s movement cost on a particular terrain.
Definition: unit.hpp:1257
map_location find_vacant_castle(const unit &leader)
Wrapper for find_vacant_tile() when looking for a vacant castle tile near a leader.
Definition: pathfind.cpp:119
goto_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:55
static manager & get_singleton()
Definition: manager.hpp:152
int minimum_recruit_price() const
Definition: team.cpp:484
map_location best_leader_loc_
The best possible location for our leader if it can&#39;t reach a village.
Definition: ca.hpp:124
bool get_state(const std::string &state) const
Check if the unit is affected by a status effect.
Definition: unit.cpp:1290
unit_iterator find_leader(int side)
Definition: map.cpp:329
void dump_reachmap(treachmap &reachmap)
Shows which villages every unit can reach (debug function).
Definition: ca.cpp:1281
Managing the AI-Game interaction - AI actions and their results.
int hitpoints() const
The current number of hitpoints this unit has.
Definition: unit.hpp:414
leader_shares_keep_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:1577
map_location keep_loc_
Location of the keep the closest to our leader.
Definition: ca.hpp:118
virtual const move_map & get_srcdst() const override
Definition: contexts.hpp:791
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:162
map_location target
Definition: contexts.hpp:86
virtual const gamemap & map() const override
Definition: game_board.hpp:109
dest_vect destinations
Definition: pathfind.hpp:99
unit_iterator begin()
Definition: map.hpp:405
The unit is poisoned - it loses health each turn.
Definition: unit.hpp:742
Composite AI stages.
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:1318
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:374
AI Support engine - creating specific ai components from config.
const int defense
bool on_board(const map_location &loc) const
Tell if a location is on the map.
Definition: map.cpp:360
-file sdl_utils.hpp
move_leader_to_keep_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:363
retreat_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:1385
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:528
#define ERR_AI_TESTING_AI_DEFAULT
Definition: ca.cpp:46
Default AI (Testing)
bool remove_village(treachmap &reachmap, tmoves &moves, const map_location &village)
Removes a village for all units, returns true if anything is deleted.
Definition: ca.cpp:926
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:1607
game_data * gamedata
Definition: resources.cpp:22
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:1394
t_translation::terrain_code get_terrain(const map_location &loc) const
Looks up terrain at a particular location.
Definition: map.cpp:292
std::multimap< map_location, map_location > move_map
The standard way in which a map of possible moves is recorded.
Definition: game_info.hpp:42
int gold() const
Definition: team.hpp:189
std::map< map_location, pathfind::paths > moves_map
The standard way in which a map of possible movement routes to location is recorded.
Definition: game_info.hpp:45
int defense_modifier(const t_translation::terrain_code &terrain) const
The unit&#39;s defense on a given terrain.
Definition: unit.cpp:1541
const config & options()
Definition: game.cpp:566
This class stores all the data for a single &#39;side&#39; (in game nomenclature).
Definition: team.hpp:44
static lg::log_domain log_ai_testing_ai_default("ai/ca/testing_ai_default")
A small explanation about what&#39;s going on here: Each action has access to two game_info objects First...
Definition: actions.cpp:58
team & get_team(int i)
Definition: game_board.hpp:104
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:259
std::vector< map_location > steps
Definition: pathfind.hpp:134
bool should_retreat(const map_location &loc, const unit_map::const_iterator &un, const move_map &srcdst, const move_map &dstsrc, double caution)
Definition: ca.cpp:1527
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:504
virtual move_result_ptr execute_move_action(const map_location &from, const map_location &to, bool remove_movement=true, bool unreach_is_ok=false) override
Definition: contexts.cpp:97
Structure which holds a single route between one location and another.
Definition: pathfind.hpp:131
virtual stopunit_result_ptr check_stopunit_action(const map_location &unit_location, bool remove_movement=true, bool remove_attacks=false) override
Definition: contexts.cpp:149
virtual move_result_ptr check_move_action(const map_location &from, const map_location &to, bool remove_movement=true, bool unreach_is_ok=false) override
Definition: contexts.cpp:141
void dispatch_complex(treachmap &reachmap, tmoves &moves, const std::size_t village_count)
Dispatches the units to a village after the simple dispatching failed.
Definition: ca.cpp:959
map_location curr
Definition: pathfind.hpp:87
const defensive_position & best_defensive_position(const map_location &unit, const move_map &dstsrc, const move_map &srcdst, const move_map &enemy_dstsrc) const override
Definition: contexts.hpp:598
bool valid() const
Definition: location.hpp:93
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:1562
virtual double get_leader_aggression() const override
Definition: contexts.hpp:716
game_board * gameboard
Definition: resources.cpp:20
virtual bool get_passive_leader() const override
Definition: contexts.hpp:736
Encapsulates the map of the game.
Definition: map.hpp:36
virtual bool get_passive_leader_shares_keep() const override
Definition: contexts.hpp:741
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:1586
virtual const move_map & get_enemy_dstsrc() const override
Definition: contexts.hpp:671
leader_control_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:1552
Managing the AIs lifecycle - headers.
virtual const std::vector< std::string > get_recruitment_pattern() const override
Definition: contexts.hpp:776
std::size_t count(const map_location &loc) const
Definition: map.hpp:400
void modify_active_ai_for_side(ai::side_number side, const config &cfg)
Modifies AI parameters for active AI of the given side.
Definition: manager.cpp:692
std::array< map_location, 6 > adjacent_loc_array_t
Definition: location.hpp:170
logger & debug()
Definition: log.cpp:96
bool dont_log(const log_domain &domain) const
Definition: log.hpp:123
int move_cost
Movement cost for reaching the end of the route.
Definition: pathfind.hpp:136
#define DBG_AI_TESTING_AI_DEFAULT
Definition: ca.cpp:43
bool dispatch_village_simple(treachmap &reachmap, tmoves &moves, std::size_t &village_count)
Definition: ca.cpp:874
Encapsulates the map of the game.
Definition: location.hpp:42
map_location leader_loc_
Locaton of our leader.
Definition: ca.hpp:121
unit_iterator find(std::size_t id)
Definition: map.cpp:311
get_healing_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:1309
bool get_ability_bool(const std::string &tag_name, const map_location &loc) const
Checks whether this unit currently possesses or is affected by a given ability.
Definition: abilities.cpp:140
bool debug_
debug log level for AI enabled?
Definition: ca.hpp:127
int w() const
Effective map width.
Definition: map.hpp:113
virtual const map_location & suitable_keep(const map_location &leader_location, const pathfind::paths &leader_paths) const override
get most suitable keep for leader - nearest free that can be reached in 1 turn, if none - return near...
Definition: contexts.hpp:906
std::size_t i
Definition: function.cpp:933
bool dispatch_unit_simple(treachmap &reachmap, tmoves &moves)
Dispatches all units who can reach one village.
Definition: ca.cpp:830
virtual const team & current_team() const override
Definition: contexts.hpp:521
int max_hitpoints() const
The max number of hitpoints this unit can have.
Definition: unit.hpp:420
std::unique_ptr< attack_result > attack_result_ptr
Definition: game_info.hpp:81
std::unique_ptr< stopunit_result > stopunit_result_ptr
Definition: game_info.hpp:86
double g
Definition: astarsearch.cpp:63
std::vector< std::pair< map_location, map_location > > movements
Definition: contexts.hpp:87
bool can_recruit() const
Whether this unit can recruit other units - ie, are they a leader unit.
Definition: unit.hpp:502
virtual double power_projection(const map_location &loc, const move_map &dstsrc) const override
Function which finds how much &#39;power&#39; a side can attack a certain location with.
Definition: contexts.hpp:751
std::string id_
Definition: rca.hpp:128
#define LOG_AI_TESTING_AI_DEFAULT
Definition: ca.cpp:44
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:540
virtual side_number get_side() const override
Get the side number.
Definition: contexts.hpp:464
std::map< map_location, std::vector< map_location > > treachmap
Definition: ca.hpp:130
virtual bool get_leader_ignores_keep() const override
Definition: contexts.hpp:726
virtual std::string get_name() const
Get the name of the candidate action (useful for debug purposes)
Definition: rca.hpp:86
void get_villages(const move_map &dstsrc, const move_map &enemy_dstsrc, unit_map::const_iterator &leader)
Definition: ca.cpp:591
#define next(ls)
Definition: llex.cpp:32
void full_dispatch(treachmap &reachmap, tmoves &moves)
Dispatches all units to a village, every unit can reach every village.
Definition: ca.cpp:1271
treachmap::iterator remove_unit(treachmap &reachmap, tmoves &moves, treachmap::iterator unit)
Removes a unit which can&#39;t reach any village anymore.
Definition: ca.cpp:943
bool is_village(const map_location &loc) const
Definition: map.cpp:64
virtual const move_map & get_dstsrc() const override
Definition: contexts.hpp:666
std::size_t distance_between(const map_location &a, const map_location &b)
Function which gives the number of hexes between two tiles (i.e.
Definition: location.cpp:600
get_villages_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:514
virtual double get_aggression() const override
Definition: contexts.hpp:616
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:1570
virtual void calculate_possible_moves(std::map< map_location, pathfind::paths > &possible_moves, move_map &srcdst, move_map &dstsrc, bool enemy, bool assume_full_movement=false, const terrain_filter *remove_destinations=nullptr) const override
Definition: contexts.hpp:558
map_location prev
Definition: astarsearch.cpp:64
const map_location & get_location() const
The current map location this unit is at.
Definition: unit.hpp:1174
std::unique_ptr< move_result > move_result_ptr
Definition: game_info.hpp:84
bool contains(const map_location &) const
Definition: pathfind.cpp:520
Standard logging facilities (interface).
const teleport_map get_teleport_locations(const unit &u, const team &viewing_team, bool see_all, bool ignore_units, bool check_vision)
Definition: teleport.cpp:259
Object which contains all the possible locations a unit can move to, with associated best routes to t...
Definition: pathfind.hpp:70
static const map_location & null_location()
Definition: location.hpp:85
static const double BAD_SCORE
Definition: rca.hpp:31
Container associating units to locations.
Definition: map.hpp:99
virtual void calculate_moves(const unit_map &units, std::map< map_location, pathfind::paths > &possible_moves, move_map &srcdst, move_map &dstsrc, bool enemy, bool assume_full_movement=false, const terrain_filter *remove_destinations=nullptr, bool see_all=false) const override
Definition: contexts.hpp:569
int side() const
The side this unit belongs to.
Definition: unit.hpp:265
virtual const terrain_filter & get_avoid() const override
Definition: contexts.hpp:656
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:65
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:1374
virtual attack_result_ptr check_attack_action(const map_location &attacker_loc, const map_location &defender_loc, int attacker_weapon) override
Definition: contexts.cpp:121
plain_route a_star_search(const map_location &src, const map_location &dst, double stop_at, const cost_calculator &calc, const std::size_t width, const std::size_t height, const teleport_map *teleports, bool border)
A config object defines a single node in a WML file, with access to child nodes.
Definition: config.hpp:68
combat_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:153
bool valid() const
Definition: map.hpp:276
virtual double get_caution() const override
Definition: contexts.hpp:661
int total_income() const
Definition: team.hpp:196
static map_location::DIRECTION n
double get_score() const
Get the usual score of the candidate action without re-evaluation.
Definition: rca.cpp:72
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:129
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:1517
#define WRN_AI_TESTING_AI_DEFAULT
Definition: ca.cpp:45
This module contains various pathfinding functions and utilities.
void remove_goal(const std::string &id)
Definition: ca.cpp:352
virtual const moves_map & get_possible_moves() const override
Definition: contexts.hpp:746
std::string::const_iterator iterator
Definition: tokenizer.hpp:24
virtual config get_leader_goal() const override
Definition: contexts.hpp:721
bool empty() const
Definition: config.cpp:873
void find_villages(treachmap &reachmap, tmoves &moves, const std::multimap< map_location, map_location > &dstsrc, const std::multimap< map_location, map_location > &enemy_dstsrc)
Definition: ca.cpp:651
move_leader_to_goals_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:250
candidate action framework
attack_analysis best_analysis_
Definition: ca.hpp:60