## WebGL: More Drawing Tools

For the last few days I am learning WebGL (and OpenGL too) as a hobby. As part of the learning process I have decided to convert some examples of OpenGL programs to WebGL programs. The book that I am reading currently is Computer Graphics Using Open GL (2nd Edition) by Francis S. Hill. There is a newer edition of this book but I don’t have that with me. Though the basic idea and graphics concepts, maths, algorithms behind these example are taken from this book, the implemented code is largely different as the book is about OpenGL with C++ and here I am working in WebGL with JavaScript. And some of these are present as exercise in the book.

Acknowledgments:

• As stated before, the original OpenGL examples/exercises are taken from the book(chapter three More Drawing Tools) written by Francis S. Hill.
• A major portion of the codes are directly taken from Learning WebGL lessons written by Giles Thomas.
• WebGLUtils utility library from Google is used for initializing WebGL and requesting animation frames.
• glMatrix is used as matrix and vector library.
• The code to find out mouse coordinates relative to the canvas is taken from here, suggested by N4ppeL and Ryan Artecona.

Disclaimer: These are not complete tutorials. I have not explained anything regarding maths, graphics, OpenGL, WebGL etc. I have written only some test codes, and written them as a hobby. Anyone can consult with the original book and lessons if interested. And as I am still learning, there could be misconceptions too. If you notice anything wrong please feel free to put a comment. I will try to fix them as early as possible.

Here are the examples:

• Plotting function $sinc(x) = \frac{sin(\pi x)}{\pi x}$ for x = [-4.0, 4.0).

Live WebGL version is here.
• Tiling Window with Dinosaurs.

Live WebGL version is here.
• Tiling Window with Flipped Dinosaurs.

Live WebGL version is here.
• Zooming in and out a dinosaur. Use + and - button to zoom in and out. Following screenshot is taken after zooming in certain amount.

Live WebGL version is here.
• Clipping lines against a rectangle using Cohen-Sutherland algorithm. 50 random lines are generated and clipped against the 25% gray rectangle. Clipped portions are drawn in red. The implementation is based on the C/C++ example from Wikipedia.

Live WebGL version is here.
• Plotting sinusoidal sequence $y_{k} = ay_{k - 1} - y_{k - 2} \text{ for } k = 1, 2, 3, ... \text{ where } y_{k} = 0 \text{ for } k < 0, y_{0} = 1, a = 2 \cos \frac{2 \pi}{S} \text{. Following screenshot is taken for } S = 59 \text{.}$

Live WebGL version is here.
• Building a figure out of several turtle motions. The hook on left is generated via three pairs of turtle forward, turn commands and the figure on right is generated by calling hook four times.

Live WebGL version is here.
• Polyspirals using Turtle Graphics.

Live WebGL version is here.
• Meander using Turtle Graphics.

Live WebGL version is here.
• The 5-, 11- and 17-Rosettes.

Live WebGL version is here.
• Pattern of 21 stars.

Live WebGL version is here.
• n-Gons sharing a common edge.

Live WebGL version is here.
• Rotated Hexagons.

Live WebGL version is here.
• Shape based on pentagon and arcs.

Live WebGL version is here.
• Patterns of Teardrops.

Live WebGL version is here.
• Curves with simple polar forms. Cardioid, Rose curves with 3 and 7 petals, Archimedean Spiral.

Live WebGL version is here.
• Electrostatic Field Lines with Orthogonal Circles.

Live WebGL version is here.
• Basic Tiling.

Live WebGL version is here.
• Truchet Tiles.

Live WebGL version is here.
• Random generated polyline for points on a parametric ellipse. A flurry of seemingly unrelated lines first appears, but soon the eye detects some order in the chaos and an elliptical envelope emerging around the cloud of lines. First screenshot is taken just after start, second one is taken after some time.

Live WebGL version is here.

## WebGL: Getting Started: Drawing Figures

For the last few days I am learning WebGL (and OpenGL too) as a hobby. As part of the learning process I have decided to convert some examples of OpenGL programs to WebGL programs. The book that I am reading currently is Computer Graphics Using Open GL (2nd Edition) by Francis S. Hill. There is a newer edition of this book but I don’t have that with me. Though the basic idea and graphics concepts, maths, algorithms behind these example are taken from this book, the implemented code is largely different as the book is about OpenGL with C++ and here I am working in WebGL with JavaScript. And some of these are present as exercise in the book.

Acknowledgments:

• As stated before, the original OpenGL examples/exercises are taken from the book(chapter two Getting Started: Drawing Figures) written by Francis S. Hill.
• A major portion of the codes are directly taken from Learning WebGL lessons written by Giles Thomas.
• WebGLUtils utility library from Google is used for initializing WebGL and requesting animation frames.
• glMatrix is used as matrix and vector library.
• The code to find out mouse coordinates relative to the canvas is taken from here, suggested by N4ppeL and Ryan Artecona.

Disclaimer: These are not complete tutorials. I have not explained anything regarding maths, graphics, OpenGL, WebGL etc. I have written only some test codes, and written them as a hobby. Anyone can consult with the original book and lessons if interested. And as I am still learning, there could be misconceptions too. If you notice anything wrong please feel free to put a comment. I will try to fix them as early as possible.

Here are the examples:

• Three simple dots where pointsize = 4.

Live WebGL version is here.
• Big Dipper Constellation.

Live WebGL version is here.
• Random Sierpinski Gasket with 3000 points.

Live WebGL version is here.
• Dot plot of function f(x) = e(-x) * cos(2 * pi * x) for x = [0, 4).

Live WebGL version is here.
• Line graph of function $f(x) = 300 - 100\cos{\frac{2\pi x}{100}} + 30\cos{\frac{4\pi x}{100.0}} + 6\cos{\frac{6\pi x}{100.0}}$. Origin is at top left, y increases downwards.

Live WebGL version is here.
• Loading polylines data from a file and render them. The data file dino.dat is taken from here.

Live WebGL version is here.
• A village of parameterized houses. Houses are drawn by calling function parameterizedHouse(peak, width, height).

Live WebGL version is here.
• Two aligned rectangles filled with colors.

Live WebGL version is here.
• Random number of rectangles with random sizes, colors at random positions.

Live WebGL version is here.
• Checkerboard pattern.

Live WebGL version is here.
• Flurry of diamonds. All simple diamond shapes are drawn by calling drawDiamond(center, radius).

Live WebGL version is here.
• Three polygons. All are drawn by calling drawPolygon(points).

Live WebGL version is here.
• Draw a point in random color after every click. Following screenshot is taken after enough clicks.

Live WebGL version is here.
• Draw random colored rectangle with every two mouse clicks. Click points specify the opposite corners of the rectangle. Right click clears the canvas. Following screenshot is taken after 16 left button clicks.

Live WebGL version is here.
• Draw random Sierpinski Gasket in random color with every three mouse clicks. Click points specify the corners of the Sierpinski Gasket. Right click clears the canvas.

Live WebGL version is here.
• Draw polyline with mosuse clicks. Every click adds a point in polyline. Right click clears the canvas. Following screenshot is taken after seven clicks.

Live WebGL version is here.
• Freehand drawing with a fat brush using mouse. Move the mouse while clicking left button to draw. Right click clears the canvas.

Live WebGL version is here.
• Random constellation of dots where random positions are generated using Linear congruential generator n(i + 1) = [A * n(i) + B] % m. Input A, B, m, seed n(0) and generate points. Following screenshot is taken for values A = 1664525, B = 1013904223, m = 4294967296, n(0) = 123456.

Live WebGL version is here.
• Consider the function
$f(x) = \left\{ \begin{array}{ll} x / 2 & \mbox{if } x\text{ is even} \\ 3x + 1 & \mbox{if } x\text{ is odd} \end{array} \right.$
Now construct a sequence of integers by taking an intial positive integer and repeating this function where output of a step is the input of the next step. The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially. For example, if initial input is 11 then we get: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

After taking an initial positive integer value, construct a ling graph by plotting number of steps k on x-axis and and value of f(k) on y-axis. Following screenshot is taken for initial value 1234.

Live WebGL version is here.

Live WebGL version is here.
• Infinite Regressions of the Golden Rectangle.

Live WebGL version is here.
• Random perfect maze generator of size R x C. Following screenshot is taken from one particular run with R = 59, C = 47. This article briefly describes the maze generation algorithm.

Live WebGL version is here.

Posted in Graphics, WebGL | Tagged , | 3 Comments

## 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 (warning: the file is big).

Like always, any feedback is welcome.

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) {
}

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());
}

}


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

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.
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.

• 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.
• And finally, any feedback is welcome.

## 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();

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 ";

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;

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";

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);

// callback