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

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;
203 extern int AStarMaxSearchIterations;
204 
205 //
206 // Convert heading into direction.
207 // N NE E SE S SW W NW
208 extern const int Heading2X[9];
209 extern const int Heading2Y[9];
210 extern const int XY2Heading[3][3];
211 
212 /*----------------------------------------------------------------------------
213 -- Functions
214 ----------------------------------------------------------------------------*/
215 
217 extern void InitPathfinder();
219 extern void FreePathfinder();
220 
222 extern int NextPathElement(CUnit &unit, short int *xdp, short int *ydp);
224 extern int UnitReachable(const CUnit &src, const CUnit &dst, int range, bool from_outside_container);
226 extern int CalcPathLengthToUnit(const CUnit &src, const CUnit &dst,
227  const int minrange, const int range);
229 extern int PlaceReachable(const CUnit &src, const Vec2i &pos, int w, int h,
230  int minrange, int maxrange, bool from_outside_container);
231 
232 //
233 // in astar.cpp
234 //
235 
236 extern void SetAStarFixedUnitCrossingCost(int cost);
237 extern int GetAStarFixedUnitCrossingCost();
238 
239 extern void SetAStarMovingUnitCrossingCost(int cost);
240 extern int GetAStarMovingUnitCrossingCost();
241 
242 extern void SetAStarUnknownTerrainCost(int cost);
243 extern int GetAStarUnknownTerrainCost();
244 
245 extern void SetAStarFixedEnemyUnitsUnpassable(const bool value);
247 
248 extern void PathfinderCclRegister();
249 
251 
252 #endif // !__PATH_FINDER_H__
UnitReachable
int UnitReachable(const CUnit &src, const CUnit &dst, int range, bool from_outside_container)
Return path length to unit 'dst'.
Definition: pathfinder.cpp:259
PathFinderData
Definition: pathfinder.h:115
GetAStarFixedUnitCrossingCost
int GetAStarFixedUnitCrossingCost()
Definition: astar.cpp:1102
PathFinderInput::GetUnitPos
const Vec2i & GetUnitPos() const
Definition: pathfinder.cpp:320
TerrainTraversal::IsVisited
bool IsVisited(const Vec2i &pos) const
Definition: pathfinder.cpp:125
PathFinderOutput::Load
void Load(lua_State *l)
Definition: script_unit.cpp:239
PathFinderInput::GetMaxRange
int GetMaxRange() const
Definition: pathfinder.h:77
TerrainTraversal::SetSize
void SetSize(unsigned int width, unsigned int height)
Definition: pathfinder.cpp:64
_move_return_
_move_return_
Definition: pathfinder.h:59
PathFinderOutput::MAX_PATH_LENGTH
@ MAX_PATH_LENGTH
Definition: pathfinder.h:103
AStarMaxSearchIterations
int AStarMaxSearchIterations
Maximum number of iterations of A* before giving up.
Definition: astar.cpp:99
CalcPathLengthToUnit
int CalcPathLengthToUnit(const CUnit &src, const CUnit &dst, const int minrange, const int range)
Return path length to unit 'dst' or error code.
Definition: pathfinder.cpp:284
AStarMovingUnitCrossingCost
int AStarMovingUnitCrossingCost
cost associated to move on a tile occupied by a moving unit
Definition: astar.cpp:98
vec2i.h
PathFinderOutput::Length
char Length
Flag fast move (one step)
Definition: pathfinder.h:111
PathfinderCclRegister
void PathfinderCclRegister()
Definition: script_pathfinder.cpp:116
PathFinderData::input
PathFinderInput input
Definition: pathfinder.h:118
AStarFixedUnitCrossingCost
int AStarFixedUnitCrossingCost
cost associated to move on a tile occupied by a fixed unit
Definition: astar.cpp:97
VisitResult
VisitResult
Definition: pathfinder.h:127
SetAStarFixedEnemyUnitsUnpassable
void SetAStarFixedEnemyUnitsUnpassable(const bool value)
Definition: astar.cpp:1133
PathFinderOutput::Path
char Path[MAX_PATH_LENGTH]
stored path length
Definition: pathfinder.h:112
TerrainTraversal::IsInvalid
bool IsInvalid(const Vec2i &pos) const
Definition: pathfinder.cpp:135
SetAStarFixedUnitCrossingCost
void SetAStarFixedUnitCrossingCost(int cost)
Definition: astar.cpp:1096
PathFinderOutput
Definition: pathfinder.h:100
AStarKnowUnseenTerrain
bool AStarKnowUnseenTerrain
Whether to have knowledge of terrain that we haven't visited yet.
Definition: astar.cpp:100
VisitResult_DeadEnd
@ VisitResult_DeadEnd
Definition: pathfinder.h:129
AStarUnknownTerrainCost
int AStarUnknownTerrainCost
Cost of using a square we haven't seen before.
Definition: astar.cpp:101
Vec2T
Definition: vec2i.h:36
PathFinderInput::GetGoalSize
const Vec2i & GetGoalSize() const
Definition: pathfinder.h:75
TerrainTraversal::PushNeighboor
void PushNeighboor(const Vec2i &pos)
Definition: pathfinder.cpp:94
PathFinderInput::SetMaxRange
void SetMaxRange(int range)
Definition: pathfinder.cpp:363
PF_WAIT
@ PF_WAIT
Reached goal stop.
Definition: pathfinder.h:63
PathFinderInput::SetMinRange
void SetMinRange(int range)
Definition: pathfinder.cpp:355
NextPathElement
int NextPathElement(CUnit &unit, short int *xdp, short int *ydp)
Returns the next element of the path.
Definition: pathfinder.cpp:434
PathFinderInput
Definition: pathfinder.h:67
TerrainTraversal::Get
dataType Get(const Vec2i &pos) const
Definition: pathfinder.cpp:140
PathFinderOutput::Fast
char Fast
how much Cycles we move.
Definition: pathfinder.h:110
GetAStarMovingUnitCrossingCost
int GetAStarMovingUnitCrossingCost()
Definition: astar.cpp:1114
TerrainTraversal::Run
bool Run(T &context)
Definition: pathfinder.h:173
TerrainTraversal::IsReached
bool IsReached(const Vec2i &pos) const
Definition: pathfinder.cpp:130
XY2Heading
const int XY2Heading[3][3]
Definition: astar.cpp:85
Heading2X
const int Heading2X[9]
Definition: astar.cpp:82
GetAStarFixedEnemyUnitsUnpassable
bool GetAStarFixedEnemyUnitsUnpassable()
Definition: astar.cpp:1138
PathFinderInput::GetUnitSize
Vec2i GetUnitSize() const
Definition: pathfinder.cpp:321
TerrainTraversal::Init
void Init()
Definition: pathfinder.cpp:71
TerrainTraversal
Definition: pathfinder.h:134
PathFinderInput::GetGoalPos
const Vec2i & GetGoalPos() const
Definition: pathfinder.h:74
PathFinderInput::GetUnit
CUnit * GetUnit() const
Definition: pathfinder.h:71
PathFinderInput::Save
void Save(CFile &file) const
Definition: unit_save.cpp:82
update-images.w
w
Definition: update-images.py:53
FreePathfinder
void FreePathfinder()
Free the pathfinder.
Definition: pathfinder.cpp:165
GetAStarUnknownTerrainCost
int GetAStarUnknownTerrainCost()
Definition: astar.cpp:1128
PathFinderOutput::PathFinderOutput
PathFinderOutput()
max length of precalculated path
Definition: pathfinder.cpp:380
PathFinderOutput::Save
void Save(CFile &file) const
Definition: unit_save.cpp:98
SetAStarUnknownTerrainCost
void SetAStarUnknownTerrainCost(int cost)
Definition: astar.cpp:1120
VisitResult_Finished
@ VisitResult_Finished
Definition: pathfinder.h:128
InitPathfinder
void InitPathfinder()
Init the pathfinder.
Definition: pathfinder.cpp:157
PathFinderOutput::Cycles
unsigned short int Cycles
Definition: pathfinder.h:109
PathFinderInput::PathFinderInput
PathFinderInput()
Definition: pathfinder.cpp:309
PathFinderInput::PathRacalculated
void PathRacalculated()
Definition: pathfinder.cpp:371
PF_REACHED
@ PF_REACHED
Unreachable stop.
Definition: pathfinder.h:62
PF_UNREACHABLE
@ PF_UNREACHABLE
This Pathfinder failed, try another.
Definition: pathfinder.h:61
PlaceReachable
int PlaceReachable(const CUnit &src, const Vec2i &pos, int w, int h, int minrange, int maxrange, bool from_outside_container)
Can the unit 'src' reach the place x,y.
Definition: pathfinder.cpp:186
Assert
#define Assert(cond)
Definition: stratagus.h:142
PF_FAILED
@ PF_FAILED
Definition: pathfinder.h:60
VisitResult_Cancel
@ VisitResult_Cancel
Definition: pathfinder.h:131
PathFinderInput::SetGoal
void SetGoal(const Vec2i &pos, const Vec2i &size)
Definition: pathfinder.cpp:335
update-images.h
h
Definition: update-images.py:53
PathFinderInput::SetUnit
void SetUnit(CUnit &_unit)
Definition: pathfinder.cpp:327
Heading2Y
const int Heading2Y[9]
Definition: astar.cpp:83
PathFinderInput::GetMinRange
int GetMinRange() const
Definition: pathfinder.h:76
TerrainTraversal::PushPos
void PushPos(const Vec2i &pos)
Definition: pathfinder.cpp:86
PathFinderData::output
PathFinderOutput output
Definition: pathfinder.h:119
PF_MOVE
@ PF_MOVE
Wait, no time or blocked.
Definition: pathfinder.h:64
CFile
Definition: iolib.h:102
CUnit
The big unit structure.
Definition: unit.h:135
TerrainTraversal::PushUnitPosAndNeighboor
void PushUnitPosAndNeighboor(const CUnit &unit)
Definition: pathfinder.cpp:110
PathFinderInput::Load
void Load(lua_State *l)
Definition: script_unit.cpp:204
VisitResult_Ok
@ VisitResult_Ok
Definition: pathfinder.h:130
TerrainTraversal::dataType
short int dataType
Definition: pathfinder.h:137
SetAStarMovingUnitCrossingCost
void SetAStarMovingUnitCrossingCost(int cost)
Definition: astar.cpp:1108
PathFinderInput::IsRecalculateNeeded
bool IsRecalculateNeeded() const
Definition: pathfinder.h:78
(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.