The Battle for Wesnoth  1.19.0-dev
pathutils_impl.hpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2018 - 2024
3  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
4 
5  This program is free software; you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation; either version 2 of the License, or
8  (at your option) any later version.
9  This program is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY.
11 
12  See the COPYING file for more details.
13 */
14 
15 #pragma once
16 
17 #include "map/location.hpp"
18 #include <set>
19 
20 /**
21  * Function that will add to @a result all elements of @a locs, plus all
22  * on-board (that is: all locs that match @a pred1) locations matching @a pred2
23  * that are connected to elements of
24  * locs by a chain of at most @a radius tiles, each of which matches @a pred2.
25  * @a result must be a std::set of locations.
26  *
27  * @a pred1 a fast predicate (used before cachecheck).
28  * @a pred2 a slow predicate (used after cachecheck).
29  */
30 template<typename FPred1, typename FPred2>
31 void get_tiles_radius(std::set<map_location>&& locs, size_t radius, std::set<map_location>& result, const FPred1& pred1, const FPred2& pred2)
32 {
33  typedef std::set<map_location> location_set;
34  location_set must_visit, filtered_out;
35  location_set not_visited = std::move(locs);
36 
37  for ( ; radius != 0 && !not_visited.empty(); --radius )
38  {
39  location_set::const_iterator it = not_visited.begin();
40  location_set::const_iterator it_end = not_visited.end();
41 
42  result.insert(it, it_end);
43  for(; it != it_end; ++it) {
44  for(const map_location& loc : get_adjacent_tiles(*it)) {
45  if( pred1(loc) ) {
46  if( !result.count(loc) && !filtered_out.count(loc) ) {
47  if( pred2(loc) ) {
48  must_visit.insert(loc);
49  }
50  else {
51  filtered_out.insert(loc);
52  }
53  }
54  }
55  }
56  }
57 
58  not_visited.swap(must_visit);
59  must_visit.clear();
60  }
61 
62  result.insert(not_visited.begin(), not_visited.end());
63 }
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::set< map_location > location_set
void get_tiles_radius(std::set< map_location > &&locs, size_t radius, std::set< map_location > &result, const FPred1 &pred1, const FPred2 &pred2)
Function that will add to result all elements of locs, plus all on-board (that is: all locs that matc...
Encapsulates the map of the game.
Definition: location.hpp:38