Pyrogenesis  trunk
CCmpPathfinder_Common.h
Go to the documentation of this file.
1 /* Copyright (C) 2017 Wildfire Games.
2  * This file is part of 0 A.D.
3  *
4  * 0 A.D. is free software: you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation, either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * 0 A.D. is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16  */
17 
18 #ifndef INCLUDED_CCMPPATHFINDER_COMMON
19 #define INCLUDED_CCMPPATHFINDER_COMMON
20 
21 /**
22  * @file
23  * Declares CCmpPathfinder. Its implementation is mainly done in CCmpPathfinder.cpp,
24  * but the short-range (vertex) pathfinding is done in CCmpPathfinder_Vertex.cpp.
25  * This file provides common code needed for both files.
26  *
27  * The long-range pathfinding is done by a LongPathfinder object.
28  */
29 
31 
32 #include "ICmpPathfinder.h"
33 
34 #include "graphics/Overlay.h"
35 #include "graphics/Terrain.h"
36 #include "maths/MathUtil.h"
37 #include "ps/CLogger.h"
40 
41 class SceneCollector;
42 class AtlasOverlay;
43 
44 #ifdef NDEBUG
45 #define PATHFIND_DEBUG 0
46 #else
47 #define PATHFIND_DEBUG 1
48 #endif
49 
50 
52 {
59 };
60 
62 {
73 };
74 
75 // A vertex around the corners of an obstruction
76 // (paths will be sequences of these vertexes)
77 struct Vertex
78 {
79  enum
80  {
84  };
85 
87  fixed g, h;
90  u8 quadInward : 4; // the quadrant which is inside the shape (or NONE)
91  u8 quadOutward : 4; // the quadrants of the next point on the path which this vertex must be in, given 'pred'
92 };
93 
94 // Obstruction edges (paths will not cross any of these).
95 // Defines the two points of the edge.
96 struct Edge
97 {
99 };
100 
101 // Axis-aligned obstruction squares (paths will not cross any of these).
102 // Defines the opposing corners of an axis-aligned square
103 // (from which four individual edges can be trivially computed), requiring p0 <= p1
104 struct Square
105 {
107 };
108 
109 // Axis-aligned obstruction edges.
110 // p0 defines one end; c1 is either the X or Y coordinate of the other end,
111 // depending on the context in which this is used.
112 struct EdgeAA
113 {
116 };
117 
118 /**
119  * Implementation of ICmpPathfinder
120  */
122 {
123 public:
124  static void ClassInit(CComponentManager& componentManager)
125  {
126  componentManager.SubscribeToMessageType(MT_Update);
127  componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays
128  componentManager.SubscribeToMessageType(MT_TerrainChanged);
129  componentManager.SubscribeToMessageType(MT_WaterChanged);
131  componentManager.SubscribeToMessageType(MT_TurnStart);
132  }
133 
135 
136  // Template state:
137 
138  std::map<std::string, pass_class_t> m_PassClassMasks;
139  std::vector<PathfinderPassability> m_PassClasses;
140 
141  // Dynamic state:
142 
143  std::vector<AsyncLongPathRequest> m_AsyncLongPathRequests;
144  std::vector<AsyncShortPathRequest> m_AsyncShortPathRequests;
145  u32 m_NextAsyncTicket; // unique IDs for asynchronous path requests
146  u16 m_SameTurnMovesCount; // current number of same turn moves we have processed this turn
147 
148  // Lazily-constructed dynamic state (not serialized):
149 
150  u16 m_MapSize; // tiles per side
151  Grid<NavcellData>* m_Grid; // terrain/passability information
152  Grid<NavcellData>* m_TerrainOnlyGrid; // same as m_Grid, but only with terrain, to avoid some recomputations
153 
154  // Update data, used for clever updates and then stored for the AI manager
155  GridUpdateInformation m_ObstructionsDirty;
156  bool m_TerrainDirty;
157  // When other components request the passability grid and trigger an update,
158  // the following regular update should not clean the dirtiness state.
159  bool m_PreserveUpdateInformations;
160 
161  // Interface to the long-range pathfinder.
162  LongPathfinder m_LongPathfinder;
163 
164  // For responsiveness we will process some moves in the same turn they were generated in
165 
166  u16 m_MaxSameTurnMoves; // max number of moves that can be created and processed in the same turn
167 
168  // memory optimizations: those vectors are created once, reused for all calculations;
169  std::vector<Edge> edgesUnaligned;
170  std::vector<EdgeAA> edgesLeft;
171  std::vector<EdgeAA> edgesRight;
172  std::vector<EdgeAA> edgesBottom;
173  std::vector<EdgeAA> edgesTop;
174 
175  // List of obstruction vertexes (plus start/end points); we'll try to find paths through
176  // the graph defined by these vertexes
177  std::vector<Vertex> vertexes;
178  // List of collision edges - paths must never cross these.
179  // (Edges are one-sided so intersections are fine in one direction, but not the other direction.)
180  std::vector<Edge> edges;
181  std::vector<Square> edgeSquares; // axis-aligned squares; equivalent to 4 edges
182 
183  bool m_DebugOverlay;
184  std::vector<SOverlayLine> m_DebugOverlayShortPathLines;
185  AtlasOverlay* m_AtlasOverlay;
186 
187  static std::string GetSchema()
188  {
189  return "<a:component type='system'/><empty/>";
190  }
191 
192  virtual void Init(const CParamNode& paramNode);
193 
194  virtual void Deinit();
195 
196  template<typename S>
197  void SerializeCommon(S& serialize);
198 
199  virtual void Serialize(ISerializer& serialize);
200 
201  virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize);
202 
203  virtual void HandleMessage(const CMessage& msg, bool global);
204 
205  virtual pass_class_t GetPassabilityClass(const std::string& name) const;
206 
207  virtual void GetPassabilityClasses(std::map<std::string, pass_class_t>& passClasses) const;
208  virtual void GetPassabilityClasses(
209  std::map<std::string, pass_class_t>& nonPathfindingPassClasses,
210  std::map<std::string, pass_class_t>& pathfindingPassClasses) const;
211 
212  const PathfinderPassability* GetPassabilityFromMask(pass_class_t passClass) const;
213 
214  virtual entity_pos_t GetClearance(pass_class_t passClass) const
215  {
216  const PathfinderPassability* passability = GetPassabilityFromMask(passClass);
217  if (!passability)
218  return fixed::Zero();
219 
220  return passability->m_Clearance;
221  }
222 
224  {
225  entity_pos_t max = fixed::Zero();
226 
227  for (const PathfinderPassability& passability : m_PassClasses)
228  if (passability.m_Clearance > max)
229  max = passability.m_Clearance;
230 
232  }
233 
234  virtual const Grid<NavcellData>& GetPassabilityGrid();
235 
236  virtual const GridUpdateInformation& GetDirtinessData() const;
237 
238  virtual Grid<u16> ComputeShoreGrid(bool expandOnWater = false);
239 
241  {
242  m_LongPathfinder.ComputePath(x0, z0, goal, passClass, ret);
243  }
244 
245  virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify);
246 
247  virtual void ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret);
248 
249  virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t controller, entity_id_t notify);
250 
251  virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
252  {
253  m_LongPathfinder.SetDebugPath(x0, z0, goal, passClass);
254  }
255 
256  virtual void SetDebugOverlay(bool enabled)
257  {
258  m_DebugOverlay = enabled;
259  m_LongPathfinder.SetDebugOverlay(enabled);
260  }
261 
262  virtual void SetHierDebugOverlay(bool enabled)
263  {
264  m_LongPathfinder.SetHierDebugOverlay(enabled, &GetSimContext());
265  }
266 
267  virtual void GetDebugData(u32& steps, double& time, Grid<u8>& grid) const
268  {
269  m_LongPathfinder.GetDebugData(steps, time, grid);
270  }
271 
272  virtual void SetAtlasOverlay(bool enable, pass_class_t passClass = 0);
273 
274  virtual bool CheckMovement(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, pass_class_t passClass) const;
275 
276  virtual ICmpObstruction::EFoundationCheck CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool onlyCenterPoint) const;
277 
278  virtual ICmpObstruction::EFoundationCheck CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass) const;
279 
280  virtual ICmpObstruction::EFoundationCheck CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass, bool onlyCenterPoint) const;
281 
282  virtual void FinishAsyncRequests();
283 
284  void ProcessLongRequests(const std::vector<AsyncLongPathRequest>& longRequests);
285 
286  void ProcessShortRequests(const std::vector<AsyncShortPathRequest>& shortRequests);
287 
288  virtual void ProcessSameTurnMoves();
289 
290  /**
291  * Regenerates the grid based on the current obstruction list, if necessary
292  */
293  virtual void UpdateGrid();
294 
295  /**
296  * Updates the terrain-only grid without updating the dirtiness informations.
297  * Useful for fast passability updates in Atlas.
298  */
299  void MinimalTerrainUpdate();
300 
301  /**
302  * Regenerates the terrain-only grid.
303  * Atlas doesn't need to have passability cells expanded.
304  */
305  void TerrainUpdateHelper(bool expandPassability = true);
306 
307  void RenderSubmit(SceneCollector& collector);
308 };
309 
311 {
312 public:
315 
317  TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder), m_PassClass(passClass)
318  {
319  }
320 
321  virtual void BuildTextureRGBA(u8* data, size_t w, size_t h)
322  {
323  // Render navcell passability, based on the terrain-only grid
324  u8* p = data;
325  for (size_t j = 0; j < h; ++j)
326  {
327  for (size_t i = 0; i < w; ++i)
328  {
329  SColor4ub color(0, 0, 0, 0);
330  if (!IS_PASSABLE(m_Pathfinder->m_TerrainOnlyGrid->get((int)i, (int)j), m_PassClass))
331  color = SColor4ub(255, 0, 0, 127);
332 
333  *p++ = color.R;
334  *p++ = color.G;
335  *p++ = color.B;
336  *p++ = color.A;
337  }
338  }
339  }
340 };
341 
342 #endif // INCLUDED_CCMPPATHFINDER_COMMON
An entity initialisation parameter node.
Definition: ParamNode.h:148
void SubscribeToMessageType(MessageTypeId mtid)
Subscribe the current component type to the given message type.
Definition: ComponentManager.cpp:574
A simple fixed-point number class.
Definition: Fixed.h:115
virtual entity_pos_t GetClearance(pass_class_t passClass) const
Definition: CCmpPathfinder_Common.h:214
Interface for ICmpObstructionManager Test functions to filter out unwanted shapes.
Definition: ICmpObstructionManager.h:282
pass_class_t m_PassClass
Definition: CCmpPathfinder_Common.h:314
static void ClassInit(CComponentManager &componentManager)
Definition: CCmpPathfinder_Common.h:124
u8 G
Definition: SColor.h:33
CFixedVector2D p0
Definition: CCmpPathfinder_Common.h:114
Implementation of ICmpPathfinder.
Definition: CCmpPathfinder_Common.h:121
Definition: FixedVector2D.h:24
u32 ticket
Definition: CCmpPathfinder_Common.h:53
Definition: CCmpPathfinder_Common.h:81
u16 pass_class_t
Definition: Pathfinding.h:29
const entity_pos_t CLEARANCE_EXTENSION_RADIUS
To make sure the long-range pathfinder is more strict than the short-range one, we need to slightly o...
Definition: Pathfinding.h:139
Line-based overlay, with world-space coordinates, rendered in the world potentially behind other obje...
Definition: Overlay.h:35
u32 ticket
Definition: CCmpPathfinder_Common.h:63
static CFixed Zero()
Definition: Fixed.h:127
u8 status
Definition: CCmpPathfinder_Common.h:89
Definition: Pathfinding.h:105
Definition: Pathfinding.h:287
Returned path.
Definition: Pathfinding.h:40
uint16_t u16
Definition: types.h:38
const CCmpPathfinder * m_Pathfinder
Definition: CCmpPathfinder_Common.h:313
Serialization interface; see serialization overview.
Definition: ISerializer.h:120
static Status Init()
Definition: h_mgr.cpp:744
Definition: Components.h:64
#define IS_PASSABLE(item, classmask)
Definition: Pathfinding.h:101
virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal &goal, pass_class_t passClass)
If the debug overlay is enabled, render the path that will computed by ComputePath.
Definition: CCmpPathfinder_Common.h:251
Definition: CCmpPathfinder_Common.h:51
CFixedVector2D p
Definition: CCmpPathfinder_Common.h:86
pass_class_t passClass
Definition: CCmpPathfinder_Common.h:57
Definition: unique_range.h:196
Pathfinder goal.
Definition: PathGoal.h:32
Structure holding grid dirtiness informations, for clever updates.
Definition: Grid.h:208
Basic 2D array, intended for storing tile data, plus support for lazy updates by ICmpObstructionManag...
Definition: ICmpPathfinder.h:34
EFoundationCheck
Definition: ICmpObstruction.h:33
Definition: CCmpPathfinder_Common.h:96
u8 B
Definition: SColor.h:34
Definition: Components.h:83
uint8_t u8
Definition: types.h:37
Pathfinder algorithms.
Definition: ICmpPathfinder.h:49
CFixedVector2D p1
Definition: CCmpPathfinder_Common.h:106
virtual void BuildTextureRGBA(u8 *data, size_t w, size_t h)
Called each frame to generate the texture to render on the terrain.
Definition: CCmpPathfinder_Common.h:321
This interface accepts renderable objects.
Definition: Scene.h:83
u8 A
Definition: SColor.h:35
Definition: CCmpPathfinder_Common.h:112
Definition: LongPathfinder.h:161
virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal &goal, pass_class_t passClass, WaypointPath &ret)
Compute a tile-based path from the given point to the goal, and return the set of waypoints...
Definition: CCmpPathfinder_Common.h:240
Definition: Components.h:70
uint32_t u32
Definition: types.h:39
const int NAVCELLS_PER_TILE
The long-range pathfinder operates primarily over a navigation grid (a uniform-cost 2D passability gr...
Definition: Pathfinding.h:117
Definition: CCmpPathfinder_Common.h:61
bool avoidMovingUnits
Definition: CCmpPathfinder_Common.h:70
entity_pos_t x0
Definition: CCmpPathfinder_Common.h:54
Definition: ComponentManager.h:40
Grid< NavcellData > * m_TerrainOnlyGrid
Definition: CCmpPathfinder_Common.h:152
fixed c1
Definition: CCmpPathfinder_Common.h:115
fixed m_Clearance
Definition: Pathfinding.h:366
Definition: Components.h:84
Definition: Components.h:81
Definition: SColor.h:30
Definition: CCmpPathfinder_Common.h:83
virtual entity_pos_t GetMaximumClearance() const
Get the larger clearance in all passability classes.
Definition: CCmpPathfinder_Common.h:223
CFixedVector2D p1
Definition: CCmpPathfinder_Common.h:98
virtual void SetDebugOverlay(bool enabled)
Toggle the storage and rendering of debug info.
Definition: CCmpPathfinder_Common.h:256
#define DEFAULT_COMPONENT_ALLOCATOR(cname)
Definition: Component.h:44
u8 R
Definition: SColor.h:32
Definition: CCmpPathfinder_Common.h:310
virtual void SetHierDebugOverlay(bool enabled)
Toggle the storage and rendering of debug info for the hierarchical pathfinder.
Definition: CCmpPathfinder_Common.h:262
entity_pos_t z0
Definition: CCmpPathfinder_Common.h:55
Definition: CCmpPathfinder_Common.h:77
Definition: Components.h:65
entity_pos_t z0
Definition: CCmpPathfinder_Common.h:65
PathGoal goal
Definition: CCmpPathfinder_Common.h:68
entity_pos_t x0
Definition: CCmpPathfinder_Common.h:64
u16 NavcellData
Definition: Pathfinding.h:100
entity_pos_t range
Definition: CCmpPathfinder_Common.h:67
fixed h
Definition: CCmpPathfinder_Common.h:87
T & get(int i, int j) const
Definition: Grid.h:117
Base class for texture-based terrain overlays, with an arbitrary number of texels per terrain tile...
Definition: TerrainOverlay.h:174
u16 pred
Definition: CCmpPathfinder_Common.h:88
entity_id_t notify
Definition: CCmpPathfinder_Common.h:58
pass_class_t passClass
Definition: CCmpPathfinder_Common.h:69
entity_id_t notify
Definition: CCmpPathfinder_Common.h:72
AtlasOverlay(const CCmpPathfinder *pathfinder, pass_class_t passClass)
Definition: CCmpPathfinder_Common.h:316
entity_pos_t clearance
Definition: CCmpPathfinder_Common.h:66
virtual void GetDebugData(u32 &steps, double &time, Grid< u8 > &grid) const
Returns some stats about the last ComputePath.
Definition: CCmpPathfinder_Common.h:267
u32 entity_id_t
Entity ID type.
Definition: Entity.h:23
Definition: CCmpPathfinder_Common.h:104
PathGoal goal
Definition: CCmpPathfinder_Common.h:56
entity_id_t group
Definition: CCmpPathfinder_Common.h:71
Definition: CCmpPathfinder_Common.h:82
Deserialization interface; see serialization overview.
Definition: IDeserializer.h:34
Definition: Message.h:24