The Battle for Wesnoth  1.19.0-dev
ca_move_to_targets.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  * @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 "terrain/filter.hpp"
30 #include "pathfind/pathfind.hpp"
31 #include "pathfind/teleport.hpp"
32 
33 #include <deque>
34 
35 namespace ai {
36 
37 namespace ai_default_rca {
38 
39 static lg::log_domain log_ai_testing_ca_move_to_targets("ai/ca/move_to_targets");
40 #define DBG_AI LOG_STREAM(debug, log_ai_testing_ca_move_to_targets)
41 #define LOG_AI LOG_STREAM(info, log_ai_testing_ca_move_to_targets)
42 #define WRN_AI LOG_STREAM(warn, log_ai_testing_ca_move_to_targets)
43 #define ERR_AI LOG_STREAM(err, log_ai_testing_ca_move_to_targets)
44 
46 {
47  move_cost_calculator(const unit& u, const gamemap& map,
48  const unit_map& units, const move_map& enemy_dstsrc)
49  : unit_(u), map_(map), units_(units),
50  enemy_dstsrc_(enemy_dstsrc),
51  max_moves_(u.total_movement()),
52  avoid_enemies_(u.usage() == "scout")
53  {}
54 
55  double cost(const map_location& loc, const double) const
56  {
57  const t_translation::terrain_code terrain = map_[loc];
58 
59  const double move_cost = unit_.movement_cost(terrain);
60 
61  if(move_cost > max_moves_) // impassable
62  return getNoPathValue();
63 
64  double res = move_cost;
65  if(avoid_enemies_){
66  res *= 1.0 + enemy_dstsrc_.count(loc);
67  }
68 
69  //if there is a unit (even a friendly one) on this tile, we increase the cost to
70  //try discourage going through units, to thwart the 'single file effect'
71  if (units_.count(loc))
72  res *= 4.0;
73 
74  return res;
75  }
76 
77 private:
78  const unit& unit_;
79  const gamemap& map_;
80  const unit_map& units_;
82  const int max_moves_;
83  const bool avoid_enemies_;
84 };
85 
87 public:
89  :avoid_(context.get_avoid()), map_(resources::gameboard->map())
90  {
91  }
92 
93 bool operator()(const target &t){
94  if (!map_.on_board(t.loc)) {
95  DBG_AI << "removing target "<< t.loc << " due to it not on_board";
96  return true;
97  }
98 
99  if (t.value<=0) {
100  DBG_AI << "removing target "<< t.loc << " due to value<=0";
101  return true;
102  }
103 
104  if (avoid_.match(t.loc)) {
105  DBG_AI << "removing target "<< t.loc << " due to 'avoid' match";
106  return true;
107  }
108 
109  return false;
110 }
111 private:
112  const terrain_filter &avoid_;
113  const gamemap &map_;
114 
115 };
116 
118  : candidate_action(context,cfg)
119 {
120 }
121 
123 {
124 }
125 
127 {
128  return get_score();
129 }
130 
132 {
134  LOG_AI << "finding targets...";
135  std::vector<target> targets;
136  while(true) {
137  if(targets.empty()) {
138  targets = find_targets(get_enemy_dstsrc());
139  targets.insert(targets.end(),additional_targets().begin(),
140  additional_targets().end());
141  LOG_AI << "Found " << targets.size() << " targets";
142  if(targets.empty()) {
143  break;
144  }
145  }
146 
147  targets.erase( std::remove_if(targets.begin(),targets.end(),remove_wrong_targets(*this)), targets.end() );
148 
149  if(targets.empty()) {
150  break;
151  }
152 
153  LOG_AI << "choosing move with " << targets.size() << " targets";
154  std::pair<map_location,map_location> move = choose_move(targets);
155  LOG_AI << "choose_move ends with " << targets.size() << " targets";
156 
157  for(std::vector<target>::const_iterator ittg = targets.begin();
158  ittg != targets.end(); ++ittg) {
159  assert(resources::gameboard->map().on_board(ittg->loc));
160  }
161 
162  if(move.first.valid() == false || move.second.valid() == false) {
163  break;
164  }
165 
166  assert (resources::gameboard->map().on_board(move.first)
167  && resources::gameboard->map().on_board(move.second));
168 
169  LOG_AI << "move: " << move.first << " -> " << move.second;
170 
171  move_result_ptr move_ptr = execute_move_action(move.first,move.second,true);
172  if(!move_ptr->is_ok()) {
173  WRN_AI << "unexpected outcome of move";
174  break;
175  }
176  }
177 }
178 
179 // structure storing the maximal possible rating of a target
183  double max_rating;
184 };
185 
186 // compare maximal possible rating of targets
187 // we can be smarter about the equal case, but keep old behavior for the moment
189  bool operator()(const rated_target& a, const rated_target& b) const {
190  return a.max_rating > b.max_rating;
191  }
192 };
193 
195  const move_map& dstsrc, const move_map& enemy_dstsrc,
196  const pathfind::plain_route& rt)
197 {
198  double move_cost = rt.move_cost;
199 
200  if(move_cost > 0) {
201  // if this unit can move to that location this turn, it has a very very low cost
202  typedef std::multimap<map_location,map_location>::const_iterator multimapItor;
203  std::pair<multimapItor,multimapItor> 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 std::pair<move_map::const_iterator,move_map::const_iterator> 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  typedef std::multimap<map_location,map_location>::const_iterator Itor;
567  std::pair<Itor,Itor> its = dstsrc.equal_range(*ri);
568  while(its.first != its.second) {
569  if (its.first->second == best->get_location()) {
570  if(!should_retreat(its.first->first,best,fullmove_srcdst,fullmove_dstsrc,enemy_dstsrc,
571  get_caution())) {
572  double value = best_target->value - best->cost() / 20.0;
573 
574  if(value > 0.0 && best_target->type != ai_target::type::mass) {
575  //there are enemies ahead. Rally troops around us to
576  //try to take the target
577  if(is_dangerous) {
578  LOG_AI << "found reinforcement target... " << its.first->first << " with value: " << value*2.0;
579  targets.emplace_back(its.first->first,value*2.0,ai_target::type::battle_aid);
580  }
581 
582  best_target->value = value;
583  } else {
584  targets.erase(best_target);
585  }
586 
587  LOG_AI << "Moving to " << its.first->first.wml_x() << "," << its.first->first.wml_y();
588 
589  return std::pair<map_location,map_location>(its.first->second,its.first->first);
590  } else {
591  LOG_AI << "dangerous!";
592  is_dangerous = true;
593  }
594  }
595 
596  ++its.first;
597  }
598  }
599 
600  if(best != units_.end()) {
601  LOG_AI << "Could not make good move, staying still";
602 
603  //this sounds like the road ahead might be dangerous, and that's why we don't advance.
604  //create this as a target, attempting to rally units around
605  targets.emplace_back(best->get_location(), best_target->value);
606  best_target = targets.end() - 1;
607  return std::pair(best->get_location(), best->get_location());
608  }
609 
610  LOG_AI << "Could not find anywhere to move!";
611  return std::pair<map_location,map_location>();
612 }
613 
614 void move_to_targets_phase::access_points(const move_map& srcdst, const map_location& u, const map_location& dst, std::vector<map_location>& out)
615 {
616  unit_map &units_ = resources::gameboard->units();
617  const gamemap &map_ = resources::gameboard->map();
618  const unit_map::const_iterator u_it = units_.find(u);
619  if(u_it == units_.end()) {
620  return;
621  }
622 
623  // unit_map single_unit(u_it->first, u_it->second);
624 
625  const std::pair<move_map::const_iterator,move_map::const_iterator> locs = srcdst.equal_range(u);
626  for(move_map::const_iterator i = locs.first; i != locs.second; ++i) {
627  const map_location& loc = i->second;
628  if (static_cast<int>(distance_between(loc,dst)) <= u_it->total_movement()) {
630  const pathfind::teleport_map allowed_teleports = pathfind::get_teleport_locations(*u_it, current_team());
631  pathfind::plain_route rt = a_star_search(loc, dst, u_it->total_movement(), calc, map_.w(), map_.h(), &allowed_teleports);
632  if(rt.steps.empty() == false) {
633  out.push_back(loc);
634  }
635  }
636  }
637 }
638 
639 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
640 {
641  const double a = rate_group(our_group,battlefield);
642  const double b = std::max<double>(rate_group(their_group,battlefield),0.01);
643  return a/b;
644 }
645 
646 void move_to_targets_phase::enemies_along_path(const std::vector<map_location>& route, const move_map& dstsrc, std::set<map_location>& res)
647 {
648  for(std::vector<map_location>::const_iterator i = route.begin(); i != route.end(); ++i) {
649  for(const map_location& adj : get_adjacent_tiles(*i)) {
650  const std::pair<move_map::const_iterator,move_map::const_iterator> itors = dstsrc.equal_range(adj);
651  for(move_map::const_iterator j = itors.first; j != itors.second; ++j) {
652  res.insert(j->second);
653  }
654  }
655  }
656 }
657 
658 map_location move_to_targets_phase::form_group(const std::vector<map_location>& route, const move_map& dstsrc, std::set<map_location>& res)
659 {
660  unit_map &units_ = resources::gameboard->units();
661  if(route.empty()) {
662  return map_location();
663  }
664 
665  std::vector<map_location>::const_iterator i;
666  for(i = route.begin(); i != route.end(); ++i) {
667  if(units_.count(*i) > 0) {
668  continue;
669  }
670 
671  std::size_t n = 0, nunits = res.size();
672 
673  const std::pair<move_map::const_iterator,move_map::const_iterator> itors = dstsrc.equal_range(*i);
674  for(move_map::const_iterator j = itors.first; j != itors.second; ++j) {
675  if(res.count(j->second) != 0) {
676  ++n;
677  } else {
678  const unit_map::const_iterator un = units_.find(j->second);
679  if(un == units_.end() || (un->can_recruit() && !is_keep_ignoring_leader(un->id())) || un->movement_left() < un->total_movement()) {
680  continue;
681  }
682 
683  res.insert(j->second);
684  }
685  }
686 
687  //if not all our units can reach this position.
688  if(n < nunits) {
689  break;
690  }
691  }
692 
693  if(i != route.begin()) {
694  --i;
695  }
696 
697  return *i;
698 }
699 
700 bool move_to_targets_phase::move_group(const map_location& dst, const std::vector<map_location>& route, const std::set<map_location>& units)
701 {
702  unit_map &units_ = resources::gameboard->units();
703  const gamemap &map_ = resources::gameboard->map();
704 
705  const std::vector<map_location>::const_iterator itor = std::find(route.begin(),route.end(),dst);
706  if(itor == route.end()) {
707  return false;
708  }
709 
710  LOG_AI << "group has " << units.size() << " members";
711 
712  map_location next;
713 
714  std::size_t direction = 0;
715 
716  //find the direction the group is moving in
717  if(itor+1 != route.end()) {
718  next = *(itor+1);
719  } else if(itor != route.begin()) {
720  next = *(itor-1);
721  }
722 
723  if(next.valid()) {
724  const auto adj = get_adjacent_tiles(dst);
725  direction = std::distance(adj.begin(), std::find(adj.begin(), adj.end(), next));
726  }
727 
728  std::deque<map_location> preferred_moves;
729  preferred_moves.push_back(dst);
730 
731  std::map<map_location,pathfind::paths> possible_moves;
732  move_map srcdst, dstsrc;
733  calculate_possible_moves(possible_moves,srcdst,dstsrc,false);
734 
735  bool gamestate_changed = false;
736 
737  for(std::set<map_location>::const_iterator i = units.begin(); i != units.end(); ++i) {
738  const unit_map::const_iterator un = units_.find(*i);
739  if(un == units_.end()) {
740  continue;
741  }
742 
743  map_location best_loc;
744  int best_defense = -1;
745  for(std::deque<map_location>::const_iterator j = preferred_moves.begin(); j != preferred_moves.end(); ++j) {
746  if(units_.count(*j)) {
747  continue;
748  }
749 
750  const std::pair<move_map::const_iterator,move_map::const_iterator> itors = dstsrc.equal_range(*j);
751  move_map::const_iterator m;
752  for(m = itors.first; m != itors.second; ++m) {
753  if(m->second == *i) {
754  break;
755  }
756  }
757 
758  if(m == itors.second) {
759  continue;
760  }
761 
762  int defense = un->defense_modifier(map_.get_terrain(*j));
763  if(best_loc.valid() == false || defense < best_defense) {
764  best_loc = *j;
765  best_defense = defense;
766  }
767  }
768 
769  if(best_loc.valid()) {
770  move_result_ptr move_res = execute_move_action(*i,best_loc);
771  gamestate_changed |= move_res->is_gamestate_changed();
772 
773  //if we were ambushed or something went wrong, abort the group's movement.
774  if (!move_res->is_ok()) {
775  return gamestate_changed;
776  }
777 
778  preferred_moves.erase(std::find(preferred_moves.begin(),preferred_moves.end(),best_loc));
779 
780  //find locations that are 'perpendicular' to the direction of movement for further units to move to.
781  const auto adj = get_adjacent_tiles(best_loc);
782  for(std::size_t n = 0; n < adj.size(); ++n) {
783  if(n != direction && ((n+3)%6) != direction && map_.on_board(adj[n]) &&
784  units_.count(adj[n]) == 0 && std::count(preferred_moves.begin(),preferred_moves.end(),adj[n]) == 0) {
785  preferred_moves.push_front(adj[n]);
786  LOG_AI << "added moves: " << adj[n].wml_x() << "," << adj[n].wml_y();
787  }
788  }
789  } else {
790  LOG_AI << "Could not move group member to any of " << preferred_moves.size() << " locations";
791  }
792  }
793 
794  return gamestate_changed;
795 }
796 
797 double move_to_targets_phase::rate_group(const std::set<map_location>& group, const std::vector<map_location>& battlefield) const
798 {
799  unit_map &units_ = resources::gameboard->units();
800  const gamemap &map_ = resources::gameboard->map();
801 
802  double strength = 0.0;
803  for(std::set<map_location>::const_iterator i = group.begin(); i != group.end(); ++i) {
804  const unit_map::const_iterator u = units_.find(*i);
805  if(u == units_.end()) {
806  continue;
807  }
808 
809  const unit &un = *u;
810 
811  int defense = 0;
812  for(std::vector<map_location>::const_iterator j = battlefield.begin(); j != battlefield.end(); ++j) {
813  defense += un.defense_modifier(map_.get_terrain(*j));
814  }
815 
816  defense /= battlefield.size();
817 
818  int best_attack = 0;
819  for(const attack_type& a : un.attacks()) {
820  const int attack_strength = a.num_attacks() * a.damage();
821  best_attack = std::max<int>(attack_strength, best_attack);
822  }
823 
824  const int rating = (defense*best_attack*un.hitpoints())/(100*un.max_hitpoints());
825  strength += static_cast<double>(rating);
826  }
827 
828  return strength;
829 }
830 
832  const move_map& srcdst, const move_map& dstsrc, const move_map& enemy_dstsrc,
833  double caution)
834 {
835  if(caution <= 0.0) {
836  return false;
837  }
838 
839  double optimal_terrain = best_defensive_position(un->get_location(), dstsrc,
840  srcdst, enemy_dstsrc).chance_to_hit/100.0;
841  const double proposed_terrain =
842  un->defense_modifier(resources::gameboard->map().get_terrain(loc))/100.0;
843 
844  // The 'exposure' is the additional % chance to hit
845  // this unit receives from being on a sub-optimal defensive terrain.
846  const double exposure = proposed_terrain - optimal_terrain;
847 
848  const double our_power = power_projection(loc,dstsrc);
849  const double their_power = power_projection(loc,enemy_dstsrc);
850  return caution*their_power*(1.0+exposure) > our_power;
851 }
852 
853 } // end of namespace ai_default_rca
854 
855 } // end of namespace ai
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:187
virtual const std::vector< target > & additional_targets() const
Definition: contexts.hpp:167
virtual double get_caution() const override
Definition: contexts.hpp:591
virtual const team & current_team() const override
Definition: contexts.hpp:450
virtual bool is_keep_ignoring_leader(const std::string &id) const override
Definition: contexts.hpp:761
virtual const move_map & get_dstsrc() const override
Definition: contexts.hpp:596
virtual std::string get_grouping() const override
Definition: contexts.hpp:631
virtual void raise_user_interact() const override
Definition: contexts.hpp:519
virtual bool get_simple_targeting() const override
Definition: contexts.hpp:736
virtual const move_map & get_srcdst() const override
Definition: contexts.hpp:716
const defensive_position & best_defensive_position(const map_location &unit, const move_map &dstsrc, const move_map &srcdst, const move_map &enemy_dstsrc) const override
Definition: contexts.hpp:530
virtual void calculate_possible_moves(std::map< map_location, pathfind::paths > &possible_moves, move_map &srcdst, move_map &dstsrc, bool enemy, bool assume_full_movement=false, const terrain_filter *remove_destinations=nullptr) const override
Definition: contexts.hpp:497
virtual double power_projection(const map_location &loc, const move_map &dstsrc) const override
Function which finds how much 'power' a side can attack a certain location with.
Definition: contexts.hpp:681
virtual double get_scout_village_targeting() const override
Definition: contexts.hpp:731
virtual const move_map & get_enemy_dstsrc() const override
Definition: contexts.hpp:601
virtual move_result_ptr execute_move_action(const map_location &from, const map_location &to, bool remove_movement=true, bool unreach_is_ok=false) override
Definition: contexts.hpp:898
virtual side_number get_side() const override
Get the side number.
Definition: contexts.hpp:396
A config object defines a single node in a WML file, with access to child nodes.
Definition: config.hpp:159
virtual const unit_map & units() const override
Definition: game_board.hpp:106
virtual const gamemap & map() const override
Definition: game_board.hpp:96
terrain_code get_terrain(const map_location &loc) const
Looks up terrain at a particular location.
Definition: map.cpp:301
int w() const
Effective map width.
Definition: map.hpp:50
int h() const
Effective map height.
Definition: map.hpp:53
bool on_board(const map_location &loc) const
Tell if a location is on the map.
Definition: map.cpp:384
Encapsulates the map of the game.
Definition: map.hpp:172
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:133
std::size_t i
Definition: function.cpp:968
int max_hitpoints() const
The max number of hitpoints this unit can have.
Definition: unit.hpp:505
int hitpoints() const
The current number of hitpoints this unit has.
Definition: unit.hpp:499
int defense_modifier(const t_translation::terrain_code &terrain) const
The unit's defense on a given terrain.
Definition: unit.cpp:1752
attack_itors attacks()
Gets an iterator over this unit's attacks.
Definition: unit.hpp:927
int movement_cost(const t_translation::terrain_code &terrain) const
Get the unit's movement cost on a particular terrain.
Definition: unit.hpp:1461
void get_adjacent_tiles(const map_location &a, map_location *res)
Function which, given a location, will place all adjacent locations in res.
Definition: location.cpp:474
std::size_t distance_between(const map_location &a, const map_location &b)
Function which gives the number of hexes between two tiles (i.e.
Definition: location.cpp:545
Standard logging facilities (interface).
#define log_scope2(domain, description)
Definition: log.hpp:275
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:270
game_board * gameboard
Definition: resources.cpp:20
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.
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:33
ai_target::type type
Definition: contexts.hpp:36
double value
Definition: contexts.hpp:34
Encapsulates the map of the game.
Definition: location.hpp:38
bool valid() const
Definition: location.hpp:89
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 a
#define b