ryzom/server/src/frontend_service/pair_selector.h

   1 // Ryzom - MMORPG Framework <http://dev.ryzom.com/projects/ryzom/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program 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 Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17
  18
  19 #ifndef NL_PAIR_SELECTOR_H
  20 #define NL_PAIR_SELECTOR_H
  21
  22 #include "nel/misc/types_nl.h"
  23 #include "game_share/entity_types.h"
  24 #include "fe_types.h"
  25 #include "selection_generator.h"
  26 #include <vector>
  27 #include <functional>
  28
  29
  30 /*
  31  * Forward declarations
  32  */
  33 class CVisionArray;
  34
  35
  36 /*
  37  * Items of TPairVector
  38  */
  39 class TPairCE
  40 {
  41 public:
  42         // Constructor
  43         TPairCE( TClientId c, CLFECOMMON::TCLEntityId e ) : ClientId(c), CeId(e) {}
  44
  45         // Copy constructor
  46         TPairCE( const TPairCE& src )
  47         {
  48                 operator=( src );
  49         }
  50
  51         // Assignment operator
  52         TPairCE& operator=( const TPairCE& src )
  53         {
  54                 // no need to check ( &src != this )
  55                 ClientId = src.ClientId;
  56                 CeId = src.CeId;
  57                 return *this;
  58         }
  59
  60         // Comparison operator ==
  61         friend bool operator==( const TPairCE& e1, const TPairCE& e2 )
  62         {
  63                 return (e1.ClientId == e2.ClientId) && (e1.CeId == e2.CeId );
  64         }
  65
  66         // Classical comparison operator < (not needed: we compare by distance instead)
  67         /*friend bool operator<( const TPairCE& e1, const TPairCE& e2 )
  68         {
  69                 if (e1.ClientId < e2.ClientId)
  70                         return true;
  71                 else if ( e1.ClientId == e2.ClientId )
  72                         return (e1.CeId < e2.CeId );
  73                 else
  74                         return false;
  75         }*/
  76
  77         TClientId                               ClientId;
  78         CLFECOMMON::TCLEntityId CeId;
  79 };
  80
  81
  82 /*
  83  * Container for pairs sorted by distance
  84  */
  85 typedef std::vector<TPairCE> TPairVector;
  86
  87
  88 /*
  89  * Comparison function object for TPairCE
  90  */
  91 struct TComparePairCE : public std::binary_function < const TPairCE&, const TPairCE&, bool >
  92 {
  93         /// Constructor
  94         TComparePairCE( CVisionArray *visionarray ) :
  95                 _VisionArray(visionarray)
  96                 {}
  97
  98         /// Comparison operator
  99         bool operator()( const TPairCE& e1, const TPairCE& e2 );
 100
 101 private:
 102
 103         /// Access to vision array to know distances
 104         CVisionArray    *_VisionArray;
 105 };
 106
 107
 108 /*
 109  * Type of index to pair
 110  */
 111 typedef sint32 TPairIndex;
 112
 113
 114 /*
 115  * TPairRange: ranges in PairsByDistance, used by pseudosort algorithm
 116  */
 117 struct TPairRange
 118 {
 119         uint                            IndexInRanges;
 120         TPairIndex                      NumberOfElements;
 121         CLFECOMMON::TCoord      DistThreshold;
 122
 123         // The "begin index" of the range depends on the previous ranges
 124         // (prevents from updating following ranges every time an index boundary changes)
 125         TPairIndex beginIndex( const std::vector<TPairRange>& vect ) const
 126         {
 127                 uint i;
 128                 TPairIndex sum = 0;
 129                 for ( i=0; i!=IndexInRanges; ++i )
 130                 {
 131                         sum += vect[i].NumberOfElements;
 132                 }
 133                 return sum;
 134         }
 135 };
 136
 137
 138 /*
 139  * Vector of ranges
 140  */
 141 typedef std::vector<TPairRange> TRanges;
 142
 143
 144
 145 /**
 146  * Pair Selector.
 147  * It selects the pairs <Client,Entity> for which the priorities of the properties
 148  * will be calculated. The pairs are stored in a vector and this one is sorted or
 149  * pseudosorted (depending on its size) by distance.
 150  *
 151  * \author Olivier Cado
 152  * \author Nevrax France
 153  * \date 2002
 154  */
 155 class CPairSelector
 156 {
 157 public:
 158
 159         /// Type of selection strategy
 160         enum TSelectionStrategy { Power2WithCeiling = 0, Scoring = 1 };
 161
 162         /// Constructor
 163         CPairSelector();
 164
 165         /// Initialization
 166         void                            init( CVisionArray *va );
 167
 168                                                 // _______________________
 169                                                 // For the vision provider
 170
 171         /// Add to the container
 172         void                            addPair( TClientId clientid, CLFECOMMON::TCLEntityId ceid, CLFECOMMON::TCoord distance );
 173
 174         /// Remove from the container
 175         void                            removePair( TClientId clientid, CLFECOMMON::TCLEntityId ceid );
 176
 177         /// Remove from the container all pairs with the specified clientid
 178         void                            removeAllPairs( TClientId clientid );
 179
 180                                                 // _______________________________
 181                                                 // For the priority subsystem root
 182
 183         /// Return true if there is no pair
 184         bool                            empty() { return _PairsByDistance.empty(); }
 185
 186         /// Sort or pseudosort the pairs, and initialize selection cycle. Must be called before a series of selectNextPair().
 187         void                            sortPairs();
 188
 189         /// Set the selection strategy
 190         void                            setSelectionStrategy( TSelectionStrategy strat );
 191
 192                                                 // ___________________
 193                                                 // For the prioritizer
 194
 195         /// Select the next pair to prioritize, or return NULL if there is no more pairs for this cycle
 196         const TPairCE           *selectNextPair();
 197
 198                                                 // ______________
 199                                                 // For statistics
 200
 201         /// Return the number of pairs in the container
 202         TPairIndex                      nbPairs() const { return _PairsByDistance.size(); }
 203
 204         /// Print the scores if there is a scoring selection generator
 205         void                            printScores() const;
 206
 207         /// Display the ranges (debugging)
 208         void                            printRanges( bool checkIntegrity ) const;
 209
 210         /// Display the pairs (debugging)
 211         void                            printPairs() const;
 212
 213         /// Pseudosort or sort (read)
 214         bool                            PseudoSort;
 215
 216         /// Selection strategy (read)
 217         TSelectionStrategy      SelStrategy;
 218
 219         /// Average number of pairs per range (read/write)
 220         TPairIndex                      NbPairsPerRange;
 221
 222         /// Number of pairs to select per cycle (read)
 223         TPairIndex                      NbPairsToSelect;
 224
 225         /// Min number of pairs to select per cycle (read/write)
 226         TPairIndex                      MinNbPairsToSelect;
 227
 228 protected:
 229
 230         /// Easy access to the last pair
 231         TPairCE&                        lastPair() { nlassert( ! _PairsByDistance.empty() ); return _PairsByDistance.back(); }
 232
 233         /// Return the number of ranges for pseudosort
 234         uint32                          nbRanges() const { return _Ranges.size(); }
 235
 236         /// Easy access to the last range for pseudosort
 237         TPairRange&                     lastRange() { nlassert( ! _Ranges.empty() ); return _Ranges.back(); }
 238
 239         /// Easy access to the last range for pseudosort (const version)
 240         const TPairRange&       lastRange() const { nlassert( ! _Ranges.empty() ); return _Ranges.back(); }
 241
 242         // Update ranges after deleting a pair
 243         void                            adjustRangesAfterDeleting();
 244
 245         /// Add a range for pseudosort, and resample the distance thresholds.
 246         void                            addRange();
 247
 248         /// Remove the last range (for pseudosort) when it's empty, and resample the distance thresholds.
 249         void                            removeLastRange();
 250
 251         /// Setup selection generator, using SelStrategy (the argument is meaningful only in strategy P2C)
 252         void                            setupSelectionGenerator( ISelectionGenerator::TSelectionLevel ceiling );
 253
 254         /// Select next level. Call selectNextPair() after selectNextLevel().
 255         void                            selectNextLevel();
 256
 257         /// Calculate NbPairsToSelect taking into account the user loop time
 258         void                            calcNbPairsToSelect();
 259
 260         /// Return the number of levels corresponding to the current size of _PairsByDistance
 261         uint                            getNbLevels() { return (_PairsByDistance.size() / NbPairsToSelect) + 1; }
 262
 263 private:
 264
 265         /// Pairs sorted by distance
 266         TPairVector                     _PairsByDistance;
 267
 268         /// Ranges used by pseudosort algorithm
 269         TRanges                         _Ranges;
 270
 271         /// Index of the current range for pseudosorting
 272         uint32                          _CurrentRangeIndex;
 273
 274         /// Selection generator (either CP2CGenerator or CScoringGenerator)
 275         ISelectionGenerator     *_SelGenerator;
 276
 277         /// Beginning index of the current level given by the selection generator
 278         TPairIndex                      _BeginIndex;
 279
 280         /// Index of currently selected pair
 281         TPairIndex                      _NextPairIndex;
 282
 283         /// Difference between previous and current NbPairsToSelect;
 284         sint32                          _NPSDelta;
 285
 286         /// Vision Array
 287         CVisionArray            *_VisionArray;
 288 };
 289
 290
 291 #endif // NL_PAIR_SELECTOR_H
 292
 293 /* End of pair_selector.h */