The Battle for Wesnoth  1.15.10+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  auto sources = teleports->get_sources();
89 
90  std::set<map_location>::const_iterator it = sources.begin();
91  for(; it != sources.end(); ++it) {
92  const double tmp_srch = heuristic(c, *it);
93  if (tmp_srch < new_srch) { new_srch = tmp_srch; }
94  }
95 
96  double new_dsth = 1.0;
97  auto targets = teleports->get_targets();
98 
99  for(it = targets.begin(); it != targets.end(); ++it) {
100  const double tmp_dsth = heuristic(*it, dst);
101  if (tmp_dsth < new_dsth) { new_dsth = tmp_dsth; }
102  }
103 
104  double new_h = new_srch + new_dsth + 1.0;
105  if (new_h < h) {
106  h = new_h;
107  t = g + h;
108  }
109  }
110  }
111 
112  bool operator<(const node& o) const {
113  return t < o.t;
114  }
115 };
116 
117 class comp {
118  const std::vector<node>& nodes_;
119 
120 public:
121  comp(const std::vector<node>& n) : nodes_(n) { }
122  bool operator()(int a, int b) const {
123  return nodes_[b] < nodes_[a];
124  }
125 };
126 
127 class indexer {
128  std::size_t w_;
129 
130 public:
131  indexer(std::size_t w) : w_(w) { }
132  std::size_t operator()(const map_location& loc) const {
133  return loc.y * w_ + loc.x;
134  }
135 };
136 }//anonymous namespace
137 
138 
140  double stop_at, const cost_calculator& calc,
141  const std::size_t width, const std::size_t height,
142  const teleport_map *teleports, bool border) {
143  //----------------- PRE_CONDITIONS ------------------
144  assert(src.valid(width, height, border));
145  assert(dst.valid(width, height, border));
146  assert(stop_at <= calc.getNoPathValue());
147  //---------------------------------------------------
148 
149  DBG_PF << "A* search: " << src << " -> " << dst << '\n';
150 
151  if (calc.cost(dst, 0) >= stop_at) {
152  LOG_PF << "aborted A* search because Start or Dest is invalid\n";
153  plain_route locRoute;
154  locRoute.move_cost = static_cast<int>(calc.getNoPathValue());
155  return locRoute;
156  }
157 
158  // increment search_counter but skip the range equivalent to uninitialized
159  search_counter += 2;
160  if (search_counter - bad_search_counter <= 1u)
161  search_counter += 2;
162 
163  static std::vector<node> nodes;
164  nodes.resize(width * height); // this create uninitialized nodes
165 
166  indexer index(width);
167  comp node_comp(nodes);
168 
169  nodes[index(dst)].g = stop_at + 1;
170  nodes[index(src)] = node(0, src, map_location::null_location(), dst, true, teleports);
171 
172  std::vector<int> pq;
173  pq.push_back(index(src));
174 
175  while (!pq.empty()) {
176  node& n = nodes[pq.front()];
177 
178  n.in = search_counter;
179 
180  std::pop_heap(pq.begin(), pq.end(), node_comp);
181  pq.pop_back();
182 
183  if (n.t >= nodes[index(dst)].g) break;
184 
185  std::vector<map_location> locs(6);
186  get_adjacent_tiles(n.curr, locs.data());
187 
188  if (teleports && !teleports->empty()) {
189  auto allowed_teleports = teleports->get_adjacents(n.curr);
190  locs.insert(locs.end(), allowed_teleports.begin(), allowed_teleports.end());
191  }
192 
193  for(auto i = locs.rbegin(); i != locs.rend(); ++i) {
194  const map_location& loc = *i;
195 
196  if (!loc.valid(width, height, border)) continue;
197  if (loc == n.curr) continue;
198  node& next = nodes[index(loc)];
199 
200  double thresh = (next.in - search_counter <= 1u) ? next.g : stop_at + 1;
201  // cost() is always >= 1 (assumed and needed by the heuristic)
202  if (n.g + 1 >= thresh) continue;
203  double cost = n.g + calc.cost(loc, n.g);
204  if (cost >= thresh) continue;
205 
206  bool in_list = next.in == search_counter + 1;
207 
208  next = node(cost, loc, n.curr, dst, true, teleports);
209 
210  if (in_list) {
211  std::push_heap(pq.begin(), std::find(pq.begin(), pq.end(), static_cast<int>(index(loc))) + 1, node_comp);
212  } else {
213  pq.push_back(index(loc));
214  std::push_heap(pq.begin(), pq.end(), node_comp);
215  }
216  }
217  }
218 
219  plain_route route;
220  if (nodes[index(dst)].g <= stop_at) {
221  DBG_PF << "found solution; calculating it...\n";
222  route.move_cost = static_cast<int>(nodes[index(dst)].g);
223  for (node curr = nodes[index(dst)]; curr.prev != map_location::null_location(); curr = nodes[index(curr.prev)]) {
224  route.steps.push_back(curr.curr);
225  }
226  route.steps.push_back(src);
227  std::reverse(route.steps.begin(), route.steps.end());
228  } else {
229  LOG_PF << "aborted a* search " << "\n";
230  route.move_cost = static_cast<int>(calc.getNoPathValue());
231  }
232 
233  return route;
234 }
235 
236 
237 }//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:132
std::set< map_location > get_adjacents(map_location loc) const
Definition: teleport.cpp:229
static double getNoPathValue()
Definition: pathfind.hpp:64
#define b
Structure which holds a single route between one location and another.
Definition: pathfind.hpp:131
bool valid() const
Definition: location.hpp:88
const std::vector< node > & nodes_
#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:37
std::size_t i
Definition: function.cpp:934
mock_party p
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:545
double t
Definition: astarsearch.cpp:64
virtual double cost(const map_location &loc, const double so_far) const =0
map_location prev
Definition: astarsearch.cpp:65
Standard logging facilities (interface).
static const map_location & null_location()
Definition: location.hpp:80
static void reverse(lua_State *L, StkId from, StkId to)
Definition: lapi.cpp:203
#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.