The Battle for Wesnoth  1.13.10+dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
ca_move_to_targets.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2009 - 2017 by Yurii Chernyi <terraninfo@terraninfo.net>
3  Part of the Battle for Wesnoth Project http://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:
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
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  ///@todo 1.9: lower this value for perf,
406  // but best_rating is too big for scout and support
407  // which give a too small locStopValue
408  // so keep costy A* for the moment.
409  //const double locStopValue = std::min(best_target->value / best_rating, (double) 100.0);
410 
411  const double locStopValue = 500.0;
413  pathfind::plain_route cur_route = pathfind::a_star_search(u->get_location(), best_target->loc, locStopValue, calc, map_.w(), map_.h(), &allowed_teleports);
414 
415  if(cur_route.steps.empty()) {
416  continue;
417  }
418 
419  double rating = rate_target(*best_target, u, dstsrc, enemy_dstsrc, cur_route);
420 
421  if(best == units_.end() || rating > best_rating) {
422  best_rating = rating;
423  best = u;
424  best_route = cur_route;
425  }
426  }
427 
428  LOG_AI << "done complex targeting...\n";
429  } else {
430  u = units_.end();
431  }
432 
433  LOG_AI << "best unit: " << best->get_location() << '\n';
434 
435  assert(best_target != targets.end());
436 
437  //if our target is a position to support, then we
438  //see if we can move to a position in support of this target
439  const move_map& srcdst = get_srcdst();
440  if(best_target->type == target::TYPE::SUPPORT) {
441  LOG_AI << "support...\n";
442 
443  std::vector<map_location> locs;
444  access_points(srcdst, best->get_location(), best_target->loc, locs);
445 
446  if(locs.empty() == false) {
447  LOG_AI << "supporting unit at " << best_target->loc.wml_x() << "," << best_target->loc.wml_y() << "\n";
448  map_location best_loc;
449  int best_defense = 0;
450  double best_vulnerability = 0.0;
451 
452  for(std::vector<map_location>::const_iterator i = locs.begin(); i != locs.end(); ++i) {
453  const int defense = best->defense_modifier(map_.get_terrain(*i));
454  //FIXME: suokko multiplied by 10 * get_caution(). ?
455  const double vulnerability = power_projection(*i,enemy_dstsrc);
456 
457  if(best_loc.valid() == false || defense < best_defense || (defense == best_defense && vulnerability < best_vulnerability)) {
458  best_loc = *i;
459  best_defense = defense;
460  best_vulnerability = vulnerability;
461  }
462  }
463 
464  LOG_AI << "returning support...\n";
465  return std::make_pair(best->get_location(), best_loc);
466  }
467  }
468 
469  std::map<map_location,pathfind::paths> dummy_possible_moves;
470  move_map fullmove_srcdst;
471  move_map fullmove_dstsrc;
472  calculate_possible_moves(dummy_possible_moves,fullmove_srcdst,fullmove_dstsrc,false,true);
473 
474  bool dangerous = false;
475 
476  if(get_grouping() != "no") {
477  LOG_AI << "grouping...\n";
478  const unit_map::const_iterator unit_at_target = units_.find(best_target->loc);
479  int movement = best->movement_left();
480 
481  const bool defensive_grouping = get_grouping() == "defensive";
482 
483  //we stop and consider whether the route to this
484  //target is dangerous, and whether we need to group some units to move in unison toward the target
485  //if any point along the path is too dangerous for our single unit, then we hold back
486  for(std::vector<map_location>::const_iterator i = best_route.steps.begin(); i != best_route.steps.end() && movement > 0; ++i) {
487 
488  //FIXME: suokko multiplied by 10 * get_caution(). ?
489  const double threat = power_projection(*i,enemy_dstsrc);
490  //FIXME: sukko doubled the power-projection them in the second test. ?
491  if ((threat >= best->hitpoints() && threat > power_projection(*i,fullmove_dstsrc)) ||
492  (i+1 >= best_route.steps.end()-1 && unit_at_target != units_.end() && current_team().is_enemy(unit_at_target->side()))) {
493  dangerous = true;
494  break;
495  }
496 
497  if(!defensive_grouping) {
498  movement -= best->movement_cost(map_.get_terrain(*i));
499  }
500  }
501 
502  LOG_AI << "done grouping...\n";
503  }
504 
505  if(dangerous) {
506  LOG_AI << "dangerous path\n";
507  std::set<map_location> group, enemies;
508  const map_location dst = form_group(best_route.steps,dstsrc,group);
509  enemies_along_path(best_route.steps,enemy_dstsrc,enemies);
510 
511  const double our_strength = compare_groups(group,enemies,best_route.steps);
512 
513  if(our_strength > 0.5 + get_caution()) {
514  LOG_AI << "moving group\n";
515  const bool res = move_group(dst,best_route.steps,group);
516  if(res) {
517  return std::pair<map_location,map_location>(map_location(1,1),map_location());
518  } else {
519  LOG_AI << "group didn't move " << group.size() << "\n";
520 
521  //the group didn't move, so end the first unit in the group's turn, to prevent an infinite loop
522  return std::make_pair(best->get_location(), best->get_location());
523 
524  }
525  } else {
526  LOG_AI << "massing to attack " << best_target->loc.wml_x() << "," << best_target->loc.wml_y()
527  << " " << our_strength << "\n";
528 
529  const double value = best_target->value;
530  const map_location target_loc = best_target->loc;
531  const map_location loc = best->get_location();
532  const unit& un = *best;
533 
534  targets.erase(best_target);
535 
536  //find the best location to mass units at for an attack on the enemies
537  map_location best_loc;
538  double best_threat = 0.0;
539  int best_distance = 0;
540 
541  const double max_acceptable_threat = un.hitpoints() / 4.0;
542 
543  std::set<map_location> mass_locations;
544 
545  const std::pair<move_map::const_iterator,move_map::const_iterator> itors = srcdst.equal_range(loc);
546  for(move_map::const_iterator i = itors.first; i != itors.second; ++i) {
547  const int distance = distance_between(target_loc,i->second);
548  const int defense = un.defense_modifier(map_.get_terrain(i->second));
549  //FIXME: suokko multiplied by 10 * get_caution(). ?
550  const double threat = (power_projection(i->second,enemy_dstsrc)*defense)/100;
551 
552  if(best_loc.valid() == false || (threat < std::max<double>(best_threat,max_acceptable_threat) && distance < best_distance)) {
553  best_loc = i->second;
554  best_threat = threat;
555  best_distance = distance;
556  }
557 
558  if(threat < max_acceptable_threat) {
559  mass_locations.insert(i->second);
560  }
561  }
562 
563  for(std::set<map_location>::const_iterator j = mass_locations.begin(); j != mass_locations.end(); ++j) {
564  if(*j != best_loc && distance_between(*j,best_loc) < 3) {
565  LOG_AI << "found mass-to-attack target... " << *j << " with value: " << value*4.0 << "\n";
566  targets.emplace_back(*j,value*4.0,target::TYPE::MASS);
567  best_target = targets.end() - 1;
568  }
569  }
570 
571  return std::pair<map_location,map_location>(loc,best_loc);
572  }
573  }
574 
575  for(std::vector<map_location>::reverse_iterator ri =
576  best_route.steps.rbegin(); ri != best_route.steps.rend(); ++ri) {
577 
578  //this is set to 'true' if we are hesitant to proceed because of enemy units,
579  //to rally troops around us.
580  bool is_dangerous = false;
581 
582  typedef std::multimap<map_location,map_location>::const_iterator Itor;
583  std::pair<Itor,Itor> its = dstsrc.equal_range(*ri);
584  while(its.first != its.second) {
585  if (its.first->second == best->get_location()) {
586  if(!should_retreat(its.first->first,best,fullmove_srcdst,fullmove_dstsrc,enemy_dstsrc,
587  get_caution())) {
588  double value = best_target->value - best->cost() / 20.0;
589 
590  if(value > 0.0 && best_target->type != target::TYPE::MASS) {
591  //there are enemies ahead. Rally troops around us to
592  //try to take the target
593  if(is_dangerous) {
594  LOG_AI << "found reinforcement target... " << its.first->first << " with value: " << value*2.0 << "\n";
595  targets.emplace_back(its.first->first,value*2.0,target::TYPE::BATTLE_AID);
596  }
597 
598  best_target->value = value;
599  } else {
600  targets.erase(best_target);
601  }
602 
603  LOG_AI << "Moving to " << its.first->first.wml_x() << "," << its.first->first.wml_y() << "\n";
604 
605  return std::pair<map_location,map_location>(its.first->second,its.first->first);
606  } else {
607  LOG_AI << "dangerous!\n";
608  is_dangerous = true;
609  }
610  }
611 
612  ++its.first;
613  }
614  }
615 
616  if(best != units_.end()) {
617  LOG_AI << "Could not make good move, staying still\n";
618 
619  //this sounds like the road ahead might be dangerous, and that's why we don't advance.
620  //create this as a target, attempting to rally units around
621  targets.emplace_back(best->get_location(), best_target->value);
622  best_target = targets.end() - 1;
623  return std::make_pair(best->get_location(), best->get_location());
624  }
625 
626  LOG_AI << "Could not find anywhere to move!\n";
627  return std::pair<map_location,map_location>();
628 }
629 
630 void move_to_targets_phase::access_points(const move_map& srcdst, const map_location& u, const map_location& dst, std::vector<map_location>& out)
631 {
632  unit_map &units_ = resources::gameboard->units();
633  const gamemap &map_ = resources::gameboard->map();
634  const unit_map::const_iterator u_it = units_.find(u);
635  if(u_it == units_.end()) {
636  return;
637  }
638 
639  // unit_map single_unit(u_it->first, u_it->second);
640 
641  const std::pair<move_map::const_iterator,move_map::const_iterator> locs = srcdst.equal_range(u);
642  for(move_map::const_iterator i = locs.first; i != locs.second; ++i) {
643  const map_location& loc = i->second;
644  if (int(distance_between(loc,dst)) <= u_it->total_movement()) {
646  const pathfind::teleport_map allowed_teleports = pathfind::get_teleport_locations(*u_it, current_team());
647  pathfind::plain_route rt = a_star_search(loc, dst, u_it->total_movement(), calc, map_.w(), map_.h(), &allowed_teleports);
648  if(rt.steps.empty() == false) {
649  out.push_back(loc);
650  }
651  }
652  }
653 }
654 
655 
656 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
657 {
658  const double a = rate_group(our_group,battlefield);
659  const double b = std::max<double>(rate_group(their_group,battlefield),0.01);
660  return a/b;
661 }
662 
663 
664 void move_to_targets_phase::enemies_along_path(const std::vector<map_location>& route, const move_map& dstsrc, std::set<map_location>& res)
665 {
666  for(std::vector<map_location>::const_iterator i = route.begin(); i != route.end(); ++i) {
667  map_location adj[6];
668  get_adjacent_tiles(*i,adj);
669  for(size_t n = 0; n != 6; ++n) {
670  const std::pair<move_map::const_iterator,move_map::const_iterator> itors = dstsrc.equal_range(adj[n]);
671  for(move_map::const_iterator j = itors.first; j != itors.second; ++j) {
672  res.insert(j->second);
673  }
674  }
675  }
676 }
677 
678 
679 map_location move_to_targets_phase::form_group(const std::vector<map_location>& route, const move_map& dstsrc, std::set<map_location>& res)
680 {
681  unit_map &units_ = resources::gameboard->units();
682  if(route.empty()) {
683  return map_location();
684  }
685 
686  std::vector<map_location>::const_iterator i;
687  for(i = route.begin(); i != route.end(); ++i) {
688  if(units_.count(*i) > 0) {
689  continue;
690  }
691 
692  size_t n = 0, nunits = res.size();
693 
694  const std::pair<move_map::const_iterator,move_map::const_iterator> itors = dstsrc.equal_range(*i);
695  for(move_map::const_iterator j = itors.first; j != itors.second; ++j) {
696  if(res.count(j->second) != 0) {
697  ++n;
698  } else {
699  const unit_map::const_iterator un = units_.find(j->second);
700  if(un == units_.end() || (un->can_recruit() && !get_leader_ignores_keep()) || un->movement_left() < un->total_movement()) {
701  continue;
702  }
703 
704  res.insert(j->second);
705  }
706  }
707 
708  //if not all our units can reach this position.
709  if(n < nunits) {
710  break;
711  }
712  }
713 
714  if(i != route.begin()) {
715  --i;
716  }
717 
718  return *i;
719 }
720 
721 
722 bool move_to_targets_phase::move_group(const map_location& dst, const std::vector<map_location>& route, const std::set<map_location>& units)
723 {
724  unit_map &units_ = resources::gameboard->units();
725  const gamemap &map_ = resources::gameboard->map();
726 
727  const std::vector<map_location>::const_iterator itor = std::find(route.begin(),route.end(),dst);
728  if(itor == route.end()) {
729  return false;
730  }
731 
732  LOG_AI << "group has " << units.size() << " members\n";
733 
735 
736  size_t direction = 0;
737 
738  //find the direction the group is moving in
739  if(itor+1 != route.end()) {
740  next = *(itor+1);
741  } else if(itor != route.begin()) {
742  next = *(itor-1);
743  }
744 
745  if(next.valid()) {
746  map_location adj[6];
747  get_adjacent_tiles(dst,adj);
748 
749  direction = std::find(adj,adj+6,next) - adj;
750  }
751 
752  std::deque<map_location> preferred_moves;
753  preferred_moves.push_back(dst);
754 
755  std::map<map_location,pathfind::paths> possible_moves;
756  move_map srcdst, dstsrc;
757  calculate_possible_moves(possible_moves,srcdst,dstsrc,false);
758 
759  bool gamestate_changed = false;
760 
761  for(std::set<map_location>::const_iterator i = units.begin(); i != units.end(); ++i) {
762  const unit_map::const_iterator un = units_.find(*i);
763  if(un == units_.end()) {
764  continue;
765  }
766 
767  map_location best_loc;
768  int best_defense = -1;
769  for(std::deque<map_location>::const_iterator j = preferred_moves.begin(); j != preferred_moves.end(); ++j) {
770  if(units_.count(*j)) {
771  continue;
772  }
773 
774  const std::pair<move_map::const_iterator,move_map::const_iterator> itors = dstsrc.equal_range(*j);
775  move_map::const_iterator m;
776  for(m = itors.first; m != itors.second; ++m) {
777  if(m->second == *i) {
778  break;
779  }
780  }
781 
782  if(m == itors.second) {
783  continue;
784  }
785 
786  int defense = un->defense_modifier(map_.get_terrain(*j));
787  if(best_loc.valid() == false || defense < best_defense) {
788  best_loc = *j;
789  best_defense = defense;
790  }
791  }
792 
793  if(best_loc.valid()) {
794  move_result_ptr move_res = execute_move_action(*i,best_loc);
795  gamestate_changed |= move_res->is_gamestate_changed();
796 
797 
798  //if we were ambushed or something went wrong, abort the group's movement.
799  if (!move_res->is_ok()) {
800  return gamestate_changed;
801  }
802 
803  preferred_moves.erase(std::find(preferred_moves.begin(),preferred_moves.end(),best_loc));
804 
805  //find locations that are 'perpendicular' to the direction of movement for further units to move to.
806  map_location adj[6];
807  get_adjacent_tiles(best_loc,adj);
808  for(size_t n = 0; n != 6; ++n) {
809  if(n != direction && ((n+3)%6) != direction && map_.on_board(adj[n]) &&
810  units_.count(adj[n]) == 0 && std::count(preferred_moves.begin(),preferred_moves.end(),adj[n]) == 0) {
811  preferred_moves.push_front(adj[n]);
812  LOG_AI << "added moves: " << adj[n].wml_x() << "," << adj[n].wml_y() << "\n";
813  }
814  }
815  } else {
816  LOG_AI << "Could not move group member to any of " << preferred_moves.size() << " locations\n";
817  }
818  }
819 
820  return gamestate_changed;
821 }
822 
823 
824 double move_to_targets_phase::rate_group(const std::set<map_location>& group, const std::vector<map_location>& battlefield) const
825 {
826  unit_map &units_ = resources::gameboard->units();
827  const gamemap &map_ = resources::gameboard->map();
828 
829  double strength = 0.0;
830  for(std::set<map_location>::const_iterator i = group.begin(); i != group.end(); ++i) {
831  const unit_map::const_iterator u = units_.find(*i);
832  if(u == units_.end()) {
833  continue;
834  }
835 
836  const unit &un = *u;
837 
838  int defense = 0;
839  for(std::vector<map_location>::const_iterator j = battlefield.begin(); j != battlefield.end(); ++j) {
840  defense += un.defense_modifier(map_.get_terrain(*j));
841  }
842 
843  defense /= battlefield.size();
844 
845  int best_attack = 0;
846  for(const attack_type& a : un.attacks()) {
847  const int attack_strength = a.num_attacks() * a.damage();
848  best_attack = std::max<int>(attack_strength, best_attack);
849  }
850 
851  const int rating = (defense*best_attack*un.hitpoints())/(100*un.max_hitpoints());
852  strength += double(rating);
853  }
854 
855  return strength;
856 }
857 
858 
859 
861  const move_map& srcdst, const move_map& dstsrc, const move_map& enemy_dstsrc,
862  double caution)
863 {
864  if(caution <= 0.0) {
865  return false;
866  }
867 
868  double optimal_terrain = best_defensive_position(un->get_location(), dstsrc,
869  srcdst, enemy_dstsrc).chance_to_hit/100.0;
870  const double proposed_terrain =
871  un->defense_modifier(resources::gameboard->map().get_terrain(loc))/100.0;
872 
873  // The 'exposure' is the additional % chance to hit
874  // this unit receives from being on a sub-optimal defensive terrain.
875  const double exposure = proposed_terrain - optimal_terrain;
876 
877  const double our_power = power_projection(loc,dstsrc);
878  const double their_power = power_projection(loc,enemy_dstsrc);
879  return caution*their_power*(1.0+exposure) > our_power;
880 }
881 
882 } // end of namespace ai_default_rca
883 
884 } // 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:607
virtual std::string get_grouping() const override
Definition: contexts.hpp:742
#define LOG_AI
virtual const unit_map & units() const
Definition: game_board.hpp:97
unit_iterator end()
Definition: map.hpp:415
This class represents a single unit of a specific type.
Definition: unit.hpp:101
bool operator()(const rated_target &a, const rated_target &b) const
size_t count(const map_location &loc) const
Definition: map.hpp:400
double value
Definition: contexts.hpp:50
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.
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.hpp:299
double get_score() const
Get the usual score of the candidate action without re-evaluation.
Definition: rca.cpp:72
bool is_enemy(int n) const
Definition: team.hpp:241
virtual const move_map & get_srcdst() const override
Definition: contexts.hpp:851
std::shared_ptr< move_result > move_result_ptr
Definition: game_info.hpp:100
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:55
static lg::log_domain log_ai_testing_ca_move_to_targets("ai/ca/move_to_targets")
int wml_y() const
Definition: location.hpp:116
bool match(const map_location &loc) const
Definition: filter.hpp:43
static double getNoPathValue()
Definition: pathfind.hpp:63
#define b
t_translation::terrain_code get_terrain(const map_location &loc) const
Looks up terrain at a particular location.
Definition: map.cpp:301
double cost(const map_location &loc, const double) const
std::multimap< map_location, map_location > move_map
The standard way in which a map of possible moves is recorded.
Definition: game_info.hpp:45
A small explanation about what'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.
int wml_x() const
Definition: location.hpp:115
virtual std::vector< target > find_targets(const move_map &enemy_dstsrc)
Definition: contexts.hpp:226
Structure which holds a single route between one location and another.
Definition: pathfind.hpp:131
bool valid() const
Definition: location.hpp:72
virtual const std::vector< target > & additional_targets() const
Definition: contexts.hpp:202
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.hpp:382
int hitpoints() const
The current number of hitpoints this unit has.
Definition: unit.hpp:394
TYPE type
Definition: contexts.hpp:52
std::vector< target >::iterator tg
int w() const
Effective map width.
Definition: map.hpp:90
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:34
int max_hitpoints() const
The max number of hitpoints this unit can have.
Definition: unit.hpp:400
int defense_modifier(const t_translation::terrain_code &terrain) const
The unit's defense on a given terrain.
Definition: unit.cpp:1535
virtual const move_map & get_enemy_dstsrc() const override
Definition: contexts.hpp:706
#define log_scope2(domain, description)
Definition: log.hpp:187
static const ::config * terrain
The terrain used to create the cache.
Definition: minimap.cpp:133
double rate_group(const std::set< map_location > &group, const std::vector< map_location > &battlefield) const
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:40
plain_route a_star_search(const map_location &src, const map_location &dst, double stop_at, const cost_calculator &calc, const size_t width, const size_t height, const teleport_map *teleports, bool border)
#define DBG_AI
int h() const
Effective map height.
Definition: map.hpp:93
virtual const team & current_team() const override
Definition: contexts.hpp:536
const std::set< std::string > movetype::effects defense
Definition: movetype.cpp:782
attack_itors attacks()
Gets an iterator over this unit's attacks.
Definition: unit.hpp:786
virtual double power_projection(const map_location &loc, const move_map &dstsrc) const override
Function which finds how much 'power' a side can attack a certain location with.
Definition: contexts.hpp:803
int movement_cost(const t_translation::terrain_code &terrain) const
Get the unit's movement cost on a particular terrain.
Definition: unit.hpp:1225
virtual double get_scout_village_targeting() const override
Definition: contexts.hpp:857
#define i
virtual side_number get_side() const override
Get the side number.
Definition: contexts.hpp:477
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:773
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
virtual const gamemap & map() const
Definition: game_board.hpp:96
bool on_board(const map_location &loc) const
Tell if a location is on the map.
Definition: map.cpp:369
#define next(ls)
Definition: llex.cpp:32
Strategic movement routine, for experimentation.
virtual const move_map & get_dstsrc() const override
Definition: contexts.hpp:700
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:585
defensive_position const & 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:619
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:259
Container associating units to locations.
Definition: map.hpp:99
double compare_groups(const std::set< map_location > &our_group, const std::set< map_location > &their_group, const std::vector< map_location > &battlefield) const
unit_iterator find(size_t id)
Definition: map.cpp:311
A config object defines a single node in a WML file, with access to child nodes.
Definition: config.hpp:93
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:1030
rated_target(const std::vector< target >::iterator &t, double r)
virtual double get_caution() const override
Definition: contexts.hpp:694
static map_location::DIRECTION n
This module contains various pathfinding functions and utilities.
virtual bool get_simple_targeting() const override
Definition: contexts.hpp:863
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
unit_map * units
Definition: resources.cpp:34
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.