The Battle for Wesnoth  1.17.0-dev
astarsearch.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2005 - 2021
3  by Guillaume Melquiond <guillaume.melquiond@gmail.com>
4  Copyright (C) 2003 by David White <dave@whitevine.net>
5  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
6 
7  This program is free software; you can redistribute it and/or modify
8  it under the terms of the GNU General Public License as published by
9  the Free Software Foundation; either version 2 of the License, or
10  (at your option) any later version.
11  This program is distributed in the hope that it will be useful,
12  but WITHOUT ANY WARRANTY.
13 
14  See the COPYING file for more details.
15 */
16 
17 #include "log.hpp"
18 #include "map/map.hpp"
19 #include "pathfind/pathfind.hpp"
20 #include "pathfind/teleport.hpp"
21 
22 #include <queue>
23 #include <map>
24 
25 static lg::log_domain log_engine("engine");
26 #define LOG_PF LOG_STREAM(info, log_engine)
27 #define DBG_PF LOG_STREAM(debug, log_engine)
28 #define ERR_PF LOG_STREAM(err, log_engine)
29 
30 namespace pathfind {
31 
32 
33 namespace {
34 double heuristic(const map_location& src, const map_location& dst)
35 {
36  // We will mainly use the distances in hexes
37  // but we subtract a tiny bonus for shorter Euclidean distance
38  // based on how the path looks on the screen.
39 
40  // 0.75 comes from the horizontal hex imbrication
41  double xdiff = (src.x - dst.x) * 0.75;
42  // we must add 0.5 to the y coordinate when x is odd
43  double ydiff = (src.y - dst.y) + ((src.x & 1) - (dst.x & 1)) * 0.5;
44 
45  // we assume a map with a maximum diagonal of 300 (bigger than a 200x200)
46  // and we divide by 90000 * 10000 to avoid interfering with the defense subcost
47  // (see shortest_path_calculator::cost)
48  // NOTE: In theory, such heuristic is barely 'admissible' for A*,
49  // But not a problem for our current A* (we use heuristic only for speed)
50  // Plus, the euclidean fraction stay below the 1MP minimum and is also
51  // a good heuristic, so we still find the shortest path efficiently.
52  return distance_between(src, dst) + (xdiff*xdiff + ydiff*ydiff) / 900000000.0;
53 
54  // TODO: move the heuristic function into the cost_calculator
55  // so we can use case-specific heuristic
56  // and clean the definition of these numbers
57 }
58 
59 // values 0 and 1 mean uninitialized
60 const unsigned bad_search_counter = 0;
61 // The number of nodes already processed.
62 static unsigned search_counter = bad_search_counter;
63 
64 struct node {
65  double g, h, t;
67  /**
68  * If equal to search_counter, the node is off the list.
69  * If equal to search_counter + 1, the node is on the list.
70  * Otherwise it is outdated.
71  */
72  unsigned in;
73 
74  node()
75  : g(1e25)
76  , h(1e25)
77  , t(1e25)
78  , curr()
79  , prev()
80  , in(bad_search_counter)
81  {
82  }
83  node(double s, const map_location &c, const map_location &p, const map_location &dst, bool i, const teleport_map* teleports):
84  g(s), h(heuristic(c, dst)), t(g + h), curr(c), prev(p), in(search_counter + i)
85  {
86  if (teleports && !teleports->empty()) {
87 
88  double new_srch = 1.0;
89  auto sources = teleports->get_sources();
90 
91  std::set<map_location>::const_iterator it = sources.begin();
92  for(; it != sources.end(); ++it) {
93  const double tmp_srch = heuristic(c, *it);
94  if (tmp_srch < new_srch) { new_srch = tmp_srch; }
95  }
96 
97  double new_dsth = 1.0;
98  auto targets = teleports->get_targets();
99 
100  for(it = targets.begin(); it != targets.end(); ++it) {
101  const double tmp_dsth = heuristic(*it, dst);
102  if (tmp_dsth < new_dsth) { new_dsth = tmp_dsth; }
103  }
104 
105  double new_h = new_srch + new_dsth + 1.0;
106  if (new_h < h) {
107  h = new_h;
108  t = g + h;
109  }
110  }
111  }
112 
113  bool operator<(const node& o) const {
114  return t < o.t;
115  }
116 };
117 
118 class comp {
119  const std::vector<node>& nodes_;
120 
121 public:
122  comp(const std::vector<node>& n) : nodes_(n) { }
123  bool operator()(int a, int b) const {
124  return nodes_[b] < nodes_[a];
125  }
126 };
127 
128 class indexer {
129  std::size_t w_;
130 
131 public:
132  indexer(std::size_t w) : w_(w) { }
133  std::size_t operator()(const map_location& loc) const {
134  return loc.y * w_ + loc.x;
135  }
136 };
137 }//anonymous namespace
138 
139 
141  double stop_at, const cost_calculator& calc,
142  const std::size_t width, const std::size_t height,
143  const teleport_map *teleports, bool border) {
144  //----------------- PRE_CONDITIONS ------------------
145  assert(src.valid(width, height, border));
146  assert(dst.valid(width, height, border));
147  assert(stop_at <= calc.getNoPathValue());
148  //---------------------------------------------------
149 
150  DBG_PF << "A* search: " << src << " -> " << dst << '\n';
151 
152  if (calc.cost(dst, 0) >= stop_at) {
153  LOG_PF << "aborted A* search because Start or Dest is invalid\n";
154  plain_route locRoute;
155  locRoute.move_cost = static_cast<int>(calc.getNoPathValue());
156  return locRoute;
157  }
158 
159  // increment search_counter but skip the range equivalent to uninitialized
160  search_counter += 2;
161  if (search_counter - bad_search_counter <= 1u)
162  search_counter += 2;
163 
164  static std::vector<node> nodes;
165  nodes.resize(width * height); // this create uninitialized nodes
166 
167  indexer index(width);
168  comp node_comp(nodes);
169 
170  nodes[index(dst)].g = stop_at + 1;
171  nodes[index(src)] = node(0, src, map_location::null_location(), dst, true, teleports);
172 
173  std::vector<int> pq;
174  pq.push_back(index(src));
175 
176  while (!pq.empty()) {
177  node& n = nodes[pq.front()];
178 
179  n.in = search_counter;
180 
181  std::pop_heap(pq.begin(), pq.end(), node_comp);
182  pq.pop_back();
183 
184  if (n.t >= nodes[index(dst)].g) break;
185 
186  std::vector<map_location> locs(6);
187  get_adjacent_tiles(n.curr, locs.data());
188 
189  if (teleports && !teleports->empty()) {
190  auto allowed_teleports = teleports->get_adjacents(n.curr);
191  locs.insert(locs.end(), allowed_teleports.begin(), allowed_teleports.end());
192  }
193 
194  for(auto i = locs.rbegin(); i != locs.rend(); ++i) {
195  const map_location& loc = *i;
196 
197  if (!loc.valid(width, height, border)) continue;
198  if (loc == n.curr) continue;
199  node& next = nodes[index(loc)];
200 
201  double thresh = (next.in - search_counter <= 1u) ? next.g : stop_at + 1;
202  // cost() is always >= 1 (assumed and needed by the heuristic)
203  if (n.g + 1 >= thresh) continue;
204  double cost = n.g + calc.cost(loc, n.g);
205  if (cost >= thresh) continue;
206 
207  bool in_list = next.in == search_counter + 1;
208 
209  next = node(cost, loc, n.curr, dst, true, teleports);
210 
211  if (in_list) {
212  std::push_heap(pq.begin(), std::find(pq.begin(), pq.end(), static_cast<int>(index(loc))) + 1, node_comp);
213  } else {
214  pq.push_back(index(loc));
215  std::push_heap(pq.begin(), pq.end(), node_comp);
216  }
217  }
218  }
219 
220  plain_route route;
221  if (nodes[index(dst)].g <= stop_at) {
222  DBG_PF << "found solution; calculating it...\n";
223  route.move_cost = static_cast<int>(nodes[index(dst)].g);
224  for (node curr = nodes[index(dst)]; curr.prev != map_location::null_location(); curr = nodes[index(curr.prev)]) {
225  route.steps.push_back(curr.curr);
226  }
227  route.steps.push_back(src);
228  std::reverse(route.steps.begin(), route.steps.end());
229  } else {
230  LOG_PF << "aborted a* search " << "\n";
231  route.move_cost = static_cast<int>(calc.getNoPathValue());
232  }
233 
234  return route;
235 }
236 
237 
238 }//namespace pathfind
const std::vector< node > & nodes
void get_adjacent_tiles(const map_location &a, map_location *res)
Function which, given a location, will place all adjacent locations in res.
Definition: location.cpp:475
#define a
bool empty() const
Definition: teleport.hpp:134
std::set< map_location > get_adjacents(map_location loc) const
Definition: teleport.cpp:234
static double getNoPathValue()
Definition: pathfind.hpp:65
#define b
Structure which holds a single route between one location and another.
Definition: pathfind.hpp:132
bool valid() const
Definition: location.hpp:89
const std::vector< node > & nodes_
#define LOG_PF
Definition: astarsearch.cpp:26
int move_cost
Movement cost for reaching the end of the route.
Definition: pathfind.hpp:137
Encapsulates the map of the game.
Definition: location.hpp:38
std::size_t i
Definition: function.cpp:967
mock_party p
static map_location::DIRECTION s
double g
Definition: astarsearch.cpp:65
static bool operator<(const placing_info &a, const placing_info &b)
Definition: game_state.cpp:140
map_location curr
Definition: astarsearch.cpp:66
int w
std::size_t index(const std::string &str, const std::size_t index)
Codepoint index corresponding to the nth character in a UTF-8 string.
Definition: unicode.cpp:72
static lg::log_domain log_engine("engine")
double h
Definition: astarsearch.cpp:65
#define next(ls)
Definition: llex.cpp:32
std::size_t distance_between(const map_location &a, const map_location &b)
Function which gives the number of hexes between two tiles (i.e.
Definition: location.cpp:546
double t
Definition: astarsearch.cpp:65
virtual double cost(const map_location &loc, const double so_far) const =0
map_location prev
Definition: astarsearch.cpp:66
Standard logging facilities (interface).
static const map_location & null_location()
Definition: location.hpp:81
static void reverse(lua_State *L, StkId from, StkId to)
Definition: lapi.cpp:203
#define DBG_PF
Definition: astarsearch.cpp:27
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)
mock_char c
static map_location::DIRECTION n
std::size_t w_
unsigned in
If equal to search_counter, the node is off the list.
Definition: astarsearch.cpp:72
This module contains various pathfinding functions and utilities.