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