## The relation between Integer Partition and Pentagonal Numbers

A partition of an integer n is defined as a way of representing n as a sum of positive integers where the order of the summands does not matter ([1]). The partition function p(n) denotes the number of possible partitions of n. For example, 5 can be represented in 7 different ways:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

So, p(5) = 7. The value of p(n) grows very quickly as n grows. For example:

p(10) = 42
p(50) = 204226
p(100) = 190569292
p(500) = 2300165032574323995027
p(1000) = 24061467864032622473692149727991
p(5000) = 169820168825442121851975101689306431361757683049829233322203824652329144349
p(10000) = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144
p(25000) = 795153665211854316623270592370059262051214684698263936645288037606040374321677412443089599487464373732598268996277510779455269671090533346705889153124159897638140712684550
p(50000) = 3626186097141667844592140891595633728165383082527785049015872755414109904256712082718122747316610565824630881772910217544261659239432670671532413858378256188987333877121891586607957389750538447474712592979263719012461858719791627302489739548263

Though there is a very easy recursive solution to find p(n) by using an intermediate function ([4]), this method is not much suitable for large values of n.

Surprisingly, p(n) can be calculated by using a simple recursive function: ([3])

p(n) = 0 for n < 0
p(0) = 1
p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + p(n - 12) + p(n - 15) - p(n - 22) - p(n - 26) + ...

At first this equation looks like a total chaos due to the sequence 1, 2, 5, 7, 12, 15, 22, 26, ..., but that is generalized Pentagonal Number sequence([2]) which is defined by:

f(k) = k(3k - 1) / 2 for k = 0, 1, -1, 2, -2, 3, -3, 4, -4, ...

Well, I am not going to prove this relation between integer partition function and pentagonal numbers here, but if anyone is really really interested then try Google and good number theory books.

Thus p(n) can be written simply as:
$p(n) = \sum_{k=1}^{\infty} (-1)^{k+1}\{p(n - f(k)) + p(n - f(-k))\}$

Finally here is a simple (read it, stupid and not optimized) Python program that exploits the relation between partition function and pentagonal numbers and generates partition values.

import sys

p = [1]

def generate(n):
for i in range(1, n + 1):
s = 0
k = 1

while True:
f = i - k * (3 * k - 1) / 2
if f < 0:
break
if k % 2:
s += p[f]
else:
s -= p[f]

f = i - k * (3 * k + 1) / 2
if f < 0:
break
if k % 2:
s += p[f]
else:
s -= p[f]

k += 1

p.append(s)

def main():
generate(int(sys.argv[1]))

for i in range(len(p)):
print i, p[i]

if __name__ == '__main__':
main()
$python partition.py 20 0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 30 10 42 11 56 12 77 13 101 14 135 15 176 16 231 17 297 18 385 19 490 20 627 Here is a file containing the partition values upto 50000. You can have a look if you are interested. Like always, any feedback is welcome. Advertisements Posted in Algorithm | Tagged | 2 Comments ## The Abuse of Design Patterns in writing a Hello World Program One comment I saw in a news group just after patterns started to become more popular was someone claiming that in a particular program they tried to use all 23 GoF patterns. They said they had failed, because they were only able to use 20. They hoped the client would call them again to come back again so maybe they could squeeze in the other 3. Trying to use all the patterns is a bad thing, because you will end up with synthetic designs—speculative designs that have flexibility that no one needs. These days software is too complex. We can’t afford to speculate what else it should do. We need to really focus on what it needs.” – Erich Gamma [1] When people starts learning design patterns, they try to use patterns everywhere. They try to use patterns anyway, it does not matter whether a pattern is required or not. They think that the more patterns are used, the better is the design. The outcome is a code with unnecessary complexity. [2] Rather that calling “using patterns”, we can call this “abusing patterns”. It is an abuse when people try to fit patterns in Hello World program. Let’s focus on an example. The problem is the classic one: Write a program that will print Hello World on standard output. A beginner in programming will write a code like this (well, it’s in Java): System.out.println("hello world"); This code seems too simple. Can we use some patterns in it? Let’s see … First we define two interfaces Subject and Observer to add Observer. public interface Subject { public void attach(Observer observer); public void detach(Observer observer); public void notifyObservers(); } public interface Observer { public void update(Subject subject); } Then we define two classes HelloWorldSubject and HelloWorldObserver that implements them. public class HelloWorldSubject implements Subject { private ArrayList<Observer> observers; private String str; public HelloWorldSubject() { super(); observers = new ArrayList<Observer>(); } public void attach(Observer observer) { observers.add(observer); } public void detach(Observer observer) { observers.remove(observer); } public void notifyObservers() { Iterator<Observer> iter = observers.iterator(); while (iter.hasNext()) { Observer observer = iter.next(); observer.update(this); } } public String getStr() { return str; } public void setStr(String str) { this.str = str; notifyObservers(); } } public class HelloWorldObserver implements Observer { public void update(Subject subject) { HelloWorldSubject sub = (HelloWorldSubject)subject; System.out.println(sub.getStr()); } } Then we add a Command. public interface Command { void execute(); } public class HelloWorldCommand implements Command { private HelloWorldSubject subject; public HelloWorldCommand(Subject subject) { super(); this.subject = (HelloWorldSubject)subject; } public void execute() { subject.setStr("hello world"); } } Then we add an Abstract Factory. public interface AbstractFactory { public Subject createSubject(); public Observer createObserver(); public Command createCommand(Subject subject); } public class HelloWorldFactory implements AbstractFactory { public Subject createSubject() { return new HelloWorldSubject(); } public Observer createObserver() { return new HelloWorldObserver(); } public Command createCommand(Subject subject) { return new HelloWorldCommand(subject); } } And finally a Singleton. public class FactoryMakerSingleton { private static FactoryMakerSingleton instance = null; private AbstractFactory factory; private FactoryMakerSingleton() { factory = new HelloWorldFactory(); } public static synchronized FactoryMakerSingleton getInstance() { if (instance == null) { instance = new FactoryMakerSingleton(); } return instance; } public AbstractFactory getFactory() { return factory; } } And the main class at last. public class AbuseDesignPatterns { public static void main(String[] args) { AbstractFactory factory = FactoryMakerSingleton.getInstance().getFactory(); Subject subject = factory.createSubject(); subject.attach(factory.createObserver()); Command command = factory.createCommand(subject); command.execute(); } } And the output is: Hello World Wow, we have managed to use four patterns in Hello World program. (Well, there is an Iterator too, but we have used built-in Java iterator which is natural in Java). This must be a great design. So where is the problem? 1. The code is too complex for a hello world program. 2. It contains the flexibility that we will never need. 3. The time spent in designing and implementing is a total waste. 4. There is a class explosion. 5. It violates the KISS principle. [3] 6. This does not serve the purpose of the problem. The purpose was to learn how to print on standard output and this code is far far away from that. Summary: Use patterns where they are natural, do not try to use them anyway. Design Patterns is a great tool to build great software. Use them wisely, do not abuse them. The code can be downloaded from here. Any feedback is welcome. And if anyone can manage to use more patterns in hello world then that will be great. References: [1] How to Use Design Patterns. [2] Chapter 13: Patterns in the Real World from Head First Design Patterns. [3] KISS Principle. Posted in Design Pattern | Tagged | 16 Comments ## Singleton in multi-threaded environment The code posted here should be considered as pseudo-code, no particular language is assumed. And also it is assumed that the reader is already familiar with the Singleton pattern, i.e. I am not going to discuss what is a Singleton, when we should use it etc. in detail. Rather I am going to discuss about the difficulties of implementing Singleton in multi-threaded environment. And there are cases where Singleton is considered evil or Anti-Pattern, but again, that is a separate discussion. If people are asked to name a design pattern, the most commonly uttered name is the Singleton. It is one of the most widely used patterns (and most abused, too). The idea behind the Singleton is simple. It ensures that the Singleton class has only one instance and provides a global access point for it. We can use a Singleton when the presence of multiple instances can potentially damage the system, and we need global access to the single instance. Let’s first see the classical implementation of Singleton: public class Singleton { private static Singleton _instance = null; private Singleton() {} public static Singleton getInstance() { if (_instance == null) { _instance = new Singleton(); } return _instance; } } The implementation is straight forward. The constructor of Singleton is private, so it is not possible to instantiate it from outside. The only way to get an instance is to call static getInstance() method. getInstance() first checks whether an instance is already created. If not, then it creates an instance, refers it via private static member _instance and then returns that. And if already created then it returns the previously created _instance. Thus only the first call to getInstance() instantiates a Singleton object and any further call returns the same object. Also note that the object is not instantiated until getInstance() is called, i.e. we only create that when actually required. This is called lazy initialization and becomes helpful if the object is resource hungry. This looks very simple and straight forward implementation. But we have a slight problem with this. This classical implementation is not thread safe. Lets see what may happen in the presence of two threads. 1. Thread-1 enters getInstance() for the first time and sees that _instance is null and thus the condition is true. 2. Before instantiating the object a thread switch occur. 3. Thread-2 enters getInstance() and it will see _instance null too, as the instantiation by Thread-1 is not completed yet. 4. Thread-2 instantiate new object and then return. 5. Thread-1 knows nothing about Thread-2. So when it gets its turn again, it instantiates another object and returns that. At this point we have two instances of Singleton which violates the fundamental purpose of the pattern. So what can we do solve this problem? The easiest solution comes up if we don’t want the lazy initialization. Something like this: public class Singleton { private static Singleton _instance = new Singleton(); private Singleton() {} public static Singleton getInstance() { return _instance; } } This is guaranteed to be thread safe. The only cost that we pay is that we loose the lazy initialization. If the singleton object is created at every run or the cost of the object is not so high then probably this is the best approach to implement a Singleton in multi-threaded environment. But what if we want the lazy initialization? The general approach to write a thread safe code is to acquire a lock before accessing the shared resource. We can acquire a thread lock after entering getInstance(). Something like this: public static Singleton getInstance() { acquire_lock(); if (_instance == null) { _instance = new Singleton(); } release_lock(); return _instance; } Again, this is guaranteed to be thread safe. Thread-2 can not proceed until Thread-1 completes the instantiation and releases the lock. Obviously after acquiring the lock Thread-2 will see _instance non-null and won’t create a separate instance. But unfortunately we have slight problem with this method, namely performance. Acquiring a thread lock is a very costly operation. Acquiring a lock at every call of getInstance() may affect the overall performance severely, specially when the calls are frequent. And to make matter worse, we only need the lock for the first time. Once _instance is set up with a valid value, there is no need of the locking. But we are acquiring the lock every time and thus wasting our resource. The very idea of lazy initialization is to use resource efficiently, but this method of locking seems overkilling. Is there any way to get around this problem? We have already realized that the lock is only needed for the first time. There is no need to acquire lock once _instance is initialized. So why don’t we acquire the lock only if _instance is null, like this: public static Singleton getInstance() { if (_instance == null) { acquire_lock(); _instance = new Singleton(); release_lock(); } return _instance; } A clever thought. But this will not work. Why? Thread-1 may see the condition true and enter the condition, but before acquiring the lock thread switch may occur. Then Thread-2 will again find the condition true and thus we are in the same situation as before. Can we fix this? Indeed we can. And with a slight modification. We only need to check _instance against null again after acquiring the lock. Like this: public static Singleton getInstance() { if (_instance == null) { acquire_lock(); if (_instance == null) { _instance = new Singleton(); } release_lock(); } return _instance; } Lets see what happens with the previous situation: 1. Thread-1 enters the condition but before acquiring the lock thread switch occurs. 2. Thread-2 enters the condition, acquires lock, instantiates, releases lock and returns like before. 3. Thread-1 acquires the lock. But now it will see that _instance is non-null and thus it will not create a new object. It will simply release the lock and return the object created by Thread-2. Looks like our problem with multiple threads is finally finished. This approach of checking twice is a design pattern in its own right and is called Double Checked Locking Pattern. Unfortunately, this is NOT guaranteed to work either. The reason is our modern compilers are too smart in optimizing things. An optimizing compiler (all modern compilers are) can reorder the instructions for various reasons. It can reorder read/write calls to improve cache performance, it may try to run as many instructions as possible in parallel when multiple execution units are present (all our modern CPUs has multiple execution units) and for many such reasons. A concrete example might clarify. int a = 10; int b = 20; int c = a + b; Here the compiler guarantees that the value of c will be 30, but it does not guarantee anything else about a and b. It can completely eliminate the first two instructions as constant expression, it can execute 1st one first and then 2nd one, or it can execute 2nd one first and then 1st one, or even it can execute them in parallel if multiple execution units are present. The summary is: we can not depend on it. Lets back to our double checked locking code. When _instance = new Singleton() is executed three things happen mainly. A portion of memory is allocated for Singleton object, that memory is initialized with the object’s data and finally _instance points to that memory location. _instance is valid only when the initialization is complete. Here the catch is that the compiler may change the order of these, i.e. it may first allocate the memory and make _instance point to that memory and then go for the initialization of the object. It is also possible that the initialization is taking place in another execution unit. Why the compiler would do so is a matter of study in compiler optimization theory, but the fact is _instance may point to an uninitialized memory. Lets see what may happen to our double checked locking code in this case: 1. Thread-1 enters getInstance(), acquires the lock and starts the instantiation process. It allocates the memory and makes _instance point to it. 2. Before the initialization of created object is complete, a thread switch is occurred. 3. Thread-2 enters getInstance() and finds _instance non-null, as it is already pointed to the allocated memory by Thread-1. 4. As Thread-2 finds _instance non-null, it thinks that the instantiation is complete and returns that. It has no way to know that the initialization is yet to be completed. 5. As a result the caller of getInstance() in Thread-2 receives something that is not initialized properly. If it tries to use the object before the initialization is actually completed, it will create major problem and may even crash the program. To make matters worse, if this occurs than it will be very difficult to figure out the exact reason of the unexpected behavior or crash, as this will happen in random. How can we deal with this? Well … this might be heart breaking, but there is NO single way which can solve this problem in ALL compilers/hardwares/platforms. We have few work around depending on the platform. 1. Marking a memory location volatile denotes to the compiler that this memory can be changed in ways not known to the compiler and thus prevents such optimization. Originally that was introduced to handle memory-mapped I/O and was not related to thread, but J2SE 5.0 and Visual C++ 5.0 ensures that volatile works correctly with multiple threads. So making _instance volatile will solve the problem for them. But that is not guaranteed to work with versions of J2SE lower than 5.0 or lower than Visual C++ 5.0 or in other C++ compilers. And also using volatile may affect the performance too. 2. A memory barrier instruction forces that all read/write instructions before the barrier must be completed before any read/write operation is executed after the barrier. For systems that support memory barrier we can solve this problem by introducing a memory barrier after the instantiation of Singleton object and by introducing a flag as test condition. Something like this: public class Singleton { private static Singleton _instance = null; private static bool flag = false; private Singleton() {} public static Singleton getInstance() { if (!flag) { acquire_lock(); if (!flag) { _instance = new Singleton(); memory_barrier(); flag = true; } release_lock(); } return _instance; } } Note that now a new flag is added as the test condition. _instance may point to uninitialized memory, but the memory barrier instruction before flag = true will ensure that flag will be false until the object is fully initialized. The combination of memory barrier and new flag instead of _instance as test condition solves the problem. But the downside of this solution is that if the compiler used does not support a memory barrier instruction natively (.NET has a memory barrier instruction) then it might be difficult to implement a barrier correctly, and may even require assembly coding. 3. In addition to double checked locking pattern there is an another approach to implement Singleton correctly known as Initialization on demand holder idiom. This method works on all versions of Java. None of the solutions works in all platforms. All of them exploit platform/compiler specific features. May be the best solution is to ignore lazy initialization. And if we want to stick with lazy initialization, then performance of the full locking version of getInstance() (where lock is acquired after entering getInstance()) can be improved by minimizing calls to getInstance() like this: // requires three calls and thus acquires lock three times Singleton.getInstance().method1(); Singleton.getInstance().method2(); Singleton.getInstance().method3(); // requires only one call and thus acquires lock only ones Singleton instance = Singleton.getInstance(); instance.method1(); instance.method2(); instance.method3(); This is not a real solution to the problem, but it can improve performance significantly in practice. For a long time I thought Singleton is the easiest pattern to understand and implement. How wrong I was!!! References 1. Singleton Pattern chapter from Design Patterns by GoF. 2. Singleton Pattern chapter from Head First Design Pattern. 3. Singleton Pattern from Wikipedia. 4. Singleton Pattern Thread Safety. 5. C++ and the Perils of Double-Checked Locking. 6. Double Checked Locking from Wikipedia. 7. Initialization on demand holder idiom from Wikipedia. 8. Memory Barrier from Wikipedia. 9. Volatile Variable from Wikipedia. Posted in Design Pattern | Tagged | 5 Comments ## 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. Posted in Design Pattern | Tagged | Leave a comment ## AS3: Inline graphics using Text Layout Framework A little bit of history Few days ago I was working on something which required graphics and text in same line. The text and graphics were fully dynamic. At first I thought it’s a 15 minutes work, as TextField supports HTML img tag. So It should be a simple one line code. textField.htmlText = "before img <img src='img.png'> after img"; The output was horrible. As shown in the screenshot, the image was moved on the next line. This is really not inline graphics what I was looking for. Then I checked the manual of TextField again and found that img tag is not fully supported, the image will be placed on the line following the img tag. Well well well, I am not going to write here how I solved the problem, as that was a little bit of dirty solution. As a result, I was looking for a better solution, Googled and asked a question on StackOverflow. Someone suggested to use Text Layout Framework from Adobe Labs. After checking, I found that this is a very powerful framework and supports many things. And now I am going to write how to show inline graphics using TLF. Text Layout Framework So what is Text Layout Framework anyway? It is a AS3 library built on the new text engine of Adobe Flash Player 10 and Adobe AIR 1.5 with lots of features like bidirectional text, vertical text, inline graphics, advanced styling capabilities, selection and editing of text and many more. It requires Flash Player 10 or Adobe AIR 1.5. The library is open source now and it is included in Flex 4 SDK. Organization of Text in TLF TLF uses a tree to represent text. Every node in the tree is an instance of a class defined in flashx.textLayout.elements package. The root node is always an instance of TextFlow class. It can have two types of children, instance of DivElement and instance of ParagraphElement which are similar to HTML div and p tag respectively. Similarly DivElement can have two types of children, DivElement instance and ParagraphElement instance. And ParagraphElement can have four types of children, instances of SpanElement, InlineGraphicElement, LinkElement and TCYElement. These four types contain primitive text and graphics. SpanElement represents the text with a common formatting, InlineGraphicElement represents inline graphic elements which are treated as a single character, LinkElement represents a hyper link and TCYElement represents text which can be perpendicular with the rest of the line (interesting?). All these elements are structured hierarchically to represent the entire text in TLF. Inline graphics using TLF 1. First I want to embed the test image for simplicity. Don’t want to load dynamically just for this demo. [Embed(source='img.png')] private static var Img:Class; 2. Create a TextFlow instance which is the root node of the tree. var textFlow:TextFlow = new TextFlow(); 3. Create a ParagraphElement and add this as a child to the root TextFlow. var para:ParagraphElement = new ParagraphElement(); textFlow.addChild(para); 4. Create the SpanElement to represent the text before the image and add this as a child to the ParagraphElement. I am using the default styling here. var spanBefore:SpanElement = new SpanElement(); spanBefore.text = "before img "; para.addChild(spanBefore); 5. Create the InlineGraphicElement to represent the image and add this as a child to the ParagraphElement. var inlineImg:InlineGraphicElement = new InlineGraphicElement(); var img:Bitmap = new Img(); inlineImg.source = img; para.addChild(inlineImg); 6. Create the second SpanElement to represent the text after the image and add this as a child to the ParagraphElement. var spanAfter:SpanElement = new SpanElement(); spanAfter.text = " after img with TLF"; para.addChild(spanAfter); 7. Now we have our text with inline graphics ready. We need to render this. For rendering simple TextFlowTextLineFactory is used here. There is another sophisticated method for rendering which I am not discussing. TextFlowTextLineFactory is sufficient when user don’t need much control over the text like editing the text. TextFlowTextLineFactory instance has a method createTextLines which takes a callback function and a TextFlow instance as parameters. Naturally TextFlow parameter is the root node of the tree that we are trying to render. The callback is fired when rendering is complete and the DisplayObject is passed to the callback. Then we simply need to add this display object in the display list. var factory:TextFlowTextLineFactory = new TextFlowTextLineFactory(); factory.compositionBounds = new Rectangle(30, 100, 500, 100); factory.createTextLines(addTextLineCallback, textFlow); // callback private function addTextLineCallback(textLine:DisplayObject):void { addChild(textLine); } And here is the result Conclusion Full code for this demo can be downloaded from here. Here I have shown only a tiny portion of the power of TLF. It is capable of much more things. Please follow the links in the reference section for the details of TLF. And as usual, any feedback is welcome. References Posted in AS3 | Tagged | 9 Comments ## Compiling the Linux kernel This is actually a very old writing. I wrote this back on 2007 in my old blog (which is now deleted). I was building my own Linux From Scratch and needed to compile the kernel as part of that. Later during our OS course we were given an assignment to add a system call in Linux kernel and as a result compiling the kernel was needed. Some of my friends were having trouble with the process. It was not a straight forward task, given the fact that most were unfamiliar with Linux itself. So I decided to write this. I know that now this may not even work for the latest kernel. Still I am keeping this here … just as a sweet memory. Building a Linux From Scratch is something that personally I consider “crazy”. Frankly speaking, compiling Linux kernel may vary from architecture to architecture and from kernel version to version. Here is one way that you can build on i386. 1. Download the latest stable kernel from kernel.org. I’m using 2.6.22.1 as an example. 2.6.22.1 can be downloaded from here. 2. Extract that.$ tar xfj linux-2.6.22.1.tar.bz2
3. Move to the source directory.
$cd linux-2.6.22.1 4. Remove any *.o files from source tree. It is recommended to do this before every compilation, even when the files are just extracted.$ make mrproper
5. Configure the kernel.
$make menuconfig Well, this is a long process. You can do lots of things. You can optimize for specific processor, for desktop or server, build the kernel with debugging symbols, even you can add your name with kernel version :-). Explore the options as much as possible. 6. Compile the kernel.$ make
7. If you have configured some parts of the kernel as loadable module (you should do that), install those modules.
# make modules_install
Modules are installed in /lib/modules. Here is a caution: if you are building the same version as your running version (or any existing version), modules will be overwritten and you may damage your running system. So be careful before doing this. It’s better to append a custom string after kernel release (local version) during configuring.
8. arch/i386/boot/bzImage is the built kernel image. Copy that to your boot partition.
# cp arch/i386/boot/bzImage /boot/bzImage-2.6.22.1
9. Copy the symbol map file.
# cp System.map /boot/System.map-2.6.22.1
10. Your configuration is stored in .config file. Save that for future reference.
# cp .config /boot/config-2.6.22.1
11. Create an initial ram disk for your kernel.
# mkinitrd /boot/initrd-2.6.22.1 2.6.22.1
12. Modify your boot loader’s configuration file. Most of the distros use grub now. /boot/grub/grub.conf or /boot/grub/menu.lst is the grub configuration file. Modify whichever is present in your distro. On some distros both are present and one is a link to another. In that case you can work with anyone, no doubt. Add the following lines:

title 2.6.22.1
root (hd0,7)
kernel /bzImage-2.6.22.1 ro root=LABEL=/1 rhgb quiet
module /initrd-2.6.22.1

What’s the meaning of all these? First line is the title which will be shown in the menu during boot time. Second line means that my boot partition is /dev/hda8. hd0 means primary master (hda) and 7 means hda8. (Yes, grub starts from zero). Third line shows the path of kernel image. ro root=LABEL=/1 rhgb quiet are the booting options. LABEL is specified in my /etc/fstab file. Fourth line is the path of initial ram disk. Both kernel and initrd paths are relative to the partition which is specified in the second line. In my system it is hda8.

Obviously these will vary from system to system. Now here is a big question: what will happen if you don’t know what is your boot partition, what is your root partition, what lies in /etc/fstab and what are the options to the kernel?? You will get all these information from grub configuration file. How? Just see the entry of your existing running kernel :-).

And finally, if you see a panic something like “policy checking”, add enforcing=0 in the kernel option list.
13. Now reboot and enjoy 🙂

Special Thanks to:

• Sayeed Hyder Sir, who was our OS course teacher and tried lots of interesting things.
• Linux from scratch project. Here is their kernel building page.
Posted in Linux | Tagged | 1 Comment

## AS3: Load assets dynamically for better performance

Asset management is a crucial point of every game. These assets may include bitmap images, audio and video files, animations, 3D models etc. etc. Depending on the size of the game there might be hundreds of such assets. How these assets and handled can have severe impact on the performance and user experience. One way to handle the assets is to embed all the assets with the main swf file. The obvious result is a big main swf file which will take more time to load and user will need to wait more. This leads to a very bad user experience for medium size games and just impossible for big size games. Better way is to embed only the required assets to start the game and load the remaining things after the game starts or load them only when that is needed. This requires dynamic loading of assets, the thing that I am going to discuss here.

In this tutorial I am going to create a simple asset file which contains 3 bitmap images, load that asset file dynamically and then load the bitmaps from the asset file. I have assumed that the reader is already familiar with the AS3 language and flash itself. That means I won’t explain what is a class, method or what is a swf or fla file.

Prepare the project and asset file

• Create a new AS project named LoaderDemo. I am using Adobe Flash Builder 4 for this. Make sure that Copy non-embed files to output folder is checked under project Properties/ActionScript Compiler (by default it is checked).
• Create a folder named Asset under the project directory. The fla file will be stored here. Note that this is not under src directory. Only the published swf file is needed in the output directory, so there is no need to store fla file under src directory.
• Create a fla file under Asset folder. Create three rectangle images of size 100×50 and fill them with color red, green and blue by using any image manipulation software like photoshop or paint. These are the bitmap images that will be loaded from the asset file. Drag and drop the files to fla’s Library panel. The bitmaps will be copied to the fla.
• Now the images are stored in the fla. An way to access them after the file is loaded is required. Right click on the blue.png and select Properties. Check Export for ActionScript and edit the Class to BoxBlue. The base class is BitmapData.
• Same thing is done for the other two images. Now the linkage for all bitmaps are established.
• Publish the file. If there is a warning something like new classes will be generated then select Yes. This will create the asset.swf file which contains the bitmaps.
• Create asset folder under src and copy the swf to src/asset. After building the project this swf will be available in output folder.
• And we are done with the asset preparation.

• Now comes the coding part. We want to load the asset after the main swf file is loaded. Add a listener for the ADDED_TO_STAGE event in the constructor of main LoaderDemo class. The swf will be loaded from this listener function.
package
{
import flash.display.Sprite;
import flash.events.Event;

{
{
}

}
}
}

• Create a class named AssetManager. This will handle the loading of the asset. This class contains an instance of AS Loader class which is used to load asset files, a callback function which will be fired after the loading is completed and the relative path to asset file. The loader is instantiated in the constructor.
package
{

public class AssetManager
{

private const ASSET_FILE_PATH:String = "asset/asset.swf";

public function AssetManager()
{
}
}
}

}

}

private var assetManager:AssetManager = null;

assetManager = new AssetManager();
}

}

• Now the swf containing the bitmaps is loaded. We need to access the bitmaps from it. During the asset preparation we linked the red, green and blue bitmap files against the class definition BoxRed, BoxGreen and BoxBlue respectively, which all are subclass of BitmapData. The first thing that is required is to get the class definition from the loaded swf. After getting the class definition we can instantiate them.

The contentLoaderInfo property (which is an instance of LoaderInfo) of assetLoader contains a property named applicationDomain, an instance of AS class ApplicationDomain which is a container of class definitions. All the classes that are defined in the swf file can be accessed by using methods of applicationDomain. So, define a method getClassDefinition in AssetManager which takes a definition string as parameter and check whether the class is present in the swf. If present then that class definition is returned as Class object.

public function getClassDefinition(definition:String):Class {
}

return null;
}

• Define a method createBitmap in LoaderDemo which takes a class name as string and returns the Bitmap if the class is present in the swf. It first gets the Class object from assetManager by calling getClassDefinition. The returned class object is a subclass of BitmapData. Then a new object is instantiated from the returned class object. The constructor of BitmapData takes two parameter, width and height. In this case that is set correctly from the asset, even then we need to pass 0, 0 for them. And then a Bitmap is created from the data and returned.
private function createBitmap(bmpClassName:String):Bitmap {
var bmpClass:Class = assetManager.getClassDefinition(bmpClassName);

if (bmpClass) {
var bmpData:BitmapData = new bmpClass(0, 0) as BitmapData;
return new Bitmap(bmpData);
}

return null;
}

• We are done. The only remaining thing is to test the code. So we create three bitmaps in assetLoaded and add them as the child.

var bmp1:Bitmap = createBitmap("BoxRed");

var bmp2:Bitmap = createBitmap("BoxGreen");
bmp2.y = 100;

var bmp3:Bitmap = createBitmap("BoxBlue");
bmp3.y = 200;
}

• After running the project, here is the output.

Few final notes

• This example handles only one asset file. In real situation more than one asset file might be required to load dynamically.
• assetManager is a member of LoaderDemo. A Singleton might be a better choice.
• createBitmap is a method of LoaderDemo. This might be okay for a small tutorial like this. But in reality a Factory should be used.
• Bitmaps are not handled here efficiently. createBitmap creates a new bitmap every time it is called. However, there should be no reason to load the same bitmap data more than once in memory. Bitmap data can be shared efficiently by using a Flyweight.
• The asset file path is hardcoded in this example. However, it is better to read them from a config file.
• Though this example contains only bitmap assets, the same technique can be used for other types of assets.
• AS3 reference manual contains detail information on Loader, URLRequest, LoaderInfo and ApplicationDomain classes.
• A nice tutorial on loader can be found here.
• There are other methods to manage assets. They can be found here.

The full code for this tutorial can be downloaded from here. Any feedback is welcome.

Posted in AS3 | Tagged | 5 Comments