The Battle for Wesnoth  1.19.13+dev
ca_move_to_targets.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2009 - 2025
3  by Yurii Chernyi <terraninfo@terraninfo.net>
4  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License as published by
8  the Free Software Foundation; either version 2 of the License, or
9  (at your option) any later version.
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY.
12 
13  See the COPYING file for more details.
14 */
15 
16 /**
17  * @file
18  * Strategic movement routine, taken from default AI
19  */
20 
22 
23 #include "ai/actions.hpp"
24 #include "game_board.hpp"
25 #include "log.hpp"
26 #include "map/map.hpp"
27 #include "resources.hpp"
28 #include "units/unit.hpp"
29 #include "utils/general.hpp"
30 #include "terrain/filter.hpp"
31 #include "pathfind/pathfind.hpp"
32 #include "pathfind/teleport.hpp"
33 
34 #include <deque>
35 
36 namespace ai {
37 
38 namespace ai_default_rca {
39 
40 static lg::log_domain log_ai_testing_ca_move_to_targets("ai/ca/move_to_targets");
41 #define DBG_AI LOG_STREAM(debug, log_ai_testing_ca_move_to_targets)
42 #define LOG_AI LOG_STREAM(info, log_ai_testing_ca_move_to_targets)
43 #define WRN_AI LOG_STREAM(warn, log_ai_testing_ca_move_to_targets)
44 #define ERR_AI LOG_STREAM(err, log_ai_testing_ca_move_to_targets)
45 
47 {
48  move_cost_calculator(const unit& u, const gamemap& map,
49  const unit_map& units, const move_map& enemy_dstsrc)
50  : unit_(u), map_(map), units_(units),
51  enemy_dstsrc_(enemy_dstsrc),
52  max_moves_(u.total_movement()),
53  avoid_enemies_(u.usage() == "scout")
54  {}
55 
56  double cost(const map_location& loc, const double) const
57  {
58  const t_translation::terrain_code terrain = map_[loc];
59 
60  const double move_cost = unit_.movement_cost(terrain);
61 
62  if(move_cost > max_moves_) // impassable
63  return getNoPathValue();
64 
65  double res = move_cost;
66  if(avoid_enemies_){
67  res *= 1.0 + enemy_dstsrc_.count(loc);
68  }
69 
70  //if there is a unit (even a friendly one) on this tile, we increase the cost to
71  //try discourage going through units, to thwart the 'single file effect'
72  if (units_.count(loc))
73  res *= 4.0;
74 
75  return res;
76  }
77 
78 private:
79  const unit& unit_;
80  const gamemap& map_;
81  const unit_map& units_;
83  const int max_moves_;
84  const bool avoid_enemies_;
85 };
86 
88 public:
90  :avoid_(context.get_avoid()), map_(resources::gameboard->map())
91  {
92  }
93 
94 bool operator()(const target &t){
95  if (!map_.on_board(t.loc)) {
96  DBG_AI << "removing target "<< t.loc << " due to it not on_board";
97  return true;
98  }
99 
100  if (t.value<=0) {
101  DBG_AI << "removing target "<< t.loc << " due to value<=0";
102  return true;
103  }
104 
105  if (avoid_.match(t.loc)) {
106  DBG_AI << "removing target "<< t.loc << " due to 'avoid' match";
107  return true;
108  }
109 
110  return false;
111 }
112 private:
113  const terrain_filter &avoid_;
114  const gamemap &map_;
115 
116 };
117 
119  : candidate_action(context,cfg)
120 {
121 }
122 
124 {
125 }
126 
128 {
129  return get_score();
130 }
131 
133 {
135  LOG_AI << "finding targets...";
136  std::vector<target> targets;
137  while(true) {
138  if(targets.empty()) {
139  targets = find_targets(get_enemy_dstsrc());
140  targets.insert(targets.end(),additional_targets().begin(),
141  additional_targets().end());
142  LOG_AI << "Found " << targets.size() << " targets";
143  if(targets.empty()) {
144  break;
145  }
146  }
147 
148  utils::erase_if(targets, remove_wrong_targets{*this});
149 
150  if(targets.empty()) {
151  break;
152  }
153 
154  LOG_AI << "choosing move with " << targets.size() << " targets";
155  std::pair<map_location,map_location> move = choose_move(targets);
156  LOG_AI << "choose_move ends with " << targets.size() << " targets";
157 
158  for(std::vector<target>::const_iterator ittg = targets.begin();
159  ittg != targets.end(); ++ittg) {
160  assert(resources::gameboard->map().on_board(ittg->loc));
161  }
162 
163  if(move.first.valid() == false || move.second.valid() == false) {
164  break;
165  }
166 
167  assert (resources::gameboard->map().on_board(move.first)
168  && resources::gameboard->map().on_board(move.second));
169 
170  LOG_AI << "move: " << move.first << " -> " << move.second;
171 
172  move_result_ptr move_ptr = execute_move_action(move.first,move.second,true);
173  if(!move_ptr->is_ok()) {
174  WRN_AI << "unexpected outcome of move";
175  break;
176  }
177  }
178 }
179 
180 // structure storing the maximal possible rating of a target
184  double max_rating;
185 };
186 
187 // compare maximal possible rating of targets
188 // we can be smarter about the equal case, but keep old behavior for the moment
190  bool operator()(const rated_target& a, const rated_target& b) const {
191  return a.max_rating > b.max_rating;
192  }
193 };
194 
196  const move_map& dstsrc, const move_map& enemy_dstsrc,
197  const pathfind::plain_route& rt)
198 {
199  double move_cost = rt.move_cost;
200 
201  if(move_cost > 0) {
202  // if this unit can move to that location this turn, it has a very very low cost
203  auto locRange = dstsrc.equal_range(tg.loc);
204  while (locRange.first != locRange.second) {
205  if (locRange.first->second == u->get_location()) {
206  move_cost = 0;
207  break;
208  }
209  ++locRange.first;
210  }
211  }
212 
213  double rating = tg.value;
214 
215  if(rating == 0)
216  return rating; // all following operations are only multiplications of 0
217 
218  // far target have a lower rating
219  if(move_cost > 0) {
220  rating /= move_cost;
221  }
222 
223  //for 'support' targets, they are rated much higher if we can get there within two turns,
224  //otherwise they are worthless to go for at all.
225  if(tg.type == ai_target::type::support) {
226  if (move_cost <= u->movement_left() * 2) {
227  rating *= 10.0;
228  } else {
229  rating = 0.0;
230  return rating;
231  }
232  }
233 
234  //scouts do not like encountering enemies on their paths
235  if (u->usage() == "scout") {
236  //scouts get a bonus for going after villages
237  if(tg.type == ai_target::type::village) {
238  rating *= get_scout_village_targeting();
239  }
240 
241  std::set<map_location> enemies_guarding;
242  enemies_along_path(rt.steps,enemy_dstsrc,enemies_guarding);
243  // note that an empty route means no guardian and thus optimal rating
244 
245  if(enemies_guarding.size() > 1) {
246  rating /= enemies_guarding.size();
247  } else {
248  //scouts who can travel on their route without coming in range of many enemies
249  //get a massive bonus, so that they can be processed first, and avoid getting
250  //bogged down in lots of grouping
251  rating *= 100;
252  }
253  }
254 
255  return rating;
256 }
257 
258 std::pair<map_location,map_location> move_to_targets_phase::choose_move(std::vector<target>& targets)
259 {
261 
263  unit_map &units_ = resources::gameboard->units();
264  const gamemap &map_ = resources::gameboard->map();
265 
267 
268  //take care of all the guardians first
269  for(u = units_.begin(); u != units_.end(); ++u) {
270  if (!(u->side() != get_side() || (u->can_recruit() && !is_keep_ignoring_leader(u->id())) || u->movement_left() <= 0 || u->incapacitated())) {
271  if (u->get_state("guardian")) {
272  LOG_AI << u->type_id() << " is guardian, staying still";
273  return std::pair(u->get_location(), u->get_location());
274  }
275  }
276  }
277 
278  //now find the first eligible remaining unit
279  for(u = units_.begin(); u != units_.end(); ++u) {
280  if (!(u->side() != get_side() || (u->can_recruit() && !is_keep_ignoring_leader(u->id())) || u->movement_left() <= 0 || u->incapacitated() || !is_allowed_unit(*u))) {
281  break;
282  }
283  }
284 
285  if(u == units_.end()) {
286  LOG_AI << "no eligible units found";
287  return std::pair<map_location,map_location>();
288  }
289 
290  const pathfind::plain_route dummy_route;
291  assert(dummy_route.steps.empty() && dummy_route.move_cost == 0);
292 
293  // We will sort all targets by a quick maximal possible rating,
294  // so we will be able to start real work by the most promising ones
295  // and if its real value is better than other maximal values
296  // then we can skip them.
297 
298  const move_map& dstsrc = get_dstsrc();
299  const move_map& enemy_dstsrc = get_enemy_dstsrc();
300  std::vector<rated_target> rated_targets;
301  for(std::vector<target>::iterator tg = targets.begin(); tg != targets.end(); ++tg) {
302  // passing a dummy route to have the maximal rating
303  double max_rating = rate_target(*tg, u, dstsrc, enemy_dstsrc, dummy_route);
304  rated_targets.emplace_back(tg, max_rating);
305  }
306 
307  //use stable_sort for the moment to preserve old AI behavior
308  std::stable_sort(rated_targets.begin(), rated_targets.end(), rated_target_comparer());
309 
310  const move_cost_calculator cost_calc(*u, map_, units_, enemy_dstsrc);
311 
312  pathfind::plain_route best_route;
313  unit_map::iterator best = units_.end();
314  double best_rating = -1.0;
315 
316  std::vector<rated_target>::iterator best_rated_target = rated_targets.end();
317 
318  std::vector<rated_target>::iterator rated_tg = rated_targets.begin();
319 
320  for(; rated_tg != rated_targets.end(); ++rated_tg) {
321  const target& tg = *(rated_tg->tg);
322 
323  LOG_AI << "Considering target at: " << tg.loc;
324  assert(map_.on_board(tg.loc));
325 
327 
328  // locStopValue controls how quickly we give up on the A* search, due
329  // to it seeming futile. Be very cautious about changing this value,
330  // as it can cause the AI to give up on searches and just do nothing.
331  const double locStopValue = 500.0;
333  pathfind::plain_route real_route = a_star_search(u->get_location(), tg.loc, locStopValue, cost_calc, map_.w(), map_.h(), &allowed_teleports);
334 
335  if(real_route.steps.empty()) {
336  LOG_AI << "Can't reach target: " << locStopValue << " = " << tg.value << "/" << best_rating;
337  continue;
338  }
339 
340  double real_rating = rate_target(tg, u, dstsrc, enemy_dstsrc, real_route);
341 
342  LOG_AI << tg.value << "/" << real_route.move_cost << " = " << real_rating;
343 
344  if(real_rating > best_rating){
345  best_rating = real_rating;
346  best_rated_target = rated_tg;
347  best_route = real_route;
348  best = u;
349  //prevent divivion by zero
350  //FIXME: stupid, should fix it at the division
351  if(best_rating == 0)
352  best_rating = 0.000000001;
353 
354  // if already higher than the maximal values of the next ratings
355  // (which are sorted, so only need to check the next one)
356  // then we have found the best target.
357  if(rated_tg+1 != rated_targets.end() && best_rating >= (rated_tg+1)->max_rating)
358  break;
359  }
360  }
361 
362  LOG_AI << "choose target...";
363 
364  if(best_rated_target == rated_targets.end()) {
365  LOG_AI << "no eligible targets found for unit at " << u->get_location();
366  return std::pair(u->get_location(), u->get_location());
367  }
368 
369  assert(best_rating >= 0);
370  std::vector<target>::iterator best_target = best_rated_target->tg;
371 
372  //if we have the 'simple_targeting' flag set, then we don't
373  //see if any other units can put a better bid forward for this
374  //target
375  bool simple_targeting = get_simple_targeting();
376 
377  if(simple_targeting == false) {
378  LOG_AI << "complex targeting...";
379  //now see if any other unit can put a better bid forward
380  for(++u; u != units_.end(); ++u) {
381  if (u->side() != get_side() || (u->can_recruit() && !is_keep_ignoring_leader(u->id())) ||
382  u->movement_left() <= 0 || u->get_state("guardian") ||
383  u->incapacitated() || !is_allowed_unit(*u))
384  {
385  continue;
386  }
387 
389 
390  const move_cost_calculator calc(*u, map_, units_, enemy_dstsrc);
391 
392  // locStopValue controls how quickly we give up on the A* search, due
393  // to it seeming futile. Be very cautious about changing this value,
394  // as it can cause the AI to give up on searches and just do nothing.
395  const double locStopValue = 500.0;
397  pathfind::plain_route cur_route = pathfind::a_star_search(u->get_location(), best_target->loc, locStopValue, calc, map_.w(), map_.h(), &allowed_teleports);
398 
399  if(cur_route.steps.empty()) {
400  continue;
401  }
402 
403  double rating = rate_target(*best_target, u, dstsrc, enemy_dstsrc, cur_route);
404 
405  if(best == units_.end() || rating > best_rating) {
406  best_rating = rating;
407  best = u;
408  best_route = cur_route;
409  }
410  }
411 
412  LOG_AI << "done complex targeting...";
413  } else {
414  u = units_.end();
415  }
416 
417  LOG_AI << "best unit: " << best->get_location();
418 
419  assert(best_target != targets.end());
420 
421  //if our target is a position to support, then we
422  //see if we can move to a position in support of this target
423  const move_map& srcdst = get_srcdst();
424  if(best_target->type == ai_target::type::support) {
425  LOG_AI << "support...";
426 
427  std::vector<map_location> locs;
428  access_points(srcdst, best->get_location(), best_target->loc, locs);
429 
430  if(locs.empty() == false) {
431  LOG_AI << "supporting unit at " << best_target->loc.wml_x() << "," << best_target->loc.wml_y();
432  map_location best_loc;
433  int best_defense = 0;
434  double best_vulnerability = 0.0;
435 
436  for(std::vector<map_location>::const_iterator i = locs.begin(); i != locs.end(); ++i) {
437  const int defense = best->defense_modifier(map_.get_terrain(*i));
438  //FIXME: suokko multiplied by 10 * get_caution(). ?
439  const double vulnerability = power_projection(*i,enemy_dstsrc);
440 
441  if(best_loc.valid() == false || defense < best_defense || (defense == best_defense && vulnerability < best_vulnerability)) {
442  best_loc = *i;
443  best_defense = defense;
444  best_vulnerability = vulnerability;
445  }
446  }
447 
448  LOG_AI << "returning support...";
449  return std::pair(best->get_location(), best_loc);
450  }
451  }
452 
453  std::map<map_location,pathfind::paths> dummy_possible_moves;
454  move_map fullmove_srcdst;
455  move_map fullmove_dstsrc;
456  calculate_possible_moves(dummy_possible_moves,fullmove_srcdst,fullmove_dstsrc,false,true);
457 
458  bool dangerous = false;
459 
460  if(get_grouping() != "no") {
461  LOG_AI << "grouping...";
462  const unit_map::const_iterator unit_at_target = units_.find(best_target->loc);
463  int movement = best->movement_left();
464 
465  const bool defensive_grouping = get_grouping() == "defensive";
466 
467  //we stop and consider whether the route to this
468  //target is dangerous, and whether we need to group some units to move in unison toward the target
469  //if any point along the path is too dangerous for our single unit, then we hold back
470  for(std::vector<map_location>::const_iterator i = best_route.steps.begin(); i != best_route.steps.end() && movement > 0; ++i) {
471 
472  //FIXME: suokko multiplied by 10 * get_caution(). ?
473  const double threat = power_projection(*i,enemy_dstsrc);
474  //FIXME: sukko doubled the power-projection them in the second test. ?
475  if ((threat >= best->hitpoints() && threat > power_projection(*i,fullmove_dstsrc)) ||
476  (i+1 >= best_route.steps.end()-1 && unit_at_target != units_.end() && current_team().is_enemy(unit_at_target->side()))) {
477  dangerous = true;
478  break;
479  }
480 
481  if(!defensive_grouping) {
482  movement -= best->movement_cost(map_.get_terrain(*i));
483  }
484  }
485 
486  LOG_AI << "done grouping...";
487  }
488 
489  if(dangerous) {
490  LOG_AI << "dangerous path";
491  std::set<map_location> group, enemies;
492  const map_location dst = form_group(best_route.steps,dstsrc,group);
493  enemies_along_path(best_route.steps,enemy_dstsrc,enemies);
494 
495  const double our_strength = compare_groups(group,enemies,best_route.steps);
496 
497  if(our_strength > 0.5 + get_caution()) {
498  LOG_AI << "moving group";
499  const bool res = move_group(dst,best_route.steps,group);
500  if(res) {
501  return std::pair<map_location,map_location>(map_location(1,1),map_location());
502  } else {
503  LOG_AI << "group didn't move " << group.size();
504 
505  //the group didn't move, so end the first unit in the group's turn, to prevent an infinite loop
506  return std::pair(best->get_location(), best->get_location());
507 
508  }
509  } else {
510  LOG_AI << "massing to attack " << best_target->loc.wml_x() << "," << best_target->loc.wml_y()
511  << " " << our_strength;
512 
513  const double value = best_target->value;
514  const map_location target_loc = best_target->loc;
515  const map_location loc = best->get_location();
516  const unit& un = *best;
517 
518  targets.erase(best_target);
519 
520  //find the best location to mass units at for an attack on the enemies
521  map_location best_loc;
522  double best_threat = 0.0;
523  int best_distance = 0;
524 
525  const double max_acceptable_threat = un.hitpoints() / 4.0;
526 
527  std::set<map_location> mass_locations;
528 
529  const auto itors = srcdst.equal_range(loc);
530  for(move_map::const_iterator i = itors.first; i != itors.second; ++i) {
531  const int distance = distance_between(target_loc,i->second);
532  const int defense = un.defense_modifier(map_.get_terrain(i->second));
533  //FIXME: suokko multiplied by 10 * get_caution(). ?
534  const double threat = (power_projection(i->second,enemy_dstsrc)*defense)/100;
535 
536  if(best_loc.valid() == false || (threat < std::max<double>(best_threat,max_acceptable_threat) && distance < best_distance)) {
537  best_loc = i->second;
538  best_threat = threat;
539  best_distance = distance;
540  }
541 
542  if(threat < max_acceptable_threat) {
543  mass_locations.insert(i->second);
544  }
545  }
546 
547  for(std::set<map_location>::const_iterator j = mass_locations.begin(); j != mass_locations.end(); ++j) {
548  if(*j != best_loc && distance_between(*j,best_loc) < 3) {
549  LOG_AI << "found mass-to-attack target... " << *j << " with value: " << value*4.0;
550  targets.emplace_back(*j,value*4.0,ai_target::type::mass);
551  best_target = targets.end() - 1;
552  }
553  }
554 
555  return std::pair<map_location,map_location>(loc,best_loc);
556  }
557  }
558 
559  for(std::vector<map_location>::reverse_iterator ri =
560  best_route.steps.rbegin(); ri != best_route.steps.rend(); ++ri) {
561 
562  //this is set to 'true' if we are hesitant to proceed because of enemy units,
563  //to rally troops around us.
564  bool is_dangerous = false;
565 
566  auto its = dstsrc.equal_range(*ri);
567  while(its.first != its.second) {
568  if (its.first->second == best->get_location()) {
569  if(!should_retreat(its.first->first,best,fullmove_srcdst,fullmove_dstsrc,enemy_dstsrc,
570  get_caution())) {
571  double value = best_target->value - best->cost() / 20.0;
572 
573  if(value > 0.0 && best_target->type != ai_target::type::mass) {
574  //there are enemies ahead. Rally troops around us to
575  //try to take the target
576  if(is_dangerous) {
577  LOG_AI << "found reinforcement target... " << its.first->first << " with value: " << value*2.0;
578  targets.emplace_back(its.first->first,value*2.0,ai_target::type::battle_aid);
579  }
580 
581  best_target->value = value;
582  } else {
583  targets.erase(best_target);
584  }
585 
586  LOG_AI << "Moving to " << its.first->first.wml_x() << "," << its.first->first.wml_y();
587 
588  return std::pair<map_location,map_location>(its.first->second,its.first->first);
589  } else {
590  LOG_AI << "dangerous!";
591  is_dangerous = true;
592  }
593  }
594 
595  ++its.first;
596  }
597  }
598 
599  if(best != units_.end()) {
600  LOG_AI << "Could not make good move, staying still";
601 
602  //this sounds like the road ahead might be dangerous, and that's why we don't advance.
603  //create this as a target, attempting to rally units around
604  targets.emplace_back(best->get_location(), best_target->value);
605  best_target = targets.end() - 1;
606  return std::pair(best->get_location(), best->get_location());
607  }
608 
609  LOG_AI << "Could not find anywhere to move!";
610  return std::pair<map_location,map_location>();
611 }
612 
613 void move_to_targets_phase::access_points(const move_map& srcdst, const map_location& u, const map_location& dst, std::vector<map_location>& out)
614 {
615  unit_map &units_ = resources::gameboard->units();
616  const gamemap &map_ = resources::gameboard->map();
617  const unit_map::const_iterator u_it = units_.find(u);
618  if(u_it == units_.end()) {
619  return;
620  }
621 
622  // unit_map single_unit(u_it->first, u_it->second);
623 
624  const auto locs = srcdst.equal_range(u);
625  for(move_map::const_iterator i = locs.first; i != locs.second; ++i) {
626  const map_location& loc = i->second;
627  if (static_cast<int>(distance_between(loc,dst)) <= u_it->total_movement()) {
629  const pathfind::teleport_map allowed_teleports = pathfind::get_teleport_locations(*u_it, current_team());
630  pathfind::plain_route rt = a_star_search(loc, dst, u_it->total_movement(), calc, map_.w(), map_.h(), &allowed_teleports);
631  if(rt.steps.empty() == false) {
632  out.push_back(loc);
633  }
634  }
635  }
636 }
637 
638 double move_to_targets_phase::compare_groups(const std::set<map_location>& our_group, const std::set<map_location>& their_group, const std::vector<map_location>& battlefield) const
639 {
640  const double a = rate_group(our_group,battlefield);
641  const double b = std::max<double>(rate_group(their_group,battlefield),0.01);
642  return a/b;
643 }
644 
645 void move_to_targets_phase::enemies_along_path(const std::vector<map_location>& route, const move_map& dstsrc, std::set<map_location>& res)
646 {
647  for(std::vector<map_location>::const_iterator i = route.begin(); i != route.end(); ++i) {
648  for(const map_location& adj : get_adjacent_tiles(*i)) {
649  const auto itors = dstsrc.equal_range(adj);
650  for(move_map::const_iterator j = itors.first; j != itors.second; ++j) {
651  res.insert(j->second);
652  }
653  }
654  }
655 }
656 
657 map_location move_to_targets_phase::form_group(const std::vector<map_location>& route, const move_map& dstsrc, std::set<map_location>& res)
658 {
659  unit_map &units_ = resources::gameboard->units();
660  if(route.empty()) {
661  return map_location();
662  }
663 
664  std::vector<map_location>::const_iterator i;
665  for(i = route.begin(); i != route.end(); ++i) {
666  if(units_.count(*i) > 0) {
667  continue;
668  }
669 
670  std::size_t n = 0, nunits = res.size();
671 
672  const auto itors = dstsrc.equal_range(*i);
673  for(move_map::const_iterator j = itors.first; j != itors.second; ++j) {
674  if(res.count(j->second) != 0) {
675  ++n;
676  } else {
677  const unit_map::const_iterator un = units_.find(j->second);
678  if(un == units_.end() || (un->can_recruit() && !is_keep_ignoring_leader(un->id())) || un->movement_left() < un->total_movement()) {
679  continue;
680  }
681 
682  res.insert(j->second);
683  }
684  }
685 
686  //if not all our units can reach this position.
687  if(n < nunits) {
688  break;
689  }
690  }
691 
692  if(i != route.begin()) {
693  --i;
694  }
695 
696  return *i;
697 }
698 
699 bool move_to_targets_phase::move_group(const map_location& dst, const std::vector<map_location>& route, const std::set<map_location>& units)
700 {
701  unit_map &units_ = resources::gameboard->units();
702  const gamemap &map_ = resources::gameboard->map();
703 
704  const std::vector<map_location>::const_iterator itor = std::find(route.begin(),route.end(),dst);
705  if(itor == route.end()) {
706  return false;
707  }
708 
709  LOG_AI << "group has " << units.size() << " members";
710 
711  map_location next;
712 
713  std::size_t direction = 0;
714 
715  //find the direction the group is moving in
716  if(itor+1 != route.end()) {
717  next = *(itor+1);
718  } else if(itor != route.begin()) {
719  next = *(itor-1);
720  }
721 
722  if(next.valid()) {
723  const auto adj = get_adjacent_tiles(dst);
724  direction = std::distance(adj.begin(), std::find(adj.begin(), adj.end(), next));
725  }
726 
727  std::deque<map_location> preferred_moves;
728  preferred_moves.push_back(dst);
729 
730  std::map<map_location,pathfind::paths> possible_moves;
731  move_map srcdst, dstsrc;
732  calculate_possible_moves(possible_moves,srcdst,dstsrc,false);
733 
734  bool gamestate_changed = false;
735 
736  for(std::set<map_location>::const_iterator i = units.begin(); i != units.end(); ++i) {
737  const unit_map::const_iterator un = units_.find(*i);
738  if(un == units_.end()) {
739  continue;
740  }
741 
742  map_location best_loc;
743  int best_defense = -1;
744  for(std::deque<map_location>::const_iterator j = preferred_moves.begin(); j != preferred_moves.end(); ++j) {
745  if(units_.count(*j)) {
746  continue;
747  }
748 
749  const auto itors = dstsrc.equal_range(*j);
750  move_map::const_iterator m;
751  for(m = itors.first; m != itors.second; ++m) {
752  if(m->second == *i) {
753  break;
754  }
755  }
756 
757  if(m == itors.second) {
758  continue;
759  }
760 
761  int defense = un->defense_modifier(map_.get_terrain(*j));
762  if(best_loc.valid() == false || defense < best_defense) {
763  best_loc = *j;
764  best_defense = defense;
765  }
766  }
767 
768  if(best_loc.valid()) {
769  move_result_ptr move_res = execute_move_action(*i,best_loc);
770  gamestate_changed |= move_res->is_gamestate_changed();
771 
772  //if we were ambushed or something went wrong, abort the group's movement.
773  if (!move_res->is_ok()) {
774  return gamestate_changed;
775  }
776 
777  preferred_moves.erase(std::find(preferred_moves.begin(),preferred_moves.end(),best_loc));
778 
779  //find locations that are 'perpendicular' to the direction of movement for further units to move to.
780  const auto adj = get_adjacent_tiles(best_loc);
781  for(std::size_t n = 0; n < adj.size(); ++n) {
782  if(n != direction && ((n+3)%6) != direction && map_.on_board(adj[n]) &&
783  units_.count(adj[n]) == 0 && std::count(preferred_moves.begin(),preferred_moves.end(),adj[n]) == 0) {
784  preferred_moves.push_front(adj[n]);
785  LOG_AI << "added moves: " << adj[n].wml_x() << "," << adj[n].wml_y();
786  }
787  }
788  } else {
789  LOG_AI << "Could not move group member to any of " << preferred_moves.size() << " locations";
790  }
791  }
792 
793  return gamestate_changed;
794 }
795 
796 double move_to_targets_phase::rate_group(const std::set<map_location>& group, const std::vector<map_location>& battlefield) const
797 {
798  unit_map &units_ = resources::gameboard->units();
799  const gamemap &map_ = resources::gameboard->map();
800 
801  double strength = 0.0;
802  for(std::set<map_location>::const_iterator i = group.begin(); i != group.end(); ++i) {
803  const unit_map::const_iterator u = units_.find(*i);
804  if(u == units_.end()) {
805  continue;
806  }
807 
808  const unit &un = *u;
809 
810  int defense = 0;
811  for(std::vector<map_location>::const_iterator j = battlefield.begin(); j != battlefield.end(); ++j) {
812  defense += un.defense_modifier(map_.get_terrain(*j));
813  }
814 
815  defense /= battlefield.size();
816 
817  int best_attack = 0;
818  for(const attack_type& a : un.attacks()) {
819  const int attack_strength = a.num_attacks() * a.damage();
820  best_attack = std::max<int>(attack_strength, best_attack);
821  }
822 
823  const int rating = (defense*best_attack*un.hitpoints())/(100*un.max_hitpoints());
824  strength += static_cast<double>(rating);
825  }
826 
827  return strength;
828 }
829 
831  const move_map& srcdst, const move_map& dstsrc, const move_map& enemy_dstsrc,
832  double caution)
833 {
834  if(caution <= 0.0) {
835  return false;
836  }
837 
838  double optimal_terrain = best_defensive_position(un->get_location(), dstsrc,
839  srcdst, enemy_dstsrc).chance_to_hit/100.0;
840  const double proposed_terrain =
841  un->defense_modifier(resources::gameboard->map().get_terrain(loc))/100.0;
842 
843  // The 'exposure' is the additional % chance to hit
844  // this unit receives from being on a sub-optimal defensive terrain.
845  const double exposure = proposed_terrain - optimal_terrain;
846 
847  const double our_power = power_projection(loc,dstsrc);
848  const double their_power = power_projection(loc,enemy_dstsrc);
849  return caution*their_power*(1.0+exposure) > our_power;
850 }
851 
852 } // end of namespace ai_default_rca
853 
854 } // end of namespace ai
map_location loc
Definition: move.cpp:172
Managing the AI-Game interaction - AI actions and their results.
double t
Definition: astarsearch.cpp:63
#define LOG_AI
#define DBG_AI
#define WRN_AI
Strategic movement routine, for experimentation.
void access_points(const move_map &srcdst, const map_location &u, const map_location &dst, std::vector< map_location > &out)
map_location form_group(const std::vector< map_location > &route, const move_map &dstsrc, std::set< map_location > &res)
void enemies_along_path(const std::vector< map_location > &route, const move_map &dstsrc, std::set< map_location > &res)
bool move_group(const map_location &dst, const std::vector< map_location > &route, const std::set< map_location > &units)
bool should_retreat(const map_location &loc, const unit_map::const_iterator &un, const move_map &srcdst, const move_map &dstsrc, const move_map &enemy_dstsrc, double caution)
double rate_group(const std::set< map_location > &group, const std::vector< map_location > &battlefield) const
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
double compare_groups(const std::set< map_location > &our_group, const std::set< map_location > &their_group, const std::vector< map_location > &battlefield) const
move_to_targets_phase(rca_context &context, const config &cfg)
double rate_target(const target &tg, const unit_map::iterator &u, const move_map &dstsrc, const move_map &enemy_dstsrc, const pathfind::plain_route &rt)
rate a target, but can also return the maximal possible rating by passing a dummy route
virtual void execute()
Execute the candidate action.
std::pair< map_location, map_location > choose_move(std::vector< target > &targets)
remove_wrong_targets(const readonly_context &context)
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
virtual std::vector< target > find_targets(const move_map &enemy_dstsrc)
Definition: contexts.hpp:181
virtual const std::vector< target > & additional_targets() const
Definition: contexts.hpp:161
virtual double get_caution() const override
Definition: contexts.hpp:583
virtual const team & current_team() const override
Definition: contexts.hpp:447
virtual bool is_keep_ignoring_leader(const std::string &id) const override
Definition: contexts.hpp:753
virtual const move_map & get_dstsrc() const override
Definition: contexts.hpp:588
virtual std::string get_grouping() const override
Definition: contexts.hpp:623
virtual void raise_user_interact() const override
Definition: contexts.hpp:516
virtual bool get_simple_targeting() const override
Definition: contexts.hpp:728
virtual const move_map & get_srcdst() const override
Definition: contexts.hpp:708
const defensive_position & best_defensive_position(const map_location &unit, const move_map &dstsrc, const move_map &srcdst, const move_map &enemy_dstsrc) const override
Definition: contexts.hpp:527
virtual void calculate_possible_moves(std::map< map_location, pathfind::paths > &possible_moves, move_map &srcdst, move_map &dstsrc, bool enemy, bool assume_full_movement=false, const terrain_filter *remove_destinations=nullptr) const override
Definition: contexts.hpp:494
virtual double power_projection(const map_location &loc, const move_map &dstsrc) const override
Function which finds how much 'power' a side can attack a certain location with.
Definition: contexts.hpp:673
virtual double get_scout_village_targeting() const override
Definition: contexts.hpp:723
virtual const move_map & get_enemy_dstsrc() const override
Definition: contexts.hpp:593
virtual move_result_ptr execute_move_action(const map_location &from, const map_location &to, bool remove_movement=true, bool unreach_is_ok=false) override
Definition: contexts.hpp:890
virtual side_number get_side() const override
Get the side number.
Definition: contexts.hpp:393
A config object defines a single node in a WML file, with access to child nodes.
Definition: config.hpp:158
virtual const unit_map & units() const override
Definition: game_board.hpp:107
virtual const gamemap & map() const override
Definition: game_board.hpp:97
terrain_code get_terrain(const map_location &loc) const
Looks up terrain at a particular location.
Definition: map.cpp:301
int w() const
Effective map width.
Definition: map.hpp:50
int h() const
Effective map height.
Definition: map.hpp:53
bool on_board(const map_location &loc) const
Tell if a location is on the map.
Definition: map.cpp:384
Encapsulates the map of the game.
Definition: map.hpp:172
Container associating units to locations.
Definition: map.hpp:98
unit_iterator end()
Definition: map.hpp:428
std::size_t count(const map_location &loc) const
Definition: map.hpp:413
unit_iterator find(std::size_t id)
Definition: map.cpp:302
unit_iterator begin()
Definition: map.hpp:418
unit_iterator find_leader(int side)
Definition: map.cpp:320
This class represents a single unit of a specific type.
Definition: unit.hpp:132
const config * cfg
std::size_t i
Definition: function.cpp:1032
int max_hitpoints() const
The max number of hitpoints this unit can have.
Definition: unit.hpp:520
int hitpoints() const
The current number of hitpoints this unit has.
Definition: unit.hpp:514
int defense_modifier(const t_translation::terrain_code &terrain) const
The unit's defense on a given terrain.
Definition: unit.cpp:1754
attack_itors attacks()
Gets an iterator over this unit's attacks.
Definition: unit.hpp:941
int movement_cost(const t_translation::terrain_code &terrain) const
Get the unit's movement cost on a particular terrain.
Definition: unit.hpp:1514
void get_adjacent_tiles(const map_location &a, map_location *res)
Function which, given a location, will place all adjacent locations in res.
Definition: location.cpp:512
std::size_t distance_between(const map_location &a, const map_location &b)
Function which gives the number of hexes between two tiles (i.e.
Definition: location.cpp:583
Standard logging facilities (interface).
#define log_scope2(domain, description)
Definition: log.hpp:276
static lg::log_domain log_ai_testing_ca_move_to_targets("ai/ca/move_to_targets")
A small explanation about what's going on here: Each action has access to two game_info objects First...
Definition: actions.cpp:59
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::shared_ptr< move_result > move_result_ptr
Definition: game_info.hpp:85
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
void erase_if(Container &container, const Predicate &predicate)
Convenience wrapper for using std::remove_if on a container.
Definition: general.hpp:106
auto * find(Container &container, const Value &value)
Convenience wrapper for using find on a container without needing to comare to end()
Definition: general.hpp:140
std::shared_ptr< move > move_ptr
Definition: typedefs.hpp:68
std::string::const_iterator iterator
Definition: tokenizer.hpp:25
This module contains various pathfinding functions and utilities.
rect dst
Location on the final composed sheet.
double cost(const map_location &loc, const double) const
move_cost_calculator(const unit &u, const gamemap &map, const unit_map &units, const move_map &enemy_dstsrc)
bool operator()(const rated_target &a, const rated_target &b) const
rated_target(const std::vector< target >::iterator &t, double r)
std::vector< target >::iterator tg
map_location loc
Definition: contexts.hpp:32
ai_target::type type
Definition: contexts.hpp:35
double value
Definition: contexts.hpp:33
Encapsulates the map of the game.
Definition: location.hpp:45
bool valid() const
Definition: location.hpp:110
static double getNoPathValue()
Definition: pathfind.hpp:65
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
A terrain string which is converted to a terrain is a string with 1 or 2 layers the layers are separa...
Definition: translation.hpp:49
static map_location::direction n
#define b