The Battle for Wesnoth  1.19.14+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(utils::contains(dispatched_units, j->second)) {
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  !utils::contains(leaders, i) &&
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(utils::contains(leaders_adj_v, itors.first->second)){
1458  can_reach_leader = true;
1459  break;
1460  }
1461 
1462  // We rate the power balance of a hex based on our power projection
1463  // compared to theirs, multiplying their power projection by their
1464  // chance to hit us on the hex we're planning to flee to.
1465  const map_location& hex = itors.first->second;
1466  const int defense = i->defense_modifier(resources::gameboard->map().get_terrain(hex));
1467  const double our_power = power_projection(hex,get_dstsrc());
1468  const double their_power = power_projection(hex,get_enemy_dstsrc()) * static_cast<double>(defense)/100.0;
1469  const double rating = our_power - their_power;
1470  if(rating > best_rating) {
1471  best_pos = hex;
1472  best_rating = rating;
1473  }
1474 
1475  // Give a bonus for getting to a village.
1476  const int modified_defense = defense - (resources::gameboard->map().is_village(hex) ? 10 : 0);
1477 
1478  if(modified_defense < best_defensive_rating) {
1479  best_defensive_rating = modified_defense;
1480  best_defensive = hex;
1481  }
1482 
1483  ++itors.first;
1484  }
1485 
1486  // If the unit is in range of its leader, it should
1487  // never retreat -- it has to defend the leader instead.
1488  if(can_reach_leader) {
1489  continue;
1490  }
1491 
1492  if(!best_pos.valid()) {
1493  best_pos = best_defensive;
1494  }
1495 
1496  if(best_pos.valid()) {
1497  move_ = check_move_action(i->get_location(), best_pos, true);
1498  if (move_->is_ok()) {
1499  return get_score();
1500  }
1501  }
1502  }
1503  }
1504  }
1505 
1506  return BAD_SCORE;
1507 }
1508 
1510 {
1511  move_->execute();
1512  if (!move_->is_ok()){
1513  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
1514  }
1515 }
1516 
1517 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)
1518 {
1519  const move_map &enemy_dstsrc = get_enemy_dstsrc();
1520 
1521  if(caution <= 0.0) {
1522  return false;
1523  }
1524 
1525  double optimal_terrain = best_defensive_position(un->get_location(), dstsrc,
1526  srcdst, enemy_dstsrc).chance_to_hit/100.0;
1527  const double proposed_terrain =
1528  un->defense_modifier(resources::gameboard->map().get_terrain(loc)) / 100.0;
1529 
1530  // The 'exposure' is the additional % chance to hit
1531  // this unit receives from being on a sub-optimal defensive terrain.
1532  const double exposure = proposed_terrain - optimal_terrain;
1533 
1534  const double our_power = power_projection(loc,dstsrc);
1535  const double their_power = power_projection(loc,enemy_dstsrc);
1536  return caution*their_power*(1.0+exposure) > our_power;
1537 }
1538 
1539 //==============================================================
1540 
1542  : candidate_action(context,cfg)
1543 {
1544 }
1545 
1547 {
1548 }
1549 
1551 {
1552  ERR_AI_TESTING_AI_DEFAULT << get_name() << ": evaluate - not yet implemented";
1553  return BAD_SCORE;
1554 }
1555 
1557 {
1558  ERR_AI_TESTING_AI_DEFAULT << get_name() << ": execute - not yet implemented";
1559 }
1560 
1561 //==============================================================
1562 
1564  :candidate_action(context, cfg)
1565 {
1566 }
1567 
1569 {
1570 }
1571 
1573 {
1574  bool have_active_leader = false;
1575  std::vector<unit_map::unit_iterator> ai_leaders = resources::gameboard->units().find_leaders(get_side());
1576  for (unit_map::unit_iterator &ai_leader : ai_leaders) {
1577  if (!is_passive_leader(ai_leader->id()) || is_passive_keep_sharing_leader(ai_leader->id())) {
1578  have_active_leader = true;
1579  break;
1580  }
1581  }
1582  if(!have_active_leader) {
1583  return BAD_SCORE;
1584  }
1585 
1586  bool allied_leaders_available = false;
1587  for(team &tmp_team : resources::gameboard->teams()) {
1588  if(!current_team().is_enemy(tmp_team.side())){
1589  std::vector<unit_map::unit_iterator> allied_leaders = resources::gameboard->units().find_leaders(get_side());
1590  if (!allied_leaders.empty()){
1591  allied_leaders_available = true;
1592  break;
1593  }
1594  }
1595  }
1596  if(allied_leaders_available){
1597  return get_score();
1598  }
1599  return BAD_SCORE;
1600 }
1601 
1603 {
1604  //get all AI leaders
1605  std::vector<unit_map::unit_iterator> ai_leaders = resources::gameboard->units().find_leaders(get_side());
1606 
1607  //calculate all possible moves (AI + allies)
1608  typedef std::map<map_location, pathfind::paths> path_map;
1609  path_map possible_moves;
1610  move_map friends_srcdst, friends_dstsrc;
1611  calculate_moves(resources::gameboard->units(), possible_moves, friends_srcdst, friends_dstsrc, false, true);
1612 
1613  //check for each ai leader if he should move away from his keep
1614  for (unit_map::unit_iterator &ai_leader : ai_leaders) {
1615  if(!ai_leader.valid() || !is_allowed_unit(*ai_leader) || (is_passive_leader(ai_leader->id()) && !is_passive_keep_sharing_leader(ai_leader->id()))) {
1616  //This can happen if wml killed or moved a leader during a movement events of another leader
1617  continue;
1618  }
1619  //only if leader is on a keep
1620  const map_location &keep = ai_leader->get_location();
1621  if ( !resources::gameboard->map().is_keep(keep) ) {
1622  continue;
1623  }
1624  map_location recruit_loc = pathfind::find_vacant_castle(*ai_leader);
1625  if(!resources::gameboard->map().on_board(recruit_loc)){
1626  continue;
1627  }
1628  bool friend_can_reach_keep = false;
1629 
1630  //for each leader, check if he's allied and can reach our keep
1631  for(path_map::const_iterator i = possible_moves.begin(); i != possible_moves.end(); ++i){
1632  const unit_map::const_iterator itor = resources::gameboard->units().find(i->first);
1633  assert(itor.valid());
1634  team &leader_team = resources::gameboard->get_team(itor->side());
1635  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())){
1636  pathfind::paths::dest_vect::const_iterator tokeep = i->second.destinations.find(keep);
1637  if(tokeep != i->second.destinations.end()){
1638  friend_can_reach_keep = true;
1639  break;
1640  }
1641  }
1642  }
1643  //if there's no allied leader who can reach the keep, check next ai leader
1644  if(friend_can_reach_keep){
1645  //determine the best place the ai leader can move to
1646  map_location best_move;
1647  int defense_modifier = 100;
1648  for(pathfind::paths::dest_vect::const_iterator i = possible_moves[keep].destinations.begin()
1649  ; i != possible_moves[keep].destinations.end()
1650  ; ++i){
1651 
1652  //calculate_moves() above uses max. moves -> need to check movement_left of leader here
1653  if(distance_between(i->curr, keep) <= 3
1654  && static_cast<int>(distance_between(i->curr, keep)) <= ai_leader->movement_left()){
1655 
1656  int tmp_def_mod = ai_leader->defense_modifier(resources::gameboard->map().get_terrain(i->curr));
1657  if(tmp_def_mod < defense_modifier){
1658  defense_modifier = tmp_def_mod;
1659  best_move = i->curr;
1660  }
1661  }
1662  }
1663  //only move if there's a place with a good defense
1664  if(defense_modifier < 100){
1665  move_result_ptr move = check_move_action(keep, best_move, true);
1666  if(move->is_ok()){
1667  move->execute();
1668  if (!move->is_ok()){
1669  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
1670  }else{
1671  ai_leader->set_goto(keep);
1672  }
1673  // This is needed for sides with multiple leaders, in case a WML event does something
1674  // or to account for a leader having previously been moved by this CA execution
1675  possible_moves.clear();
1676  calculate_moves(resources::gameboard->units(), possible_moves, friends_srcdst, friends_dstsrc, false, true);
1677  }else{
1678  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
1679  }
1680  }
1681  }
1682  ai_leader->remove_movement_ai();
1683  }
1684  //ERR_AI_TESTING_AI_DEFAULT << get_name() << ": evaluate - not yet implemented";
1685 }
1686 
1687 //==============================================================
1688 
1689 } //end of namespace testing_ai_default
1690 
1691 } //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: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: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: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: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: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: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:1276
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:1541
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:1556
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:1550
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:1572
leader_shares_keep_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:1563
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:1602
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:1517
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:1509
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:474
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
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
void get_adjacent_tiles(const map_location &a, utils::span< map_location, 6 > res)
Function which, given a location, will place all adjacent locations in res.
Definition: location.cpp:512
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:118
bool contains(const Container &container, const Value &value)
Returns true iff value is found in container.
Definition: general.hpp:87
auto * find(Container &container, const Value &value)
Convenience wrapper for using find on a container without needing to comare to end()
Definition: general.hpp:141
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:46
bool valid() const
Definition: location.hpp:111
static const map_location & null_location()
Definition: location.hpp:103
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