Encapsulate a family of algorithms using Strategy Pattern

The scenario
Suppose we are writing a game where the world (or at least some part of it) is full of evil (sounds familiar?) and the goal of the player is to free the world from the grasp of evil. The player will make an epic journey through different levels, face different enemies and need to kill them. The enemies will attack the player too, no doubt. In general the enemies will use some simple algorithm to attack to the player. But to make the game more challenging and interesting we want to introduce some sophisticated attacking algorithms in the enemies. For example, some enemies will go defensive when their health is low, some will go into more attacking position based on the situation and some can have more complex algorithm which considers the number of total enemies present, though all the enemies will not support every algorithms. For example, only a level boss can have a complex attacking algorithm. And these enemies will be able to change their attacking algorithm at run time. So we need a good design which will give us enough flexibility in managing the attacking algorithms.

Flexibility that we want to achieve

  • Different enemies can have same algorithm.
  • It should be easier to modify an existing algorithm.
  • We should be able to add new algorithms without much problem.
  • We should be able to add new types of enemies without much problem.
  • We should be able to vary the algorithm itself and other things of the enemy independently.

A naive design
We have a base EnemyBot class which is the super class for all enemies. For this moment we have three types of enemies: enemy with gun, enemy with sword and level boss. They are encapsulated by the classes GunnerBot, SwordyBot and BossBot respectively. And right now we have four attacking algorithms in out hand: A simple attacking algorithm, an aggressive algorithm where the enemy will risk its life, a defensive algorithm and a grid algorithm which is the most complex one. Only a level boss can use this grid algorithm. EnemyBot has a virtual attack function which we are going to override in sub enemy classes. In this function we will use if-else against the current algorithm and code that algorithm. Something like this:

void GunnerBot::attack() {
    if (currentAlgo == SIMPLE_ATTACK) {
        // implement simple attack
    } else if (currentAlgo == AGGRESSIVE_ATTACK) {
        // implement aggressive attack
    } else if (currentAlgo == DEFENSIVE_ATTACK) {
        // implement defensive attack
    }
}

void SwordyBot::attack() {
    if (currentAlgo == SIMPLE_ATTACK) {
        // implement simple attack
    } else if (currentAlgo == AGGRESSIVE_ATTACK) {
        // implement aggressive attack
    } else if (currentAlgo == DEFENSIVE_ATTACK) {
        // implement defensive attack
    }
}

void BossBot::attack() {
    if (currentAlgo == SIMPLE_ATTACK) {
        // implement simple attack
    } else if (currentAlgo == AGGRESSIVE_ATTACK) {
        // implement aggressive attack
    } else if (currentAlgo == DEFENSIVE_ATTACK) {
        // implement defensive attack
    } else if (currentAlgo == GRID_ATTACK) {
        // implement grid attack
    }
}

Note that only BossBot is able to make a grid attack.

Problems with the naive design

  • Every enemy bot implements it’s attacking algorithm in it’s own way, e.g. all three of them have their own implementations of algorithms except the grid algorithm. None of them are sharing the implementations. The same implementation is present in multiple places. It is not possible to move the implementations in base class either, as all algorithms are not supported by all enemies (e.g. all enemies will have a grid algorithm then which we don’t want). This design may lead to complete different behaviors of same algorithm in different enemies.
  • Modifying an existing algorithm is obviously difficult. We need to find out all the enemy classes and change in every places to modify one. For example, if we want to change the behavior of simple algorithm then we need to change in all three enemy classes.
  • Adding a new enemy or algorithm is difficult with this design. And they can’t be changed without affecting one another. The enemy behaviors and attacking algorithms are tightly coupled in enemy classes.
  • Implementing attacking algorithms in enemy classes make them unnecessarily heavy, as some algorithms (like the grid) can be sufficiently complex to implement.

A better approach
The root cause of all the problems is the coupling of attacking algorithms in the enemy classes. What if we create a different class hierarchy to encapsulate the algorithms. Every different attacking algorithm will be encapsulated by a different class. But first of all, lets define a base class. We name this AttackStrategy.

class AttackStrategy {
private:
protected:
    string name;
public:
    AttackStrategy();
    virtual ~AttackStrategy();
    virtual void attack() = 0;
    string getName();
};

AttackStrategy::AttackStrategy() {
}

AttackStrategy::~AttackStrategy() {
}

string AttackStrategy::getName() {
    return name;
}

AttackStrategy defines the basic interface for an attacking algorithm. It declares a pure virtual function attack which the subclasses must need to implement. This makes AttackStrategy an abstract class. Every subclasses will implement attack to implement its specific algorithm.

Next we create a subclass of it named SimpleAttackStrategy which implements the simple attacking algorithm, as the name suggests. It implements simple attacking algorithm in its attack method.

class SimpleAttackStrategy : public AttackStrategy {
private:
public:
    SimpleAttackStrategy();
    virtual ~SimpleAttackStrategy();
    void attack();
};

SimpleAttackStrategy::SimpleAttackStrategy() {
    name = "SimpleAttackStrategy";
}

SimpleAttackStrategy::~SimpleAttackStrategy() {
}

void SimpleAttackStrategy::attack() {
    cout << "Attcking with Simple Attack Strategy" << endl;
}

Similarly other three algorithms are implemented by subclasses AggressiveAttackStrategy, DefensiveAttackStrategy and GridAttackStrategy.

class AggressiveAttackStrategy : public  AttackStrategy {
private:
public:
    AggressiveAttackStrategy();
    virtual ~AggressiveAttackStrategy();
    void attack();
};

AggressiveAttackStrategy::AggressiveAttackStrategy() {
    name = "AggressiveAttackStrategy";
}

AggressiveAttackStrategy::~AggressiveAttackStrategy() {
}

void AggressiveAttackStrategy::attack() {
    cout << "Attacking with Aggressive Attack Strategy" << endl;
}

class DefensiveAttackStrategy : public AttackStrategy {
private:
public:
    DefensiveAttackStrategy();
    virtual ~DefensiveAttackStrategy();
    void attack();
};

DefensiveAttackStrategy::DefensiveAttackStrategy() {
    name = "DefensiveAttackStrategy";
}

DefensiveAttackStrategy::~DefensiveAttackStrategy() {
}

void DefensiveAttackStrategy::attack() {
    cout << "Attacking with Defensive Attack Strategy" << endl;
}

class GridAttackStrategy : public AttackStrategy {
private:
public:
    GridAttackStrategy();
    virtual ~GridAttackStrategy();
    void attack();
};

GridAttackStrategy::GridAttackStrategy() {
    name = "GridAttackStrategy";
}

GridAttackStrategy::~GridAttackStrategy() {
}

void GridAttackStrategy::attack() {
    cout << "Attacking with Grid Attack Strategy" << endl;
}

Now we have out strategy classes ready, its time to think how to integrate them with the enemies. We will made slight changes (well … big changes actually) to the enemy classes to go with this new design. First see how the base EnemyBot looks like.

class EnemyBot {
private:
protected:
    AttackStrategy *attackStrategy;
    string name;
public:
    EnemyBot();
    virtual ~EnemyBot();
    virtual void setAttackStrategy(AttackStrategy *strategy);
    virtual void attack();
};

EnemyBot::EnemyBot() {
    attackStrategy = NULL;
    name = "EnemyBot";
}

EnemyBot::~EnemyBot() {
    if (attackStrategy) {
        delete attackStrategy;
    }
}

void EnemyBot::setAttackStrategy(AttackStrategy *strategy) {
    if (attackStrategy) {
        delete attackStrategy;
    }
    cout << "Set " << strategy->getName() << " to " << name << endl;
    attackStrategy = strategy;
}

void EnemyBot::attack() {
    cout << name << " ";
    attackStrategy->attack();
}

We have added an AttackStrategy member in EnemyBot named attackStrategy and also a setter function setAttackStrategy for it. The big change comes in the attack function. It no longer implements any attacking algorithm, neither it has any if-else code. It simply delegates the call to the attackStrategy->attack function. In this way the EnemyBot does not contain any actual code to implement an attacking algorithm. To achieve its attacking behavior it depends on attackStrategy member which can be set by setAttackStrategy at run time.

The subclasses have become simpler too. They don’t need to override the attack method to insert all if-else codes. All they need to do is to override the setAttackStrategy function to exclude the algorithms that they don’t support.

class GunnerBot : public  EnemyBot {
private:
public:
    GunnerBot();
    virtual ~GunnerBot();
    void setAttackStrategy(AttackStrategy *strategy);
};

GunnerBot::GunnerBot() {
    name = "GunnerBot";
    attackStrategy = new SimpleAttackStrategy();
}

GunnerBot::~GunnerBot() {
}

void GunnerBot::setAttackStrategy(AttackStrategy *strategy) {
    if (strategy->getName() == "GridAttackStrategy") {
        return;
    }
    EnemyBot::setAttackStrategy(strategy);
}

class SwordyBot : public EnemyBot {
private:
public:
    SwordyBot();
    virtual ~SwordyBot();
    void setAttackStrategy(AttackStrategy *strategy);
};

SwordyBot::SwordyBot() {
    name = "SwordyBot";
    attackStrategy = new DefensiveAttackStrategy();
}

SwordyBot::~SwordyBot() {
}

void SwordyBot::setAttackStrategy(AttackStrategy *strategy) {
    if (strategy->getName() == "GridAttackStrategy") {
        return;
    }
    EnemyBot::setAttackStrategy(strategy);
}

class BossBot : public EnemyBot {
private:
public:
    BossBot();
    virtual ~BossBot();
};

BossBot::BossBot() {
    name = "BossBot";
    attackStrategy = new GridAttackStrategy();
}

BossBot::~BossBot() {
}

Mark how GridAttackStrategy is ignored by GunnerBot and SwordyBot. Moreover, there is no need to override setAttackStrategy in BossBot as it supports all the algorithms. These subclasses also set a default strategy in their constructor.

How all these work
Lets summarize how all the pieces fit together. First of all, now we have two different class hierarchies. Every classes of AttackStrategy hierarchy encapsulate a specific attacking algorithm. And every classes of EnemyBot hierarchy encapsulate a specific type of enemy. These two hierarchies are largely independent. The strategy classes do not know anything about the enemies. All they know is how to make an attack, regardless of the type of enemy that using them. And enemy classes do not know anything about the attacking algorithms. All they know is that they have a member object which knows how to make an attack. The enemies do not care about the implementation of the algorithm. They just depend on the strategy member and delegates any attacking request to it. When an enemy is instantiated, it has a default strategy. So any attack call will make an attack with default strategy. But this default strategy can be changed anytime by calling the setter. We may want to change a strategy based on various conditions which are independent from the strategy itself. In the setter we first check whether new strategy is supported by the enemy, and if yes, then we change the member strategy object. Any subsequent call to attack will create an attack with new strategy. And this strategy can be changed again any time. Every time the attack call will make an attack with the current strategy object set. That’s how the two hierarchies work together without knowing the details of one another.

Simulation of the design
We want to simulate our new design to verify that everything is working as expected. The Simulator is a sort of dumb class. It has three enemy members (one of each types) and a simulate function. In this function we run a loop 1000 times. At every iteration we generate a random number and based on the value we either make an attack with one enemy or change the attackStrategy of a random enemy to a new random AttackStrategy.

class Simulator {
private:
    GunnerBot *gunner;
    SwordyBot *swordy;
    BossBot *boss;
public:
    Simulator();
    virtual ~Simulator();
    void simulate();
};

Simulator::Simulator() {
    gunner = new GunnerBot();
    swordy = new SwordyBot();
    boss = new BossBot();

    srand(time(NULL));
}

Simulator::~Simulator() {
    delete gunner;
    delete swordy;
    delete boss;
}

void Simulator::simulate() {
    int r;

    for (int i = 0; i < 1000; i++) {
        cout << i << " : ";
        
        r = rand() % 4;

        if (r == 0) {
            gunner->attack();
        } else if (r == 1) {
            swordy->attack();
        } else if (r == 2) {
            boss->attack();
        } else {
            r = rand() % 3;
            EnemyBot *bot;

            if (r == 0) {
                bot = gunner;
            } else if (r == 1) {
                bot = swordy;
            } else {
                bot = boss;
            }

            r = rand() % 4;

            if (r == 0) {
                bot->setAttackStrategy(new SimpleAttackStrategy());
            } else if (r == 1) {
                bot->setAttackStrategy(new AggressiveAttackStrategy());
            } else if (r == 2) {
                bot->setAttackStrategy(new DefensiveAttackStrategy());
            } else {
                bot->setAttackStrategy(new GridAttackStrategy());
            }
        }
    }
}

The main function is more straight forward. It only creates a simulator and run the simulation.

int main(int argc, char** argv) {
    Simulator *sim = new Simulator();
    sim->simulate();
    delete sim;

    return 0;
}

Simulation result
First 50 steps of output from a sample simulation run is shown below. The full output file for this run is available here.

0 : SwordyBot Attacking with Defensive Attack Strategy
1 : BossBot Attacking with Grid Attack Strategy
2 : GunnerBot Attcking with Simple Attack Strategy
3 : BossBot Attacking with Grid Attack Strategy
4 : SwordyBot Attacking with Defensive Attack Strategy
5 : SwordyBot Attacking with Defensive Attack Strategy
6 : SwordyBot Attacking with Defensive Attack Strategy
7 : SwordyBot Attacking with Defensive Attack Strategy
8 : BossBot Attacking with Grid Attack Strategy
9 : BossBot Attacking with Grid Attack Strategy
10 : GunnerBot Attcking with Simple Attack Strategy
11 : BossBot Attacking with Grid Attack Strategy
12 : SwordyBot Attacking with Defensive Attack Strategy
13 : BossBot Attacking with Grid Attack Strategy
14 : Set GridAttackStrategy to BossBot
15 : GunnerBot Attcking with Simple Attack Strategy
16 : BossBot Attacking with Grid Attack Strategy
17 : BossBot Attacking with Grid Attack Strategy
18 : Set AggressiveAttackStrategy to SwordyBot
19 : SwordyBot Attacking with Aggressive Attack Strategy
20 : BossBot Attacking with Grid Attack Strategy
21 : BossBot Attacking with Grid Attack Strategy
22 : GunnerBot Attcking with Simple Attack Strategy
23 : Set AggressiveAttackStrategy to SwordyBot
24 : SwordyBot Attacking with Aggressive Attack Strategy
25 : SwordyBot Attacking with Aggressive Attack Strategy
26 : Set SimpleAttackStrategy to GunnerBot
27 : BossBot Attacking with Grid Attack Strategy
28 : SwordyBot Attacking with Aggressive Attack Strategy
29 : 30 : BossBot Attacking with Grid Attack Strategy
31 : SwordyBot Attacking with Aggressive Attack Strategy
32 : Set GridAttackStrategy to BossBot
33 : BossBot Attacking with Grid Attack Strategy
34 : Set SimpleAttackStrategy to SwordyBot
35 : GunnerBot Attcking with Simple Attack Strategy
36 : Set AggressiveAttackStrategy to SwordyBot
37 : BossBot Attacking with Grid Attack Strategy
38 : GunnerBot Attcking with Simple Attack Strategy
39 : BossBot Attacking with Grid Attack Strategy
40 : Set DefensiveAttackStrategy to GunnerBot
41 : BossBot Attacking with Grid Attack Strategy
42 : GunnerBot Attacking with Defensive Attack Strategy
43 : Set SimpleAttackStrategy to SwordyBot
44 : SwordyBot Attcking with Simple Attack Strategy
45 : GunnerBot Attacking with Defensive Attack Strategy
46 : SwordyBot Attcking with Simple Attack Strategy
47 : GunnerBot Attacking with Defensive Attack Strategy
48 : GunnerBot Attacking with Defensive Attack Strategy
49 : SwordyBot Attcking with Simple Attack Strategy
50 : SwordyBot Attcking with Simple Attack Strategy

From step 0 – 13 all enemies are attacking with their default attack strategies. At step 18 attackStrategy of SwordyBot is changed and and at step 19 it is attacking with the new AggressiveAttackStrategy. Similarly at step 40 GunnerBot gets new strategy which it uses at step 42 and at step 75 BossBot gets SimpleAttackStrategy which it uses until step 92. Moreover, GridAttackStrategy is set only to BossBot. We get no debug output for step 29. The reason is simple. It is trying to set GridAttackStrategy either to GunnerBot or to SwordyBot which is ignored by them.

Advantages of the new design

  • The same implementation of the algorithm is used by all enemies. There is no duplicate code, neither there is any dirty chain of if-else. There is no possibility that the implementation of same algorithm would vary from enemy to enemy.
  • Modifying an existing algorithm is fairly easy. We only need to change the class which encapsulates the algorithm. There is no need to consider how many types of enemies are using that.
  • Enemy and Strategy classes are now loosely coupled. We can add new enemy or new algorithm without changing the other.
  • This separation in two hierarchies makes both of them simpler. Now enemies can concentrate on the enemy specific matters, without thinking much of the attacking algorithms and strategies can concentrate on the algorithms, without thinking much of the enemy specific matters. Remember that these algorithms are not trivial ones, they can be sufficiently complex. So encapsulating them in separate classes makes it easier to handle.

The Strategy Pattern
The way we have solved this design problem is known as Strategy Pattern. It is used when there is a family of related algorithms and encapsulating each of them is necessary. The main player of this pattern is the Strategy base class which defines the interface for an algorithm (AttackStrategy in our example). Each subclass of Strategy encapsulates a specific implementation of the algorithm (SimpleAttackStrategy, AggressiveAttackStrategy, DefensiveAttackStrategy, GridAttackStrategy). And the client which uses the strategy object is called Context (EnemyBot and its subclasses). The context has a strategy and delegates any algorithmic request to it. The context does not care about the specific concrete implementation of strategy, it only works with the interface defined by the base Strategy class.

Here is the UML diagram of Strategy Pattern:

Footnotes and references

  • Our demo code only prints some debugging output, no actual attacking algorithm is implemented, neither there is any real enemy bot. That is natural. After all, this writing is about the design pattern, it’s not about AI algorithms. That is, here we are dealing with how to encapsulate an algorithm, not the algorithm itself.
  • There are very little differences among the enemy subclasses and strategy subclasses. That is also because of demo. In real application, there will be huge difference between SimpleAttackStrategy and GridAttackStrategy, between GunnerBot and BossBot.
  • Here I have discussed very little part of the Strategy pattern. Design Patterns: Elements of Reusable Object-Oriented Software by Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides contains in depth discussion about the patterns.
  • Another good book for design patterns (specially for beginners in the field) is Head First Design Patterns by Elisabeth Freeman, Eric Freeman, Bert Bates and Kathy Sierra.
  • The code for this demo can be downloaded from here.
  • And finally, any feedback is welcome.
Advertisements
This entry was posted in Design Pattern and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s