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