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