1 // _________ __ __
2 // / _____// |_____________ _/ |______ ____ __ __ ______
3 // \_____ \\ __\_ __ \__ \\ __\__ \ / ___\| | \/ ___/
4 // / \| | | | \// __ \| | / __ \_/ /_/ > | /\___ |
5 // /_______ /|__| |__| (____ /__| (____ /\___ /|____//____ >
6 // \/ \/ \//_____/ \/
7 // ______________________ ______________________
8 // T H E W A R B E G I N S
9 // Stratagus - A free fantasy real time strategy game engine
10 //
11 /**@name pathfinder.h - The path finder headerfile. */
12 //
13 // (c) Copyright 1998-2005 by Lutz Sammer, Russell Smith
14 //
15 // This program is free software; you can redistribute it and/or modify
16 // it under the terms of the GNU General Public License as published by
17 // the Free Software Foundation; only version 2 of the License.
18 //
19 // This program is distributed in the hope that it will be useful,
20 // but WITHOUT ANY WARRANTY; without even the implied warranty of
21 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 // GNU General Public License for more details.
23 //
24 // You should have received a copy of the GNU General Public License
25 // along with this program; if not, write to the Free Software
26 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
27 // 02111-1307, USA.
28 //
29
30 #ifndef __PATH_FINDER_H__
31 #define __PATH_FINDER_H__
32
33 //@{
34
35 #if defined(DEBUG_ASTAR)
36 #define AstarDebugPrint(x) DebugPrint(x)
37 #else
38 #define AstarDebugPrint(x)
39 #endif
40
41 /*----------------------------------------------------------------------------
42 -- Declarations
43 ----------------------------------------------------------------------------*/
44
45 #include <queue>
46 #include "vec2i.h"
47
48 class CUnit;
49 class CFile;
50 struct lua_State;
51
52 /**
53 ** Result codes of the pathfinder.
54 **
55 ** @todo
56 ** Another idea is SINT_MAX as reached, SINT_MIN as unreachable
57 ** stop others how far to goal.
58 */
59 enum _move_return_ {
60 PF_FAILED = -3, /// This Pathfinder failed, try another
61 PF_UNREACHABLE = -2, /// Unreachable stop
62 PF_REACHED = -1, /// Reached goal stop
63 PF_WAIT = 0, /// Wait, no time or blocked
64 PF_MOVE = 1 /// On the way moving
65 };
66
67 class PathFinderInput
68 {
69 public:
70 PathFinderInput();
GetUnit()71 CUnit *GetUnit() const { return unit; }
72 const Vec2i &GetUnitPos() const;
73 Vec2i GetUnitSize() const;
GetGoalPos()74 const Vec2i &GetGoalPos() const { return goalPos; }
GetGoalSize()75 const Vec2i &GetGoalSize() const { return goalSize; }
GetMinRange()76 int GetMinRange() const { return minRange; }
GetMaxRange()77 int GetMaxRange() const { return maxRange; }
IsRecalculateNeeded()78 bool IsRecalculateNeeded() const { return isRecalculatePathNeeded; }
79
80 void SetUnit(CUnit &_unit);
81 void SetGoal(const Vec2i &pos, const Vec2i &size);
82 void SetMinRange(int range);
83 void SetMaxRange(int range);
84
85 void PathRacalculated();
86
87 void Save(CFile &file) const;
88 void Load(lua_State *l);
89
90 private:
91 CUnit *unit;
92 Vec2i unitSize;
93 Vec2i goalPos;
94 Vec2i goalSize;
95 int minRange;
96 int maxRange;
97 bool isRecalculatePathNeeded;
98 };
99
100 class PathFinderOutput
101 {
102 public:
103 enum {MAX_PATH_LENGTH = 28}; /// max length of precalculated path
104 public:
105 PathFinderOutput();
106 void Save(CFile &file) const;
107 void Load(lua_State *l);
108 public:
109 unsigned short int Cycles; /// how much Cycles we move.
110 char Fast; /// Flag fast move (one step)
111 char Length; /// stored path length
112 char Path[MAX_PATH_LENGTH]; /// directions of stored path
113 };
114
115 class PathFinderData
116 {
117 public:
118 PathFinderInput input;
119 PathFinderOutput output;
120 };
121
122
123 //
124 // Terrain traversal stuff.
125 //
126
127 enum VisitResult {
128 VisitResult_Finished,
129 VisitResult_DeadEnd,
130 VisitResult_Ok,
131 VisitResult_Cancel
132 };
133
134 class TerrainTraversal
135 {
136 public:
137 typedef short int dataType;
138 public:
139 void SetSize(unsigned int width, unsigned int height);
140 void Init();
141
142 void PushPos(const Vec2i &pos);
143 void PushNeighboor(const Vec2i &pos);
144 void PushUnitPosAndNeighboor(const CUnit &unit);
145
146 template <typename T>
147 bool Run(T &context);
148
149 bool IsVisited(const Vec2i &pos) const;
150 bool IsReached(const Vec2i &pos) const;
151 bool IsInvalid(const Vec2i &pos) const;
152
153 // Accept pos to be at one inside the real map
154 dataType Get(const Vec2i &pos) const;
155
156 private:
157 void Set(const Vec2i &pos, dataType value);
158
159 struct PosNode {
PosNodePosNode160 PosNode(const Vec2i &pos, const Vec2i &from) : pos(pos), from(from) {}
161 Vec2i pos;
162 Vec2i from;
163 };
164
165 private:
166 std::vector<dataType> m_values;
167 std::queue<PosNode> m_queue;
168 unsigned int m_extented_width;
169 unsigned int m_height;
170 };
171
172 template <typename T>
Run(T & context)173 bool TerrainTraversal::Run(T &context)
174 {
175 for (; m_queue.empty() == false; m_queue.pop()) {
176 const PosNode &posNode = m_queue.front();
177
178 switch (context.Visit(*this, posNode.pos, posNode.from)) {
179 case VisitResult_Finished: return true;
180 case VisitResult_DeadEnd: Set(posNode.pos, -1); break;
181 case VisitResult_Ok: PushNeighboor(posNode.pos); break;
182 case VisitResult_Cancel: return false;
183 }
184 Assert(IsVisited(posNode.pos));
185 }
186 return false;
187 }
188
189
190 /*----------------------------------------------------------------------------
191 -- Variables
192 ----------------------------------------------------------------------------*/
193
194 /// cost associated to move on a tile occupied by a fixed unit
195 extern int AStarFixedUnitCrossingCost;
196 /// cost associated to move on a tile occupied by a moving unit
197 extern int AStarMovingUnitCrossingCost;
198 /// Whether to have knowledge of terrain that we haven't visited yet
199 extern bool AStarKnowUnseenTerrain;
200 /// Cost of using a square we haven't seen before.
201 extern int AStarUnknownTerrainCost;
202
203 //
204 // Convert heading into direction.
205 // N NE E SE S SW W NW
206 extern const int Heading2X[9];
207 extern const int Heading2Y[9];
208 extern const int XY2Heading[3][3];
209
210 /*----------------------------------------------------------------------------
211 -- Functions
212 ----------------------------------------------------------------------------*/
213
214 /// Init the pathfinder
215 extern void InitPathfinder();
216 /// Free the pathfinder
217 extern void FreePathfinder();
218
219 /// Returns the next element of the path
220 extern int NextPathElement(CUnit &unit, short int *xdp, short int *ydp);
221 /// Return path length to unit 'dst'.
222 extern int UnitReachable(const CUnit &src, const CUnit &dst, int range);
223 /// Return path length to unit 'dst' or error code.
224 extern int CalcPathLengthToUnit(const CUnit &src, const CUnit &dst,
225 const int minrange, const int range);
226 /// Can the unit 'src' reach the place x,y
227 extern int PlaceReachable(const CUnit &src, const Vec2i &pos, int w, int h,
228 int minrange, int maxrange);
229
230 //
231 // in astar.cpp
232 //
233
234 extern void SetAStarFixedUnitCrossingCost(int cost);
235 extern int GetAStarFixedUnitCrossingCost();
236
237 extern void SetAStarMovingUnitCrossingCost(int cost);
238 extern int GetAStarMovingUnitCrossingCost();
239
240 extern void SetAStarUnknownTerrainCost(int cost);
241 extern int GetAStarUnknownTerrainCost();
242
243 extern void SetAStarFixedEnemyUnitsUnpassable(const bool value);
244 extern bool GetAStarFixedEnemyUnitsUnpassable();
245
246 extern void PathfinderCclRegister();
247
248 //@}
249
250 #endif // !__PATH_FINDER_H__
251