/*****************************************************************************
The Dark Mod GPL Source Code
This file is part of the The Dark Mod Source Code, originally based
on the Doom 3 GPL Source Code as published in 2011.
The Dark Mod Source Code 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. For details, see LICENSE.TXT.
Project: The Dark Mod (http://www.thedarkmod.com/)
******************************************************************************/
/*!
* This is the interface for an n-tree structure which sorts and holds
* darkmod hiding spots.
*
*
*
*/
#ifndef DARKMOD_HIDING_SPOT_TREE
#define DARKMOD_HIDING_SPOT_TREE
/*!
// @structure darkModHidingSpot
// @author SophisticatedAZombie (DMH)
// This structure holds information about a hiding spot.
*/
struct darkModHidingSpot
{
aasGoal_t goal;
// The hiding spot characteristic bit flags
// as defined by the darkModHidingSpotType enumeration
int hidingSpotTypes;
// The light quotient of the spot.
float lightQuotient;
// The hiding spot "hidingness" quality, without distance from the search
// center factored in.
float qualityWithoutDistanceFactor;
// The hiding spot "hidingness" quality, from 0 to 1.0
float quality;
};
//-------------------------------------------------------------------------
struct TDarkmodHidingSpotAreaNode
{
// greebo: This is a unique ID to resolve pointers after map restore
int id;
unsigned int aasAreaIndex;
unsigned int count;
TDarkmodHidingSpotAreaNode* p_prevSibling;
TDarkmodHidingSpotAreaNode* p_nextSibling;
// Each area node holds a list of hiding spots
idList spots;
// Quality of the best spot in the area
float bestSpotQuality;
// The extents
idBounds bounds;
};
//---------------------------------------------------------------------------
class CDarkmodHidingSpotTree
{
private:
// The highest used area node id (0 on initialisiation)
int maxAreaNodeId;
protected:
// The number of areas
unsigned int numAreas;
unsigned int numSpots;
// The first area
TDarkmodHidingSpotAreaNode* p_firstArea;
TDarkmodHidingSpotAreaNode* p_lastArea;
// Mapping methods, retrieves node pointers for indices and vice versa
int getAreaNodeId(TDarkmodHidingSpotAreaNode* area) const; // returns -1 for invalid pointer
TDarkmodHidingSpotAreaNode* getAreaNode(int areaNodeId) const; // returns NULL for invalid Id
/*!
* Gets the Nth spot from the tree, where N is a 0 based index.
* This is a slow iteration from the beginning of the tree
* and should only be used if the index being retrieved is less than the
* previous index retrieved or if none has yet been retrieved
* since the last time the tree was altered.
*
* @return Pointer to spot, NULL if index was out of bounds
*/
darkModHidingSpot* getNthSpotInternal(unsigned int index, idBounds& out_areaNodeBounds);
/*!
* This method sorts the area by hiding spot light internally
*
* @param inout_p_firstNode On input, pointer to the first point in the area
* On return, pointer to the first point in the list, sorted from
* greatest to least quality.
*
* @param numSpots The number of spots in the list passed in. The number of
* spots is not changed by sorting, unless the algorithm is broken, in which
* case you should fix it yourself, damnit.
*/
void quicksortHidingSpotList(darkModHidingSpot*& inout_p_firstNode, unsigned int numSpots);
/*!
* This method sorts the given area list
*
* @param inout_p_firstNode On input, pointer to the first area
* On return, pointer to the first area in the list, sorted from
* greatest to least quality.
*
* @param numAreas The number of areas in the list passed in.
*/
void quicksortAreaList
(
TDarkmodHidingSpotAreaNode*& inout_p_firstNode,
unsigned int numAreas
);
/*!
* This method breaks a node into 8 rough "octants"
* The original node is used as one of the octants, and
* the other nodes created between this node and the next
* original node in the list
*
* @param in_p_areaNode The node that is to be sub-divided.
*
* @param out_numSubAreasWithPoints Passes back out the number
* of sub areas (up to 8) that had points.
*
* @param out_subAreas Passes back the pointers to the sub
* areas that had points (up to 8)
*/
bool subDivideArea
(
TDarkmodHidingSpotAreaNode* in_p_areaNode,
unsigned int& out_numSubAreasWithPoints,
TDarkmodHidingSpotAreaNode* out_p_subAreas[8]
);
public:
/*!
* Constructor for an empty tree
*/
CDarkmodHidingSpotTree();
/*!
* Destroys all nodes and clears the
* tree memory usage on destruction
*/
~CDarkmodHidingSpotTree();
/*!
* Destroys all nodes and clears the tree memory
* usage.
*/
void clear();
void Save( idSaveGame *savefile ) const;
void Restore( idRestoreGame *savefile );
/*!
* Get the number of spots in the entire tree
*/
ID_INLINE unsigned int getNumSpots()
{
return numSpots;
}
/*!
* Gets the node for an area by area index
*/
TDarkmodHidingSpotAreaNode* getArea(unsigned int areaIndex);
/*!
* Inserts an area and returns the are node handle
* for use in inserting hiding spots.
*/
TDarkmodHidingSpotAreaNode* insertArea(unsigned int areaIndex);
/*!
* Tests a spot for redundancy with spots already in
* the same area. Redundancy occurs if the distance
* is less than the redundancy distance.
* If redundant, the existing point may be updated
* to higher quality values if the new point was
* of higher quality than the existing point.
*
* @return true if redundant
* @return false if not redundant
*/
bool determineSpotRedundancy
(
TDarkmodHidingSpotAreaNode* p_areaNode,
aasGoal_t goal,
int hidingSpotTypes,
float quality,
float redundancyDistance
);
/*!
* Inserts a hiding spot into a given area node.
*
* @param p_areaNode The area node to which the point should be added
*
* @param goal The goal descriptor of the point
*
* @param hidingSpotTypes The types of hiding spot that apply to the point
*
* @param quality The measure of hiding spot quality from 0.0 to 1.0
*
* @param redundancyDistance The distance between points for a unique point
* to be created. If the new point is within this distance from a point
* already in the area, the points will be combined.
* If this number is < 0.0, then no redundancy testing is done.
*
*/
bool insertHidingSpot
(
TDarkmodHidingSpotAreaNode* p_areaNode,
aasGoal_t goal,
int hidingSpotTypes,
float lightQuotient,
float qualityWithoutDistanceFactor,
float quality,
float redundancyDistance
);
/*!
* This method is intended to be used once all of the
* nodes in the tree have been created and all the points
* inserted. It subdivides each area in the tree
* into octants based on x/y/z midline partitions.
* It does this over and over on any area which contains
* more than the limiting number of points.
*
* @param maxPointsPerArea
*
* @return true on succes
*
* @return false on failure, structure may be corrupted due
* to failure to allocate new area nodes. This should only
* happen if the computer critically runs out of memory
* (time to shut down the application).
*
*/
bool subDivideAreas(unsigned int maxPointsPerArea);
/*!
* Starts an iteration of the areas in the tree
*/
TDarkmodHidingSpotAreaNode* getFirstArea();
/*!
* Moves forward in an iteration of the tree
*/
TDarkmodHidingSpotAreaNode* getNextArea(TDarkmodHidingSpotAreaNode* curArea);
/*!
* Gets first hiding spot in area
*/
darkModHidingSpot* getFirstHidingSpotInArea(TDarkmodHidingSpotAreaNode* area);
/*!
* Gets next hiding spot in area
*/
// greebo: Commented this out, the hidingspot structures are a linked list anyway.
//darkModHidingSpot* getNextHidingSpotInArea(TDarkModHidingSpotTreeIterationHandle& inout_spotHandle);
/*!
* This speeds up requests for the Nth spot if N is >= the
* last N requested and not by much (such as N+1)
*
* @param index The index of the spot to get
*
*/
darkModHidingSpot* getNthSpot(unsigned int index);
/*!
* This speeds up requests for the Nth spot if N is >= the
* last N requested and not by much (such as N+1)
*
* @param index The index of the spot to get.
*
* @param out_areaBounds The bounds of the sub-area containing
* the spot
*
*/
darkModHidingSpot* getNthSpotWithAreaNodeBounds(unsigned int index, idBounds& out_areaNodeBounds);
/*!
* Attempts to split off one Nth of the tree (1/N) in a logical fashion
* for sharing a search. The caller provides a tree which after the call
* contains only the areas and spots removed from this tree.
*
* @param N The fraction 1/Nth of this tree will be moved to the other tree
* If N is 0 nothing is moved.
*
* @param out_otherTree This is the tree to which the fraction of the tree
* will be moved. The tree is cleared before any areas or spots are moved
* to it.
*/
//bool getOneNth(unsigned int N, CDarkmodHidingSpotTree& out_otherTree); // grayman #3857
/*!
* This copies this tree into another tree.
*/
bool copy(CDarkmodHidingSpotTree* p_out_otherTree);
/*!
* This method rescores the points and repriortizes the list based on a new search center.
* This can be used if a new stimulus is detected while searching, to bias the search
* toward the new stimulous.
*
*/
bool sortForNewCenter(idVec3 center, float searchRadius);
};
#endif