Debian Codegraph @

CorsixTH/Src/th_pathfind.h

raw
1 /*
2 Copyright (c) 2009 Peter "Corsix" Cawley
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this software and associated documentation files (the "Software"), to deal in
6 the Software without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
8 of the Software, and to permit persons to whom the Software is furnished to do
9 so, subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20 SOFTWARE.
21 */
22
23 #ifndef CORSIX_TH_TH_PATHFIND_H_
24 #define CORSIX_TH_TH_PATHFIND_H_
25
26 #include "config.h"
27
28 #include <cstdint>
29 #include <vector>
30
31 #include "lua.hpp"
32
33 class level_map;
34 class lua_persist_reader;
35 class lua_persist_writer;
36 class pathfinder;
37 enum class object_type : uint8_t;
38 struct map_tile_flags;
39
40 /** Directions of movement. */
41 enum class travel_direction {
42 north = 0, ///< Move to the north.
43 east = 1, ///< Move to the east.
44 south = 2, ///< Move to the south.
45 west = 3 ///< Move to the west.
46 };
47
48 /** Node in the path finder routines. */
49 struct path_node {
50 //! Pointer to the previous node in the path to this cell.
51 /*!
52 Points to nullptr if this is the first cell in the path, or points to
53 itself if it is not part of a path.
54 */
55 const path_node* prev;
56
57 //! X-position of this cell (constant)
58 int x;
59
60 //! Y-position of this cell (constant)
61 int y;
62
63 //! Current shortest distance to this cell
64 /*!
65 Defined as prev->distance + 1 (or 0 if prev == nullptr).
66 Value is undefined if not part of a path.
67 */
68 int distance;
69
70 //! Minimum distance from this cell to the goal
71 /*!
72 Value is only dependent upon the cell position and the goal
73 position, and is undefined if not part of a path.
74 */
75 int guess;
76
77 //! Index of this cell in the open heap
78 /*!
79 If the cell is not in the open heap, then this value is undefined.
80 */
81 size_t open_idx;
82
83 //! True if the cell has already been visited (popped from the open heap)
84 bool visited;
85
86 //! Total cost of this node.
87 /*!
88 @return Total cost of the node, traveled distance and guess to the
89 destination.
90 */
91 inline int value() const { return distance + guess; }
92 };
93
94 /** Base class of the path finders. */
95 class abstract_pathfinder {
96 public:
97 abstract_pathfinder(pathfinder* pf);
98 virtual ~abstract_pathfinder() = default;
99
100 //! Initialize the path finder.
101 /*!
102 @param pMap Map to search on.
103 @param iStartX X coordinate of the start position.
104 @param iStarty Y coordinate of the start position.
105 @return The initial node to expand.
106 */
107 path_node* init(const level_map* pMap, int iStartX, int iStarty);
108
109 //! Expand the \a pNode to its neighbours.
110 /*!
111 @param pNode Node to expand.
112 @param flags Flags of the node.
113 @param iWidth Width of the map.
114 @return Whether the search is done.
115 */
116 bool search_neighbours(path_node* pNode, map_tile_flags flags, int iWidth);
117
118 void record_neighbour_if_passable(path_node* pNode,
119 map_tile_flags neighbour_flags,
120 bool passable, path_node* pNeighbour);
121
122 //! Guess distance to the destination for \a pNode.
123 /*!
124 @param pNode Node to fill.
125 */
126 virtual int guess_distance(path_node* pNode) = 0;
127
128 //! Try the \a pNeighbour node.
129 /*!
130 @param pNode Source node.
131 @param flags Flags of the node.
132 @param pNeighbour Neighbour of \a pNode to try.
133 @param direction Direction of travel.
134 @return Whether the search is done.
135 */
136 virtual bool try_node(path_node* pNode, map_tile_flags flags,
137 path_node* pNeighbour, travel_direction direction) = 0;
138
139 protected:
140 pathfinder* parent; ///< Path finder parent object, containing shared data.
141 const level_map* map; ///< Map being searched.
142 };
143
144 class basic_pathfinder : public abstract_pathfinder {
145 public:
146 explicit basic_pathfinder(pathfinder* pf)
147 : abstract_pathfinder(pf), destination_x(0), destination_y(0) {}
148
149 int guess_distance(path_node* pNode) override;
150 bool try_node(path_node* pNode, map_tile_flags flags, path_node* pNeighbour,
151 travel_direction direction) override;
152
153 bool find_path(const level_map* pMap, int iStartX, int iStartY, int iEndX,
154 int iEndY);
155
156 int destination_x; ///< X coordinate of the destination of the path.
157 int destination_y; ///< Y coordinate of the destination of the path.
158 };
159
160 class hospital_finder : public abstract_pathfinder {
161 public:
162 explicit hospital_finder(pathfinder* pf) : abstract_pathfinder(pf) {}
163
164 int guess_distance(path_node* pNode) override;
165 bool try_node(path_node* pNode, map_tile_flags flags, path_node* pNeighbour,
166 travel_direction direction) override;
167
168 bool find_path_to_hospital(const level_map* pMap, int iStartX, int iStartY);
169 };
170
171 class idle_tile_finder : public abstract_pathfinder {
172 public:
173 explicit idle_tile_finder(pathfinder* pf)
174 : abstract_pathfinder(pf),
175 best_next_node(nullptr),
176 best_distance(0),
177 start_x(0),
178 start_y(0) {}
179
180 int guess_distance(path_node* pNode) override;
181 bool try_node(path_node* pNode, map_tile_flags flags, path_node* pNeighbour,
182 travel_direction direction) override;
183
184 //| Find a tile for idling.
185 /*!
186 @param pMap Map to search.
187 @param iStartX X coordinate of the start position.
188 @param iStartY Y coordinate of the start position.
189 @param iN Return the Nth idle tile. Used for queueing and randomizing idle
190 tiles.
191 @param parcelId Id of the parcel with valid destinations, use \c 0 for
192 any parcel.
193 */
194 bool find_idle_tile(const level_map* pMap, int iStartX, int iStartY, int iN,
195 int parcelId);
196
197 path_node* best_next_node;
198 double best_distance;
199 int start_x; ///< X coordinate of the start position.
200 int start_y; ///< Y coordinate of the start position.
201 };
202
203 class object_visitor : public abstract_pathfinder {
204 public:
205 explicit object_visitor(pathfinder* pf)
206 : abstract_pathfinder(pf),
207 L(nullptr),
208 visit_function_index{},
209 max_distance{},
210 target_any_object_type{},
211 target{} {}
212
213 int guess_distance(path_node* pNode) override;
214 bool try_node(path_node* pNode, map_tile_flags flags, path_node* pNeighbour,
215 travel_direction direction) override;
216
217 bool visit_objects(const level_map* pMap, int iStartX, int iStartY,
218 object_type eTHOB, int iMaxDistance, lua_State* L,
219 int iVisitFunction, bool anyObjectType);
220
221 lua_State* L;
222 int visit_function_index;
223 int max_distance;
224 bool target_any_object_type;
225 object_type target;
226 };
227
228 //! Finds paths through maps
229 /*!
230 A pathfinder is used for finding a path through a map. A single pathfinder
231 instance is not reentrant, but separate instances are. Users of the class
232 should call find_path() to test if there is a path between two points on a
233 map, and then use get_path_length() and/or push_result() to get the actual
234 path.
235
236 Internally, the A* search algorithm is used. The open set is implemented as
237 a heap in open_heap, and there is no explicit closed set. For each cell
238 of the map, a path_node structure is created (and cached between searches if
239 the map size is constant), which holds information about said map cell in
240 the current search. The algorithm is implemented in such a way that most
241 path find operations do not need to allocate (or free) any memory.
242 */
243 class pathfinder {
244 public:
245 pathfinder();
246 ~pathfinder();
247
248 void set_default_map(const level_map* pMap);
249
250 inline bool find_path(const level_map* pMap, int iStartX, int iStartY,
251 int iEndX, int iEndY) {
252 return basic_pathfinder.find_path(pMap, iStartX, iStartY, iEndX, iEndY);
253 }
254
255 inline bool find_idle_tile(const level_map* pMap, int iStartX, int iStartY,
256 int iN, int parcelId) {
257 return idle_tile_finder.find_idle_tile(pMap, iStartX, iStartY, iN,
258 parcelId);
259 }
260
261 inline bool find_path_to_hospital(const level_map* pMap, int iStartX,
262 int iStartY) {
263 return hospital_finder.find_path_to_hospital(pMap, iStartX, iStartY);
264 }
265
266 inline bool visit_objects(const level_map* pMap, int iStartX, int iStartY,
267 object_type eTHOB, int iMaxDistance, lua_State* L,
268 int iVisitFunction, bool anyObjectType) {
269 return object_visitor.visit_objects(pMap, iStartX, iStartY, eTHOB,
270 iMaxDistance, L, iVisitFunction,
271 anyObjectType);
272 }
273
274 int get_path_length() const;
275 bool get_path_end(int* pX, int* pY) const;
276 void push_result(lua_State* L) const;
277
278 void persist(lua_persist_writer* pWriter) const;
279 void depersist(lua_persist_reader* pReader);
280
281 //! Allocate node cache for all tiles of the map.
282 /*!
283 @param iWidth Width of the map.
284 @param iHeight Height of the map.
285 */
286 void allocate_node_cache(int iWidth, int iHeight);
287
288 path_node* pop_from_open_heap();
289 void push_to_open_heap(path_node* pNode);
290 void open_heap_promote(path_node* pNode);
291
292 const level_map* default_map;
293
294 //! 2D array of nodes, one for each map cell
295 std::vector<path_node> nodes;
296
297 //! Array of "dirty" nodes which need to be reset before the next path find
298 /*!
299 This array is always large enough to hold every single node, and
300 #dirty_node_count holds the number of items currently in the array.
301 */
302 path_node** dirty_node_list;
303
304 //! Heap of not yet evaluated nodes as a 0-based array
305 /*!
306 This array conforms to the conditions:
307 value(i) <= value(i * 2 + 1)
308 value(i) <= value(i * 2 + 2)
309 This causes the array to be a minimum binary heap.
310 */
311 std::vector<path_node*> open_heap;
312
313 path_node* destination;
314 int node_cache_width;
315 int node_cache_height;
316 int dirty_node_count;
317
318 private:
319 ::basic_pathfinder basic_pathfinder;
320 ::hospital_finder hospital_finder;
321 ::idle_tile_finder idle_tile_finder;
322 ::object_visitor object_visitor;
323 };
324
325 #endif // CORSIX_TH_TH_PATHFIND_H_