Strategy pattern applied

  
Yesterday I started thinking about how to improve the behaviour of one of the enemies on our Master's final project game, Once Upon a Night. At some point, I found myself thinking how the enemy might have to choose among a variety of available attacks once the main character enters the attack range for more than one attack types (obviously, if there is only one kind of attack it may launch, there is no problem). The easiest way would be to stick with a common selection policy (for instance "pick the first one", or "pick randomly"), but it wouldn't be very flexible. Then, almost immediately, one of the GoF patterns sprung to my mind. Of course, I mean the Strategy Pattern. According to their book, the pattern's intent is to define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it.

To make the concept clearer, I'll show you a simple implementation that I sketched last night applied to the attack selection policy for enemies. It should be correct (save for missing includes, which I've omitted) aside from a few typos.

First, some macros and typedefs...

// Attack selection strategies using the same-name design pattern. // Let's say we have an enemy currently chasing the player. // At some point,their distance gets close enough for // the enemy to launch one or several possible attacks. // If more than one attack is available, which one would it select? // This code shows how several selection choices may be // available at once by using the well-known strategy pattern. #define SAFEDELETE(x) if (x) {delete x; x=NULL;} #define SAFEDELETEARRAY(x) if (x) {delete[] x; x=NULL;} // Struct containing a hypothetic attack type data struct TAttackData { std::string name; int damage; int attackRange; int cooldown; int energy; }; // A collection of available attacks, indexed by their name typedef std::map<std::string, TAttackData*> TAttackCollection; // Functor-like struct used to fetch the vector of values of a map struct getValue { template <typename T> typename T::second_type operator()(T keyValuePair) const { return keyValuePair.second; } }; // Return the vector of attacks from an attacks map. std::vector<TAttackData*> getValues(const TAttackCollection&  availableAttacks) { //BEWARE! This is inefficient, it'll copy the vector to return it. //Passing the vector as a parameter might be a better option std::vector<TAttackData*> attacksVector; std::transform(availableAttacks.begin(),availableAttacks.end(), std::back_inserter(attacksVector), getValue()); return attacksVector; }

And now, let's define our base strategy class, and a couple of concrete implementations.

// Base strategy class. class AttackSelectionStrategy { public: virtual TAttackData* selectAttack(const TAttackCollection& availableAttacks)=0; }; // Concrete strategy: an enemy using this strategy will always choose // the highest-damage class HighestDamageStrategy: public AttackSelectionStrategy { public: bool compareHighestDamage(TAttackData* one, TAttackData* other) { return one->cooldown>other->cooldown; } virtual TAttackData* selectAttack(const TAttackCollection&      availableAttacks) { if (!availableAttacks.empty()) { std::vector<TAttackData*> attacks = getValues(availableAttacks); std::sort(attacks.begin(),attacks.end(),   compareHighestDamage); return attacks[0]; } return NULL; } }; // Another concrete strategy: this time, an enemy using it // will choose the available attack that has a lowest cooldown, // so it may attack again as quickly as possible. class LowestCooldownStrategy: public AttackSelectionStrategy { public: bool compareCooldown(TAttackData* one, TAttackData* other) { return one->cooldown<other->cooldown; } virtual TAttackData* selectAttack(const TAttackCollection&     availableAttacks) { if (!availableAttacks.empty()) { std::vector<TAttackData*> attacks = getValues(availableAttacks); std::sort(attacks.begin(),attacks.end(),compareCooldown); return attacks[0]; } return NULL; } };

Next is some sample client code using strategies:

void AnEnemy::selectAvailableAttack() { AttackSelectionStrategy* myStrategy = new HighestDamageStrategy(); setCurrentAttack(myStrategy->selectAttack(mAvailableAttacks)); SAFEDELETE(myStrategy); }

However, this is quite rigid, which defeats the purpose of the pattern. I then thought of a way to select specific strategies. Two different alternatives came to my mind, in both cases using an enumerated type as a discriminant.

//Strategy selector enumerated type enum TStrategyPolicy { HIGHEST_DAMAGE, RANDOM, FIRST, LOWEST_COOLDOWN, LOWEST_ENERGY, WEIGHTED //..etc }; // Now, to implement the strategy selector I have thought of two // different alternatives: // I could use a factory function that had a switch statement // on a TStrategyPolicy value, instancing one // or the other strategy on demand. // The second possibility consists on defining a // map <TStrategyPolicy, AttackSelectionStrategy*> // and initializing the map at the beginning. // When the time comes to select a strategy, // the selector function/class would just access the map. // While simpler, it has a bit of overhead since an // instance of all strategies has to be created regardless of if // it is used or not. However, if // a getStrategy() method is used frequently, it may actually turn // out being more efficient, since // every strategy will only be instanced once. //OPTION 1: FACTORY FUNCTION AttackSelectionStrategy* createStrategy(TStrategyPolicy selector) { // Ensure that this function's client frees the // dynamic memory, or memory leaks are bound to appear. switch(selector) {      case HIGHEST_DAMAGE: return new HighestDamageStrategy();      case LOWEST_COOLDOWN: return new LowestCooldownStrategy();      //...remaining cases        default: return NULL; } } //OPTION 2: USE A MAP OF STRATEGIES AND RETRIEVE AN INSTANCE WHENEVER //YOU WANT typedef std::map<TStrategyPolicy,AttackSelectionStrategy*> TStrategyCollection; class StrategySelector { private: TStrategyCollection mStrategies; public: // The initialization is hardcoded, which would require to // recompile any time a new strategy was added // (this will also happen using a factory function), but without // any reflection-like device that'd // allow us to dynamically load on runtime a particular subclass // (I'll have to research more on RTTI or some libraries) // there's little else to do. // If I'm mistaken, which is really likely, I'm open to // corrections :) void initStrategies() { cleanupStrategies(); mStrategies[HIGHEST_DAMAGE]= new HighestDamageStrategy(); mStrategies[LOWEST_COOLDOWN]= new LowestCooldownStrategy(); //... } // Free memory void cleanupStrategies() { if (!mStrategies.empty()) { for (TStrategyCollection::iterator it=mStrategies.begin();      it!=mStrategies.end();++it) {      SAFEDELETE(it->second); } mStrategies.clear(); } } // Retrieve a given strategy. AttackSelectionStrategy* getStrategy(TStrategyPolicy index) { if (!mStrategies.empty() && mStrategies.find(index)!=mStrategies.end()) { return mStrategies[index]; } return NULL; } };

Any of these two alternatives would allow for some interesting results. For instance, you might script behaviours for enemies, such as 'Aggressive', 'Defensive', 'Ranged', etc, and the attack selection policy might be a behaviour-dependent parameter.

The client method I presented before would be rewritten to this (of course, myStrategy can be refactored to an AnEnemy class member, which would require at least a setter method allowing changes on the strategy selection algorithm to apply):

//Using option 1 void AnEnemy::selectAvailableAttack(TStrategyPolicy strategyId) { AttackSelectionStrategy* myStrategy = createStrategy(strategyId); if (myStrategy) { setCurrentAttack(myStrategy->selectAttack(mAvailableAttacks)); SAFEDELETE(myStrategy); } // else throw exception, or do something to notify the strategyId // wasn't valid } // Using option 2: assume StrategySelector is a Singleton // (http://en.wikipedia.org/wiki/Singleton_pattern). void AnEnemy::selectAvailableAttack(TStrategyPolicy strategyId) { AttackSelectionStrategy* myStrategy = StrategySelector::getInstance()->getStrategy(strategyId); if (myStrategy) { setCurrentAttack(myStrategy->selectAttack(availableAttacks)); myStrategy=NULL; // Don't delete the strategy here: that'll be handled by // the StrategySelector when it invokes its cleanup method } // else throw exception, or do something to notify the strategyId // wasn't valid }

Now, we can define as many strategies as we want, and the code for the class AnEnemy won't have to be changed to do that. We may provide the strategy selection policy externally through the value of an int that would be cast to a TStrategyPolicy.

In fact, using LUA and luabind, which allows exposing C++ enums to LUA, we wouldn't even need to care about casting between enums and ints.

Unfortunately, due to tight time constraints, we've been trimming the variety of attacks that enemies can launch on our game, so this code will never see the light beyond this modest blog post.


LARGELY UNRELATED RANT: I've been a happy user of the Opera browser for close to 8 years now. However, after the 10.60 release some Google services, such as Google Calendar, Gmail or Google Docs, are screwed up in varying degrees of severity. My biggest annoyance is at the moment Docs. Besides being close to unusable when using their new version, I've been crashing every time it auto-saves, or when I manually save my work. Restarting the browser and logging back in every two minutes is a real pain in the a#se, so I've ended up switching to Firefox so that I could finish this post without fear of having to restart again.

People in Opera Software, PLEASE, can you fix that???