• entries
    146
  • comments
    436
  • views
    197743

Patterns and Refactoring, Part 1

Sign in to follow this  

192 views

Design Pattern Categories
Design patterns can typically be divided up into categories that help to quantify the problems they deal with. A comprehensive list of these categories would be infeasible to put together, seeing as how there are hundreds of thousands of different categories, and that patterns exist in many categories at once. There are a few categories that are easy enough to list, and that most patterns fall into either one or the other. Perhaps most obviously, the two categories are language specific, and ,language agnostic. The majority of patterns in existence fall into one category or the other (mostly the latter). However, there are a growing number which fall into both categories, depending on how you implement them.

The first example that comes to mind is that of policies. The policy pattern is just a generalization of the strategy pattern, which we will discuss later. Typically the policy pattern is used to abstract chunks of an algorithm for extension. Through inheritance, one is able to customize the behavior of an algorithm. One sample of the strategy pattern would be the IComparable interface in the .Net framework. IComparable allows you to customize the behavior of algorithms that use comparisons on types, thus enabling you to sort a container in the order you wish, find an element containing the data you want, and has many other applications as well.

The policy pattern has another face though, in C++ you can implement a form of the policy pattern using templates. It's the same basic pattern, but with a meta-programming flavor added to it. You can see this used throughout the C++ standard library. For instance, the associative containers the standard library contains all allow you to specify a comparison predicate. You can also see this same pattern being exposed in boost, where you can implement pieces of objects through policies that are passed in as template parameters.

What is most interesting about this is that a growing number of language agnostic patterns are starting to be implemented as meta-programming patterns in C++. This pattern of moving from a fairly language agnostic approach to much more specialized compile-time constructs demonstrates just a fraction of the power behind patterns. Using meta-patterns provide a very powerful approach to generate a great deal of reusable and extensible code without having to actually write the code. Instead you write the templates behind the code and use meta-programming and patterns to generate the actual code. Best of all, such approaches allow for optimizations that would be non-trivial to write in other cases. You would end up duplicating by hand a great deal of code which would decrease the maintainability of the code base.

I have a plan...
Strategy. No, not the military or business kind, but instead the design pattern. In a moment you're going to see a refactoring that will turn a piece of code that probably looks rather familiar to you (don't like, I KNOW you do these kinds of things), into something much more interesting. But first we need to describe the strategy pattern.

What
The Strategy design pattern allows you to decouple an algorithm from its host. Thus you can switch the algorithm (or host) without changing the other side of the equation (sounds like something that would violate a few mathematical rules [grin]).

Why
Use the strategy pattern when you have several objects that are basically the same, and differ in their behavior. Refactoring to a strategy pattern can have several benefits: It exposes an interface which can be used for extension and it limits the amount of subclassing you need to do in order to alter the behavior of an object.

How
If you don't know how to read UML, now is a good time to learn. The following diagram gives all the details needed to implement it. Basically, you pull extract an interface that represents the parts of the algorithm that you want to make generic. Then you pass in a concrete implementation of that interface to the host, and the host can now call to that concrete implementation for algorithm specific behavior.
Strategy UML

A refactoring example
Lets assume that we have something like the following code (which you do or did):

public enum PoisonType {
NoPoison,
WeakPoison,
StrongPoison,
DeadlyPoison
}

public class Weapon {
public Weapon(double baseDamage) : this(baseDamage, PoisonType.NoPoison) { }
public Weapon(double baseDamage, PoisonType poisonType) {
this.baseDamage = baseDamage;
this.poisonType = poisonType;
}

public double CalculateDamage(double defenderAc) {
Random rand = new Random();
double damageDone = (baseDamage * rand.NextDouble() - defenderAc);

switch (poisonType) {
case PoisonType.NoPoison:
return damageDone;
case PoisonType.WeakPoison:
if (rand.NextDouble() > 0.1) {
return damageDone + damageDone * .1;
}
break;
case PoisonType.StrongPoison:
if (rand.NextDouble() > 0.2) {
return damageDone + damageDone * .2;
}
break;
case PoisonType.DeadlyPoison:
if (rand.NextDouble() > 0.3) {
return damageDone + damageDone * .3;
}
break;
default:
throw new InvalidOperationException("Unknown enumeration value: " + poisonType);
}

return damageDone;
}

private double baseDamage;
private PoisonType poisonType;
}





Now, first things first, lets assume that this is just a small snippet of the total code. As you can see, we have an enumeration which we are using here to determine if a person takes poisoned damage or not. If they do, we then add on an amount of damage comparable to the poison strength. Now, look at this piece of code and think of one word that describes it. Assuming you are thinking correctly, you should have come up with the word: 'Inflexible'. The reason it is inflexible is because you:

  • Have to change constants in order to configure the amount of damage a poison does.

  • Have a series of magical numbers that really mean nothing to you

  • Have a bunch of duplicate code, that would further get duplicated as you add new types of poisons

  • Have no default implementation, thus extending the current implementation is buggy. (If you miss one switch statements, you get exceptions).



The first refactoring I would do is to replace the magic numbers with constants. Then I would refactor the poison calculations out to another method.

public double CalculateDamage(double defenderAc) {
Random rand = new Random();
double damageDone = (baseDamage * rand.NextDouble() - defenderAc);

switch (poisonType) {
case PoisonType.NoPoison:
return damageDone;
case PoisonType.WeakPoison:
return damageDone + CalculatePoisonDamage(rand, damageDone, WeakPoisonChance, WeakPoisonDamageRatio);
case PoisonType.StrongPoison:
return damageDone + CalculatePoisonDamage(rand, damageDone, StrongPoisonChance, StrongPoisonChance);
case PoisonType.DeadlyPoison:
return damageDone + CalculatePoisonDamage(rand, damageDone, DeadlyPoisonChance, DeadlyPoisonDamageRatio);
default:
throw new InvalidOperationException("Unknown enumeration value: " + poisonType);
}
}

private static double CalculatePoisonDamage(Random rand, double damage, double poisonChance, double poisonDamageRatio) {
if (rand.NextDouble() < poisonChance)
return poisonChance * damage;
return 0;
}

private const double WeakPoisonChance = 0.1;
private const double StrongPoisonChance = 0.2;
private const double DeadlyPoisonChance = 0.3;

private const double WeakPoisonDamageRatio = 0.1;
private const double StrongPoisonDamageRatio = 0.2;
private const double DeadlyPoisonDamageRatio = 0.3;





This is better, but it's still not very extensible. First of all, we can't load in our own poison chances or poison damage ratios. Extensibility is still a problem as well. What we could do, however, is refactor the enumeration out to a strategy pattern. We could then have the pattern provide methods to retrieve the poison chance and poison damage ratio values. Using this method we would be able to eliminate the switch, and allow for poison values to be loaded from a file, or other data source.

Performing this refactoring gives us the following code,

public class PoisonType {
public static readonly PoisonType NoPoison = new PoisonType(0.0, 0.0);
public static readonly PoisonType WeakPoison = new PoisonType(0.1, 0.1);
public static readonly PoisonType StrongPoison = new PoisonType(0.2, 0.2);
public static readonly PoisonType DeadlyPoison = new PoisonType(0.3, 0.3);

public PoisonType() : this(0, 0) { }

public PoisonType(double poisonChance, double damageRatio) {
this.poisonChance = poisonChance;
this.damageRatio = damageRatio;
}

public virtual double CalculateDamage(Random rand, double damage) {
if (rand.NextDouble() < poisonChance) {
return damage * damageRatio;
}

return 0;
}

private double poisonChance;
private double damageRatio;
}

public class Weapon {
public Weapon(double baseDamage) : this(baseDamage, PoisonType.NoPoison) { }
public Weapon(double baseDamage, PoisonType poisonType) {
this.baseDamage = baseDamage;
this.poisonType = poisonType;
}

public double CalculateDamage(double defenderAc) {
Random rand = new Random();
double damageDone = (baseDamage * rand.NextDouble() - defenderAc);

return damageDone + poisonType.CalculateDamage(rand, damageDone);
}

private double baseDamage;
private PoisonType poisonType;
}





As you can see, the code is much simpler now. Not only that, but with the virtual member of the PoisonType class, you can easily extend it to calculate damage in a variety of other ways. You will also note that it would be very difficult to accidentally miss implementing part of the algorithm, as the strategy interface would expose everything you should implement.

Notes
If you look at the UML and at my sample, you might notice that they don't match. Remember, the description of a pattern is just a generalization, and if you recall the quote from the previous journal, you can see what he means about being able to use a pattern many different times without ever implementing it the same way twice.

In the previous issue I mentioned a particular pattern by name in relation to enterprise patterns and multithreading patterns. The name I used, however was incorrect. I said Transaction Script when I meant to write Transaction. I have since gone back and fixed the journal entry.

Software Development Guidelines

  • Upfront design should be limited to a high level overview.
    Diagramming implementation details is a poor idea, as requirements will change. Placing implementation details in your design documents will end up prematurely outdating them. It is best to leave such details as performance requirements, if any at all.



The End of the Road
Some people seem to think that any sort of initial optimizations are premature. Now, this seems quite silly to me. Algorithmic optimizations are hardly premature, especially if you know the constraints of your operation (which you often times do). Looking at it realistically, putting off algorithmic optimizations tends to have a rather large impact on development time. Best to do it right the first time, than to have to refactor it a dozen buggy times. However, you should always temper such optimizations by examining the need for them. For instance, quicksort is a great sorting method, and most standard library implementations provide a form of quicksort (or introsort which is uses quicksort). But does that mean that you should write your own sort (such as an ordersort) for your application just because you know it will perform better (up to about 5000 elements) than a quicksort? The answer is no. In general the quicksort will work just fine, instead you should profile, and if you find that quicksort is providing enough of a bottleneck to warrant the implementation of another sorting method, then by all means go for it.

On the other hand, if you happen to know that you are going to need to perform inserts throughout a container (not just at the end), then there is no reason NOT to write your code using a linked list (also provided by most standard libraries) outright. In this case, you know something about the problem (specifically that you will be inserting at the start, middle, and end point) and so you can make an appropriate choice of container/algorithm to solve the problem. That is in no way a premature optimization, that's just smart programming.

Another common thing that I see is that people associate managed code with slowness. They also take the fact that there aren't many commercial games implemented in managed code to be a sign of it's weakness. Hardly. Looking at things in terms of history, the game development world is like a snail when it comes to implementing new (and often better) technologies. While everyone else was using the ox and iron plow on their fields, game programmers were using sticks and stones. That's not to say that using technologies like C++ is a failing. Quite the opposite, I would say that C++ provides many advantages for game programming in terms of compile-time programming flexibility. It also has many limitations on it that severely hamper your ability to make data-driven applications.

However, that being said, you do see managed games popping up, but more commonly, you see them popping up on the tools side of development. Since tools need to be up and running quickly to get development underway, you typically see them built using managed code. Even more interesting however is that most of these tools integrate with the engine. If a managed tool can integrate with the engine, then could not a managed game?

Well, that's enough of my ramblings for today.
Sign in to follow this  


4 Comments


Recommended Comments

I thought your choice of categorization was an interesting one. Design patterns are typically divided up according to their function (behavioral, structural, etc.), so this was an unusual and refreshing take on the matter. Kudos!

Share this comment


Link to comment
cool :D
but wouldn't we want to abstract further and focus on abstarct damage types (fire/ice ad nasuem), and then do relations (a tree perhaps) of how protection agaist one damage type will effect other damage types.

hmmm. wish I wasn't at work.
Also, yeah that doesn't come across enough about optimizations, but from what I see, people "optimizing" early on aren't worried about which data storage, or how to structure their framework, but worried about squeezing the best performance out of one function by switching around how it is called etc.

Share this comment


Link to comment
Nice article.

Quote:

If you look at the UML and at my sample, you might notice that they don't match. Remember, the description of a pattern is just a generalization, and if you recall the quote from the previous journal, you can see what he means about being able to use a pattern many different times without ever implementing it the same way twice.


I think its worth mentioning that the C++ library Loki provides some common patterns and allows you to highly customise them through policy classes, meaning you can tailor them to the current situation, without having to implement them again from the ground up.

I feel Loki is somewhat lacking though, I think it would be good if it was added into boost and expanded to contain more of the GoF patterns.

Looking forward to your next update!

Share this comment


Link to comment
Quote:

If a managed tool can integrate with the engine, then could not a managed game?

Reality Engine :) I know of a few big productions using that engine right now that are building the full game in C# 2.0.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now