The Battle for Wesnoth  1.19.0-dev
ca.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2009 - 2024
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_data.hpp"
27 #include "log.hpp"
28 #include "map/map.hpp"
29 #include "resources.hpp"
30 #include "team.hpp"
31 #include "units/unit.hpp"
32 #include "pathfind/pathfind.hpp"
33 #include "pathfind/teleport.hpp"
34 
35 #include <numeric>
36 
37 #include <SDL2/SDL_timer.h>
38 
39 static lg::log_domain log_ai_testing_ai_default("ai/ca/testing_ai_default");
40 #define DBG_AI_TESTING_AI_DEFAULT LOG_STREAM(debug, log_ai_testing_ai_default)
41 #define LOG_AI_TESTING_AI_DEFAULT LOG_STREAM(info, log_ai_testing_ai_default)
42 #define WRN_AI_TESTING_AI_DEFAULT LOG_STREAM(warn, log_ai_testing_ai_default)
43 #define ERR_AI_TESTING_AI_DEFAULT LOG_STREAM(err, log_ai_testing_ai_default)
44 
45 namespace ai {
46 
47 namespace ai_default_rca {
48 
49 //==============================================================
50 
51 goto_phase::goto_phase( rca_context &context, const config &cfg )
52  : candidate_action(context,cfg)
53  , move_()
54 {
55 }
56 
58 {
59 }
60 
62 {
63  // Execute goto-movements - first collect gotos in a list
64  std::vector<map_location> gotos;
65  unit_map &units_ = resources::gameboard->units();
66  const gamemap &map_ = resources::gameboard->map();
67 
68  for(unit_map::iterator ui = units_.begin(); ui != units_.end(); ++ui) {
69  if (ui->get_goto() == ui->get_location()) {
70  ui->set_goto(map_location());
71  } else if (ui->side() == get_side() && map_.on_board(ui->get_goto())) {
72  gotos.push_back(ui->get_location());
73  }
74  }
75 
76  for(std::vector<map_location>::const_iterator g = gotos.begin(); g != gotos.end(); ++g) {
77  unit_map::const_iterator ui = units_.find(*g);
78  // passive_leader: never moves or attacks
79  if(ui->can_recruit() && is_passive_leader(ui->id())){
80  continue;
81  }
82  // end of passive_leader
83 
84  if(!is_allowed_unit(*ui)){
85  continue;
86  }
87 
89 
91 
93  route = pathfind::a_star_search(ui->get_location(), ui->get_goto(), 10000.0, calc, map_.w(), map_.h(), &allowed_teleports);
94 
95  if (!route.steps.empty()){
96  move_ = check_move_action(ui->get_location(), route.steps.back(), true, true);
97  } else {
98  // there is no direct path (yet)
99  // go to the nearest hex instead.
100  // maybe a door will open later or something
101 
102  int closest_distance = -1;
103  std::pair<map_location,map_location> closest_move;
104  for(move_map::const_iterator i = get_dstsrc().begin(); i != get_dstsrc().end(); ++i) {
105  if(i->second != ui->get_location()) {
106  continue;
107  }
108  int distance = distance_between(i->first,ui->get_goto());
109  if(closest_distance == -1 || distance < closest_distance) {
110  closest_distance = distance;
111  closest_move = *i;
112  }
113  }
114  if(closest_distance != -1) {
115  move_ = check_move_action(ui->get_location(), closest_move.first);
116  } else {
117  continue;
118  }
119  }
120 
121  if (move_->is_ok()) {
122  return get_score();
123  }
124  }
125 
126  return BAD_SCORE;
127 }
128 
130 {
131  if (!move_) {
132  return;
133  }
134 
135  move_->execute();
136  if (!move_->is_ok()){
137  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
138  }
139 
140  // In some situations, a theoretically possible path is blocked by allies,
141  // resulting in the unit not moving. In this case, we remove all remaining
142  // movement from the unit in order to prevent blacklisting of the CA.
143  if (!move_->is_gamestate_changed()){
144  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute did not move unit; removing moves instead";
145  stopunit_result_ptr stopunit = check_stopunit_action(move_->get_unit_location(), true, false);
146  stopunit->execute();
147  }
148 }
149 
150 //==============================================================
151 
153  : candidate_action(context,cfg),best_analysis_(),choice_rating_(-1000.0)
154 {
155 }
156 
158 {
159 }
160 
162 {
163  const unit_map &units_ = resources::gameboard->units();
164  std::vector<std::string> options = get_recruitment_pattern();
165 
166  choice_rating_ = -1000.0;
167  int ticks = SDL_GetTicks();
168 
169  const std::vector<attack_analysis> analysis = get_attacks(); //passive_leader: in aspect_attacks::analyze_targets()
170 
171  int time_taken = SDL_GetTicks() - ticks;
172  LOG_AI_TESTING_AI_DEFAULT << "took " << time_taken << " ticks for " << analysis.size()
173  << " positions. Analyzing...";
174 
175  ticks = SDL_GetTicks();
176 
177  const int max_sims = 50000;
178  int num_sims = analysis.empty() ? 0 : max_sims/analysis.size();
179  if(num_sims < 20)
180  num_sims = 20;
181  if(num_sims > 40)
182  num_sims = 40;
183 
184  LOG_AI_TESTING_AI_DEFAULT << "simulations: " << num_sims;
185 
186  const int max_positions = 30000;
187  const int skip_num = analysis.size()/max_positions;
188 
189  std::vector<attack_analysis>::const_iterator choice_it = analysis.end();
190  for(std::vector<attack_analysis>::const_iterator it = analysis.begin();
191  it != analysis.end(); ++it) {
192 
193  if(skip_num > 0 && ((it - analysis.begin())%skip_num) && it->movements.size() > 1)
194  continue;
195 
196  // This is somewhat inefficient. It would be faster to exclude these attacks
197  // in get_attacks() above, but the CA filter information is not available inside
198  // the attacks aspect code. Providing the filtering here is only done for consistency
199  // with other CAs though, the recommended method of filtering attacks is via
200  // 'filter_own' of the attacks aspect.
201  bool skip_attack = false;
202  for(std::size_t i = 0; i != it->movements.size(); ++i) {
203  const unit_map::const_iterator u = units_.find(it->movements[i].first);
204  if (!u.valid() || (!is_allowed_unit(*u))) {
205  skip_attack = true;
206  break;
207  }
208  }
209  if (skip_attack)
210  continue;
211 
212  const double rating = it->rating(get_aggression(),*this);
213  LOG_AI_TESTING_AI_DEFAULT << "attack option rated at " << rating << " ("
214  << (it->uses_leader ? get_leader_aggression() : get_aggression()) << ")";
215 
216  if(rating > choice_rating_) {
217  choice_it = it;
218  choice_rating_ = rating;
219  }
220  }
221 
222  time_taken = SDL_GetTicks() - ticks;
223  LOG_AI_TESTING_AI_DEFAULT << "analysis took " << time_taken << " ticks";
224 
225  // suokko tested the rating against current_team().caution()
226  // Bad mistake -- the AI became extremely reluctant to attack anything.
227  // Documenting this in case someone has this bright idea again...*don't*...
228  if(choice_rating_ > 0.0) {
229  best_analysis_ = *choice_it;
230  return get_score();
231  } else {
232  return BAD_SCORE;
233  }
234 }
235 
237 {
238  assert(choice_rating_ > 0.0);
239  map_location from = best_analysis_.movements[0].first;
240  map_location to = best_analysis_.movements[0].second;
241  map_location target_loc = best_analysis_.target;
242 
243  if (from!=to) {
244  move_result_ptr move_res = execute_move_action(from,to,false);
245  if (!move_res->is_ok()) {
246  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok, move failed";
247  return;
248  }
249  }
250 
251  attack_result_ptr attack_res = check_attack_action(to, target_loc, -1);
252  if (!attack_res->is_ok()) {
253  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok, attack cancelled";
254  } else {
255  attack_res->execute();
256  if (!attack_res->is_ok()) {
257  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok, attack failed";
258  }
259  }
260 
261 }
262 
263 //==============================================================
264 
266  : candidate_action(context,cfg), auto_remove_(), dst_(), id_(), move_()
267 {
268 }
269 
271 {
272 }
273 
275 {
276 
278  //passive leader can reach a goal
279 
280  if (goal.empty()) {
281  LOG_AI_TESTING_AI_DEFAULT << get_name() << "Empty or Nonexistent goal found";
282  return BAD_SCORE;
283  }
284 
285  double max_risk = goal["max_risk"].to_double(1 - get_caution());
286  auto_remove_ = goal["auto_remove"].to_bool();
287 
289  if (!dst_.valid()) {
290  ERR_AI_TESTING_AI_DEFAULT << "Invalid goal: "<<std::endl<<goal;
291  return BAD_SCORE;
292  }
293 
294  const unit_map &units_ = resources::gameboard->units();
295  const std::vector<unit_map::const_iterator> leaders = units_.find_leaders(get_side());
296  if (leaders.empty()) {
297  return BAD_SCORE;
298  }
299 
300  const unit* leader = nullptr;
301  for (const unit_map::const_iterator& l_itor : leaders) {
302  if (!l_itor->incapacitated() && l_itor->movement_left() > 0 && is_allowed_unit(*l_itor)) {
303  leader = &(*l_itor);
304  break;
305  }
306  }
307 
308  if (leader == nullptr) {
309  WRN_AI_TESTING_AI_DEFAULT << "Leader not found";
310  return BAD_SCORE;
311  }
312 
313  id_ = goal["id"].str();
314  if (leader->get_location() == dst_) {
315  //goal already reached
316  if (auto_remove_ && !id_.empty()) {
317  remove_goal(id_);
318  } else {
319  move_ = check_move_action(leader->get_location(), leader->get_location(), !auto_remove_);//we do full moves if we don't want to remove goal
320  if (move_->is_ok()) {
321  return get_score();
322  } else {
323  return BAD_SCORE;
324  }
325  }
326  }
327 
329  const pathfind::teleport_map allowed_teleports = pathfind::get_teleport_locations(*leader, current_team());
330  pathfind::plain_route route = a_star_search(leader->get_location(), dst_, 1000.0, calc,
331  resources::gameboard->map().w(), resources::gameboard->map().h(), &allowed_teleports);
332  if(route.steps.empty()) {
333  LOG_AI_TESTING_AI_DEFAULT << "route empty";
334  return BAD_SCORE;
335  }
336 
337  const pathfind::paths leader_paths(*leader, false, true, current_team());
338 
339  std::map<map_location,pathfind::paths> possible_moves;
340  possible_moves.emplace(leader->get_location(), leader_paths);
341 
342  map_location loc;
343  for (const map_location &l : route.steps)
344  {
345  if (leader_paths.destinations.contains(l) &&
346  power_projection(l, get_enemy_dstsrc()) < leader->hitpoints() * max_risk)
347  {
348  loc = l;
349  }
350  }
351 
352  if(loc.valid()) {
353  move_ = check_move_action(leader->get_location(), loc, false);
354  if (move_->is_ok()) {
355  return get_score();
356  }
357  }
358  return BAD_SCORE;
359 
360 }
361 
363 {
364  move_->execute();
365  if (!move_->is_ok()){
366  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
367  }
368  if (move_->get_unit_location()==dst_) {
369  //goal already reached
370  if (auto_remove_ && !id_.empty()) {
371  remove_goal(id_);
372  }
373  }
374 }
375 
376 void move_leader_to_goals_phase::remove_goal(const std::string &id)
377 {
378  config mod_ai;
379  mod_ai["side"] = get_side();
380  mod_ai["path"] = "aspect[leader_goal].facet["+id+"]";
381  mod_ai["action"] = "delete";
383 }
384 
385 //==============================================================
386 
388  : candidate_action(context,cfg),move_()
389 {
390 
391 }
392 
394 {
395 
396 }
397 
399 {
400  if (is_keep_ignoring_leader("")) {
401  return BAD_SCORE;
402  }
403 
404  // 1. Collect all leaders in a list
405  // 2. Get the suitable_keep for each leader
406  // 3. Choose the leader with the nearest suitable_keep (and which still have moves)
407  // 4. If leader can reach this keep in 1 turn -> set move_ to there
408  // 5. If not -> Calculate the best move_ (use a-star search)
409  // 6. Save move_ for execution
410 
411  // 1.
412  const unit_map &units_ = resources::gameboard->units();
413  const std::vector<unit_map::const_iterator> leaders = units_.find_leaders(get_side());
414  if (leaders.empty()) {
415  return BAD_SCORE;
416  }
417 
418  // 2. + 3.
419  const unit* best_leader = nullptr;
420  map_location best_keep;
421  int shortest_distance = 99999;
422 
423  for (const unit_map::const_iterator& leader : leaders) {
424  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()))) {
425  continue;
426  }
427 
428  // Find where the leader can move
429  const ai::moves_map &possible_moves = get_possible_moves();
430  const ai::moves_map::const_iterator& p_it = possible_moves.find(leader->get_location());
431  if (p_it == possible_moves.end()) {
432  return BAD_SCORE;
433  }
434  const pathfind::paths leader_paths = p_it->second;
435 
436  const map_location& keep = suitable_keep(leader->get_location(), leader_paths);
437  if (keep == map_location::null_location() || keep == leader->get_location()) {
438  continue;
439  }
440 
442 
443  const pathfind::teleport_map allowed_teleports = pathfind::get_teleport_locations(*leader, current_team());
444 
445  pathfind::plain_route route;
446  route = pathfind::a_star_search(leader->get_location(), keep, 10000.0, calc, resources::gameboard->map().w(), resources::gameboard->map().h(), &allowed_teleports);
447 
448  if (!route.steps.empty() || route.move_cost < shortest_distance) {
449  best_leader = &(*leader);
450  best_keep = keep;
451  shortest_distance = route.move_cost;
452  }
453  }
454 
455  if (best_leader == nullptr) {
456  return BAD_SCORE;
457  }
458 
459  // 4.
460  const unit* leader = best_leader;
461  const map_location keep = best_keep;
462  const pathfind::paths leader_paths(*leader, false, true, current_team());
464  const pathfind::teleport_map allowed_teleports = pathfind::get_teleport_locations(*leader, current_team());
465 
466  if (leader_paths.destinations.contains(keep) && units_.count(keep) == 0) {
467  move_ = check_move_action(leader->get_location(), keep, false);
468  if (move_->is_ok()) {
469  return get_score();
470  }
471  }
472 
473  // 5.
474  // The leader can't move to his keep, try to move to the closest location
475  // to the keep where there are no enemies in range.
476  // Make a map of the possible locations the leader can move to,
477  // ordered by the distance from the keep.
478  typedef std::multimap<int, map_location> ordered_locations;
479  ordered_locations moves_toward_keep;
480 
481  pathfind::plain_route route;
482  route = pathfind::a_star_search(leader->get_location(), keep, 10000.0, calc, resources::gameboard->map().w(), resources::gameboard->map().h(), &allowed_teleports);
483 
484  // find next hop
486  int next_hop_cost = 0;
487  for (const map_location& step : route.steps) {
488  if (leader_paths.destinations.contains(step) && units_.count(step) == 0) {
489  next_hop = step;
490  next_hop_cost += leader->movement_cost(resources::gameboard->map().get_terrain(step));
491  }
492  }
493  if (next_hop == map_location::null_location()) {
494  return BAD_SCORE;
495  }
496  //define the next hop to have the lowest cost (0)
497  moves_toward_keep.emplace(0, next_hop);
498 
499  for (const pathfind::paths::step &dest : leader_paths.destinations) {
500  if (!units_.find(dest.curr).valid()) {
501  route = pathfind::a_star_search(dest.curr, next_hop, 10000.0, calc,
502  resources::gameboard->map().w(), resources::gameboard->map().h(), &allowed_teleports);
503  if (route.move_cost < next_hop_cost) {
504  moves_toward_keep.emplace(route.move_cost, dest.curr);
505  }
506  }
507  }
508 
509  // Find the first location which we can move to,
510  // without the threat of enemies.
511  for (const ordered_locations::value_type& pair : moves_toward_keep) {
512  const map_location& loc = pair.second;
513  if (get_enemy_dstsrc().count(loc) == 0) {
514  move_ = check_move_action(leader->get_location(), loc, true);
515  if (move_->is_ok()) {
516  return get_score();
517  }
518  }
519  }
520  return BAD_SCORE;
521 }
522 
524 {
525  move_->execute();
526  if (!move_->is_ok()) {
527  LOG_AI_TESTING_AI_DEFAULT << get_name() <<"::execute not ok";
528  }
529 }
530 
531 //==============================================================
532 
534  : candidate_action(context,cfg)
535  , keep_loc_()
536  , leader_loc_()
537  , best_leader_loc_()
538  , debug_(false)
539  , moves_()
540 {
541 }
542 
544 {
545 }
546 
548 {
549  moves_.clear();
552  if (!moves_.empty()) {
553  return get_score();
554  }
555  return BAD_SCORE;
556 }
557 
559 {
560  unit_map &units_ = resources::gameboard->units();
561  unit_map::const_iterator leader = units_.find_leader(get_side());
562  // Move all the units to get villages, however move the leader last,
563  // so that the castle will be cleared if it wants to stop to recruit along the way.
564  std::pair<map_location,map_location> leader_move;
565 
566  for(tmoves::const_iterator i = moves_.begin(); i != moves_.end(); ++i) {
567 
568  if(leader != units_.end() && leader->get_location() == i->second) {
569  leader_move = *i;
570  } else {
571  if (resources::gameboard->find_visible_unit(i->first, current_team()) == units_.end()) {
572  move_result_ptr move_res = execute_move_action(i->second,i->first,true);
573  if (!move_res->is_ok()) {
574  return;
575  }
576 
577  const map_location loc = move_res->get_unit_location();
578  leader = units_.find_leader(get_side());
579  const unit_map::const_iterator new_unit = units_.find(loc);
580 
581  if (new_unit != units_.end() &&
582  power_projection(i->first, get_enemy_dstsrc()) >= new_unit->hitpoints() / 4.0)
583  {
584  LOG_AI_TESTING_AI_DEFAULT << "found support target... " << new_unit->get_location();
585  }
586  }
587  }
588  }
589 
590  if(leader_move.second.valid()) {
591  if((resources::gameboard->find_visible_unit(leader_move.first , current_team()) == units_.end())
592  && resources::gameboard->map().is_village(leader_move.first)) {
593  move_result_ptr move_res = execute_move_action(leader_move.second,leader_move.first,true);
594  if (!move_res->is_ok()) {
595  return;
596  }
597  }
598  }
599 
600  return;
601 }
602 
604  const move_map& dstsrc, const move_map& enemy_dstsrc,
605  unit_map::const_iterator &leader)
606 {
607  DBG_AI_TESTING_AI_DEFAULT << "deciding which villages we want...";
608  unit_map &units_ = resources::gameboard->units();
609  const int ticks = SDL_GetTicks();
611  if(leader != units_.end()) {
612  keep_loc_ = nearest_keep(leader->get_location());
613  leader_loc_ = leader->get_location();
614  } else {
617  }
618 
620 
621  // Find our units who can move.
622  treachmap reachmap;
623  for(unit_map::const_iterator u_itor = units_.begin();
624  u_itor != units_.end(); ++u_itor) {
625  if(u_itor->can_recruit() && is_passive_leader(u_itor->id())){
626  continue;
627  }
628  if(u_itor->side() == get_side() && u_itor->movement_left() && is_allowed_unit(*u_itor)) {
629  reachmap.emplace(u_itor->get_location(), std::vector<map_location>());
630  }
631  }
632 
633  DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " units found who can try to capture a village.";
634 
635  find_villages(reachmap, moves_, dstsrc, enemy_dstsrc);
636 
637  treachmap::iterator itor = reachmap.begin();
638  while(itor != reachmap.end()) {
639  if(itor->second.empty()) {
640  itor = remove_unit(reachmap, moves_, itor);
641  } else {
642  ++itor;
643  }
644  }
645 
646  if(!reachmap.empty()) {
647  DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " units left after removing the ones who "
648  "can't reach a village, send the to the dispatcher.";
649 
650  dump_reachmap(reachmap);
651 
652  dispatch(reachmap, moves_);
653  } else {
654  DBG_AI_TESTING_AI_DEFAULT << "No more units left after removing the ones who can't reach a village.";
655  }
656 
657  LOG_AI_TESTING_AI_DEFAULT << "Village assignment done: " << (SDL_GetTicks() - ticks)
658  << " ms, resulted in " << moves_.size() << " units being dispatched.";
659 
660 }
661 
663  treachmap& reachmap,
664  tmoves& moves,
665  const std::multimap<map_location,map_location>& dstsrc,
666  const std::multimap<map_location,map_location>& enemy_dstsrc)
667 
668 {
669  std::map<map_location, double> vulnerability;
670 
671  std::size_t min_distance = 100000;
672  const gamemap &map_ = resources::gameboard->map();
673  std::vector<team> &teams_ = resources::gameboard->teams();
674 
675  // When a unit is dispatched we need to make sure we don't
676  // dispatch this unit a second time, so store them here.
677  std::vector<map_location> dispatched_units;
678  for(std::multimap<map_location, map_location>::const_iterator
679  j = dstsrc.begin();
680  j != dstsrc.end(); ++j) {
681 
682  const map_location &current_loc = j->first;
683 
684  if(j->second == leader_loc_) {
685  const std::size_t distance = distance_between(keep_loc_, current_loc);
686  if(distance < min_distance) {
687  min_distance = distance;
688  best_leader_loc_ = current_loc;
689  }
690  }
691 
692  if(std::find(dispatched_units.begin(), dispatched_units.end(),
693  j->second) != dispatched_units.end()) {
694  continue;
695  }
696 
697  if(map_.is_village(current_loc) == false) {
698  continue;
699  }
700 
701  bool want_village = true, owned = false;
702  for(std::size_t n = 0; n != teams_.size(); ++n) {
703  owned = teams_[n].owns_village(current_loc);
704  if(owned && !current_team().is_enemy(n+1)) {
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  itor->second.erase(std::remove(itor->second.begin(), itor->second.end(), village), itor->second.end());
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  typedef std::multimap<map_location,map_location>::const_iterator Itor;
1344  std::pair<Itor,Itor> 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  Itor 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  typedef move_map::const_iterator Itor;
1449  std::pair<Itor,Itor> itors = get_srcdst().equal_range(i->get_location());
1450  map_location best_pos, best_defensive(i->get_location());
1451 
1452  double best_rating = -1000.0;
1453  int best_defensive_rating = i->defense_modifier(resources::gameboard->map().get_terrain(i->get_location()))
1454  - (resources::gameboard->map().is_village(i->get_location()) ? 10 : 0);
1455  while(itors.first != itors.second) {
1456 
1457  //if(leader != units_.end() && std::count(leader_adj,
1458  // leader_adj + 6, itors.first->second)) {
1459  if(std::find(leaders_adj_v.begin(), leaders_adj_v.end(), itors.first->second) != leaders_adj_v.end()){
1460 
1461  can_reach_leader = true;
1462  break;
1463  }
1464 
1465  // We rate the power balance of a hex based on our power projection
1466  // compared to theirs, multiplying their power projection by their
1467  // chance to hit us on the hex we're planning to flee to.
1468  const map_location& hex = itors.first->second;
1469  const int defense = i->defense_modifier(resources::gameboard->map().get_terrain(hex));
1470  const double our_power = power_projection(hex,get_dstsrc());
1471  const double their_power = power_projection(hex,get_enemy_dstsrc()) * static_cast<double>(defense)/100.0;
1472  const double rating = our_power - their_power;
1473  if(rating > best_rating) {
1474  best_pos = hex;
1475  best_rating = rating;
1476  }
1477 
1478  // Give a bonus for getting to a village.
1479  const int modified_defense = defense - (resources::gameboard->map().is_village(hex) ? 10 : 0);
1480 
1481  if(modified_defense < best_defensive_rating) {
1482  best_defensive_rating = modified_defense;
1483  best_defensive = hex;
1484  }
1485 
1486  ++itors.first;
1487  }
1488 
1489  // If the unit is in range of its leader, it should
1490  // never retreat -- it has to defend the leader instead.
1491  if(can_reach_leader) {
1492  continue;
1493  }
1494 
1495  if(!best_pos.valid()) {
1496  best_pos = best_defensive;
1497  }
1498 
1499  if(best_pos.valid()) {
1500  move_ = check_move_action(i->get_location(), best_pos, true);
1501  if (move_->is_ok()) {
1502  return get_score();
1503  }
1504  }
1505  }
1506  }
1507  }
1508 
1509  return BAD_SCORE;
1510 }
1511 
1513 {
1514  move_->execute();
1515  if (!move_->is_ok()){
1516  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
1517  }
1518 }
1519 
1520 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)
1521 {
1522  const move_map &enemy_dstsrc = get_enemy_dstsrc();
1523 
1524  if(caution <= 0.0) {
1525  return false;
1526  }
1527 
1528  double optimal_terrain = best_defensive_position(un->get_location(), dstsrc,
1529  srcdst, enemy_dstsrc).chance_to_hit/100.0;
1530  const double proposed_terrain =
1531  un->defense_modifier(resources::gameboard->map().get_terrain(loc)) / 100.0;
1532 
1533  // The 'exposure' is the additional % chance to hit
1534  // this unit receives from being on a sub-optimal defensive terrain.
1535  const double exposure = proposed_terrain - optimal_terrain;
1536 
1537  const double our_power = power_projection(loc,dstsrc);
1538  const double their_power = power_projection(loc,enemy_dstsrc);
1539  return caution*their_power*(1.0+exposure) > our_power;
1540 }
1541 
1542 //==============================================================
1543 
1545  : candidate_action(context,cfg)
1546 {
1547 }
1548 
1550 {
1551 }
1552 
1554 {
1555  ERR_AI_TESTING_AI_DEFAULT << get_name() << ": evaluate - not yet implemented";
1556  return BAD_SCORE;
1557 }
1558 
1560 {
1561  ERR_AI_TESTING_AI_DEFAULT << get_name() << ": execute - not yet implemented";
1562 }
1563 
1564 //==============================================================
1565 
1567  :candidate_action(context, cfg)
1568 {
1569 }
1570 
1572 {
1573 }
1574 
1576 {
1577  bool have_active_leader = false;
1578  std::vector<unit_map::unit_iterator> ai_leaders = resources::gameboard->units().find_leaders(get_side());
1579  for (unit_map::unit_iterator &ai_leader : ai_leaders) {
1580  if (!is_passive_leader(ai_leader->id()) || is_passive_keep_sharing_leader(ai_leader->id())) {
1581  have_active_leader = true;
1582  break;
1583  }
1584  }
1585  if(!have_active_leader) {
1586  return BAD_SCORE;
1587  }
1588 
1589  bool allied_leaders_available = false;
1590  for(team &tmp_team : resources::gameboard->teams()) {
1591  if(!current_team().is_enemy(tmp_team.side())){
1592  std::vector<unit_map::unit_iterator> allied_leaders = resources::gameboard->units().find_leaders(get_side());
1593  if (!allied_leaders.empty()){
1594  allied_leaders_available = true;
1595  break;
1596  }
1597  }
1598  }
1599  if(allied_leaders_available){
1600  return get_score();
1601  }
1602  return BAD_SCORE;
1603 }
1604 
1606 {
1607  //get all AI leaders
1608  std::vector<unit_map::unit_iterator> ai_leaders = resources::gameboard->units().find_leaders(get_side());
1609 
1610  //calculate all possible moves (AI + allies)
1611  typedef std::map<map_location, pathfind::paths> path_map;
1612  path_map possible_moves;
1613  move_map friends_srcdst, friends_dstsrc;
1614  calculate_moves(resources::gameboard->units(), possible_moves, friends_srcdst, friends_dstsrc, false, true);
1615 
1616  //check for each ai leader if he should move away from his keep
1617  for (unit_map::unit_iterator &ai_leader : ai_leaders) {
1618  if(!ai_leader.valid() || !is_allowed_unit(*ai_leader) || (is_passive_leader(ai_leader->id()) && !is_passive_keep_sharing_leader(ai_leader->id()))) {
1619  //This can happen if wml killed or moved a leader during a movement events of another leader
1620  continue;
1621  }
1622  //only if leader is on a keep
1623  const map_location &keep = ai_leader->get_location();
1624  if ( !resources::gameboard->map().is_keep(keep) ) {
1625  continue;
1626  }
1627  map_location recruit_loc = pathfind::find_vacant_castle(*ai_leader);
1628  if(!resources::gameboard->map().on_board(recruit_loc)){
1629  continue;
1630  }
1631  bool friend_can_reach_keep = false;
1632 
1633  //for each leader, check if he's allied and can reach our keep
1634  for(path_map::const_iterator i = possible_moves.begin(); i != possible_moves.end(); ++i){
1635  const unit_map::const_iterator itor = resources::gameboard->units().find(i->first);
1636  assert(itor.valid());
1637  team &leader_team = resources::gameboard->get_team(itor->side());
1638  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())){
1639  pathfind::paths::dest_vect::const_iterator tokeep = i->second.destinations.find(keep);
1640  if(tokeep != i->second.destinations.end()){
1641  friend_can_reach_keep = true;
1642  break;
1643  }
1644  }
1645  }
1646  //if there's no allied leader who can reach the keep, check next ai leader
1647  if(friend_can_reach_keep){
1648  //determine the best place the ai leader can move to
1649  map_location best_move;
1650  int defense_modifier = 100;
1651  for(pathfind::paths::dest_vect::const_iterator i = possible_moves[keep].destinations.begin()
1652  ; i != possible_moves[keep].destinations.end()
1653  ; ++i){
1654 
1655  //calculate_moves() above uses max. moves -> need to check movement_left of leader here
1656  if(distance_between(i->curr, keep) <= 3
1657  && static_cast<int>(distance_between(i->curr, keep)) <= ai_leader->movement_left()){
1658 
1659  int tmp_def_mod = ai_leader->defense_modifier(resources::gameboard->map().get_terrain(i->curr));
1660  if(tmp_def_mod < defense_modifier){
1661  defense_modifier = tmp_def_mod;
1662  best_move = i->curr;
1663  }
1664  }
1665  }
1666  //only move if there's a place with a good defense
1667  if(defense_modifier < 100){
1668  move_result_ptr move = check_move_action(keep, best_move, true);
1669  if(move->is_ok()){
1670  move->execute();
1671  if (!move->is_ok()){
1672  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
1673  }else{
1674  ai_leader->set_goto(keep);
1675  }
1676  // This is needed for sides with multiple leaders, in case a WML event does something
1677  // or to account for a leader having previously been moved by this CA execution
1678  possible_moves.clear();
1679  calculate_moves(resources::gameboard->units(), possible_moves, friends_srcdst, friends_dstsrc, false, true);
1680  }else{
1681  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
1682  }
1683  }
1684  }
1685  ai_leader->remove_movement_ai();
1686  }
1687  //ERR_AI_TESTING_AI_DEFAULT << get_name() << ": evaluate - not yet implemented";
1688 }
1689 
1690 //==============================================================
1691 
1692 } //end of namespace testing_ai_default
1693 
1694 } //end of namespace ai
Managing the AI-Game interaction - AI actions and their results.
Managing the AIs lifecycle - headers TODO: Refactor history handling and internal commands.
double g
Definition: astarsearch.cpp:63
map_location prev
Definition: astarsearch.cpp:64
#define DBG_AI_TESTING_AI_DEFAULT
Definition: ca.cpp:40
#define WRN_AI_TESTING_AI_DEFAULT
Definition: ca.cpp:42
static lg::log_domain log_ai_testing_ai_default("ai/ca/testing_ai_default")
#define ERR_AI_TESTING_AI_DEFAULT
Definition: ca.cpp:43
#define LOG_AI_TESTING_AI_DEFAULT
Definition: ca.cpp:41
Default AI (Testing)
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:236
attack_analysis best_analysis_
Definition: ca.hpp:60
combat_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:152
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:161
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: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:533
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:547
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:662
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:558
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:603
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:61
move_result_ptr move_
Definition: ca.hpp:44
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:129
goto_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:51
leader_control_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:1544
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:1559
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:1553
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:1575
leader_shares_keep_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:1566
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:1605
move_leader_to_goals_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:265
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:362
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:274
void remove_goal(const std::string &id)
Definition: ca.cpp:376
move_leader_to_keep_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:387
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:398
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:523
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:1520
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:1512
std::vector< std::pair< map_location, map_location > > movements
Definition: contexts.hpp:75
map_location target
Definition: contexts.hpp:74
static const double BAD_SCORE
Definition: rca.hpp:33
virtual std::string get_name() const
Get the name of the candidate action (useful for debug purposes)
Definition: rca.hpp:96
bool is_allowed_unit(const unit &u) const
Flag indicating whether unit may be used by this candidate action.
Definition: rca.cpp:88
double get_score() const
Get the usual score of the candidate action without re-evaluation.
Definition: rca.cpp:73
static manager & get_singleton()
Definition: manager.hpp:142
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:665
virtual double get_caution() const override
Definition: contexts.hpp:591
virtual const map_location & suitable_keep(const map_location &leader_location, const pathfind::paths &leader_paths) const override
get most suitable keep for leader - nearest free that can be reached in 1 turn, if none - return near...
Definition: contexts.hpp:856
virtual config get_leader_goal() const override
Definition: contexts.hpp:651
virtual const team & current_team() const override
Definition: contexts.hpp:450
virtual bool is_keep_ignoring_leader(const std::string &id) const override
Definition: contexts.hpp:761
virtual bool is_passive_keep_sharing_leader(const std::string &id) const override
Definition: contexts.hpp:771
virtual const map_location & nearest_keep(const map_location &loc) const override
Definition: contexts.hpp:821
virtual const move_map & get_dstsrc() const override
Definition: contexts.hpp:596
virtual const terrain_filter & get_avoid() const override
Definition: contexts.hpp:586
virtual const attacks_vector & get_attacks() const override
Definition: contexts.hpp:576
virtual void calculate_moves(const unit_map &units, std::map< map_location, pathfind::paths > &possible_moves, move_map &srcdst, move_map &dstsrc, bool enemy, bool assume_full_movement=false, const terrain_filter *remove_destinations=nullptr, bool see_all=false) const override
Definition: contexts.hpp:505
virtual const move_map & get_srcdst() const override
Definition: contexts.hpp:716
const defensive_position & best_defensive_position(const map_location &unit, const move_map &dstsrc, const move_map &srcdst, const move_map &enemy_dstsrc) const override
Definition: contexts.hpp:530
virtual void calculate_possible_moves(std::map< map_location, pathfind::paths > &possible_moves, move_map &srcdst, move_map &dstsrc, bool enemy, bool assume_full_movement=false, const terrain_filter *remove_destinations=nullptr) const override
Definition: contexts.hpp:497
virtual bool is_passive_leader(const std::string &id) const override
Definition: contexts.hpp:766
virtual double power_projection(const map_location &loc, const move_map &dstsrc) const override
Function which finds how much 'power' a side can attack a certain location with.
Definition: contexts.hpp:681
virtual const std::vector< std::string > get_recruitment_pattern() const override
Definition: contexts.hpp:701
virtual move_result_ptr check_move_action(const map_location &from, const map_location &to, bool remove_movement=true, bool unreach_is_ok=false) override
Definition: contexts.hpp:470
virtual double get_aggression() const override
Definition: contexts.hpp:546
virtual stopunit_result_ptr check_stopunit_action(const map_location &unit_location, bool remove_movement=true, bool remove_attacks=false) override
Definition: contexts.hpp:487
virtual double get_leader_aggression() const override
Definition: contexts.hpp:646
virtual const move_map & get_enemy_dstsrc() const override
Definition: contexts.hpp:601
virtual attack_result_ptr check_attack_action(const map_location &attacker_loc, const map_location &defender_loc, int attacker_weapon) override
Definition: contexts.hpp:465
virtual const moves_map & get_possible_moves() const override
Definition: contexts.hpp:676
virtual move_result_ptr execute_move_action(const map_location &from, const map_location &to, bool remove_movement=true, bool unreach_is_ok=false) override
Definition: contexts.hpp:898
virtual side_number get_side() const override
Get the side number.
Definition: contexts.hpp:396
A config object defines a single node in a WML file, with access to child nodes.
Definition: config.hpp:159
virtual const std::vector< team > & teams() const override
Definition: game_board.hpp:79
team & get_team(int i)
Definition: game_board.hpp:91
virtual const unit_map & units() const override
Definition: game_board.hpp:106
virtual const gamemap & map() const override
Definition: game_board.hpp:96
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:65
bool dont_log(const log_domain &domain) const
Definition: log.hpp:211
This class stores all the data for a single 'side' (in game nomenclature).
Definition: team.hpp:74
int gold() const
Definition: team.hpp:175
int total_income() const
Definition: team.hpp:182
int minimum_recruit_price() const
Definition: team.cpp:486
Container associating units to locations.
Definition: map.hpp:98
std::vector< unit_iterator > find_leaders(int side)
Definition: map.cpp:348
unit_iterator end()
Definition: map.hpp:428
std::size_t count(const map_location &loc) const
Definition: map.hpp:413
unit_iterator find(std::size_t id)
Definition: map.cpp:302
unit_iterator begin()
Definition: map.hpp:418
unit_iterator find_leader(int side)
Definition: map.cpp:320
This class represents a single unit of a specific type.
Definition: unit.hpp:133
std::size_t i
Definition: function.cpp:968
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:180
int max_hitpoints() const
The max number of hitpoints this unit can have.
Definition: unit.hpp:505
int hitpoints() const
The current number of hitpoints this unit has.
Definition: unit.hpp:499
bool get_state(const std::string &state) const
Check if the unit is affected by a status effect.
Definition: unit.cpp:1331
bool can_recruit() const
Whether this unit can recruit other units - ie, are they a leader unit.
Definition: unit.hpp:612
const std::string & id() const
Gets this unit's id.
Definition: unit.hpp:380
int side() const
The side this unit belongs to.
Definition: unit.hpp:343
@ STATE_POISONED
The unit is slowed - it moves slower and does less damage.
Definition: unit.hpp:861
int defense_modifier(const t_translation::terrain_code &terrain) const
The unit's defense on a given terrain.
Definition: unit.cpp:1749
const map_location & get_location() const
The current map location this unit is at.
Definition: unit.hpp:1357
int movement_cost(const t_translation::terrain_code &terrain) const
Get the unit's movement cost on a particular terrain.
Definition: unit.hpp:1440
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:474
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:545
Standard logging facilities (interface).
#define STREAMING_LOG
Definition: log.hpp:296
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
void remove()
Removes a tip.
Definition: tooltip.cpp:109
logger & debug()
Definition: log.cpp:320
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:270
const config & options()
Definition: game.cpp:552
game_board * gameboard
Definition: resources.cpp:20
game_data * gamedata
Definition: resources.cpp:22
std::string::const_iterator iterator
Definition: tokenizer.hpp:25
This module contains various pathfinding functions and utilities.
candidate action framework
Encapsulates the map of the game.
Definition: location.hpp:38
bool valid() const
Definition: location.hpp:89
static const map_location & null_location()
Definition: location.hpp:81
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
static map_location::DIRECTION n