The Battle for Wesnoth  1.15.9+dev
ca_move_to_targets.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2009 - 2018 by Yurii Chernyi <terraninfo@terraninfo.net>
3  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
4 
5  This program is free software; you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation; either version 2 of the License, or
8  (at your option) any later version.
9  This program is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY.
11 
12  See the COPYING file for more details.
13 */
14 
15 /**
16  * @file
17  * Strategic movement routine, taken from default AI
18  */
19 
21 
22 #include "ai/composite/ai.hpp"
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" << std::endl;
96  return true;
97  }
98 
99  if (t.value<=0) {
100  DBG_AI << "removing target "<< t.loc << " due to value<=0" << std::endl;
101  return true;
102  }
103 
104  if (avoid_.match(t.loc)) {
105  DBG_AI << "removing target "<< t.loc << " due to 'avoid' match" << std::endl;
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...\n";
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\n";
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\n";
154  std::pair<map_location,map_location> move = choose_move(targets);
155  LOG_AI << "choose_move ends with " << targets.size() << " targets\n";
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 << '\n';
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"<<std::endl;
174  break;
175  }
176  }
177 }
178 
179 // structure storing the maximal possible rating of a target
181  rated_target(const std::vector<target>::iterator& t, double r) : tg(t), max_rating(r) {}
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 == 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 == 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\n";
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\n";
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 <<"\n";
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 << "\n";
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 << "\n";
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...\n";
363 
364  if(best_rated_target == rated_targets.end()) {
365  LOG_AI << "no eligible targets found for unit at " << u->get_location() << std::endl;
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...\n";
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...\n";
413  } else {
414  u = units_.end();
415  }
416 
417  LOG_AI << "best unit: " << best->get_location() << '\n';
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 == target::TYPE::SUPPORT) {
425  LOG_AI << "support...\n";
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() << "\n";
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...\n";
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...\n";
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...\n";
487  }
488 
489  if(dangerous) {
490  LOG_AI << "dangerous path\n";
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\n";
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() << "\n";
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 << "\n";
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 << "\n";
550  targets.emplace_back(*j,value*4.0,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 != 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 << "\n";
579  targets.emplace_back(its.first->first,value*2.0,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() << "\n";
588 
589  return std::pair<map_location,map_location>(its.first->second,its.first->first);
590  } else {
591  LOG_AI << "dangerous!\n";
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\n";
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!\n";
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\n";
711 
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() << "\n";
787  }
788  }
789  } else {
790  LOG_AI << "Could not move group member to any of " << preferred_moves.size() << " locations\n";
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
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:519
virtual std::string get_grouping() const override
Definition: contexts.hpp:626
#define LOG_AI
int h() const
Effective map height, in hexes.
Definition: map.hpp:124
unit_iterator end()
Definition: map.hpp:428
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
virtual const unit_map & units() const override
Definition: game_board.hpp:109
This class represents a single unit of a specific type.
Definition: unit.hpp:120
int movement_cost(const t_translation::terrain_code &terrain) const
Get the unit&#39;s movement cost on a particular terrain.
Definition: unit.hpp:1431
double value
Definition: contexts.hpp:43
unit_iterator find_leader(int side)
Definition: map.cpp:327
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:492
virtual const move_map & get_srcdst() const override
Definition: contexts.hpp:711
std::shared_ptr< move_result > move_result_ptr
Definition: game_info.hpp:84
bool operator()(const rated_target &a, const rated_target &b) const
virtual const gamemap & map() const override
Definition: game_board.hpp:99
unit_iterator begin()
Definition: map.hpp:418
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 lg::log_domain log_ai_testing_ca_move_to_targets("ai/ca/move_to_targets")
bool on_board(const map_location &loc) const
Tell if a location is on the map.
Definition: map.cpp:382
double rate_group(const std::set< map_location > &group, const std::vector< map_location > &battlefield) const
t_translation::terrain_code get_terrain(const map_location &loc) const
Looks up terrain at a particular location.
Definition: map.cpp:314
static double getNoPathValue()
Definition: pathfind.hpp:64
std::multimap< map_location, map_location > move_map
The standard way in which a map of possible moves is recorded.
Definition: game_info.hpp:42
#define b
int defense_modifier(const t_translation::terrain_code &terrain) const
The unit&#39;s defense on a given terrain.
Definition: unit.cpp:1596
A small explanation about what&#39;s going on here: Each action has access to two game_info objects First...
Definition: actions.cpp:59
std::vector< map_location > steps
Definition: pathfind.hpp:134
virtual double evaluate()
Evaluate the candidate action, resetting the internal state of the action.
virtual std::vector< target > find_targets(const move_map &enemy_dstsrc)
Definition: contexts.hpp:197
Structure which holds a single route between one location and another.
Definition: pathfind.hpp:131
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
TYPE type
Definition: contexts.hpp:45
bool is_allowed_unit(const unit &u) const
Flag indicating whether unit may be used by this candidate action.
Definition: rca.cpp:89
bool valid() const
Definition: location.hpp:88
std::vector< target >::iterator tg
game_board * gameboard
Definition: resources.cpp:20
Composite AI with turn sequence which is a vector of stages.
Encapsulates the map of the game.
Definition: map.hpp:33
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:251
virtual const move_map & get_enemy_dstsrc() const override
Definition: contexts.hpp:596
#define log_scope2(domain, description)
Definition: log.hpp:209
std::size_t count(const map_location &loc) const
Definition: map.hpp:413
int move_cost
Movement cost for reaching the end of the route.
Definition: pathfind.hpp:136
Encapsulates the map of the game.
Definition: location.hpp:37
unit_iterator find(std::size_t id)
Definition: map.cpp:309
int w() const
Effective map width, in hexes.
Definition: map.hpp:121
#define DBG_AI
std::size_t i
Definition: function.cpp:933
virtual const team & current_team() const override
Definition: contexts.hpp:450
int max_hitpoints() const
The max number of hitpoints this unit can have.
Definition: unit.hpp:498
attack_itors attacks()
Gets an iterator over this unit&#39;s attacks.
Definition: unit.hpp:918
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:676
virtual double get_scout_village_targeting() const override
Definition: contexts.hpp:716
virtual side_number get_side() const override
Get the side number.
Definition: contexts.hpp:396
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:67
#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:177
virtual const move_map & get_dstsrc() const override
Definition: contexts.hpp:591
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
bool move_group(const map_location &dst, const std::vector< map_location > &route, const std::set< map_location > &units)
double t
Definition: astarsearch.cpp:64
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
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:265
Container associating units to locations.
Definition: map.hpp:97
virtual bool is_keep_ignoring_leader(const std::string &id) const override
Definition: contexts.hpp:746
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:59
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:883
rated_target(const std::vector< target >::iterator &t, double r)
virtual double get_caution() const override
Definition: contexts.hpp:586
static map_location::DIRECTION n
double get_score() const
Get the usual score of the candidate action without re-evaluation.
Definition: rca.cpp:74
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:721
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:24
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.