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