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)
41 double xdiff = (src.
x - dst.
x) * 0.75;
43 double ydiff = (src.
y - dst.
y) + ((src.
x & 1) - (dst.
x & 1)) * 0.5;
52 return distance_between(src, dst) + (xdiff*xdiff + ydiff*ydiff) / 900000000.0;
60 const unsigned bad_search_counter = 0;
62 static unsigned search_counter = bad_search_counter;
80 ,
in(bad_search_counter)
86 if (teleports && !teleports->empty()) {
88 double new_srch = 1.0;
89 auto sources = teleports->get_sources();
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; }
97 double new_dsth = 1.0;
98 auto targets = teleports->get_targets();
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; }
105 double new_h = new_srch + new_dsth + 1.0;
122 comp(
const std::vector<node>&
n) :
nodes_(
n) { }
123 bool operator()(
int a,
int b)
const {
132 indexer(std::size_t
w) :
w_(
w) { }
134 return loc.
y *
w_ + loc.
x;
142 const std::size_t width,
const std::size_t height,
145 assert(src.
valid(width, height, border));
146 assert(dst.
valid(width, height, border));
150 DBG_PF <<
"A* search: " << src <<
" -> " << dst;
152 if (calc.
cost(dst, 0) >= stop_at) {
153 LOG_PF <<
"aborted A* search because Start or Dest is invalid";
161 if (search_counter - bad_search_counter <= 1u)
164 static std::vector<node>
nodes;
165 nodes.resize(width * height);
167 indexer
index(width);
168 comp node_comp(
nodes);
174 pq.push_back(
index(src));
176 while (!pq.empty()) {
177 node&
n =
nodes[pq.front()];
179 n.in = search_counter;
181 std::pop_heap(pq.begin(), pq.end(), node_comp);
186 std::vector<map_location> locs(6);
189 if (teleports && !teleports->
empty()) {
191 locs.insert(locs.end(), allowed_teleports.begin(), allowed_teleports.end());
194 for(
auto i = locs.rbegin();
i != locs.rend(); ++
i) {
197 if (!loc.
valid(width, height, border))
continue;
198 if (loc ==
n.curr)
continue;
201 double thresh = (next.in - search_counter <= 1u) ? next.g : stop_at + 1;
203 if (
n.g + 1 >= thresh)
continue;
204 double cost =
n.g + calc.
cost(loc,
n.g);
205 if (cost >= thresh)
continue;
207 bool in_list = next.in == search_counter + 1;
209 next = node(cost, loc,
n.curr, dst,
true, teleports);
212 std::push_heap(pq.begin(), std::find(pq.begin(), pq.end(),
static_cast<int>(
index(loc))) + 1, node_comp);
214 pq.push_back(
index(loc));
215 std::push_heap(pq.begin(), pq.end(), node_comp);
222 DBG_PF <<
"found solution; calculating it...";
227 route.
steps.push_back(src);
228 std::reverse(route.
steps.begin(), route.
steps.end());
230 LOG_PF <<
"aborted a* search ";
static lg::log_domain log_engine("engine")
const std::vector< node > & nodes_
unsigned in
If equal to search_counter, the node is off the list.
std::set< map_location > get_adjacents(map_location loc) const
const std::vector< node > & nodes
static bool operator<(const placing_info &a, const placing_info &b)
void get_adjacent_tiles(const map_location &a, map_location *res)
Function which, given a location, will place all adjacent locations in res.
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.
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.
This module contains various pathfinding functions and utilities.
Encapsulates the map of the game.
static const map_location & null_location()
static double getNoPathValue()
virtual double cost(const map_location &loc, const double so_far) const =0
Structure which holds a single route between one location and another.
std::vector< map_location > steps
int move_cost
Movement cost for reaching the end of the route.
static map_location::DIRECTION n
static map_location::DIRECTION s