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