Thursday, September 22, 2016

Improving software design using SOLID & GRASP principles



In this article I am going to improve the design of a class and show how some SOLID and GRASP principles help in this process.

Preview
I will have a class Fibb that does some computation (Fibonacci sequence)
Then I will add a new capability to this class (printing the result) in the simplest way.
We will notice that there are issues with this way of adding the capability, mainly because the class Fibb will be cluttered with a lot of code that will be difficult to maintain and extend.
To improve the code, I will delegate the task of printing to another class, Printer.
Then we will notice that Printer is bearing more information than needed.
I will use polymorphism to improve the use of Printer class.
The final design will be checked against some principles from SOLID and GRASP to show that it is a good design.


Before I start
Fibonacci sequence is a series of numbers.
Each number is found by adding the two numbers before it in the sequence.
The 1st and the 2nd Fibonacci numbers are given/known by default and they are, usually, 0 and 1.
The 3rd Fibonacci number is found by summing up the 1st and 2nd numbers, so its value is 1
The 4th Fibonacci number is found by summing up the 2nd and 3rd numbers, so its value is 2
And so on ...

A simple class
Let's consider the simplest version of Fibonacci sequence computing class (check http://www.rosettacode.org/wiki/Fibonacci_sequence for more robust versions)
The class offers a function that, given a number/rank, will find the corresponding Fibonacci number.
#include <iostream>
using namespace std;

class Fibb
{
    public:
    int operator()(int n)
    {
        if(n<0)
        {
            cout << "this case is not supported!"<<endl;
            return 0;
        }
   
        if(n==0)
            return 0;
       
        if(n==1)
            return 1;
       
        int fnow = 0, fnext = 1, tempf;

        while(--n>0)
        {
            tempf = fnow + fnext;
            fnow = fnext;
            fnext = tempf;
        }

        return fnext;   
    }

};

int main()
{
    int r;
    Fibb fibb;

    r = fibb(0);
    cout << r << endl;
    r = fibb(1);
    cout << r << endl;
    r = fibb(2);
    cout << r << endl;
    r = fibb(3);
    cout << r << endl;
}




Adding the printing capability
Now, we want the computing class to print the result, instead of the client doing it (the function main above). So we'll add a function OutputResult


The code will look like the highlighted below:


#include <iostream>
using namespace std;

class Fibb
{
    public:
    int operator()(int n)
    {
        if(n<0)
        {
            cout << "this case is not supported!"<<endl;
            return 0;
        }
   
        if(n==0)
            return 0;
       
        if(n==1)
            return 1;
       
        int fnow = 0, fnext = 1, tempf;

        while(--n>0)
        {
            tempf = fnow + fnext;
            fnow = fnext;
            fnext = tempf;
        }

        OutputResult();
         
        return fnext;    
    }
    void OutputResult()
    {
        cout << fnext << endl;
    }

};

int main()
{
    Fibb fibb;
    fibb(0);
    fibb(1);
    fibb(2); 
    fibb(3);

}

But this code is not perfect from the point of view of OOP: What if we want to offer the possibility to output the result to a file as well ?

Printing (version 2)

One solution is adding a variable to the class Fibb that lets it decide how to print the result:


class Fibb 
{

public:
    enum class DestinationFlag
    {
        e_toScreen,
        e_toFile,
    };
private:
    DestinationFlag     m_df;  //the variable that decides how to print the result
    fostream            m_os;
  
public:  
    bool Init(DestinationFlag df, const char* filename=nullptr)
    {
        bool res=true;
        m_df = df;
      
        if(df == e_toFile)
        {
            //check filename parameter
            //try to open file
            // manage file management errors
            // and set m_os and/or res
          
        }
      
        return res;
    }  
  
    void OutputResult()
    {
        if(m_df == e_toFile)
            m_os << fnext << endl;
        else
            cout << fnext << endl;
    }

    int operator()(int n)
    {

       ...
};

int main()

{
    FibbToFile();
    FibbToScreen();
}

void FibbToFile()

{
    Fibb fibb;

    if(!fibb.Init(e_toFile, "a_file_to_output_to.txt"))

        return;
      
    fibb(5);
}

void FibbToScreen()

{
    Fibb fibb;

    fibb.Init(e_toScreen);

    fibb(3);
}


Issues in version 2

Offering the possibility to print the result to a file, in this way, has many problems.
This is because Fibb class is now doing more than it should.
Not only it's doing its core task, which is to compute Fibonacci sequence, it is now also :
- maintaining the way to print the result, through the member m_df.
- managing the stream to output to m_os and all its related issues (file no found, file can't be created, ...). This will also lead to defining function members just for this task.
- the member m_os is always there in Fibb objects even when they are printing to the screen. This is a waste of memory space.


Another problem with this way is that Fibb starts to be difficult to test. A key technique in testing code is isolation. To have reliable tests of a functionality, it should be easy to isolate from other parts and functionalities of a system.
In our case, how would we test the correct handling of the output file management and check its different errors without modifying Fibb just for testing this functionality ?


Issues in version 2 from SOLID and GRASP's perspective

We can also detect issues with this solution by checking it against some SOLID and GRASP principles:

- The 'S' in SOLID principle states that a class should have a single responsibility.
In our case, Fibb is breaking this rule because it is also managing printing.

Fibb is also breaking the "high cohesion" in GRASP. The roles of the members in Fibb are not coherent; there is a member to compute Fibonacci sequence, another to decide of the way printing should happen and other members to manage a file.


- The 'O' in SOLID states that the capabilities of a class/system should be open to extension and closed to modification.

In our case, we can not extend the capability of printing to memory or extend it to send the result through network without modifying the class Fibb.


Let's improve the code.


Delegating printing


Let's do a high level analysis.

The key idea we should use to solve this kind of problems is to say:
1- Fibb calculates Fibonacci sequence.
2- Fibb signals an object/code to print something (the result n our case)
3- Fibb should ideally know nothing about the object it asks to print data
4- The object printing data should know nothing about Fibb. A direct implication of this is:
4.1-the object printing data should be able to print anything passed on to it from any class/code.
4.2-any change in Fibb should not affect the object, and vise-versa

All these points can be achieved by delegating the print operations to a different class:




In terms of code, it will look like:

class Fibb
{
 

    Printer  *  m_printer;  
public:  
    Fibb(Printer *p = nullptr):m_printer(p) { } 


    void OutputResult()

    {
        if(m_printer)
            m_printer->Print(fnext); 
    }
    int operator()(int n)
    {
     ...
};

The issue here is that Printer needs to know where to print data: screen or file.

To achieve this we can have Printer::print have a code like :


void Printer::Print()
{
    if(m_df == e_toFile)
        m_os << fnext << endl;
    else
        cout << fnext << endl;
}

and the class will have a member m_df that is set at construction to either e_toFile or e_toScreen.



The class Printer will be defined as:

class Printer
{
    DestinationFlag     m_df;  //the variable that decides how to print the result
    fostream                m_os;
  
public:  
    void Print();
    bool Init(DestinationFlag df, const char* filename=nullptr)
    {
        bool res=true;
        m_df = df;
      
        if(df == e_toFile)
        {
            //check filename parameter
            //try to open file
            // manage file management errors
            // and set m_os and/or res
          
        }
      
        return res;
    }  
  
};

But we have another problem here also.
When Printer class is instantiated to print to the screen, any code and field related to printing to file is not going to be used, but it will still be part of the instance.
And when it is instantiated to print to a file, any code and field related to printing to the screen is not going to be used.
This appears clearly in the Printer::Print where we branch following the state of the object.

Polymorphism


Fibb needs to use a reference to only one class that can represent either classes.

It means to have a base class having all the common code and/or field, and to derive from it classes specialised to do each a specific and a different task.
In our case, Fibb will reference Printer, which will be the base class for PrinterToScreen and PrinterToFile classes. These will specialise any code they need.





These classes will have the following implementation


class Printer
{
public:
    virtual ~Printer(){}
    virtual void Print(int n)=0;
};


class PrinterToScreen : public Printer

{
public:
    void Print(int n) override
    {
        cout << n << endl;
    }   
};

class PrinterToFile : public Printer

{
    ofstream f;
   
public:
    enum class eStatus
    {
        Failure,
        Success
    };
public:
    ~PrinterToFile()
     {
         f.close();
     }
    eStatus Init(const char * filename)
    {
            //check filename parameter
            //try to open file
            // manage file management errors
            //return eStatus::Failure or eStatus::Success
    }
    void Print(int n) override
    {
        f << n << endl;
    }   
};


Notice how all the code related to printing to file is now located in a separate class. So when an object of PrinterToFile in instantiated to print to a file, it does not have any superfluous data or code.
The same goes for objects of PrinterToScreen class. 


And this is how to use this new design






int main()
{
    FibbToFile();
    FibbToScreen();
}

void FibbToFile()
{
     PrinterToFile pf;

    if(pf.Init("a_file_to_output_to.txt") != PrinterToFile::eStatus::Success)

        return;

     Fibb fibb(&pf);

     
    fibb(4);
   
}

void FibbToScreen()

{
    PrinterToScreen ps;
    Fibb fibb(&pc);

    fibb(3);


}


Verification of the design 
from SOLID and GRASP's perspective

Let's check this design against some of the patterns/rules in SOLID and GRASP principles:


-Single Responsibility Principle: Each class in the design has one and only one responsibility.


-Dependency Inversion Principle: Instead of Fibb depending directly on the class printing to the screen and/or the one printing to a file, it only depends on an interface.

An abstraction layer has been introduced between Fibb and PrinterToScreen and PrinterToFile.

-Open Closed Principle: If we need to extend the capability of the system so we can print to memory, we can easily do it by deriving a new class from Printer and override Print function. The new design is open to extension while being closed to modification to any existing classes.



-High Cohesion: each class has only members that collaborate toward one goal


-Information expert: Each class has all the necessary members to fulfil its task. None of them needs anything from its peers.


-Low coupling: it is possible to change how the PrinterToScreen does its job without the need of altering Fibb and vise-versa. The same goes for the rest.


-Protected variations: same remark as for open closed principle above.

-Polymorphism: No manual branching is done to execute a code based on the setting of Printer, as was done before:

void Printer::Print()
{
    if(m_df == e_toFile)
        m_os << fnext << endl;
    else
        cout << fnext << endl;
}

This branching is replaced by the creation of the proper object, an instance of PrinterToScreen or of PrinterToFile.

Conclusion

We've gone from Fibb taking in charge a task (printing) not belonging to its core job, to delegating the task to another class (Printer), to making Printer a representative of concrete printing classes.

The final version of the design allows for easy extension and easy testing of each class in isolation.

Sunday, July 3, 2016

Prey and Predators demo



The PreyPred demo is a board where predators try to find and chase preys to eat them.
Preys try to flee from predators and hide behind obstacles.



The source code of the demo can be downloaded HERE.
A rough video presentation of the demo can be downloaded HERE.


1 - Introduction

The PreyPred demo is an MFC application that displays a board, predators, preys and obstacles.
The EXE directory contains the executable of the demo. The source code can be loaded using SRC\prj\PreyPred.dsw file.

Predators are represented by red circles. They search and chase preys.
Preys are represented by blue circles. They try to flee from predator and hide behind obstacles.
A straight line in a circle represent the direction it is moving in. There are four directions an actor (predators and preys) can face and move in : up, down, left or right. It can't move in a diagonal way.
Obstacles are black squares and actors can not walk in squares containing them.


2 - Configuration files

1 - The data/map.xml file describes the following :
-the size of the board in squares
-the height and width of a square in pixels
-the positions of obstacles
-the positions of actors along with their directions.

2 - Actor's capabilities are described in data/predator.xml and data/prey.xml files.
Both files define vision parameters : the range of view in squares and the angle of view.
They also define the rate of behavior execution using the NbrOfFramesBeforeUpdate element. A value of "2" means the behavior is run each 2 frames.
data/predator.xml also defines the amount of time, in frames, a predator remembers the location where it has last seen a prey.
And data/prey.xml defines the hearing range, in squares, of a prey.

These configuration files are loaded by "Loader" class

The behavior of actors is implemented using finite state machine technique.


3 - Predator

The predator actor has two behaviors :

1- SearchAndChase :
It is most of the time in this behavior. It searches for preys and chases them.
When in SearchAndChase behavior, it uses vision capability to detect preys through Vivisibility::GetSeenObjects.
If a prey is detected, a path to its location is constructed and followed through frames.



When more than one prey has been detected, it selects the nearest one using Actor::GetNearestObject.
A path to the position of that pery is constructed using Path::GetAStraightPathFromTo, and the walk is carried out using Path::Walk.

Each frame, squares seen in the field of vision are explored for preys. If preys are found, it picks the nearest prey and compares its position to the location of the previous frame's prey.
The nearest seen prey in the current frame may be the same as the one set for chase in a previous one. It may also be a really new prey that entered vision field of the predator.
A new path to this new prey is constructed if it is nearer than the one being chased. In the contrary, the predator continues to walk the path found in the previous frame.
When no preys have been seen in a frame, the predator continues to walk, for some time, the path set in a previous frame.
The amount of time it sticks to this path is the number of frames specified by the element MemoryTime in the data/predator.xml.
When this time is over, the predator looses its memory, and no more follows this path; the prey has been lost.

A prey can disappear from the predator's vision in one of these case :
- it has gone behind an obstacle. Obstacle squares block actor vision.
- it has been eaten by another predator.
- or when the predator changes direction while walking to it.


2- Eat :
When it has reached a prey, it switches to this behavior to eat the prey.


4 - Prey

The prey detects predators by using the hearing capability. It uses vision capability to detect obstalces in front of it.
Obstacles are important for the prey to hide from chasing predators.

Prey can be in one of the following three behaviors:

1-Idle :
The prey starts in this behavior and remains in it until one or more predators have been detected. It also switches from flee behavior to this behavior when no predators have been detected for the number of frames specified by NbrOfFramesInFleeWithoutDanger element in data/prey.xml

2-Flee :
It switches to this behavior to try and flee from chasing predators either by runing away from them or by picking a location behind an obstacle; this location is called "refuge".



The main idea behind fleeing is that the prey constructs a fleeing vector depending on chasing predators' locations. Based on the fleeing vector, it constructs and follows a path.
While fleeing, it tries to find a refuge when it sees an obstacle. A refuge is detected based on the fleeing vector. A good refuge is one that is behind an obstacle relative to the fleeing vector. (cf Prey::IsAValidRefuge and Prey::FindARefuge)

3-Hide :
When the prey reaches a refuge, it stands still in it for the number of frames specified by NbrOfFramesHiding element in data/prey.xml. if predators are detected in the meantime, it switches to the fleeing behavior.


5 - Path

Paths followed by actors are instances of the Path class.
A path is a list of instructions. Each Instruction could be either a move or a change of orientation.
A move instruction only makes the actor step one square in the direction it's facing (cf Move::Alter)
An orientation instruction make the actor turn in a specified direction (cf Orientation::Alter)

Path class provides the following main functions:
-Path::GetAStraightPathInDirection finds a path, starting from a situation (a position and direction), in the direction specified by the secong argument.
The max distance of the path is by default 5 squares length. The vector of direction is clamped and corrected if it leads out of the board.
-Path::GetAStraightPathFromTo finds a path, starting from a situation (a position and direction), to a square given as the second argument.
-Path::ConstructThePathFromSquares constructs a path based on a list of linked squares.


6 - SquareLine

Is a class providing two main functionnalities :
-SquareLine::CanSee tells whether or not there is any obstacle hiding the center of a square from that of another one.
-SquareLine::GetALine provide a list of squares crossed by a segment starting from the center of a square and ending at the center of another one.

Each one of these functions is overloaded by a function that is public, which receives parameters to initialize the context of the recursive one.


7 - Visibility

Actor's vision capability is based on Visibility class.
Visibility class has functions that determine the squares seen given a range, an angle, a position and a direction.
Obstacles present in the field of view hide other squares.

-Visibility class constructs two lines that delimits the viewing triangle. These two lines are created depending on the range and angle of view, the direction and position of the actor.
-Visibility::GetSquaresInViewingTriangle function constructs a list of squares which centeral pixels are between the two delimiting lines and in the range of view.
-Visibility::GetSeenSquares uses SquareLine class to eliminate squares hidden by obstacles from the list of squares reported inside the viewing triangle.
-Visibility::GetSeenObjects is the only public function in Visibility class. It is used to allow the predator to detect the prey and vice-versa.


8 - Hearing

Capability hearing is only available for the prey. It allows it to detect predators all around it, and in the range of squares specified by HearingRange element in data/prey.xml


9 - Collision

No management is done to avoid collision of actors.


10 - Debugging

1- The game can display its messages by sending them to the "logger" application.
Messages sending is done by using the function "Debugger::GetInstance().Output"
The "logger" application is in fact a simple text editor, with the capability of receiving text from other applications.
2- Inside the circle representing an actor, some letters are displayed, depending the behavior an actor is in.

The prey actor displays one the following letters :
"F" for fleeing.
"R" for going to a refuge.
"H" for hiding

The predator actor displays one the following letters :
"C" for chasing
"L" for lost prey, can't see it.
"M" for using memory to go to where a prey has last been seen.


11 - Third party code

- XML file loader (libs\Xml and code\xml) from flipcode.net
- math\xlines.cpp from Graphics Gems


12 - Known issues

-Find a refuge based on the fleeing vector is not a good idea. A good refuge should rather be one that can't be seen by predators.
-When a prey is sandwiched by two predators, two fleeing vectors are generated which combination yields a null vector. In this case Prey::GetVectorAwayFromAll returns the vector (1,1) as the fleeing vector. It should, in fact, return a vector perpendicular to two vectors.
-When the prey is near the border and the m_fleeingvector is leading it out of the board, m_fleeingvector is set to (1,1) which is not a good idea. A thorough search should be undertaken to find a fleeing vector according to which border the prey is near of and where predators are.


13 - Still to do

-GetAnyPath function and Path member should appear in Actor class.
-Non straight paths should also be found by Path class. Follow the Prey::FindARefuge to do it.
-Use factory method pattern for actors and obstacles creation in Loader.
-Prey::m_fleeingvector and Prey::m_fleeingvectorangle should be part of a structure istead of being exposed in Prey class.
-Prey::m_refuge should be a location that is not seen by any predator. presently, the refuge is found based on the fleeing direction.
-In Prey::Behavior_Flee, some predators appear two times in l_detectedprdt list because they are seen and heard.
-In Prey::Behavior_Flee, when m_fleeingvector ends up to null, choose a fleeing vector according the boarder the prey is at, instead of (1,1).
-Logger window should close when closing the app.
-HObject::GetType() not used in CMainWindow::DrawBoard

Sunday, June 22, 2014

The Three Stones Game

"The Three Stones" is an OpenGL game I have developed. The player needs to align three tiles of the same color horizontally or vertically to score.
You can download the source code here.
The executable to run the game is Exe\TheThreeStones.exe

The following is a technical description of the game



1- Technical features


The main technical features implemented in the game are:

1-Memory management:
- Overload of new and delete operators (Code\Mem\MemTracker.cpp)
- Overload std::allocator to be used by STL container (Code\Mem\allocator.h)
- Implementation of a memory tracker to detect possible memory leaks (Code\Mem\MemTracker.cpp)
- Use of Boost::smart_ptr library

2-Delayed functions execution:
Some functions should not be executed when they are called. They are registered for later execution. This is implemented through the structure DelayedFunctionInfo (Code\ObjectsManager.h)

3-Vertex animation used in Encouragement class (Code\Graphic\Anim.*)
In the figure below, the Envouragement class is showing the animated “wow” text with the player scoring a high score.







4-The Score class (Code\Score.*) uses interpolation along a quadratic-polynomial-curvy path (inspired from the Uniform B-Spline curve) to move the score from the squares that created it to the score rectangle.
The following figure shows the paths crossed by three scores. 








5-Finite state machine:
Implemented in Game, Board and Tile classes.



2- Overview


Overview of the main elements in the game:

1-
Game class contains the different phases of the game, implemented using finite state machine (see chart below).
It contains and manages a board, a score, a time counter and an encouragement object.

2-
The board class contains 64 tiles. Each tile can be one of 5 types (colors)

3-
ObjectsManager is a class that calls Update and Draw functions of Object class. The main classes of the game are derived from Object class.

Objects contained between activeobjects.next and activeobjectstail.prev are updated and drawn.
Those contained between activeobjectstail.next and activeobjects.prev are drawn only. This allows the board, tiles, score and time counter to be drawn in a frozen state when the intro, the count down and the time out objects are in the front.


3- Compiling the game


- Boost library is needed to compile the game.
- The game was compiled and tested in Microsoft VS 2010 Express and VS 2012


4- Class diagrams



4.1- Object class

The following is the class diagram showing the relation between Object class and some main classes in the game :





4.2- Sprite class

The following is the class diagram showing the relation between Object and Sprite classes and some main classes in the game :



5- The Game's finite state machine


The different phases of the game are implemented in the Game class




6- The Board's finite state machine


The board's states are determined by the behavior of the tiles.
Here are the states of the Board object:




7- The Tile's finite state machine


Here are the states of a Tile object :