/*
** Command & Conquer Generals(tm)
** Copyright 2025 Electronic Arts Inc.
**
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation, either version 3 of the License, or
** (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program. If not, see .
*/
////////////////////////////////////////////////////////////////////////////////
// //
// (c) 2001-2003 Electronic Arts Inc. //
// //
////////////////////////////////////////////////////////////////////////////////
// FILE: PartitionManager.h //////////////////////////////////////////////////////
//-----------------------------------------------------------------------------
//
// Westwood Studios Pacific.
//
// Confidential Information
// Copyright (C) 2001 - All Rights Reserved
//
//-----------------------------------------------------------------------------
//
// Project: RTS3
//
// File name: PartitionManager.h
//
// Created: Steven Johnson, September 2001
//
// Desc: Partition management, this system will allow us to partition the
// objects in space, iterate objects in specified volumes,
// regions, by types and other properties.
//
//-----------------------------------------------------------------------------
#pragma once
#ifndef __PARTITIONMANAGER_H_
#define __PARTITIONMANAGER_H_
//-----------------------------------------------------------------------------
// Includes
//-----------------------------------------------------------------------------
#include "Common/GameCommon.h" // ensure we get DUMP_PERF_STATS, or not
#include "GameLogic/ObjectIter.h"
#include "Common/KindOf.h"
#include "Common/Snapshot.h"
#include "Common/Geometry.h"
#include "GameClient/Display.h" // for ShroudLevel
//-----------------------------------------------------------------------------
// defines
//-----------------------------------------------------------------------------
/*
Note, this isn't very accurate currently, so use with caution. (srj)
*/
#define PM_CACHE_TERRAIN_HEIGHT
/*
5% speed improvement, at cost of more memory.
*/
#define FASTER_GCO
const Real HUGE_DIST = 1000000.0f;
//-----------------------------------------------------------------------------
// Type Definitions
//-----------------------------------------------------------------------------
struct Coord3D;
class CellAndObjectIntersection;
class Object;
class PartitionManager;
class PartitionData;
class PartitionFilter;
class PartitionCell;
class Player;
class PolygonTrigger;
class Squad;
class Team;
class ThingTemplate;
class GhostObject;
class CommandButton;
enum CommandSourceType;
// ----------------------------------------------------------------------------------------------
enum ValueOrThreat
{
VOT_CashValue = 1,
VOT_ThreatValue,
VOT_NumItems
};
// ----------------------------------------------------------------------------------------------
enum FindPositionFlags
{
FPF_NONE = 0x00000000, // no options, default behavior
FPF_IGNORE_WATER = 0x00000001, // a position found underwater is ok
FPF_WATER_ONLY = 0x00000002, // find positions in the water only
FPF_IGNORE_ALL_OBJECTS = 0x00000004, // ignore all objects, positions inside objects are ok
FPF_IGNORE_ALLY_OR_NEUTRAL_UNITS = 0x00000008, // ignore friendly units (requires relationshipObject)
FPF_IGNORE_ALLY_OR_NEUTRAL_STRUCTURES = 0x00000010, // ignore friendly structures (requires relationshipObject)
FPF_IGNORE_ENEMY_UNITS = 0x00000020, // ignore enemy units (requires relationshipObject)
FPF_IGNORE_ENEMY_STRUCTURES = 0x00000040, // ignore enemy structures (requires relationshipObject)
FPF_USE_HIGHEST_LAYER = 0x00000080, // examine pos on highest layer at given xy (rather than on ground layer)
};
// ----------------------------------------------------------------------------------------------
const Real RANDOM_START_ANGLE = -99999.9f; ///< no start angle (an unlikely number to use for the start angle)
struct FindPositionOptions
{
FindPositionOptions( void )
{
flags = FPF_NONE;
minRadius = 0.0f;
maxRadius = 0.0f;
startAngle = RANDOM_START_ANGLE;
maxZDelta = 1e10f; // ie, any z delta.
ignoreObject = NULL;
sourceToPathToDest = NULL;
relationshipObject = NULL;
};
FindPositionFlags flags; ///< flags for finding the legal position
Real minRadius; ///< min radius to search around
Real maxRadius; ///< max radius to search around
Real startAngle; ///< use this angle to start the search at
Real maxZDelta; ///< maximum delta-z we will allow
const Object *ignoreObject; ///< ignore this object in legal position checks
const Object *sourceToPathToDest; ///< object that must be able to path to the position chosen
const Object *relationshipObject; ///< object to use for relationship tests
};
//=====================================
/** */
//=====================================
enum DistanceCalculationType
{
FROM_CENTER_2D = 0, ///< measure from Object center in 2d.
FROM_CENTER_3D = 1, ///< measure from Object center in 3d.
FROM_BOUNDINGSPHERE_2D = 2, ///< measure from Object bounding sphere in 2d.
FROM_BOUNDINGSPHERE_3D = 3 ///< measure from Object bounding sphere in 3d.
};
//=====================================
/**
a Plain Old Data structure that is used to get optional results from collidesWith().
*/
struct CollideLocAndNormal
{
Coord3D loc;
Coord3D normal;
};
//=====================================
/**
PartitionContactList is a utility class used by the Partition Manager
to hold potential collisions as it updates objects in the partition.
It stores pairs of potentially-colliding objects (eliminating duplicates)
for processing after all partitions are updated.
*/
//=====================================
class PartitionContactList;
//=====================================
/**
This class (often called COI for short) is the abstraction
of the intersection between an Object and a Partition Cell.
For every Cell that an Object's geometry touches, even partially,
we allocate a COI. This allows us to maintain an efficient two-way
list, such that for every Object, we know the Cells that it touches;
and, for every Cell, we know the Objects that touch it.
*/
//=====================================
class CellAndObjectIntersection // not MPO: we allocate these in arrays
{
private:
PartitionCell *m_cell; ///< the cell being touched
PartitionData *m_module; ///< the module (and thus, Object) touching
CellAndObjectIntersection *m_prevCoi, *m_nextCoi; ///< if in use, next/prev in this cell. if not in use, next/prev free in this module.
public:
// Note, we allocate these in arrays, thus we must have a default ctor (and NOT descend from MPO)
CellAndObjectIntersection();
~CellAndObjectIntersection();
/**
make 'this' refer to the specified cell and module. Normally, this
involves updated the member variables and adding 'this' to the Cell's
list of COIs.
*/
void addCoverage(PartitionCell *cell, PartitionData *module);
/**
make 'this' refer to nothing at all. this involves resetting the member
variables to null, and removing 'this' from the Cell's list of COI's.
*/
void removeAllCoverage();
/**
return the Cell for this COI (null if the COI is not in use)
*/
inline PartitionCell *getCell() { return m_cell; }
/**
return the Module for this COI (null if the COI is not in use)
*/
inline PartitionData *getModule() { return m_module; }
/**
return the previous COI in the Cell's list of COIs.
*/
inline CellAndObjectIntersection *getPrevCoi() { return m_prevCoi; }
/**
return the next COI in the Cell's list of COIs.
*/
inline CellAndObjectIntersection *getNextCoi() { return m_nextCoi; }
// only for use by PartitionCell.
void friend_addToCellList(CellAndObjectIntersection **pListHead);
void friend_removeFromCellList(CellAndObjectIntersection **pListHead);
};
/**
This class encapsulates one area interaction with PartitionCells. The user decides what to do with it.
*/
class SightingInfo : public MemoryPoolObject, public Snapshot
{
MEMORY_POOL_GLUE_WITH_USERLOOKUP_CREATE( SightingInfo, "SightingInfo" );
public:
SightingInfo();
void reset();
Bool isInvalid() const;
Coord3D m_where;
Real m_howFar;
PlayerMaskType m_forWhom; // ask not for whom the sighting is masked; it masks for thee
UnsignedInt m_data; // Threat and value use as the value. Sighting uses it for a Timestamp
protected:
// snapshot method
virtual void crc( Xfer *xfer );
virtual void xfer( Xfer *xfer );
virtual void loadPostProcess();
};
//=====================================
/**
We sometimes need to save whether or not an area was fogged or permanently revealed through a
script. This helps us do so.
*/
//=====================================
enum
{
STORE_DONTTOUCH = 0,
STORE_FOG = 1,
STORE_PERMANENTLY_REVEALED = 2
};
struct ShroudStatusStoreRestore
{
std::vector m_foggedOrRevealed[MAX_PLAYER_COUNT];
Int m_cellsWide; // m_cellsHigh is computed by m_foggedOrRevealed[0].size() / m_cellsWide
};
//=====================================
/**
The world's terrain is partitioned into a large grid of Partition Cells.
The Cell is the fundamental unit of space in the Partition Manager.
*/
//=====================================
class PartitionCell : public Snapshot // not MPO: allocated in an array
{
private:
CellAndObjectIntersection* m_firstCoiInCell; ///< list of COIs in this cell (may be null).
ShroudLevel m_shroudLevel[MAX_PLAYER_COUNT];
#ifdef PM_CACHE_TERRAIN_HEIGHT
Real m_loTerrainZ; ///< lowest terrain-pt in this cell
Real m_hiTerrainZ; ///< highest terrain-pt in this cell
#endif
Int m_threatValue[MAX_PLAYER_COUNT];
Int m_cashValue[MAX_PLAYER_COUNT];
Short m_coiCount; ///< number of COIs in this cell.
Short m_cellX; ///< x-coord of this cell within the Partition Mgr coords (NOT in world coords)
Short m_cellY; ///< y-coord of this cell within the Partition Mgr coords (NOT in world coords)
public:
// Note, we allocate these in arrays, thus we must have a default ctor (and NOT descend from MPO)
PartitionCell();
#ifdef PM_CACHE_TERRAIN_HEIGHT
void init(Int x, Int y, Real loZ, Real hiZ) { m_cellX = x; m_cellY = y; m_loTerrainZ = loZ; m_hiTerrainZ = hiZ; }
#else
void init(Int x, Int y) { m_cellX = x; m_cellY = y; }
#endif
~PartitionCell();
// --------------- inherited from Snapshot interface --------------
void crc( Xfer *xfer );
void xfer( Xfer *xfer );
void loadPostProcess( void );
Int getCoiCount() const { return m_coiCount; } ///< return number of COIs touching this cell.
Int getCellX() const { return m_cellX; }
Int getCellY() const { return m_cellY; }
void addLooker( Int playerIndex );
void removeLooker( Int playerIndex );
void addShrouder( Int playerIndex );
void removeShrouder( Int playerIndex );
CellShroudStatus getShroudStatusForPlayer( Int playerIndex ) const;
// @todo: All of these are inline candidates
UnsignedInt getThreatValue( Int playerIndex );
void addThreatValue( Int playerIndex, UnsignedInt threatValue );
void removeThreatValue( Int playerIndex, UnsignedInt threatValue );
UnsignedInt getCashValue( Int playerIndex );
void addCashValue( Int playerIndex, UnsignedInt cashValue );
void removeCashValue( Int playerIndex, UnsignedInt cashValue );
void invalidateShroudedStatusForAllCois(Int playerIndex);
#ifdef PM_CACHE_TERRAIN_HEIGHT
inline Real getLoTerrain() const { return m_loTerrainZ; }
inline Real getHiTerrain() const { return m_hiTerrainZ; }
#endif
void getCellCenterPos(Real& x, Real& y);
inline CellAndObjectIntersection *getFirstCoiInCell() { return m_firstCoiInCell; }
#ifdef _DEBUG
void validateCoiList();
#endif
// intended only for CellAndObjectIntersection.
void friend_addToCellList(CellAndObjectIntersection *coi);
// intended only for CellAndObjectIntersection.
void friend_removeFromCellList(CellAndObjectIntersection *coi);
};
//=====================================
/**
A PartitionData is the part of an Object that understands
how to maintain the Object in the space partitioning system.
*/
//=====================================
class PartitionData : public MemoryPoolObject
{
MEMORY_POOL_GLUE_WITH_USERLOOKUP_CREATE(PartitionData, "PartitionDataPool" )
private:
enum DirtyStatus
{
NOT_DIRTY,
NEED_COLLISION_CHECK,
NEED_CELL_UPDATE_AND_COLLISION_CHECK
};
Object *m_object; ///< Object this module is for
GhostObject *m_ghostObject; ///< Temporary object used when real object is gone but player thinks it's there because of fog.
PartitionData *m_next; ///< next module in master list
PartitionData *m_prev; ///< prev module in master list
PartitionData *m_nextDirty;
PartitionData *m_prevDirty;
Int m_coiArrayCount; ///< number of COIs allocated (may be more than are in use)
Int m_coiInUseCount; ///< number of COIs that are actually in use
CellAndObjectIntersection *m_coiArray; ///< The array of COIs
Int m_doneFlag;
DirtyStatus m_dirtyStatus;
ObjectShroudStatus m_shroudedness[MAX_PLAYER_COUNT];
ObjectShroudStatus m_shroudednessPrevious[MAX_PLAYER_COUNT]; ///m_prevDirty = this;
*pListHead = this;
}
void removeFromDirtyModules(PartitionData** pListHead)
{
m_dirtyStatus = NOT_DIRTY;
if (m_nextDirty)
m_nextDirty->m_prevDirty = m_prevDirty;
if (m_prevDirty)
m_prevDirty->m_nextDirty = m_nextDirty;
else
*pListHead = m_nextDirty;
m_prevDirty = 0;
m_nextDirty = 0;
}
};
//=====================================
/**
this is an ABC. PartitionData::iterate allows you to pass multiple filters
to filter out objects you don't want. it calls this method on the objects
in question; any that get false returned, are not iterated. Note that
either modMain or posMain will be null, but not both: the filter must be aware
of this, and respond appropriately. (ie, the filter may be used for filtering
against an object, or against a position.)
*/
class PartitionFilter
{
public:
virtual Bool allow(Object *objOther) = 0;
#if defined(_DEBUG) || defined(_INTERNAL)
virtual const char* debugGetName() = 0;
#endif
};
//=====================================
/**
Reject any objects that aren't currently flying.
*/
class PartitionFilterIsFlying : public PartitionFilter
{
public:
PartitionFilterIsFlying() { }
virtual Bool allow(Object *objOther);
#if defined(_DEBUG) || defined(_INTERNAL)
virtual const char* debugGetName() { return "PartitionFilterIsFlying"; }
#endif
};
//=====================================
class PartitionFilterWouldCollide : public PartitionFilter
{
private:
Coord3D m_position;
GeometryInfo m_geom;
Real m_angle;
Bool m_desiredCollisionResult; // collision must match this for allow to return true
public:
PartitionFilterWouldCollide(const Coord3D& pos, const GeometryInfo& geom, Real angle, Bool desired);
virtual Bool allow(Object *objOther);
#if defined(_DEBUG) || defined(_INTERNAL)
virtual const char* debugGetName() { return "PartitionFilterWouldCollide"; }
#endif
};
//=====================================
/**
Reject any objects that aren't controlled by the same player.
*/
class PartitionFilterSamePlayer : public PartitionFilter
{
private:
const Player *m_player;
public:
PartitionFilterSamePlayer(const Player *player) : m_player(player) { }
virtual Bool allow(Object *objOther);
#if defined(_DEBUG) || defined(_INTERNAL)
virtual const char* debugGetName() { return "PartitionFilterSamePlayer"; }
#endif
};
//=====================================
/**
Reject any objects that don't match the alliance
affiliations compared with 'm_obj'. You
may reject objects that are allied, neutral,
or enemy with respect to it.
*/
class PartitionFilterRelationship : public PartitionFilter
{
private:
const Object *m_obj;
Int m_flags;
public:
enum
{
ALLOW_ALLIES = (1< OffsetVec;
typedef std::vector RadiusVec;
#endif
PartitionData *m_moduleList; ///< master partition module list
Region3D m_worldExtents; ///< should be same as TheTerrainLogic->getExtents()
Real m_cellSize; ///< edge size of each cell, in world coord space
Real m_cellSizeInv; ///< 1/cellSize (used for efficiency)
Int m_cellCountX; ///< number of cells, x
Int m_cellCountY; ///< number of cells, y
Int m_totalCellCount; ///< x * y
PartitionCell* m_cells; ///< array of cells
PartitionData* m_dirtyModules;
Bool m_updatedSinceLastReset; ///< Used to force a return of OBJECTSHROUD_INVALID before update has been called.
std::queue m_pendingUndoShroudReveals; ///< Anything can queue up an Undo to happen later. This is a queue, because "later" is a constant
#ifdef FASTER_GCO
Int m_maxGcoRadius;
RadiusVec m_radiusVec;
#endif
protected:
/**
This is an internal function that is used to implement the public
getClosestObject and iterateObjects calls.
*/
Object *PartitionManager::getClosestObjects(
const Object *obj,
const Coord3D *pos,
Real maxDist,
DistanceCalculationType dc,
PartitionFilter **filters,
SimpleObjectIterator *iter, // if nonnull, append ALL satisfactory objects to the iterator (not just the single closest)
Real *closestDistArg,
Coord3D *closestVecArg
);
void shutdown( void );
/// used to validate the positions for findPositionAround family of methods
Bool tryPosition( const Coord3D *center, Real dist, Real angle,
const FindPositionOptions *options, Coord3D *result );
typedef Int (*CellAlongLineProc)(PartitionCell* cell, void* userData);
Int iterateCellsAlongLine(const Coord3D& pos, const Coord3D& posOther, CellAlongLineProc proc, void* userData);
// note iterateCellsBreadthFirst returns the cell index that made the CellBreadthFirstProc return
// non-Zero.
typedef Int (*CellBreadthFirstProc)(PartitionCell* cell, void* userData);
Int iterateCellsBreadthFirst(const Coord3D *pos, CellBreadthFirstProc proc, void *userData);
#ifdef FASTER_GCO
Int calcMinRadius(const ICoord2D& cur);
void calcRadiusVec();
#endif
// These are all friend functions now. They will continue to function as before, but can be passed into
// the DiscreteCircle::drawCircle function.
friend void hLineAddLooker(Int x1, Int x2, Int y, void *playerIndex);
friend void hLineRemoveLooker(Int x1, Int x2, Int y, void *playerIndex);
friend void hLineAddShrouder(Int x1, Int x2, Int y, void *playerIndex);
friend void hLineRemoveShrouder(Int x1, Int x2, Int y, void *playerIndex);
friend void hLineAddThreat(Int x1, Int x2, Int y, void *threatValueParms);
friend void hLineRemoveThreat(Int x1, Int x2, Int y, void *threatValueParms);
friend void hLineAddValue(Int x1, Int x2, Int y, void *threatValueParms);
friend void hLineRemoveValue(Int x1, Int x2, Int y, void *threatValueParms);
void processPendingUndoShroudRevealQueue(Bool considerTimestamp = TRUE); ///< keep popping and processing untill you get to one that is in the future
void resetPendingUndoShroudRevealQueue(); ///< Just delete everything in the queue without doing anything with them
public:
PartitionManager( void );
virtual ~PartitionManager( void );
// --------------- inherited from Subsystem interface -------------
virtual void init( void ); ///< initialize
virtual void reset( void ); ///< system reset
virtual void update( void ); ///< system update
// ----------------------------------------------------------------
// --------------- inherited from Snapshot interface --------------
void crc( Xfer *xfer );
void xfer( Xfer *xfer );
void loadPostProcess( void );
inline Bool getUpdatedSinceLastReset( void ) const { return m_updatedSinceLastReset; }
void registerObject( Object *object ); ///< add thing to system
void unRegisterObject( Object *object ); ///< remove thing from system
void registerGhostObject( GhostObject* object); ///isInListDirtyModules(&m_dirtyModules);
}
inline void prependToDirtyModules(PartitionData* o)
{
o->prependToDirtyModules(&m_dirtyModules);
}
inline void removeFromDirtyModules(PartitionData* o)
{
o->removeFromDirtyModules(&m_dirtyModules);
}
inline void removeAllDirtyModules()
{
while (m_dirtyModules)
{
PartitionData *tmp = m_dirtyModules;
removeFromDirtyModules(tmp);
}
}
/**
Reveals the map for the given player, but does not override Shroud generation. (Script)
*/
void revealMapForPlayer( Int playerIndex );
/**
Reveals the map for the given player, AND permanently disables all Shroud generation (Observer Mode).
*/
void revealMapForPlayerPermanently( Int playerIndex );
/**
Adds a layer of permanent blindness. Used solely to undo the permanent reveal for debugging
*/
void undoRevealMapForPlayerPermanently( Int playerIndex );
/**
Resets the shroud for the given player with passive shroud (can re-explore).
*/
void shroudMapForPlayer( Int playerIndex );
/** this doesn't change the actual shroud values in logic, just pushes them
back out to the display... this should generally only be used when the local
player changes.
*/
void refreshShroudForLocalPlayer();
/**
Shrouded has no absolute meaning. It only makes sense to say "Shrouded for him".
*/
CellShroudStatus getShroudStatusForPlayer( Int playerIndex, Int x, Int y ) const;
CellShroudStatus getShroudStatusForPlayer( Int playerIndex, const Coord3D *loc ) const;
Real getGroundOrStructureHeight(Real posx, Real posy);
void getMostValuableLocation( Int playerIndex, UnsignedInt whichPlayerTypes, ValueOrThreat valType, Coord3D *outLocation );
void getNearestGroupWithValue( Int playerIndex, UnsignedInt whichPlayerTypes, ValueOrThreat valType, const Coord3D *sourceLocation,
Int valueRequired, Bool greaterThan, Coord3D *outLocation );
// If saveToFog is true, then we are writing STORE_FOG.
// If saveToFog is false, then we are writing STORE_PERMENANT_REVEAL
void storeFoggedCells(ShroudStatusStoreRestore &outPartitionStore, Bool storeToFog) const;
void restoreFoggedCells(const ShroudStatusStoreRestore &inPartitionStore, Bool restoreToFog);
}; // end class PartitionManager
// -----------------------------------------------------------------------------
inline void PartitionManager::worldToCell(Real wx, Real wy, Int *cx, Int *cy)
{
*cx = REAL_TO_INT_FLOOR((wx - m_worldExtents.lo.x) * m_cellSizeInv);
*cy = REAL_TO_INT_FLOOR((wy - m_worldExtents.lo.y) * m_cellSizeInv);
}
//-----------------------------------------------------------------------------
inline Int PartitionManager::worldToCellDist(Real w)
{
return REAL_TO_INT_CEIL(w * m_cellSizeInv);
}
//-----------------------------------------------------------------------------
inline PartitionCell *PartitionManager::getCellAt(Int x, Int y)
{
return (x < 0 || y < 0 || x >= m_cellCountX || y >= m_cellCountY) ? NULL : &m_cells[y * m_cellCountX + x];
}
//-----------------------------------------------------------------------------
inline const PartitionCell *PartitionManager::getCellAt(Int x, Int y) const
{
return (x < 0 || y < 0 || x >= m_cellCountX || y >= m_cellCountY) ? NULL : &m_cells[y * m_cellCountX + x];
}
//-----------------------------------------------------------------------------
#ifdef FASTER_GCO
// nothing
#else
class CellOutwardIterator
{
private:
PartitionManager *m_mgr;
Int m_cellCenterX, m_cellCenterY;
Int m_maxRadius;
Int m_cellRadius;
Int m_delta[2];
Int m_inc;
Int m_cnt;
Int m_axis;
Int m_iter;
PartitionCell *nextCell(Bool skipEmpties);
public:
CellOutwardIterator(PartitionManager *mgr, Int x, Int y);
~CellOutwardIterator();
PartitionCell *next() { return nextCell(false); }
PartitionCell *nextNonEmpty() { return nextCell(true); }
Int getCurCellRadius() const { return m_cellRadius; }
Int getMaxRadius() const { return m_maxRadius; }
void setMaxRadius(Int max) { m_maxRadius = max; }
};
#endif
//-----------------------------------------------------------------------------
// Inlining
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
// Externals
//-----------------------------------------------------------------------------
extern PartitionManager *ThePartitionManager; ///< object manager singleton
#endif // __PARTITIONMANAGER_H_