Pyrogenesis  trunk
ICmpRangeManager.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_ICMPRANGEMANAGER
19 #define INCLUDED_ICMPRANGEMANAGER
20 
21 #include "maths/FixedVector3D.h"
22 #include "maths/FixedVector2D.h"
23 
27 
28 #include "graphics/Terrain.h" // for TERRAIN_TILE_SIZE
29 
31 
32 /**
33  * Provides efficient range-based queries of the game world,
34  * and also LOS-based effects (fog of war).
35  *
36  * (These are somewhat distinct concepts but they share a lot of the implementation,
37  * so for efficiency they're combined into this class.)
38  *
39  * Possible use cases:
40  * - combat units need to detect targetable enemies entering LOS, so they can choose
41  * to auto-attack.
42  * - auras let a unit have some effect on all units (or those of the same player, or of enemies)
43  * within a certain range.
44  * - capturable animals need to detect when a player-owned unit is nearby and no units of other
45  * players are in range.
46  * - scenario triggers may want to detect when units enter a given area.
47  * - units gathering from a resource that is exhausted need to find a new resource of the
48  * same type, near the old one and reachable.
49  * - projectile weapons with splash damage need to find all units within some distance
50  * of the target point.
51  * - ...
52  *
53  * In most cases the users are event-based and want notifications when something
54  * has entered or left the range, and the query can be set up once and rarely changed.
55  * These queries have to be fast. It's fine to approximate an entity as a point.
56  *
57  * Current design:
58  *
59  * This class handles just the most common parts of range queries:
60  * distance, target interface, and player ownership.
61  * The caller can then apply any more complex filtering that it needs.
62  *
63  * There are two types of query:
64  * Passive queries are performed by ExecuteQuery and immediately return the matching entities.
65  * Active queries are set up by CreateActiveQuery, and then a CMessageRangeUpdate message will be
66  * sent to the entity once per turn if anybody has entered or left the range since the last RangeUpdate.
67  * Queries can be disabled, in which case no message will be sent.
68  */
70 {
71 public:
72  /**
73  * External identifiers for active queries.
74  */
75  typedef u32 tag_t;
76 
77  /**
78  * Access the spatial subdivision kept by the range manager.
79  * @return pointer to spatial subdivision structure.
80  */
82 
83  /**
84  * Set the bounds of the world.
85  * Entities should not be outside the bounds (else efficiency will suffer).
86  * @param x0,z0,x1,z1 Coordinates of the corners of the world
87  * @param vertices Number of terrain vertices per side
88  */
89  virtual void SetBounds(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, ssize_t vertices) = 0;
90 
91  /**
92  * Execute a passive query.
93  * @param source the entity around which the range will be computed.
94  * @param minRange non-negative minimum distance in metres (inclusive).
95  * @param maxRange non-negative maximum distance in metres (inclusive); or -1.0 to ignore distance.
96  * @param owners list of player IDs that matching entities may have; -1 matches entities with no owner.
97  * @param requiredInterface if non-zero, an interface ID that matching entities must implement.
98  * @return list of entities matching the query, ordered by increasing distance from the source entity.
99  */
100  virtual std::vector<entity_id_t> ExecuteQuery(entity_id_t source,
101  entity_pos_t minRange, entity_pos_t maxRange, const std::vector<int>& owners, int requiredInterface) = 0;
102 
103  /**
104  * Execute a passive query.
105  * @param pos the position around which the range will be computed.
106  * @param minRange non-negative minimum distance in metres (inclusive).
107  * @param maxRange non-negative maximum distance in metres (inclusive); or -1.0 to ignore distance.
108  * @param owners list of player IDs that matching entities may have; -1 matches entities with no owner.
109  * @param requiredInterface if non-zero, an interface ID that matching entities must implement.
110  * @return list of entities matching the query, ordered by increasing distance from the source entity.
111  */
112  virtual std::vector<entity_id_t> ExecuteQueryAroundPos(const CFixedVector2D& pos,
113  entity_pos_t minRange, entity_pos_t maxRange, const std::vector<int>& owners, int requiredInterface) = 0;
114 
115  /**
116  * Construct an active query. The query will be disabled by default.
117  * @param source the entity around which the range will be computed.
118  * @param minRange non-negative minimum distance in metres (inclusive).
119  * @param maxRange non-negative maximum distance in metres (inclusive); or -1.0 to ignore distance.
120  * @param owners list of player IDs that matching entities may have; -1 matches entities with no owner.
121  * @param requiredInterface if non-zero, an interface ID that matching entities must implement.
122  * @param flags if a entity in range has one of the flags set it will show up.
123  * @return unique non-zero identifier of query.
124  */
125  virtual tag_t CreateActiveQuery(entity_id_t source,
126  entity_pos_t minRange, entity_pos_t maxRange, const std::vector<int>& owners, int requiredInterface, u8 flags) = 0;
127 
128  /**
129  * Construct an active query of a paraboloic form around the unit.
130  * The query will be disabled by default.
131  * @param source the entity around which the range will be computed.
132  * @param minRange non-negative minimum horizontal distance in metres (inclusive). MinRange doesn't do parabolic checks.
133  * @param maxRange non-negative maximum distance in metres (inclusive) for units on the same elevation;
134  * or -1.0 to ignore distance.
135  * For units on a different elevation, a physical correct paraboloid with height=maxRange/2 above the unit is used to query them
136  * @param elevationBonus extra bonus so the source can be placed higher and shoot further
137  * @param owners list of player IDs that matching entities may have; -1 matches entities with no owner.
138  * @param requiredInterface if non-zero, an interface ID that matching entities must implement.
139  * @param flags if a entity in range has one of the flags set it will show up.
140  * @return unique non-zero identifier of query.
141  */
142  virtual tag_t CreateActiveParabolicQuery(entity_id_t source,
143  entity_pos_t minRange, entity_pos_t maxRange, entity_pos_t elevationBonus, const std::vector<int>& owners, int requiredInterface, u8 flags) = 0;
144 
145 
146  /**
147  * Get the average elevation over 8 points on distance range around the entity
148  * @param id the entity id to look around
149  * @param range the distance to compare terrain height with
150  * @return a fixed number representing the average difference. It's positive when the entity is on average higher than the terrain surrounding it.
151  */
152  virtual entity_pos_t GetElevationAdaptedRange(const CFixedVector3D& pos, const CFixedVector3D& rot, entity_pos_t range, entity_pos_t elevationBonus, entity_pos_t angle) const = 0;
153 
154  /**
155  * Destroy a query and clean up resources. This must be called when an entity no longer needs its
156  * query (e.g. when the entity is destroyed).
157  * @param tag identifier of query.
158  */
159  virtual void DestroyActiveQuery(tag_t tag) = 0;
160 
161  /**
162  * Re-enable the processing of a query.
163  * @param tag identifier of query.
164  */
165  virtual void EnableActiveQuery(tag_t tag) = 0;
166 
167  /**
168  * Disable the processing of a query (no RangeUpdate messages will be sent).
169  * @param tag identifier of query.
170  */
171  virtual void DisableActiveQuery(tag_t tag) = 0;
172 
173  /**
174  * Check if the processing of a query is enabled.
175  * @param tag identifier of a query.
176  */
177  virtual bool IsActiveQueryEnabled(tag_t tag) const = 0;
178 
179  /**
180  * Immediately execute a query, and re-enable it if disabled.
181  * The next RangeUpdate message will say who has entered/left since this call,
182  * so you won't miss any notifications.
183  * @param tag identifier of query.
184  * @return list of entities matching the query, ordered by increasing distance from the source entity.
185  */
186  virtual std::vector<entity_id_t> ResetActiveQuery(tag_t tag) = 0;
187 
188  /**
189  * Returns a list of all entities for a specific player.
190  * (This is on this interface because it shares a lot of the implementation.
191  * Maybe it should be extended to be more like ExecuteQuery without
192  * the range parameter.)
193  */
194  virtual std::vector<entity_id_t> GetEntitiesByPlayer(player_id_t player) const = 0;
195 
196  /**
197  * Returns a list of all entities of all players except gaia.
198  */
199  virtual std::vector<entity_id_t> GetNonGaiaEntities() const = 0;
200 
201  /**
202  * Toggle the rendering of debug info.
203  */
204  virtual void SetDebugOverlay(bool enabled) = 0;
205 
206  /**
207  * Returns the mask for the specified identifier.
208  */
209  virtual u8 GetEntityFlagMask(const std::string& identifier) const = 0;
210 
211  /**
212  * Set the flag specified by the identifier to the supplied value for the entity
213  * @param ent the entity whose flags will be modified.
214  * @param identifier the flag to be modified.
215  * @param value to which the flag will be set.
216  */
217  virtual void SetEntityFlag(entity_id_t ent, const std::string& identifier, bool value) = 0;
218 
219  // LOS interface:
220 
222  {
227  };
228 
230  {
234  };
235 
236  /**
237  * Object providing efficient abstracted access to the LOS state.
238  * This depends on some implementation details of CCmpRangeManager.
239  *
240  * This *ignores* the GetLosRevealAll flag - callers should check that explicitly.
241  */
243  {
244  private:
245  friend class CCmpRangeManager;
246  friend class TestLOSTexture;
247 
248  CLosQuerier(u32 playerMask, const std::vector<u32>& data, ssize_t verticesPerSide) :
249  m_Data(&data[0]), m_PlayerMask(playerMask), m_VerticesPerSide(verticesPerSide)
250  {
251  }
252 
253  const CLosQuerier& operator=(const CLosQuerier&); // not implemented
254 
255  public:
256  /**
257  * Returns whether the given vertex is visible (i.e. is within a unit's LOS).
258  */
259  inline bool IsVisible(ssize_t i, ssize_t j) const
260  {
261  if (!(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide))
262  return false;
263 
264  // Check high bit of each bit-pair
265  if ((m_Data[j*m_VerticesPerSide + i] & m_PlayerMask) & 0xAAAAAAAAu)
266  return true;
267  else
268  return false;
269  }
270 
271  /**
272  * Returns whether the given vertex is explored (i.e. was (or still is) within a unit's LOS).
273  */
274  inline bool IsExplored(ssize_t i, ssize_t j) const
275  {
276  if (!(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide))
277  return false;
278 
279  // Check low bit of each bit-pair
280  if ((m_Data[j*m_VerticesPerSide + i] & m_PlayerMask) & 0x55555555u)
281  return true;
282  else
283  return false;
284  }
285 
286  /**
287  * Returns whether the given vertex is visible (i.e. is within a unit's LOS).
288  * i and j must be in the range [0, verticesPerSide), else behaviour is undefined.
289  */
290  inline bool IsVisible_UncheckedRange(ssize_t i, ssize_t j) const
291  {
292 #ifndef NDEBUG
293  ENSURE(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide);
294 #endif
295  // Check high bit of each bit-pair
296  if ((m_Data[j*m_VerticesPerSide + i] & m_PlayerMask) & 0xAAAAAAAAu)
297  return true;
298  else
299  return false;
300  }
301 
302  /**
303  * Returns whether the given vertex is explored (i.e. was (or still is) within a unit's LOS).
304  * i and j must be in the range [0, verticesPerSide), else behaviour is undefined.
305  */
306  inline bool IsExplored_UncheckedRange(ssize_t i, ssize_t j) const
307  {
308 #ifndef NDEBUG
309  ENSURE(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide);
310 #endif
311  // Check low bit of each bit-pair
312  if ((m_Data[j*m_VerticesPerSide + i] & m_PlayerMask) & 0x55555555u)
313  return true;
314  else
315  return false;
316  }
317 
318  private:
320  const u32* m_Data;
322  };
323 
324  /**
325  * Returns a CLosQuerier for checking whether vertex positions are visible to the given player
326  * (or other players it shares LOS with).
327  */
328  virtual CLosQuerier GetLosQuerier(player_id_t player) const = 0;
329 
330  /**
331  * Toggle the scripted Visibility component activation for entity ent.
332  */
333  virtual void ActivateScriptedVisibility(entity_id_t ent, bool status) = 0;
334 
335  /**
336  * Returns the visibility status of the given entity, with respect to the given player.
337  * Returns VIS_HIDDEN if the entity doesn't exist or is not in the world.
338  * This respects the GetLosRevealAll flag.
339  */
340  virtual ELosVisibility GetLosVisibility(CEntityHandle ent, player_id_t player) const = 0;
341  virtual ELosVisibility GetLosVisibility(entity_id_t ent, player_id_t player) const = 0;
342 
343  /**
344  * Request the update of the visibility cache of ent at next turn.
345  * Typically used for fogging.
346  */
347  virtual void RequestVisibilityUpdate(entity_id_t ent) = 0;
348 
349 
350  /**
351  * GetLosVisibility wrapped for script calls.
352  * Returns "hidden", "fogged" or "visible".
353  */
354  std::string GetLosVisibility_wrapper(entity_id_t ent, player_id_t player) const;
355 
356  /**
357  * Explore all tiles (but leave them in the FoW) for player p
358  */
359  virtual void ExploreAllTiles(player_id_t p) = 0;
360 
361  /**
362  * Explore the tiles inside each player's territory.
363  * This is done only at the beginning of the game.
364  */
365  virtual void ExploreTerritories() = 0;
366 
367  /**
368  * Reveal the shore for specified player p.
369  * This works like for entities: if RevealShore is called multiple times with enabled, it
370  * will be necessary to call it the same number of times with !enabled to make the shore
371  * fall back into the FoW.
372  */
373  virtual void RevealShore(player_id_t p, bool enable) = 0;
374 
375  /**
376  * Set whether the whole map should be made visible to the given player.
377  * If player is -1, the map will be made visible to all players.
378  */
379  virtual void SetLosRevealAll(player_id_t player, bool enabled) = 0;
380 
381  /**
382  * Returns whether the whole map has been made visible to the given player.
383  */
384  virtual bool GetLosRevealAll(player_id_t player) const = 0;
385 
386  /**
387  * Set the LOS to be restricted to a circular map.
388  */
389  virtual void SetLosCircular(bool enabled) = 0;
390 
391  /**
392  * Returns whether the LOS is restricted to a circular map.
393  */
394  virtual bool GetLosCircular() const = 0;
395 
396  /**
397  * Sets shared LOS data for player to the given list of players.
398  */
399  virtual void SetSharedLos(player_id_t player, const std::vector<player_id_t>& players) = 0;
400 
401  /**
402  * Returns shared LOS mask for player.
403  */
404  virtual u32 GetSharedLosMask(player_id_t player) const = 0;
405 
406  /**
407  * Get percent map explored statistics for specified player.
408  */
409  virtual u8 GetPercentMapExplored(player_id_t player) const = 0;
410 
411  /**
412  * Get percent map explored statistics for specified set of players.
413  * Note: this function computes statistics from scratch and should not be called too often.
414  */
415  virtual u8 GetUnionPercentMapExplored(const std::vector<player_id_t>& players) const = 0;
416 
417 
418  /**
419  * Perform some internal consistency checks for testing/debugging.
420  */
421  virtual void Verify() = 0;
422 
423  DECLARE_INTERFACE_TYPE(RangeManager)
424 };
425 
426 #endif // INCLUDED_ICMPRANGEMANAGER
Definition: IComponent.h:33
virtual tag_t CreateActiveParabolicQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, entity_pos_t elevationBonus, const std::vector< int > &owners, int requiredInterface, u8 flags)=0
Construct an active query of a paraboloic form around the unit.
virtual FastSpatialSubdivision * GetSubdivision()=0
Access the spatial subdivision kept by the range manager.
A simple fixed-point number class.
Definition: Fixed.h:115
const CLosQuerier & operator=(const CLosQuerier &)
CLosQuerier(u32 playerMask, const std::vector< u32 > &data, ssize_t verticesPerSide)
Definition: ICmpRangeManager.h:248
Definition: FixedVector2D.h:24
virtual void ExploreTerritories()=0
Explore the tiles inside each player&#39;s territory.
virtual u32 GetSharedLosMask(player_id_t player) const =0
Returns shared LOS mask for player.
virtual entity_pos_t GetElevationAdaptedRange(const CFixedVector3D &pos, const CFixedVector3D &rot, entity_pos_t range, entity_pos_t elevationBonus, entity_pos_t angle) const =0
Get the average elevation over 8 points on distance range around the entity.
ssize_t m_VerticesPerSide
Definition: ICmpRangeManager.h:321
virtual void ActivateScriptedVisibility(entity_id_t ent, bool status)=0
Toggle the scripted Visibility component activation for entity ent.
Definition: ICmpRangeManager.h:232
Object wrapping an entity_id_t, with a SEntityComponentCache to support fast QueryInterface() / CmpPt...
Definition: Entity.h:79
virtual void Verify()=0
Perform some internal consistency checks for testing/debugging.
bool IsExplored_UncheckedRange(ssize_t i, ssize_t j) const
Returns whether the given vertex is explored (i.e.
Definition: ICmpRangeManager.h:306
virtual ELosVisibility GetLosVisibility(CEntityHandle ent, player_id_t player) const =0
Returns the visibility status of the given entity, with respect to the given player.
Provides efficient range-based queries of the game world, and also LOS-based effects (fog of war)...
Definition: ICmpRangeManager.h:69
virtual u8 GetUnionPercentMapExplored(const std::vector< player_id_t > &players) const =0
Get percent map explored statistics for specified set of players.
virtual u8 GetEntityFlagMask(const std::string &identifier) const =0
Returns the mask for the specified identifier.
Definition: ICmpRangeManager.h:233
virtual void SetDebugOverlay(bool enabled)=0
Toggle the rendering of debug info.
uint8_t u8
Definition: types.h:37
bool IsExplored(ssize_t i, ssize_t j) const
Returns whether the given vertex is explored (i.e.
Definition: ICmpRangeManager.h:274
virtual tag_t CreateActiveQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, const std::vector< int > &owners, int requiredInterface, u8 flags)=0
Construct an active query.
int32_t player_id_t
valid player IDs are non-negative (see ICmpOwnership)
Definition: Player.h:24
virtual std::vector< entity_id_t > ResetActiveQuery(tag_t tag)=0
Immediately execute a query, and re-enable it if disabled.
Definition: ICmpRangeManager.h:223
virtual CLosQuerier GetLosQuerier(player_id_t player) const =0
Returns a CLosQuerier for checking whether vertex positions are visible to the given player (or other...
virtual void DisableActiveQuery(tag_t tag)=0
Disable the processing of a query (no RangeUpdate messages will be sent).
ELosState
Definition: ICmpRangeManager.h:221
Definition: ICmpRangeManager.h:225
Range manager implementation.
Definition: CCmpRangeManager.cpp:332
#define ENSURE(expr)
ensure the expression <expr> evaluates to non-zero.
Definition: debug.h:287
virtual void SetLosRevealAll(player_id_t player, bool enabled)=0
Set whether the whole map should be made visible to the given player.
uint32_t u32
Definition: types.h:39
u32 m_PlayerMask
Definition: ICmpRangeManager.h:319
virtual bool GetLosRevealAll(player_id_t player) const =0
Returns whether the whole map has been made visible to the given player.
virtual void SetEntityFlag(entity_id_t ent, const std::string &identifier, bool value)=0
Set the flag specified by the identifier to the supplied value for the entity.
A basic square subdivision scheme for finding entities in range More efficient than SpatialSubdivisio...
Definition: Spatial.h:365
virtual void RevealShore(player_id_t p, bool enable)=0
Reveal the shore for specified player p.
Definition: FixedVector3D.h:24
virtual std::vector< entity_id_t > GetEntitiesByPlayer(player_id_t player) const =0
Returns a list of all entities for a specific player.
std::string GetLosVisibility_wrapper(entity_id_t ent, player_id_t player) const
GetLosVisibility wrapped for script calls.
Definition: ICmpRangeManager.cpp:24
#define DECLARE_INTERFACE_TYPE(iname)
Definition: Interface.h:23
virtual void SetLosCircular(bool enabled)=0
Set the LOS to be restricted to a circular map.
Definition: ICmpRangeManager.h:231
const u32 * m_Data
Definition: ICmpRangeManager.h:320
virtual void SetSharedLos(player_id_t player, const std::vector< player_id_t > &players)=0
Sets shared LOS data for player to the given list of players.
virtual std::vector< entity_id_t > ExecuteQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, const std::vector< int > &owners, int requiredInterface)=0
Execute a passive query.
intptr_t ssize_t
Definition: wposix_types.h:82
virtual u8 GetPercentMapExplored(player_id_t player) const =0
Get percent map explored statistics for specified player.
friend class TestLOSTexture
Definition: ICmpRangeManager.h:246
ELosVisibility
Definition: ICmpRangeManager.h:229
bool IsVisible_UncheckedRange(ssize_t i, ssize_t j) const
Returns whether the given vertex is visible (i.e.
Definition: ICmpRangeManager.h:290
Object providing efficient abstracted access to the LOS state.
Definition: ICmpRangeManager.h:242
bool IsVisible(ssize_t i, ssize_t j) const
Returns whether the given vertex is visible (i.e.
Definition: ICmpRangeManager.h:259
virtual std::vector< entity_id_t > GetNonGaiaEntities() const =0
Returns a list of all entities of all players except gaia.
virtual void EnableActiveQuery(tag_t tag)=0
Re-enable the processing of a query.
virtual void RequestVisibilityUpdate(entity_id_t ent)=0
Request the update of the visibility cache of ent at next turn.
Definition: ICmpRangeManager.h:224
Entity coordinate types.
virtual void ExploreAllTiles(player_id_t p)=0
Explore all tiles (but leave them in the FoW) for player p.
u32 entity_id_t
Entity ID type.
Definition: Entity.h:23
Definition: ICmpRangeManager.h:226
virtual bool IsActiveQueryEnabled(tag_t tag) const =0
Check if the processing of a query is enabled.
u32 tag_t
External identifiers for active queries.
Definition: ICmpRangeManager.h:75
virtual void SetBounds(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, ssize_t vertices)=0
Set the bounds of the world.
virtual void DestroyActiveQuery(tag_t tag)=0
Destroy a query and clean up resources.
virtual std::vector< entity_id_t > ExecuteQueryAroundPos(const CFixedVector2D &pos, entity_pos_t minRange, entity_pos_t maxRange, const std::vector< int > &owners, int requiredInterface)=0
Execute a passive query.
virtual bool GetLosCircular() const =0
Returns whether the LOS is restricted to a circular map.