| 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_ |