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