1 #ifndef _Pathfinder_h_ 2 #define _Pathfinder_h_ 3 4 #include "UniverseObject.h" 5 6 #include <vector> 7 #include <map> 8 #include <set> 9 #include <unordered_set> 10 11 #ifdef FREEORION_WIN32 12 // because the linker gets confused about Win32 API functions... 13 # undef GetObject 14 # undef GetObjectA 15 #endif 16 17 /** The Pathfinder class contains the locations of systems, the 18 * starlanes and functions to determine pathing and trip duration 19 * around the Universe. */ 20 class FO_COMMON_API Pathfinder { 21 public: 22 typedef std::shared_ptr<const Pathfinder> ConstPtr; 23 typedef std::shared_ptr<UniverseObjectVisitor> SystemExclusionPredicateType; 24 25 /** \name Structors */ //@{ 26 Pathfinder(); 27 virtual ~Pathfinder(); 28 //@} 29 30 /** \name Accessors */ //@{ 31 32 /** Returns the straight-line distance between the objects with the given 33 * IDs. \throw std::out_of_range This function will throw if either object 34 * ID is out of range. */ 35 double LinearDistance(int object1_id, int object2_id) const; 36 37 /** Returns the number of starlane jumps between the systems with the given 38 * IDs. If there is no path between the systems, -1 is returned. 39 * \throw std::out_of_range This function will throw if either system 40 * ID is not a valid system id. */ 41 short JumpDistanceBetweenSystems(int system1_id, int system2_id) const; 42 43 /** Returns the number of starlane jumps between any two objects, accounting 44 * for cases where one or the other are fleets / ships on starlanes between 45 * systems. Returns INT_MAX when no path exists, or either object does not 46 * exist. */ 47 int JumpDistanceBetweenObjects(int object1_id, int object2_id) const; 48 49 /** Returns the sequence of systems, including \a system1_id and 50 * \a system2_id, that defines the shortest path from \a system1 to 51 * \a system2, and the distance travelled to get there. If no such path 52 * exists, the list will be empty. Note that the path returned may be via 53 * one or more starlane, or may be "offroad". The path is calculated 54 * using the visibility for empire \a empire_id, or without regard to 55 * visibility if \a empire_id == ALL_EMPIRES. 56 * \throw std::out_of_range This function will throw if either system ID 57 * is out of range, or if the empire ID is not known. */ 58 std::pair<std::list<int>, double> ShortestPath(int system1_id, int system2_id, int empire_id = ALL_EMPIRES) const; 59 60 /** Shortest path known to an empire between two systems, excluding routes 61 * for systems containing objects for @p system_predicate. 62 * @param system1_id source System id 63 * @param system2_id destination System id 64 * @param empire_id ID of viewing Empire 65 * @param system_predicate UniverseObjectVisitor, A System is excluded as a potential node in any route 66 * if it is or contains a matched object 67 * 68 * @returns list of System ids, distance between systems */ 69 std::pair<std::list<int>, double> ShortestPath(int system1_id, int system2_id, int empire_id, 70 const SystemExclusionPredicateType& system_predicate) const; 71 72 /** Returns the shortest starlane path distance between any two objects, accounting 73 * for cases where one or the other are fleets / ships on starlanes between 74 * systems. Returns -1 when no path exists, or either object does not 75 * exist. */ 76 double ShortestPathDistance(int object1_id, int object2_id) const; 77 78 /** Returns the sequence of systems, including \a system1 and \a system2, 79 * that defines the path with the fewest jumps from \a system1 to 80 * \a system2, and the number of jumps to get there. If no such path 81 * exists, the list will be empty. The path is calculated using the 82 * visibility for empire \a empire_id, or without regard to visibility if 83 * \a empire_id == ALL_EMPIRES. \throw std::out_of_range This function 84 * will throw if either system ID is out of range or if the empire ID is 85 * not known. */ 86 std::pair<std::list<int>, int> LeastJumpsPath(int system1_id, int system2_id, int empire_id = ALL_EMPIRES, 87 int max_jumps = INT_MAX) const; 88 89 /** Returns whether there is a path known to empire \a empire_id between 90 * system \a system1 and system \a system2. The path is calculated using 91 * the visibility for empire \a empire_id, or without regard to visibility 92 * if \a empire_id == ALL_EMPIRES. \throw std::out_of_range This function 93 * will throw if either system ID is out of range or if the empire ID is 94 * not known. */ 95 bool SystemsConnected(int system1_id, int system2_id, int empire_id = ALL_EMPIRES) const; 96 97 /** Returns true iff \a system is reachable from another system (i.e. it 98 * has at least one known starlane to it). This does not guarantee that 99 * the system is reachable from any specific other system, as two separate 100 * groups of locally but not globally interconnected systems may exist. 101 * The starlanes considered depend on their visibility for empire 102 * \a empire_id, or without regard to visibility if 103 * \a empire_id == ALL_EMPIRES. */ 104 bool SystemHasVisibleStarlanes(int system_id, int empire_id = ALL_EMPIRES) const; 105 106 /** Returns the systems that are one starlane hop away from system 107 * \a system. The returned systems are indexed by distance from 108 * \a system. The neighborhood is calculated using the visibility 109 * for empire \a empire_id, or without regard to visibility if 110 * \a empire_id == ALL_EMPIRES. 111 * \throw std::out_of_range This function will throw if the system 112 * ID is out of range. */ 113 //TODO empire_id is never set to anything other than self, which in 114 //the AI's is the same as ALL_EMPIRES 115 std::multimap<double, int> ImmediateNeighbors(int system_id, int empire_id = ALL_EMPIRES) const; 116 117 /** Returns the system ids of systems that are within \p jumps of the \p 118 candidates system ids.*/ 119 std::unordered_set<int> WithinJumps(size_t jumps, const std::vector<int>& candidates) const; 120 121 /** Returns the partition (near, far) of the \p candidate objects into two sets, those that are within \p 122 jumps of the \p stationary objects and that are not.*/ 123 std::pair<std::vector<std::shared_ptr<const UniverseObject>>, 124 std::vector<std::shared_ptr<const UniverseObject>>> 125 WithinJumpsOfOthers( 126 int jumps, 127 const std::vector<std::shared_ptr<const UniverseObject>>& candidates, 128 const std::vector<std::shared_ptr<const UniverseObject>>& stationary) const; 129 130 /** Returns the id of the System object that is closest to the specified 131 * (\a x, \a y) location on the map, by direct-line distance. */ 132 int NearestSystemTo(double x, double y) const; 133 134 //@} 135 136 /** \name Mutators */ //@{ 137 138 /** Fills pathfinding data structure and determines least jumps distances 139 * between systems for the empire with id \a for_empire_id or uses the 140 * main / true / visible objects if \a for_empire_id is ALL_EMPIRES*/ 141 void InitializeSystemGraph(const std::vector<int> system_ids, int for_empire_id = ALL_EMPIRES); 142 143 /** Regenerates per-empire system view graphs by filtering the complete 144 * system graph based on empire visibility. Does not regenerate the base 145 * graph to account for actual system-starlane connectivity changes. */ 146 void UpdateEmpireVisibilityFilteredSystemGraphs(int for_empire_id = ALL_EMPIRES); 147 //@} 148 149 class PathfinderImpl; 150 private: 151 const std::unique_ptr<PathfinderImpl> pimpl; 152 }; 153 154 #endif // _Pathfinder_h_ 155