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