Debian Codegraph @

engine/core/pathfinder/routepather/multilayersearch.h

raw
1 /***************************************************************************
2 * Copyright (C) 2005-2019 by the FIFE team *
3 * http://www.fifengine.net *
4 * This file is part of FIFE. *
5 * *
6 * FIFE is free software; you can redistribute it and/or *
7 * modify it under the terms of the GNU Lesser General Public *
8 * License as published by the Free Software Foundation; either *
9 * version 2.1 of the License, or (at your option) any later version. *
10 * *
11 * This library is distributed in the hope that it will be useful, *
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
14 * Lesser General Public License for more details. *
15 * *
16 * You should have received a copy of the GNU Lesser General Public *
17 * License along with this library; if not, write to the *
18 * Free Software Foundation, Inc., *
19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA *
20 ***************************************************************************/
21
22 #ifndef FIFE_PATHFINDER_MULTILAYERSEARCH
23 #define FIFE_PATHFINDER_MULTILAYERSEARCH
24
25 // Standard C++ library includes
26
27 // 3rd party library includes
28
29 // FIFE includes
30 // These includes are split up in two parts, separated by one empty line
31 // First block: files included from the FIFE root src directory
32 // Second block: files included from the same folder
33 #include "util/structures/priorityqueue.h"
34
35 #include "routepathersearch.h"
36
37 namespace FIFE {
38
39 class CellCache;
40 class Route;
41 class Zone;
42
43 /** MultiLayerSearch using A*
44 */
45 class MultiLayerSearch: public RoutePatherSearch {
46 public:
47 /** Constructor
48 *
49 * @param route A pointer to the route for which a path should be searched.
50 * @param sessionId A integer containing the session id for this search.
51 */
52 MultiLayerSearch(Route* route, const int32_t sessionId);
53
54 /** Destructor
55 */
56 ~MultiLayerSearch();
57
58 /** Updates the search.
59 *
60 * Each update checks all neighbors of the last checked coordinate and selects the most favorable.
61 */
62 void updateSearch();
63
64 /** Calculates final path.
65 *
66 * If the search is successful then a path is created.
67 */
68 void calcPath();
69
70 private:
71 /** Creates or resets the SearchFrontier.
72 *
73 * @param startInt The start coordinate as integer identifier.
74 * @param cache A pointer to the start CellCache.
75 */
76 void createSearchFrontier(int32_t startInt, CellCache* cache);
77
78 /** Calculates path parts per layer.
79 *
80 */
81 void calcPathStep();
82
83 /** Fetch targets from neighbor layers.
84 *
85 */
86 void searchBetweenTargetsNeighbor();
87
88 /** Fetch targets from map.
89 *
90 */
91 void searchBetweenTargetsMap();
92
93 //! A location object representing where the search started.
94 Location m_to;
95 //! A location object representing where the search ended.
96 Location m_from;
97
98 //! A pointer to the start CellCache.
99 CellCache* m_startCache;
100 //! A pointer to the end CellCache.
101 CellCache* m_endCache;
102 //! A pointer to the currently used CellCache.
103 CellCache* m_currentCache;
104
105 // A pointer to the start Zone.
106 Zone* m_startZone;
107 // A pointer to the end Zone.
108 Zone* m_endZone;
109
110 //! The start coordinate as an int32_t.
111 int32_t m_startCoordInt;
112 //! The last used start coordinate as an int32_t.
113 int32_t m_lastStartCoordInt;
114 //! The destination coordinate as an int32_t.
115 int32_t m_destCoordInt;
116 //! The last used destination coordinate as an int32_t.
117 int32_t m_lastDestCoordInt;
118 //! The next coordinate to check out.
119 int32_t m_next;
120
121 //! The shortest path tree.
122 std::vector<int32_t> m_spt;
123 //! The search frontier.
124 std::vector<int32_t> m_sf;
125 //! A table to hold the costs.
126 std::vector<double> m_gCosts;
127 //! Priority queue to hold nodes on the sf in order.
128 PriorityQueue<int32_t, double> m_sortedFrontier;
129
130 //! List of targets that need to be solved to reach the real target.
131 std::list<Cell*> m_betweenTargets;
132 //! Indicates if last between target could be achieved
133 bool m_foundLast;
134 //! Path to which all steps are added.
135 Path m_path;
136 };
137 }
138 #endif