_________ __                 __
        /   _____//  |_____________ _/  |______     ____  __ __  ______
        \_____  \\   __\_  __ \__  \\   __\__  \   / ___\|  |  \/  ___/
        /        \|  |  |  | \// __ \|  |  / __ \_/ /_/  >  |  /\___ \
       /_______  /|__|  |__|  (____  /__| (____  /\___  /|____//____  >
               \/                  \/          \//_____/            \/
    ______________________                           ______________________
                          T H E   W A R   B E G I N S
                   Stratagus - A free fantasy real time strategy game engine

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pathfinder.h
Go to the documentation of this file.
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 //
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 
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 
60  PF_FAILED = -3,
62  PF_REACHED = -1,
63  PF_WAIT = 0,
64  PF_MOVE = 1
65 };
66 
68 {
69 public:
71  CUnit *GetUnit() const { return unit; }
72  const Vec2i &GetUnitPos() const;
73  Vec2i GetUnitSize() const;
74  const Vec2i &GetGoalPos() const { return goalPos; }
75  const Vec2i &GetGoalSize() const { return goalSize; }
76  int GetMinRange() const { return minRange; }
77  int GetMaxRange() const { return maxRange; }
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 
101 {
102 public:
103  enum {MAX_PATH_LENGTH = 28};
104 public:
106  void Save(CFile &file) const;
107  void Load(lua_State *l);
108 public:
109  unsigned short int Cycles;
110  char Fast;
111  char Length;
113 };
114 
116 {
117 public:
120 };
121 
122 
123 //
124 // Terrain traversal stuff.
125 //
126 
132 };
133 
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 {
160  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>
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 
195 extern int AStarFixedUnitCrossingCost;
197 extern int AStarMovingUnitCrossingCost;
199 extern bool AStarKnowUnseenTerrain;
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 
215 extern void InitPathfinder();
217 extern void FreePathfinder();
218 
220 extern int NextPathElement(CUnit &unit, short int *xdp, short int *ydp);
222 extern int UnitReachable(const CUnit &unit, const CUnit &dst, int range);
224 extern int PlaceReachable(const CUnit &src, const Vec2i &pos, int w, int h,
225  int minrange, int maxrange);
226 
227 //
228 // in astar.cpp
229 //
230 
231 extern void SetAStarFixedUnitCrossingCost(int cost);
232 extern int GetAStarFixedUnitCrossingCost();
233 
234 extern void SetAStarMovingUnitCrossingCost(int cost);
235 extern int GetAStarMovingUnitCrossingCost();
236 
237 extern void SetAStarUnknownTerrainCost(int cost);
238 extern int GetAStarUnknownTerrainCost();
239 
240 extern void PathfinderCclRegister();
241 
243 
244 #endif // !__PATH_FINDER_H__
void InitPathfinder()
Init the pathfinder.
Definition: pathfinder.cpp:157
int AStarMovingUnitCrossingCost
cost associated to move on a tile occupied by a moving unit
Definition: astar.cpp:101
void PushNeighboor(const Vec2i &pos)
Definition: pathfinder.cpp:94
void Load(lua_State *l)
Definition: script_unit.cpp:174
void PathRacalculated()
Definition: pathfinder.cpp:303
PathFinderOutput output
Definition: pathfinder.h:119
int GetAStarUnknownTerrainCost()
Definition: astar.cpp:1162
Definition: pathfinder.h:103
void SetGoal(const Vec2i &pos, const Vec2i &size)
Definition: pathfinder.cpp:267
const int Heading2X[9]
Definition: astar.cpp:82
bool IsInvalid(const Vec2i &pos) const
Definition: pathfinder.cpp:135
void SetMinRange(int range)
Definition: pathfinder.cpp:287
const Vec2i & GetUnitPos() const
Definition: pathfinder.cpp:252
const Vec2i & GetGoalSize() const
Definition: pathfinder.h:75
PathFinderInput input
Definition: pathfinder.h:118
dataType Get(const Vec2i &pos) const
Definition: pathfinder.cpp:140
unsigned short int Cycles
Definition: pathfinder.h:109
const int XY2Heading[3][3]
Definition: astar.cpp:85
int GetMaxRange() const
Definition: pathfinder.h:77
bool IsRecalculateNeeded() const
Definition: pathfinder.h:78
The big unit structure.
Definition: unit.h:119
Definition: pathfinder.h:67
PathFinderOutput()
max length of precalculated path
Definition: pathfinder.cpp:312
bool IsVisited(const Vec2i &pos) const
Definition: pathfinder.cpp:125
_move_return_
Definition: pathfinder.h:59
void PushUnitPosAndNeighboor(const CUnit &unit)
Definition: pathfinder.cpp:110
void Save(CFile &file) const
Definition: unit_save.cpp:98
short int dataType
Definition: pathfinder.h:137
void SetAStarUnknownTerrainCost(int cost)
Definition: astar.cpp:1154
Definition: pathfinder.h:129
Definition: pathfinder.h:100
void SetMaxRange(int range)
Definition: pathfinder.cpp:295
Reached goal stop.
Definition: pathfinder.h:63
Definition: iolib.h:101
Vec2i GetUnitSize() const
Definition: pathfinder.cpp:253
void PathfinderCclRegister()
Definition: script_pathfinder.cpp:107
#define Assert(cond)
Definition: stratagus.h:119
Definition: pathfinder.h:115
void SetAStarFixedUnitCrossingCost(int cost)
Definition: astar.cpp:1130
void Save(CFile &file) const
Definition: unit_save.cpp:82
void PushPos(const Vec2i &pos)
Definition: pathfinder.cpp:86
Definition: pathfinder.h:128
CUnit * GetUnit() const
Definition: pathfinder.h:71
Definition: pathfinder.h:134
bool AStarKnowUnseenTerrain
Whether to have knowledge of terrain that we haven't visited yet.
Definition: astar.cpp:102
void SetAStarMovingUnitCrossingCost(int cost)
Definition: astar.cpp:1142
Unreachable stop.
Definition: pathfinder.h:62
void Load(lua_State *l)
Definition: script_unit.cpp:209
int AStarFixedUnitCrossingCost
cost associated to move on a tile occupied by a fixed unit
Definition: astar.cpp:100
void SetSize(unsigned int width, unsigned int height)
Definition: pathfinder.cpp:64
char Length
Flag fast move (one step)
Definition: pathfinder.h:111
const int Heading2Y[9]
Definition: astar.cpp:83
int AStarUnknownTerrainCost
Cost of using a square we haven't seen before.
Definition: astar.cpp:103
void SetUnit(CUnit &_unit)
Definition: pathfinder.cpp:259
bool IsReached(const Vec2i &pos) const
Definition: pathfinder.cpp:130
int UnitReachable(const CUnit &unit, const CUnit &dst, int range)
Return distance to unit.
Definition: pathfinder.cpp:223
void FreePathfinder()
Free the pathfinder.
Definition: pathfinder.cpp:165
This Pathfinder failed, try another.
Definition: pathfinder.h:61
int NextPathElement(CUnit &unit, short int *xdp, short int *ydp)
Returns the next element of the path.
Definition: pathfinder.cpp:366
int GetAStarFixedUnitCrossingCost()
Definition: astar.cpp:1136
PathFinderInput()
Definition: pathfinder.cpp:241
int GetAStarMovingUnitCrossingCost()
Definition: astar.cpp:1148
Definition: vec2i.h:36
Definition: pathfinder.h:131
void Init()
Definition: pathfinder.cpp:71
Definition: pathfinder.h:130
Definition: pathfinder.h:60
bool Run(T &context)
Definition: pathfinder.h:173
char Path[MAX_PATH_LENGTH]
stored path length
Definition: pathfinder.h:112
VisitResult
Definition: pathfinder.h:127
int PlaceReachable(const CUnit &src, const Vec2i &pos, int w, int h, int minrange, int maxrange)
Can the unit 'src' reach the place x,y.
Definition: pathfinder.cpp:186
int GetMinRange() const
Definition: pathfinder.h:76
char Fast
how much Cycles we move.
Definition: pathfinder.h:110
const Vec2i & GetGoalPos() const
Definition: pathfinder.h:74
Wait, no time or blocked.
Definition: pathfinder.h:64
(C) Copyright 1998-2012 by The Stratagus Project under the GNU General Public License.
All trademarks and copyrights on this page are owned by their respective owners.