The Battle for Wesnoth  1.19.5+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.
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 
651 
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 
674  // When a unit is dispatched we need to make sure we don't
675  // dispatch this unit a second time, so store them here.
676  std::vector<map_location> dispatched_units;
677  for(std::multimap<map_location, map_location>::const_iterator
678  j = dstsrc.begin();
679  j != dstsrc.end(); ++j) {
680 
681  const map_location &current_loc = j->first;
682 
683  if(j->second == leader_loc_) {
684  const std::size_t distance = distance_between(keep_loc_, current_loc);
685  if(distance < min_distance) {
686  min_distance = distance;
687  best_leader_loc_ = current_loc;
688  }
689  }
690 
691  if(std::find(dispatched_units.begin(), dispatched_units.end(),
692  j->second) != dispatched_units.end()) {
693  continue;
694  }
695 
696  if(map_.is_village(current_loc) == false) {
697  continue;
698  }
699 
700  bool want_village = true, owned = false;
701  for(const team& t : resources::gameboard->teams()) {
702  owned = t.owns_village(current_loc);
703  if(owned && !current_team().is_enemy(t.side())) {
704  want_village = false;
705  }
706 
707  if(owned) {
708  break;
709  }
710  }
711 
712  if(want_village == false) {
713  continue;
714  }
715 
716  // If it is a neutral village, and we have no leader,
717  // then the village is of no use to us, and we don't want it.
718  if(!owned && leader_loc_ == map_location::null_location()) {
719  continue;
720  }
721 
722  double threat = 0.0;
723  const std::map<map_location,double>::const_iterator vuln = vulnerability.find(current_loc);
724  if(vuln != vulnerability.end()) {
725  threat = vuln->second;
726  } else {
727  threat = power_projection(current_loc,enemy_dstsrc);
728  vulnerability.emplace(current_loc, threat);
729  }
730 
732  if (u == resources::gameboard->units().end() || u->get_state("guardian") || !is_allowed_unit(*u) || (u->can_recruit() && is_passive_leader(u->id()))) {
733  continue;
734  }
735 
736  const unit &un = *u;
737  //FIXME: suokko turned this 2:1 to 1.5:1.0.
738  //and dropped the second term of the multiplication. Is that better?
739  //const double threat_multipler = (current_loc == leader_loc?2:1) * current_team().caution() * 10;
740  if(un.hitpoints() < (threat*2*un.defense_modifier(map_.get_terrain(current_loc)))/100) {
741  continue;
742  }
743 
744  // If the next and previous destination differs from our current destination,
745  // we're the only one who can reach the village -> dispatch.
746  std::multimap<map_location, map_location>::const_iterator next = j;
747  ++next; // j + 1 fails
748  const bool at_begin = (j == dstsrc.begin());
749  std::multimap<map_location, map_location>::const_iterator prev = j; //FIXME seems not to work
750  if(!at_begin) {
751  --prev;
752  }
753 #if 1
754  if((next == dstsrc.end() || next->first != current_loc)
755  && (at_begin || prev->first != current_loc)) {
756 
757  move_result_ptr move_check_res = check_move_action(j->second,j->first,true);
758  if (move_check_res->is_ok()) {
759  DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << j->second << " to village " << j->first;
760  moves.emplace_back(j->first, j->second);
761  }
762  reachmap.erase(j->second);
763  dispatched_units.push_back(j->second);
764  continue;
765  }
766 #endif
767  reachmap[j->second].push_back(current_loc);
768  }
769 
770  DBG_AI_TESTING_AI_DEFAULT << moves.size() << " units already dispatched, "
771  << reachmap.size() << " left to evaluate.";
772 }
773 
775 {
776  DBG_AI_TESTING_AI_DEFAULT << "Starting simple dispatch.";
777 
778  // we now have a list with units with the villages they can reach.
779  // keep trying the following steps as long as one of them changes
780  // the state.
781  // 1. Dispatch units who can reach 1 village (if more units can reach that
782  // village only one can capture it, so use the first in the list.)
783  // 2. Villages which can only be reached by one unit get that unit dispatched
784  // to them.
785  std::size_t village_count = 0;
786  bool dispatched = true;
787  while(dispatched) {
788  dispatched = false;
789 
790  if(dispatch_unit_simple(reachmap, moves)) {
791  dispatched = true;
792  } else {
793  if(reachmap.empty()) {
794  DBG_AI_TESTING_AI_DEFAULT << "dispatch_unit_simple() found a final solution.";
795  break;
796  } else {
797  DBG_AI_TESTING_AI_DEFAULT << "dispatch_unit_simple() couldn't dispatch more units.";
798  }
799  }
800 
801  if(dispatch_village_simple(reachmap, moves, village_count)) {
802  dispatched = true;
803  } else {
804  if(reachmap.empty()) {
805  DBG_AI_TESTING_AI_DEFAULT << "dispatch_village_simple() found a final solution.";
806  break;
807  } else {
808  DBG_AI_TESTING_AI_DEFAULT << "dispatch_village_simple() couldn't dispatch more units.";
809  }
810  }
811 
812  if(!reachmap.empty() && dispatched) {
813  DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " unit(s) left restarting simple dispatching.";
814 
816  }
817  }
818 
819  if(reachmap.empty()) {
820  DBG_AI_TESTING_AI_DEFAULT << "No units left after simple dispatcher.";
821  return;
822  }
823 
824  DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " units left for complex dispatch with "
825  << village_count << " villages left.";
826 
828 
829  dispatch_complex(reachmap, moves, village_count);
830 }
831 
832 // Returns need further processing
833 // false Nothing has been modified or no units left
835 {
836  bool result = false;
837 
838  treachmap::iterator itor = reachmap.begin();
839  while(itor != reachmap.end()) {
840  if(itor->second.size() == 1) {
841  const map_location village = itor->second[0];
842  result = true;
843 
844  DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << itor->first << " to village " << village;
845  moves.emplace_back(village, itor->first);
846  reachmap.erase(itor++);
847 
848  if(remove_village(reachmap, moves, village)) {
849  itor = reachmap.begin();
850  }
851 
852  } else {
853  ++itor;
854  }
855  }
856 
857  // Test special cases.
858  if(reachmap.empty()) {
859  // We're done.
860  return false;
861  }
862 
863  if(reachmap.size() == 1) {
864  // One unit left.
865  DBG_AI_TESTING_AI_DEFAULT << "Dispatched _last_ unit at " << reachmap.begin()->first
866  << " to village " << reachmap.begin()->second[0];
867 
868  moves.emplace_back(reachmap.begin()->second[0], reachmap.begin()->first);
869 
870  reachmap.clear();
871  // We're done.
872  return false;
873  }
874 
875  return result;
876 }
877 
879  treachmap& reachmap, tmoves& moves, std::size_t& village_count)
880 {
881 
882  bool result = false;
883  bool dispatched = true;
884  while(dispatched) {
885  dispatched = false;
886 
887  // build the reverse map
888  std::map<map_location /*village location*/,
889  std::vector<map_location /* units that can reach it*/>>reversemap;
890 
891  treachmap::const_iterator itor = reachmap.begin();
892  for(;itor != reachmap.end(); ++itor) {
893 
894  for(std::vector<map_location>::const_iterator
895  v_itor = itor->second.begin();
896  v_itor != itor->second.end(); ++v_itor) {
897 
898  reversemap[*v_itor].push_back(itor->first);
899 
900  }
901  }
902 
903  village_count = reversemap.size();
904 
905  itor = reversemap.begin();
906  while(itor != reversemap.end()) {
907  if(itor->second.size() == 1) {
908  // One unit can reach this village.
909  const map_location village = itor->first;
910  dispatched = true;
911  result = true;
912 
913  DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << itor->second[0] << " to village " << itor->first;
914  moves.emplace_back(itor->first, itor->second[0]);
915 
916  reachmap.erase(itor->second[0]);
917  remove_village(reachmap, moves, village);
918  // Get can go to some trouble to remove the unit from the other villages
919  // instead we abort this loop end do a full rebuild on the map.
920  break;
921  } else {
922  ++itor;
923  }
924  }
925  }
926 
927  return result;
928 }
929 
931  treachmap& reachmap, tmoves& moves, const map_location& village)
932 {
933  bool result = false;
934  treachmap::iterator itor = reachmap.begin();
935  while(itor != reachmap.end()) {
936  utils::erase(itor->second, village);
937  if(itor->second.empty()) {
938  result = true;
939  itor = remove_unit(reachmap, moves, itor);
940  } else {
941  ++itor;
942  }
943  }
944  return result;
945 }
946 
948  treachmap& reachmap, tmoves& moves, treachmap::iterator unit)
949 {
950  assert(unit->second.empty());
951 
953  DBG_AI_TESTING_AI_DEFAULT << "Dispatch leader at " << leader_loc_ << " closer to the keep at "
954  << best_leader_loc_;
955 
956  moves.emplace_back(best_leader_loc_, leader_loc_);
957  }
958 
959  reachmap.erase(unit++);
960  return unit;
961 }
962 
964  treachmap& reachmap, tmoves& moves, const std::size_t village_count)
965 {
966  // ***** ***** Init and dispatch if every unit can reach every village.
967 
968  const std::size_t unit_count = reachmap.size();
969  // The maximum number of villages we can capture with the available units.
970  const std::size_t max_result = unit_count < village_count ? unit_count : village_count;
971 
972  assert(unit_count >= 2 && village_count >= 2);
973 
974  // Every unit can reach every village.
975  if(unit_count == 2 && village_count == 2) {
976  DBG_AI_TESTING_AI_DEFAULT << "Every unit can reach every village for 2 units, dispatch them.";
977  full_dispatch(reachmap, moves);
978  return;
979  }
980 
981  std::vector<map_location> units(unit_count);
982  std::vector<std::size_t> villages_per_unit(unit_count);
983  std::vector<map_location> villages;
984  std::vector<std::size_t> units_per_village(village_count);
985 
986  // We want to test the units, the ones who can reach the least
987  // villages first so this is our lookup map.
988  std::multimap<std::size_t /* villages_per_unit value*/,
989  std::size_t /*villages_per_unit index*/> unit_lookup;
990 
991  std::vector</*unit*/boost::dynamic_bitset</*village*/>> matrix(reachmap.size(), boost::dynamic_bitset<>(village_count));
992 
993  treachmap::const_iterator itor = reachmap.begin();
994  for(std::size_t u = 0; u < unit_count; ++u, ++itor) {
995  units[u] = itor->first;
996  villages_per_unit[u] = itor->second.size();
997  unit_lookup.emplace(villages_per_unit[u], u);
998 
999  assert(itor->second.size() >= 2);
1000 
1001  for(std::size_t v = 0; v < itor->second.size(); ++v) {
1002 
1003  std::size_t v_index;
1004  // find the index of the v in the villages
1005  std::vector<map_location>::const_iterator v_itor =
1006  std::find(villages.begin(), villages.end(), itor->second[v]);
1007  if(v_itor == villages.end()) {
1008  v_index = villages.size(); // will be the last element after push_back.
1009  villages.push_back(itor->second[v]);
1010  } else {
1011  v_index = v_itor - villages.begin();
1012  }
1013 
1014  units_per_village[v_index]++;
1015 
1016  matrix[u][v_index] = true;
1017  }
1018  }
1019  for(std::vector<std::size_t>::const_iterator upv_it = units_per_village.begin();
1020  upv_it != units_per_village.end(); ++upv_it) {
1021 
1022  assert(*upv_it >=2);
1023  }
1024 
1025  if(debug_) {
1026  // Print header
1027  STREAMING_LOG << "Reach matrix:\n\nvillage";
1028  std::size_t u, v;
1029  for(v = 0; v < village_count; ++v) {
1030  STREAMING_LOG << '\t' << villages[v];
1031  }
1032  STREAMING_LOG << "\ttotal\nunit\n";
1033 
1034  // Print data
1035  for(u = 0; u < unit_count; ++u) {
1036  STREAMING_LOG << units[u];
1037 
1038  for(v = 0; v < village_count; ++v) {
1039  STREAMING_LOG << '\t' << matrix[u][v];
1040  }
1041  STREAMING_LOG << "\t" << villages_per_unit[u] << '\n';
1042  }
1043 
1044  // Print footer
1045  STREAMING_LOG << "total";
1046  for(v = 0; v < village_count; ++v) {
1047  STREAMING_LOG << '\t' << units_per_village[v];
1048  }
1049  STREAMING_LOG << '\n';
1050  }
1051 
1052  // Test the special case, everybody can reach all villages
1053  const bool reach_all = ((village_count == unit_count)
1054  && (std::accumulate(villages_per_unit.begin(), villages_per_unit.end(), std::size_t())
1055  == (village_count * unit_count)));
1056 
1057  if(reach_all) {
1058  DBG_AI_TESTING_AI_DEFAULT << "Every unit can reach every village, dispatch them";
1059  full_dispatch(reachmap, moves);
1060  reachmap.clear();
1061  return;
1062  }
1063 
1064  // ***** ***** Find a square
1065  std::multimap<std::size_t /* villages_per_unit value*/, std::size_t /*villages_per_unit index*/>
1066  ::const_iterator src_itor = unit_lookup.begin();
1067 
1068  while(src_itor != unit_lookup.end() && src_itor->first == 2) {
1069 
1070  for(std::multimap<std::size_t, std::size_t>::const_iterator
1071  dst_itor = unit_lookup.begin();
1072  dst_itor != unit_lookup.end(); ++ dst_itor) {
1073 
1074  // avoid comparing us with ourselves.
1075  if(src_itor == dst_itor) {
1076  continue;
1077  }
1078 
1079  boost::dynamic_bitset<> result = matrix[src_itor->second] & matrix[dst_itor->second];
1080  std::size_t matched = result.count();
1081 
1082  // we found a solution, dispatch
1083  if(matched == 2) {
1084  // Collect data
1085  std::size_t first = result.find_first();
1086  std::size_t second = result.find_next(first);
1087 
1088  const map_location village1 = villages[first];
1089  const map_location village2 = villages[second];
1090 
1091  const bool perfect = (src_itor->first == 2 &&
1092  dst_itor->first == 2 &&
1093  units_per_village[first] == 2 &&
1094  units_per_village[second] == 2);
1095 
1096  // Dispatch
1097  DBG_AI_TESTING_AI_DEFAULT << "Found a square.\nDispatched unit at " << units[src_itor->second]
1098  << " to village " << village1;
1099  moves.emplace_back(village1, units[src_itor->second]);
1100 
1101  DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << units[dst_itor->second]
1102  << " to village " << village2;
1103  moves.emplace_back(village2, units[dst_itor->second]);
1104 
1105  // Remove the units
1106  reachmap.erase(units[src_itor->second]);
1107  reachmap.erase(units[dst_itor->second]);
1108 
1109  // Evaluate and start correct function.
1110  if(perfect) {
1111  // We did a perfect dispatch 2 units who could visit 2 villages.
1112  // This means we didn't change the assertion for this functions
1113  // so call ourselves recursively, and finish afterwards.
1114  DBG_AI_TESTING_AI_DEFAULT << "Perfect dispatch, do complex again.";
1115  dispatch_complex(reachmap, moves, village_count - 2);
1116  return;
1117  } else {
1118  // We did a not perfect dispatch but we did modify things
1119  // so restart dispatching.
1120  DBG_AI_TESTING_AI_DEFAULT << "NON Perfect dispatch, do dispatch again.";
1121  remove_village(reachmap, moves, village1);
1122  remove_village(reachmap, moves, village2);
1123  dispatch(reachmap, moves);
1124  return;
1125  }
1126  }
1127  }
1128 
1129  ++src_itor;
1130  }
1131 
1132  // ***** ***** Do all permutations.
1133  // Now walk through all possible permutations
1134  // - test whether the suggestion is possible
1135  // - does it result in max_villages
1136  // - dispatch and ready
1137  // - is it's result better as the last best
1138  // - store
1139  std::vector<std::pair<map_location, map_location>> best_result;
1140 
1141  // Bruteforcing all possible permutations can result in a slow game.
1142  // So there needs to be a balance between the best possible result and
1143  // not too slow. From the test (at the end of the file) a good number is
1144  // picked. In general we shouldn't reach this point too often if we do
1145  // there are a lot of villages which are unclaimed and a lot of units
1146  // to claim them.
1147  const std::size_t max_options = 8;
1148  if(unit_count >= max_options && village_count >= max_options) {
1149 
1150  DBG_AI_TESTING_AI_DEFAULT << "Too many units " << unit_count << " and villages "
1151  << village_count<<" found, evaluate only the first "
1152  << max_options << " options;";
1153 
1154  std::vector<std::size_t> perm (max_options, 0);
1155  for(std::size_t i =0; i < max_options; ++i) {
1156  perm[i] = i;
1157  }
1158  while(std::next_permutation(perm.begin(), perm.end())) {
1159 
1160  // Get result for current permutation.
1161  std::vector<std::pair<map_location,map_location>> result;
1162  for(std::size_t u = 0; u < max_options; ++u) {
1163  if(matrix[u][perm[u]]) {
1164  result.emplace_back(villages[perm[u]], units[u]);
1165 
1166  }
1167  }
1168  if(result.size() == max_result) {
1169  best_result.swap(result);
1170  break;
1171  }
1172 
1173  if(result.size() > best_result.size()) {
1174  best_result.swap(result);
1175  }
1176  }
1177  // End of loop no optimal found, assign the best
1178  moves.insert(moves.end(), best_result.begin(), best_result.end());
1179 
1180  // Clean up the reachmap for dispatched units.
1181  for(const auto& unit_village_pair : best_result) {
1182  reachmap.erase(unit_village_pair.second);
1183  }
1184 
1185  // Try to dispatch whatever is left
1186  dispatch(reachmap, moves);
1187  return;
1188 
1189  } else if(unit_count <= village_count) {
1190 
1191  DBG_AI_TESTING_AI_DEFAULT << "Unit major";
1192 
1193  std::vector<std::size_t> perm (unit_count, 0);
1194  for(std::size_t i =0; i < unit_count; ++i) {
1195  perm[i] = i;
1196  }
1197  while(std::next_permutation(perm.begin(), perm.end())) {
1198  // Get result for current permutation.
1199  std::vector<std::pair<map_location,map_location>> result;
1200  for(std::size_t u = 0; u < unit_count; ++u) {
1201  if(matrix[u][perm[u]]) {
1202  result.emplace_back(villages[perm[u]], units[u]);
1203 
1204  }
1205  }
1206  if(result.size() == max_result) {
1207  moves.insert(moves.end(), result.begin(), result.end());
1208  reachmap.clear();
1209  return;
1210  }
1211 
1212  if(result.size() > best_result.size()) {
1213  best_result.swap(result);
1214  }
1215  }
1216  // End of loop no optimal found, assign the best
1217  moves.insert(moves.end(), best_result.begin(), best_result.end());
1218 
1219  // clean up the reachmap we need to test whether the leader is still there
1220  // and if so remove him manually to get him dispatched.
1221  for(const auto& unit_village_pair : best_result) {
1222  reachmap.erase(unit_village_pair.second);
1223  }
1225  if(unit != reachmap.end()) {
1226  unit->second.clear();
1227  remove_unit(reachmap, moves, unit);
1228  }
1229  reachmap.clear();
1230 
1231  } else {
1232 
1233  DBG_AI_TESTING_AI_DEFAULT << "Village major";
1234 
1235  std::vector<std::size_t> perm (village_count, 0);
1236  for(std::size_t i =0; i < village_count; ++i) {
1237  perm[i] = i;
1238  }
1239  while(std::next_permutation(perm.begin(), perm.end())) {
1240  // Get result for current permutation.
1241  std::vector<std::pair<map_location,map_location>> result;
1242  for(std::size_t v = 0; v < village_count; ++v) {
1243  if(matrix[perm[v]][v]) {
1244  result.emplace_back(villages[v], units[perm[v]]);
1245 
1246  }
1247  }
1248  if(result.size() == max_result) {
1249  moves.insert(moves.end(), result.begin(), result.end());
1250  reachmap.clear();
1251  return;
1252  }
1253 
1254  if(result.size() > best_result.size()) {
1255  best_result.swap(result);
1256  }
1257  }
1258  // End of loop no optimal found, assigne the best
1259  moves.insert(moves.end(), best_result.begin(), best_result.end());
1260 
1261  // clean up the reachmap we need to test whether the leader is still there
1262  // and if so remove him manually to get him dispatched.
1263  for(const auto& unit_village_pair : best_result) {
1264  reachmap.erase(unit_village_pair.second);
1265  }
1267  if(unit != reachmap.end()) {
1268  unit->second.clear();
1269  remove_unit(reachmap, moves, unit);
1270  }
1271  reachmap.clear();
1272  }
1273 }
1274 
1276 {
1277  treachmap::const_iterator itor = reachmap.begin();
1278  for(std::size_t i = 0; i < reachmap.size(); ++i, ++itor) {
1279  DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << itor->first
1280  << " to village " << itor->second[i];
1281  moves.emplace_back(itor->second[i], itor->first);
1282  }
1283 }
1284 
1286 {
1287  if(!debug_) {
1288  return;
1289  }
1290 
1291  for(treachmap::const_iterator itor =
1292  reachmap.begin(); itor != reachmap.end(); ++itor) {
1293 
1294  STREAMING_LOG << "Reachlist for unit at " << itor->first;
1295 
1296  if(itor->second.empty()) {
1297  STREAMING_LOG << "\tNone";
1298  }
1299 
1300  for(std::vector<map_location>::const_iterator
1301  v_itor = itor->second.begin();
1302  v_itor != itor->second.end(); ++v_itor) {
1303 
1304  STREAMING_LOG << '\t' << *v_itor;
1305  }
1306  STREAMING_LOG << '\n';
1307  }
1308 }
1309 
1310 //==============================================================
1311 
1313  : candidate_action(context,cfg),move_()
1314 {
1315 }
1316 
1318 {
1319 }
1320 
1322 {
1323  // Find units in need of healing.
1324  unit_map &units_ = resources::gameboard->units();
1325  unit_map::iterator u_it = units_.begin();
1326  for(; u_it != units_.end(); ++u_it) {
1327  unit &u = *u_it;
1328 
1329  if(u.can_recruit() && is_passive_leader(u.id())){
1330  continue;
1331  }
1332 
1333  // If the unit is on our side, has lost as many or more than
1334  // 1/2 round worth of healing, and doesn't regenerate itself,
1335  // then try to find a vacant village for it to rest in.
1336  if(u.side() == get_side() &&
1339  !u.get_ability_bool("regenerate") && is_allowed_unit(*u_it))
1340  {
1341  // Look for the village which is the least vulnerable to enemy attack.
1342  typedef std::multimap<map_location,map_location>::const_iterator Itor;
1343  std::pair<Itor,Itor> 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  Itor best_loc = it.second;
1348  while(it.first != it.second) {
1349  const map_location& dst = it.first->second;
1350  if (resources::gameboard->map().gives_healing(dst) && (units_.find(dst) == units_.end() || dst == u_it->get_location())) {
1351  const double vuln = power_projection(dst, get_enemy_dstsrc());
1352  DBG_AI_TESTING_AI_DEFAULT << "found village with vulnerability: " << vuln;
1353  if(vuln < best_vulnerability) {
1354  best_vulnerability = vuln;
1355  best_loc = it.first;
1356  DBG_AI_TESTING_AI_DEFAULT << "chose village " << dst;
1357  }
1358  }
1359 
1360  ++it.first;
1361  }
1362 
1363  // If we have found an eligible village,
1364  // and we can move there without expecting to get whacked next turn:
1365  if(best_loc != it.second && best_vulnerability*leader_penalty < u.hitpoints()) {
1366  move_ = check_move_action(best_loc->first,best_loc->second,true);
1367  if (move_->is_ok()) {
1368  return get_score();
1369  }
1370  }
1371  }
1372  }
1373 
1374  return BAD_SCORE;
1375 }
1376 
1378 {
1379  LOG_AI_TESTING_AI_DEFAULT << "moving unit to village for healing...";
1380  move_->execute();
1381  if (!move_->is_ok()){
1382  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
1383  }
1384 }
1385 
1386 //==============================================================
1387 
1389  : candidate_action(context,cfg), move_()
1390 {
1391 }
1392 
1394 {
1395 }
1396 
1398 {
1399 
1400  // Get versions of the move map that assume that all units are at full movement
1401  const unit_map& units_ = resources::gameboard->units();
1402 
1403  //unit_map::const_iterator leader = units_.find_leader(get_side());
1404  std::vector<unit_map::const_iterator> leaders = units_.find_leaders(get_side());
1405  std::map<map_location,pathfind::paths> dummy_possible_moves;
1406 
1407  move_map fullmove_srcdst;
1408  move_map fullmove_dstsrc;
1409  calculate_possible_moves(dummy_possible_moves, fullmove_srcdst, fullmove_dstsrc,
1410  false, true, &get_avoid());
1411 
1412  std::vector<map_location> leaders_adj_v;
1413  for (unit_map::const_iterator leader : leaders) {
1414  for(const map_location& loc : get_adjacent_tiles(leader->get_location())) {
1415  bool found = false;
1416  for (map_location &new_loc : leaders_adj_v) {
1417  if(new_loc == loc){
1418  found = true;
1419  break;
1420  }
1421  }
1422  if(!found){
1423  leaders_adj_v.push_back(loc);
1424  }
1425  }
1426  }
1427  //leader_adj_count = leaders_adj_v.size();
1428 
1429  for(unit_map::const_iterator i = units_.begin(); i != units_.end(); ++i) {
1430  if (i->side() == get_side() &&
1431  i->movement_left() == i->total_movement() &&
1432  //leaders.find(*i) == leaders.end() && //unit_map::const_iterator(i) != leader &&
1433  std::find(leaders.begin(), leaders.end(), i) == leaders.end() &&
1434  !i->incapacitated() && is_allowed_unit(*i))
1435  {
1436  // This unit still has movement left, and is a candidate to retreat.
1437  // We see the amount of power of each side on the situation,
1438  // and decide whether it should retreat.
1439  if(should_retreat(i->get_location(), i, fullmove_srcdst, fullmove_dstsrc, get_caution())) {
1440 
1441  bool can_reach_leader = false;
1442 
1443  // Time to retreat. Look for the place where the power balance
1444  // is most in our favor.
1445  // If we can't find anywhere where we like the power balance,
1446  // just try to get to the best defensive hex.
1447  typedef move_map::const_iterator Itor;
1448  std::pair<Itor,Itor> itors = get_srcdst().equal_range(i->get_location());
1449  map_location best_pos, best_defensive(i->get_location());
1450 
1451  double best_rating = -1000.0;
1452  int best_defensive_rating = i->defense_modifier(resources::gameboard->map().get_terrain(i->get_location()))
1453  - (resources::gameboard->map().is_village(i->get_location()) ? 10 : 0);
1454  while(itors.first != itors.second) {
1455 
1456  //if(leader != units_.end() && std::count(leader_adj,
1457  // leader_adj + 6, itors.first->second)) {
1458  if(std::find(leaders_adj_v.begin(), leaders_adj_v.end(), itors.first->second) != leaders_adj_v.end()){
1459 
1460  can_reach_leader = true;
1461  break;
1462  }
1463 
1464  // We rate the power balance of a hex based on our power projection
1465  // compared to theirs, multiplying their power projection by their
1466  // chance to hit us on the hex we're planning to flee to.
1467  const map_location& hex = itors.first->second;
1468  const int defense = i->defense_modifier(resources::gameboard->map().get_terrain(hex));
1469  const double our_power = power_projection(hex,get_dstsrc());
1470  const double their_power = power_projection(hex,get_enemy_dstsrc()) * static_cast<double>(defense)/100.0;
1471  const double rating = our_power - their_power;
1472  if(rating > best_rating) {
1473  best_pos = hex;
1474  best_rating = rating;
1475  }
1476 
1477  // Give a bonus for getting to a village.
1478  const int modified_defense = defense - (resources::gameboard->map().is_village(hex) ? 10 : 0);
1479 
1480  if(modified_defense < best_defensive_rating) {
1481  best_defensive_rating = modified_defense;
1482  best_defensive = hex;
1483  }
1484 
1485  ++itors.first;
1486  }
1487 
1488  // If the unit is in range of its leader, it should
1489  // never retreat -- it has to defend the leader instead.
1490  if(can_reach_leader) {
1491  continue;
1492  }
1493 
1494  if(!best_pos.valid()) {
1495  best_pos = best_defensive;
1496  }
1497 
1498  if(best_pos.valid()) {
1499  move_ = check_move_action(i->get_location(), best_pos, true);
1500  if (move_->is_ok()) {
1501  return get_score();
1502  }
1503  }
1504  }
1505  }
1506  }
1507 
1508  return BAD_SCORE;
1509 }
1510 
1512 {
1513  move_->execute();
1514  if (!move_->is_ok()){
1515  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
1516  }
1517 }
1518 
1519 bool retreat_phase::should_retreat(const map_location& loc, const unit_map::const_iterator& un, const move_map &srcdst, const move_map &dstsrc, double caution)
1520 {
1521  const move_map &enemy_dstsrc = get_enemy_dstsrc();
1522 
1523  if(caution <= 0.0) {
1524  return false;
1525  }
1526 
1527  double optimal_terrain = best_defensive_position(un->get_location(), dstsrc,
1528  srcdst, enemy_dstsrc).chance_to_hit/100.0;
1529  const double proposed_terrain =
1530  un->defense_modifier(resources::gameboard->map().get_terrain(loc)) / 100.0;
1531 
1532  // The 'exposure' is the additional % chance to hit
1533  // this unit receives from being on a sub-optimal defensive terrain.
1534  const double exposure = proposed_terrain - optimal_terrain;
1535 
1536  const double our_power = power_projection(loc,dstsrc);
1537  const double their_power = power_projection(loc,enemy_dstsrc);
1538  return caution*their_power*(1.0+exposure) > our_power;
1539 }
1540 
1541 //==============================================================
1542 
1544  : candidate_action(context,cfg)
1545 {
1546 }
1547 
1549 {
1550 }
1551 
1553 {
1554  ERR_AI_TESTING_AI_DEFAULT << get_name() << ": evaluate - not yet implemented";
1555  return BAD_SCORE;
1556 }
1557 
1559 {
1560  ERR_AI_TESTING_AI_DEFAULT << get_name() << ": execute - not yet implemented";
1561 }
1562 
1563 //==============================================================
1564 
1566  :candidate_action(context, cfg)
1567 {
1568 }
1569 
1571 {
1572 }
1573 
1575 {
1576  bool have_active_leader = false;
1577  std::vector<unit_map::unit_iterator> ai_leaders = resources::gameboard->units().find_leaders(get_side());
1578  for (unit_map::unit_iterator &ai_leader : ai_leaders) {
1579  if (!is_passive_leader(ai_leader->id()) || is_passive_keep_sharing_leader(ai_leader->id())) {
1580  have_active_leader = true;
1581  break;
1582  }
1583  }
1584  if(!have_active_leader) {
1585  return BAD_SCORE;
1586  }
1587 
1588  bool allied_leaders_available = false;
1589  for(team &tmp_team : resources::gameboard->teams()) {
1590  if(!current_team().is_enemy(tmp_team.side())){
1591  std::vector<unit_map::unit_iterator> allied_leaders = resources::gameboard->units().find_leaders(get_side());
1592  if (!allied_leaders.empty()){
1593  allied_leaders_available = true;
1594  break;
1595  }
1596  }
1597  }
1598  if(allied_leaders_available){
1599  return get_score();
1600  }
1601  return BAD_SCORE;
1602 }
1603 
1605 {
1606  //get all AI leaders
1607  std::vector<unit_map::unit_iterator> ai_leaders = resources::gameboard->units().find_leaders(get_side());
1608 
1609  //calculate all possible moves (AI + allies)
1610  typedef std::map<map_location, pathfind::paths> path_map;
1611  path_map possible_moves;
1612  move_map friends_srcdst, friends_dstsrc;
1613  calculate_moves(resources::gameboard->units(), possible_moves, friends_srcdst, friends_dstsrc, false, true);
1614 
1615  //check for each ai leader if he should move away from his keep
1616  for (unit_map::unit_iterator &ai_leader : ai_leaders) {
1617  if(!ai_leader.valid() || !is_allowed_unit(*ai_leader) || (is_passive_leader(ai_leader->id()) && !is_passive_keep_sharing_leader(ai_leader->id()))) {
1618  //This can happen if wml killed or moved a leader during a movement events of another leader
1619  continue;
1620  }
1621  //only if leader is on a keep
1622  const map_location &keep = ai_leader->get_location();
1623  if ( !resources::gameboard->map().is_keep(keep) ) {
1624  continue;
1625  }
1626  map_location recruit_loc = pathfind::find_vacant_castle(*ai_leader);
1627  if(!resources::gameboard->map().on_board(recruit_loc)){
1628  continue;
1629  }
1630  bool friend_can_reach_keep = false;
1631 
1632  //for each leader, check if he's allied and can reach our keep
1633  for(path_map::const_iterator i = possible_moves.begin(); i != possible_moves.end(); ++i){
1634  const unit_map::const_iterator itor = resources::gameboard->units().find(i->first);
1635  assert(itor.valid());
1636  team &leader_team = resources::gameboard->get_team(itor->side());
1637  if(itor != resources::gameboard->units().end() && itor->can_recruit() && itor->side() != get_side() && (leader_team.total_income() + leader_team.gold() > leader_team.minimum_recruit_price())){
1638  pathfind::paths::dest_vect::const_iterator tokeep = i->second.destinations.find(keep);
1639  if(tokeep != i->second.destinations.end()){
1640  friend_can_reach_keep = true;
1641  break;
1642  }
1643  }
1644  }
1645  //if there's no allied leader who can reach the keep, check next ai leader
1646  if(friend_can_reach_keep){
1647  //determine the best place the ai leader can move to
1648  map_location best_move;
1649  int defense_modifier = 100;
1650  for(pathfind::paths::dest_vect::const_iterator i = possible_moves[keep].destinations.begin()
1651  ; i != possible_moves[keep].destinations.end()
1652  ; ++i){
1653 
1654  //calculate_moves() above uses max. moves -> need to check movement_left of leader here
1655  if(distance_between(i->curr, keep) <= 3
1656  && static_cast<int>(distance_between(i->curr, keep)) <= ai_leader->movement_left()){
1657 
1658  int tmp_def_mod = ai_leader->defense_modifier(resources::gameboard->map().get_terrain(i->curr));
1659  if(tmp_def_mod < defense_modifier){
1660  defense_modifier = tmp_def_mod;
1661  best_move = i->curr;
1662  }
1663  }
1664  }
1665  //only move if there's a place with a good defense
1666  if(defense_modifier < 100){
1667  move_result_ptr move = check_move_action(keep, best_move, true);
1668  if(move->is_ok()){
1669  move->execute();
1670  if (!move->is_ok()){
1671  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
1672  }else{
1673  ai_leader->set_goto(keep);
1674  }
1675  // This is needed for sides with multiple leaders, in case a WML event does something
1676  // or to account for a leader having previously been moved by this CA execution
1677  possible_moves.clear();
1678  calculate_moves(resources::gameboard->units(), possible_moves, friends_srcdst, friends_dstsrc, false, true);
1679  }else{
1680  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok";
1681  }
1682  }
1683  }
1684  ai_leader->remove_movement_ai();
1685  }
1686  //ERR_AI_TESTING_AI_DEFAULT << get_name() << ": evaluate - not yet implemented";
1687 }
1688 
1689 //==============================================================
1690 
1691 } //end of namespace testing_ai_default
1692 
1693 } //end of namespace ai
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: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:1377
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:1321
get_healing_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:1312
void dump_reachmap(treachmap &reachmap)
Shows which villages every unit can reach (debug function).
Definition: ca.cpp:1285
bool dispatch_village_simple(treachmap &reachmap, tmoves &moves, std::size_t &village_count)
Definition: ca.cpp:878
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:947
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:834
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:774
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:963
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:930
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:1275
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:1543
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:1558
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:1552
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
Definition: ca.cpp:1574
leader_shares_keep_phase(rca_context &context, const config &cfg)
Definition: ca.cpp:1565
virtual void execute()
Execute the candidate action.
Definition: ca.cpp:1604
move_leader_to_goals_phase(rca_context &context, const config &cfg)
Definition: ca.cpp: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:1519
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:1511
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:172
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:302
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:385
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:215
This class stores all the data for a single 'side' (in game nomenclature).
Definition: team.hpp:75
int gold() const
Definition: team.hpp:176
int total_income() const
Definition: team.hpp:183
int minimum_recruit_price() const
Definition: team.cpp:487
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
@ reachmap
Overlay on unreachable hexes.
std::size_t i
Definition: function.cpp:1028
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:181
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:1386
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:1716
const map_location & get_location() const
The current map location this unit is at.
Definition: unit.hpp:1404
int movement_cost(const t_translation::terrain_code &terrain) const
Get the unit's movement cost on a particular terrain.
Definition: unit.hpp:1487
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:479
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:550
Standard logging facilities (interface).
#define STREAMING_LOG
Definition: log.hpp:300
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:323
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:111
std::string::const_iterator iterator
Definition: tokenizer.hpp:25
This module contains various pathfinding functions and utilities.
candidate action framework
rect dst
Location on the final composed sheet.
Encapsulates the map of the game.
Definition: location.hpp:45
bool valid() const
Definition: location.hpp:110
static const map_location & null_location()
Definition: location.hpp:102
bool contains(const map_location &) const
Definition: pathfind.cpp:514
map_location curr
Definition: pathfind.hpp:89
Object which contains all the possible locations a unit can move to, with associated best routes to t...
Definition: pathfind.hpp:73
dest_vect destinations
Definition: pathfind.hpp:101
Structure which holds a single route between one location and another.
Definition: pathfind.hpp:133
std::vector< map_location > steps
Definition: pathfind.hpp:135
int move_cost
Movement cost for reaching the end of the route.
Definition: pathfind.hpp:137
bool valid() const
Definition: map.hpp:273