Program Your Face Off

Let's write a c++ math libraryI (part 2)

2014-10-20T06:17:00.001-07:00

Last time we made a class to encapsulate a 2D vector with floating point entries. In this post we'll finish up with the 3 and 4 dimensional vector classes. None of these will be particularly useful however, until we make a matrix class that can transform these vectors.

So let's get started.

vector3f.h

#ifndef _VECTOR3F_H_
#define _VECTOR3F_H_

class vector3f
{
private:
    float elements[3];
public:

    static const int SIZE;

    vector3f(float x = 0.0f, float y = 0.0f, float z = 0.0f);

    vector3f(const vector3f& other);

    vector3f normal() const;

    void normalize();

    float length() const;

    static float dot(const vector3f& vector1, const vector3f& vector2);

    static vector3f cross(const vector3f& vector1, const vector3f& vector2);

    vector3f& operator=(const vector3f& other);

    vector3f operator-() const;

    vector3f operator*(float scalar) const;

    vector3f operator/(float scalar) const;

    friend vector3f operator+(const vector3f& vector1, const vector3f& vector2);

    friend vector3f operator-(const vector3f& vector1, const vector3f& vector2);

    friend vector3f operator*(float scalar, const vector3f& vector);

    friend bool operator==(const vector3f& vector1, const vector3f& vector2);

    friend bool operator!=(const vector3f& vector1, const vector3f& vector2);

    float& operator[](int index);
};

#endif

You'll notice we have a function that the vector2f class does not: cross
This is the cross product of two 3D vectors which produces a vector perpendicular to both input vectors in a direction determined by the right hand rule. It is only defined for 3 dimensional vectors.

vector3f.cpp

#include "vector3f.h"
#include <cmath>

const int vector3f::SIZE = 3;

vector3f::vector3f(float x, float y, float z)
{
    elements[0] = x;
    elements[1] = y;
    elements[2] = z;
}

vector3f::vector3f(const vector3f& other)
{
    elements[0] = other.elements[0];
    elements[1] = other.elements[1];
    elements[2] = other.elements[2];
}

vector3f vector3f::normal() const
{
    float l = length();
    return vector3f(elements[0] / l, elements[1] / l, elements[2] / l);
}

void vector3f::normalize()
{
    float l = length();
    elements[0] /= l;
    elements[1] /= l;
    elements[2] /= l;
}

float vector3f::length() const
{
    return std::sqrt(elements[0] * elements[0] + elements[1] * elements[1] + elements[2] * elements[2]);
}

float vector3f::dot(const vector3f& vector1, const vector3f& vector2)
{
    return vector1.elements[0] * vector2.elements[0] + vector1.elements[1] * vector2.elements[1] +
        vector1.elements[2] * vector2.elements[2];
}

vector3f vector3f::cross(const vector3f& vector1, const vector3f& vector2)
{
    return vector3f(vector1.elements[1] * vector2.elements[2] - vector1.elements[2] * vector2.elements[0],
        vector1.elements[2] * vector2.elements[0] - vector1.elements[0] * vector2.elements[2],
        vector1.elements[0] * vector2.elements[1] - vector1.elements[1] * vector2.elements[0]);
}

vector3f& vector3f::operator=(const vector3f& other)
{
    if (this != &other)
    {
        elements[0] = other.elements[0];
        elements[1] = other.elements[1];
        elements[2] = other.elements[2];
    }
        return *this;
}

vector3f vector3f::operator-() const
{
    return vector3f(-elements[0], -elements[1], -elements[2]);
}

vector3f vector3f::operator*(float scalar) const
{
    return vector3f(scalar * elements[0], scalar * elements[1], scalar * elements[2]);
}

vector3f vector3f::operator/(float scalar) const
{
    return vector3f(elements[0] / scalar, elements[1] / scalar, elements[2] / scalar);
}

vector3f operator+(const vector3f& vector1, const vector3f& vector2)
{
    return vector3f(vector1.elements[0] + vector2.elements[0], vector1.elements[1] + vector2.elements[1],
        vector1.elements[2] * vector2.elements[2]);
}

vector3f operator-(const vector3f& vector1, const vector3f& vector2)
{
    return vector3f(vector1.elements[0] - vector2.elements[0], vector1.elements[1] - vector2.elements[1],
        vector1.elements[2] - vector2.elements[2]);
}

vector3f operator*(float scalar, const vector3f& vector)
{
    return vector3f(scalar * vector.elements[0], scalar * vector.elements[1],
        scalar * vector.elements[2]);
}

bool operator==(const vector3f& vector1, const vector3f& vector2)
{
    return ((vector1.elements[0] == vector2.elements[0]) && (vector1.elements[1] == vector2.elements[1]) &&
        vector1.elements[2] == vector2.elements[2]);
}

bool operator!=(const vector3f& vector1, const vector3f& vector2)
{
    return ((vector1.elements[0] != vector2.elements[0]) || (vector1.elements[1] != vector2.elements[1]) ||
        vector1.elements[2] != vector2.elements[2]);
}

float& vector3f::operator[](int index)
{
    return elements[index];
}

vector4f.h

#ifndef _VECTOR4F_H_
#define _VECTOR4F_H_

class KOGAPI vector4f
{
private:
    float elements[4];
 
public:

    static const int SIZE;

    vector4f(float x = 0.0f, float y = 0.0f, float z = 0.0f, float w = 0.0f);

    vector4f(const vector4f& other);

    vector4f normal() const;

    void normalize();

    float length() const;

    static float dot(const vector4f& vector1, const vector4f& vector2);

    vector4f& operator=(const vector4f& other);

    vector4f operator-() const;

    vector4f operator*(float scalar) const;

    vector4f operator/(float scalar) const;

    friend vector4f operator+(const vector4f& vector1, const vector4f& vector2);

    friend vector4f operator-(const vector4f& vector1, const vector4f& vector2);

    friend vector4f operator*(float scalar, const vector4f& vector);

    friend bool operator==(const vector4f& vector1, const vector4f& vector2);

    friend bool operator!=(const vector4f& vector1, const vector4f& vector2);

    float& operator[](int index);
};

#endif

vector4f.cpp

#include "vector4f.h"
#include <cmath>

vector4f::vector4f(float x, float y, float z, float w)
{
    elements[0] = x;
    elements[1] = y;
    elements[2] = z;
    elements[3] = w;
}

vector4f::vector4f(const vector4f& other)
{
    elements[0] = other.elements[0];
    elements[1] = other.elements[1];
    elements[2] = other.elements[2];
    elements[3] = other.elements[3];
}

vector4f vector4f::normal() const
{
    float l = length();
    return vector4f(elements[0] / l, elements[1] / l, elements[2] / l, elements[3] / l);
}

void vector4f::normalize()
{
    float l = length();
    elements[0] /= l;
    elements[1] /= l;
    elements[2] /= l;
    elements[3] /= l;
}

float vector4f::length() const
{
    return std::sqrt(elements[0] * elements[0] + elements[1] * elements[1] + elements[2] * elements[2] +
        elements[3] * elements[3]);
}

float vector4f::dot(const vector4f& vector1, const vector4f& vector2)
{
    return vector1.elements[0] * vector2.elements[0] + vector1.elements[1] * vector2.elements[1] +
        vector1.elements[2] * vector2.elements[2] + vector1.elements[3] * vector2.elements[3];
}

vector4f& vector4f::operator=(const vector4f& other)
{
    if (this != &other)
    {
        elements[0] = other.elements[0];
        elements[1] = other.elements[1];
        elements[2] = other.elements[2];
        elements[3] = other.elements[3];
    }
    return *this;
}

vector4f vector4f::operator-() const
{
    return vector4f(-elements[0], -elements[1], -elements[2], -elements[3]);
}

vector4f vector4f::operator*(float scalar) const
{
    return vector4f(scalar * elements[0], scalar * elements[1], scalar * elements[2],
        scalar * elements[3]);
}

vector4f vector4f::operator/(float scalar) const
{
    return vector4f(elements[0] / scalar, elements[1] / scalar, elements[2] / scalar,
        elements[3] / scalar);
}

vector4f operator+(const vector4f& vector1, const vector4f& vector2)
{
    return vector4f(vector1.elements[0] + vector2.elements[0], vector1.elements[1] + vector2.elements[1],
        vector1.elements[2] * vector2.elements[2], vector1.elements[3] + vector2.elements[3]);
}

vector4f operator-(const vector4f& vector1, const vector4f& vector2)
{
    return vector4f(vector1.elements[0] - vector2.elements[0], vector1.elements[1] - vector2.elements[1],
        vector1.elements[2] - vector2.elements[2], vector1.elements[3] - vector2.elements[3]);
}

vector4f operator*(float scalar, const vector4f& vector)
{
    return vector4f(scalar * vector.elements[0], scalar * vector.elements[1],
        scalar * vector.elements[2], scalar * vector.elements[3]);
}

bool operator==(const vector4f& vector1, const vector4f& vector2)
{
    return ((vector1.elements[0] == vector2.elements[0]) && (vector1.elements[1] == vector2.elements[1]) &&
        vector1.elements[2] == vector2.elements[2] && vector1.elements[3] == vector2.elements[3]);
}

bool operator!=(const vector4f& vector1, const vector4f& vector2)
{
    return ((vector1.elements[0] != vector2.elements[0]) || (vector1.elements[1] != vector2.elements[1]) ||
        (vector1.elements[2] != vector2.elements[2]) || (vector1.elements[3] != vector2.elements[3]));
}

float& vector4f::operator[](int index)
{
    return elements[index];
}

That's it for now. Next post we'll set up the matrix and quaternion class.
Questions are always welcome and if you have an idea for a tutorial or series you'd like to see feel free to comment it!.

Let's write a c++ math library!

2014-10-17T06:30:00.003-07:00

Wow, it's been a long time since I've updated this blog. So I've really been getting into C++ and OpenGL lately.
Why C++?
Well,

It's been around forever
It's easier to write cross platform applications
Unlike C it's object oriented out of the box
Pointers are fun
I like it. Whatever, I know someone who puts garlic on their peanut butter sandwiches, go bother him.

If you don't know C++ there's endless resources out there. So I'd like to start by writing a math library for rendering graphics. This means linear algebra. Go beef up on your linear algebra if you don't know much about it. Here's an MIT course on the subject. Have fun.

Let's get started! First we'll need a vector class. A few actually so let's start with a 2D vector with floating point elements.

vector2f.h

#ifndef _VECTOR2F_H_
#define _VECTOR2F_H_

class vector2f
{
private:
    float elements[2];

public:
    vector2f(float x = 0.0f, float y = 0.0f);

    vector2f(const vector2f& other);
    
    float length() const;

    static float dot(const vector2f& vector1, const vector2f& vector2);

    vector2f operator-();
    
    vector2f operator*(float scalar);

    friend operator*(float scalar, const vector2f& vector);

    friend operator/(const vector2f& vector, float scalar);

    friend operator+(const vector2f& vector1, const vector2f& vector2);

    friend operator-(const vector2f& vector1, const vector2f& vector2);

    vector2f& operator=(const vector2f& other);

    float& operator[](int index);

    friend bool operator==(const vector2f& vector1, const vector2f& vector2);

    friend bool operator!=(const vector2f& vector1, const vector2f& vector2);
};

#endif

That's good for now but we'll probably add more to this class later. Let's take a look at the source code.

vector2f.cpp

#include "vector2f.h"
#include <cmath>

vector2f::vector2f(float x, float y)
{
 elements[0] = x;
 elements[1] = y;
}

vector2f::vector2f(const vector2f& other)
{
    elements[0] = other.elements[0];
    elements[1] = other.elements[1];
}

float vector2f::length() const
{
    return std::sqrt(elements[0] * elements[0] + elements[1] * elements[1]);
}

float vector2f::dot(const vector2f& vector1, const vector2f& vector2)
{
    return vector1.elements[0] * vector2.elements[0] + vector1.elements[1] * vector2.elements[1];
}

vector2f vector2f::operator-()
{
    return vector2f(-elements[0], -elements[1]);
}

vector2f vector2f::operator*(float scalar)
{
    return vector2f(scalar * elements[0], scalar * elements[1]);
}

vector2f operator*(float scalar, const vector2f& vector)
{
    return vector2f(scalar * vector.elements[0], scalar * vector.elements[1]);
}

vector2f operator/(const vector2f& vector, float scalar)
{
    return vector2f(vector.elements[0] / scalar, vector.elements[1] / scalar);
}

vector2f operator+(const vector2f& vector1, const vector2f& vector2)
{
    return vector2f(vector1.elements[0] + vector2.elements[0], vector1.elements[1] + vector2.elements[1]);
}

vector2f operator-(const vector2f& vector1, const vector2f& vector2)
{
    return vector2f(vector1.elements[0] - vector2.elements[0], vector1.elements[1] - vector2.elements[1]);
}

vector2f& vector2f::operator=(const vector2f& other)
{
    if (this != &other)
    {
     elements[0] = other.elements[0];
     elements[1] = other.elements[1];
    }
    return *this;
}

float& vector2f::operator[](int index)
{
     //unsafe!  TODO:  add bounds checking
     return elements[index];
}

bool operator==(const vector2f& vector1, const vector2f& vector2)
{
    return (vector1.elements[0] == vector2.elements[0] &&
        vector1.elements[1] == vector2.elements[1]);
}

bool operator!=(const vector2f& vector1, const vector2f& vector2)
{
    return (vector1.elements[0] != vector2.elements[0] ||
        vector1.elements[1] != vector2.elements[1]);
}

Hey, alright! That should be pretty good for now. This is pretty basic stuff but I thought someone might benefit from seeing how it's done. Later we'll add matrix classes and even a quaternion class for rotation.
That's it for now, though!

next: part 2

The GJK Algorithm

2012-01-17T12:33:00.000-08:00

This code sample uses the GJK Algorithm to determine if two convex regions in 3-space are intersecting.
There's a good tutorial on how this algorithm actually works here and another one here. This is my implementation in c#.
One can extend this to handle any convex shape at all as long as it has a function to determine the furthest point in the shape along a give direction, ie. if one were to walk along a line determined by a direction, starting "behind" the shape, determine the last point of the shape that you'll pass. This basically boils down to finding the shape's position that has the largest dot product with the direction.
While this can be tricky, GJK can handle any convex shape that implements this function making it very flexible. It's also faster than many other methods and uses minimal resources.
Now on to the code.
PhysicsExtensionMethods static class:

static class PhysicsExtensionMethods
{
    public static bool IsInSameDirection(this Vector3 vector, Vector3 otherVector)
    {
        return Vector3.Dot(vector, otherVector) > 0;
    }

    public static bool IsInOppositeDirection(this Vector3 vector, Vector3 otherVector)
    {
        return Vector3.Dot(vector, otherVector) < 0;
    }
}

IConvexRegion interface:

public interface IConvexRegion
{
    /// <summary>
    /// Calculates the furthest point on the region 
    /// along a given direction.
    /// </summary>
    Vector3 GetFurthestPoint(Vector3 direction);
}

Simplex class:

/// <summary>
/// Represents a generalized Tetrehedron
/// </summary>
class Simplex
{
    List<Vector3> _vertices =
        new List<Vector3>();

    public int Count
    {
        get { return _vertices.Count; }
    }

    public Vector3 this[int i]
    {
        get { return _vertices[i]; }
    }

    public Simplex(params Vector3[] vertices)
    {
        for (int i = 0; i < vertices.Length; i++)
        {
            _vertices.Add(vertices[i]);
        }
    }
      
    public void Add(Vector3 vertex)
    {
        _vertices.Add(vertex);
    }

    public void Remove(Vector3 vertex)
    {
        _vertices.Remove(vertex);
    }
}

GJKAlgorithm static class:

public static class GJKAlgorithm
{
    public static bool Intersects(IConvexRegion regioneOne, IConvexRegion regionTwo)
    {
        //Get an initial point on the Minkowski difference.
        Vector3 s = Support(regioneOne, regionTwo, Vector3.One);
        
        //Create our initial simplex.
        Simplex simplex = new Simplex(s);

        //Choose an initial direction toward the origin.
        Vector3 d = -s;

        //Choose a maximim number of iterations to avoid an 
        //infinite loop during a non-convergent search.
        int maxIterations = 50;

        for (int i = 0; i < maxIterations; i++)
        {
            //Get our next simplex point toward the origin.
            Vector3 a = Support(regioneOne, regionTwo, d);

            //If we move toward the origin and didn't pass it 
            //then we never will and there's no intersection.
            if (a.IsInOppositeDirection(d))
            {
                return false;
            }
            //otherwise we add the new
            //point to the simplex and
            //process it.
            simplex.Add(a);
            //Here we either find a collision or we find the closest feature of
            //the simplex to the origin, make that the new simplex and update the direction
            //to move toward the origin from that feature.
            if (ProcessSimplex(ref simplex, ref d))
            {
                return true;
            }
        }
        //If we still couldn't find a simplex 
        //that contains the origin then we
        //"probably" have an intersection.
        return true;
    }

    /// <summary>
    ///Either finds a collision or the closest feature of the simplex to the origin, 
    ///and updates the simplex and direction.
    /// </summary>
    static bool ProcessSimplex(ref Simplex simplex, ref Vector3 direction)
    {
        if (simplex.Count == 2)
        {
            return ProcessLine(ref simplex, ref direction);
        }
        else if (simplex.Count == 3)
        {
            return ProcessTriangle(ref simplex, ref direction);
        }
        else
        {
            return ProcessTetrehedron(ref simplex, ref direction);
        }
    }

    /// <summary>
    /// Determines which Veronoi region of a line segment 
    /// the origin is in, utilizing the preserved winding
    /// of the simplex to eliminate certain regions.
    /// </summary>
    static bool ProcessLine(ref Simplex simplex, ref Vector3 direction)
    {
        Vector3 a = simplex[1];
        Vector3 b = simplex[0];
        Vector3 ab = b - a;
        Vector3 aO = -a;

        if (ab.IsInSameDirection(aO))
        {
            float dot = Vector3.Dot(ab, aO);
            float angle = (float)Math.Acos(dot / (ab.Length() * aO.Length()));
            direction = Vector3.Cross(Vector3.Cross(ab, aO), ab);
        }
        else
        {
            simplex.Remove(b);
            direction = aO;
        }
        return false;
    }

    /// <summary>
    /// Determines which Veronoi region of a triangle 
    /// the origin is in, utilizing the preserved winding
    /// of the simplex to eliminate certain regions.
    /// </summary>
    static bool ProcessTriangle(ref Simplex simplex, ref Vector3 direction)
    {
        Vector3 a = simplex[2];
        Vector3 b = simplex[1];
        Vector3 c = simplex[0];
        Vector3 ab = b - a;
        Vector3 ac = c - a;
        Vector3 abc = Vector3.Cross(ab, ac);
        Vector3 aO = -a;
        Vector3 acNormal = Vector3.Cross(abc, ac);
        Vector3 abNormal = Vector3.Cross(ab, abc);

        if (acNormal.IsInSameDirection(aO))
        {
            if (ac.IsInSameDirection(aO))
            {
                simplex.Remove(b);
                direction = Vector3.Cross(Vector3.Cross(ac, aO), ac);
            }
            else
            {
                if (ab.IsInSameDirection(aO))
                {
                    simplex.Remove(c);
                    direction = Vector3.Cross(Vector3.Cross(ab, aO), ab);
                }
                else
                {
                    simplex.Remove(b);
                    simplex.Remove(c);
                    direction = aO;
                }
            }
        }
        else
        {
            if (abNormal.IsInSameDirection(aO))
            {
                if (ab.IsInSameDirection(aO))
                {
                    simplex.Remove(c);
                    direction = Vector3.Cross(Vector3.Cross(ab, aO), ab);
                }
                else
                {
                    simplex.Remove(b);
                    simplex.Remove(c);
                    direction = aO;
                }
            }
            else
            {
                if (abc.IsInSameDirection(aO))
                {
                    direction = Vector3.Cross(Vector3.Cross(abc, aO), abc);
                }
                else
                {
                    direction = Vector3.Cross(Vector3.Cross(-abc, aO), -abc);
                }
            }
        }
        return false;
    }

    /// <summary>
    /// Determines which Veronoi region of a tetrahedron
    /// the origin is in, utilizing the preserved winding
    /// of the simplex to eliminate certain regions.
    /// </summary>
    static bool ProcessTetrehedron(ref Simplex simplex, ref Vector3 direction)
    {
        Vector3 a = simplex[3];
        Vector3 b = simplex[2];
        Vector3 c = simplex[1];
        Vector3 d = simplex[0];
        Vector3 ac = c - a;
        Vector3 ad = d - a;
        Vector3 ab = b - a;
        Vector3 bc = c - b;
        Vector3 bd = d - b;
            
        Vector3 acd = Vector3.Cross(ad, ac);
        Vector3 abd = Vector3.Cross(ab, ad);
        Vector3 abc = Vector3.Cross(ac, ab);
            
        Vector3 aO = -a;

        if (abc.IsInSameDirection(aO))
        {
            if (Vector3.Cross(abc, ac).IsInSameDirection(aO))
            {
                simplex.Remove(b);
                simplex.Remove(d);
                direction = Vector3.Cross(Vector3.Cross(ac, aO), ac);
            }
            else if (Vector3.Cross(ab, abc).IsInSameDirection(aO))
            {
                simplex.Remove(c);
                simplex.Remove(d);
                direction = Vector3.Cross(Vector3.Cross(ab, aO), ab);
            }
            else
            {
                simplex.Remove(d);
                direction = abc;
            }
        }
        else if (acd.IsInSameDirection(aO))
        {
            if (Vector3.Cross(acd, ad).IsInSameDirection(aO))
            {
                simplex.Remove(b);
                simplex.Remove(c);
                direction = Vector3.Cross(Vector3.Cross(ad, aO), ad);
            }
            else if (Vector3.Cross(ac, acd).IsInSameDirection(aO))
            {
                simplex.Remove(b);
                simplex.Remove(d);
                direction = Vector3.Cross(Vector3.Cross(ac, aO), ac);
            }
            else
            {
                simplex.Remove(b);
                direction = acd;
            }
        }
        else if (abd.IsInSameDirection(aO))
        {
            if (Vector3.Cross(abd, ab).IsInSameDirection(aO))
            {
                simplex.Remove(c);
                simplex.Remove(d);
                direction = Vector3.Cross(Vector3.Cross(ab, aO), ab);
            }
            else if (Vector3.Cross(ad, abd).IsInSameDirection(aO))
            {
                simplex.Remove(b);
                simplex.Remove(c);
                direction = Vector3.Cross(Vector3.Cross(ad, aO), ad);
            }
            else
            {
                simplex.Remove(c);
                direction = abd;
            }
        }
        else
        {
            return true;
        }

        return false;
    }

    /// <summary>
    /// Calculates the furthest point on the Minkowski 
    /// difference along a given direction.
    /// </summary>
    static Vector3 Support(
        IConvexRegion regionOne, 
        IConvexRegion regionTwo,
        Vector3 direction)
    {
        return regionOne.GetFurthestPoint(direction) -
            regionTwo.GetFurthestPoint(-direction);
    }
}

Sphere class:

public class Sphere : IConvexRegion
{
    public Vector3 Center;
    public float Radius;

    public Sphere(Vector3 center, float radius)
    {
        Center = center;
        Radius = radius;
    }

    public Vector3 GetFurthestPoint(Vector3 direction)
    {
        if (direction != Vector3.Zero)
        {
            direction.Normalize();
        }
        return Center + Radius * direction;
    }
}

Box class:

public class Box : IConvexRegion
{
    public Vector3 Center;
    Vector3 _halfDimensions = Vector3.One;
    Quaternion _orientation = Quaternion.Identity;

    public Vector3 Dimensions
    {
        get { return 2f * _halfDimensions; }
    }

    public Box(Vector3 center)
        : this(center, 1f, 1f, 1f) { }

    public Box(Vector3 center,
        float width,
        float height,
        float depth)
        : this(center, width, height, depth, Matrix.Identity) { }

    public Box(Vector3 center,
        float width,
        float height,
        float depth,
        Matrix rotationMatrix)
    {
        Center = center;
        _halfDimensions = new Vector3(
            width / 2f,
            height / 2f,
            depth / 2f);
        _orientation = Quaternion.CreateFromRotationMatrix(rotationMatrix);
    }

    public Vector3 GetFurthestPoint(Vector3 direction)
    {
        Vector3 halfHeight = _halfDimensions.Y * Vector3.Up;
        Vector3 halfWidth = _halfDimensions.X * Vector3.Right;
        Vector3 halfDepth = _halfDimensions.Z * Vector3.Backward;

        Vector3[] vertices = new Vector3[8];
        vertices[0] = halfWidth + halfHeight + halfDepth;
        vertices[1] = -halfWidth + halfHeight + halfDepth;
        vertices[2] = halfWidth - halfHeight + halfDepth;
        vertices[3] = halfWidth + halfHeight - halfDepth;
        vertices[4] = -halfWidth - halfHeight + halfDepth;
        vertices[5] = halfWidth - halfHeight - halfDepth;
        vertices[6] = -halfWidth + halfHeight - halfDepth;
        vertices[7] = -halfWidth - halfHeight - halfDepth;

        Matrix rotationTransform = Matrix.CreateFromQuaternion(_orientation);
        Matrix translation = Matrix.CreateTranslation(Center);
        Matrix world = rotationTransform *
            translation;

        Vector3 furthestPoint = Vector3.Transform(vertices[0], world);
        float maxDot = Vector3.Dot(furthestPoint, direction);
        for (int i = 1; i < 8; i++)
        {
            Vector3 vertex = Vector3.Transform(vertices[i], world);
            float dot = Vector3.Dot(vertex, direction);
            if (dot > maxDot)
            {
                maxDot = dot;
                furthestPoint = vertex;
            }               
        }
        return furthestPoint;
    }

    public Matrix CalculateWorld()
    {
        return Matrix.CreateScale(Dimensions) *
            Matrix.CreateFromQuaternion(_orientation) *
            Matrix.CreateTranslation(Center);
    }
}

I hope this is helpful to someone :) Enjoy!

Game State Management

2012-01-08T13:06:00.000-08:00

In this article we'll be building a game state management system similar to the one here on the Microsoft App Hub. It's a nice little framework if you've never checked it out before.
We'll be going through how to build something like this as well as extending the idea to support controls, eg. buttons, check-boxes, etc.
The basic idea is that we have a collection of GameScreens that update, handle input, and draw themselves. A ScreenManager class holds this collection and treats it as sort of a stack in the update process (although it's held in memory as a list). The top-most screen on the stack accepts input and forces screens below it to hide. We'll also have a collection of ScreenControls contained in each Screen. These will also update, handle input and draw but will have no effect on each other and will generally contain some events like Clicked or what have you. How these events are handled will be up to the GameScreen but the conditions under which each event fires will be decided by the ScreenControl.
For starters, go ahead and create a new XNA Windows Game project. I named mine GameStateTutorial.
We're going to need four classes to start go ahead and right click on the game project in your solution explorer and select Add -> Class... then add a class named ScreenManager. Do the same thing to create a GameScreen class, an InputState class and a ScreenControl class.
Let's work on the InputState class first.
This class will watch for player input and will be passed to screens when they handle input.

class InputState
{
    //We're going to handle the XBox case for input too so we'll
    //need to specify the max number of players.
    const int _maxInputs = 4;

    //We'll hold the input state for each player in arrays.
    public readonly KeyboardState[] CurrentKeyStates;
    public readonly KeyboardState[] PreviousKeyStates;
    public readonly GamePadState[] CurrentGamePadStates;
    public readonly GamePadState[] PreviousGamePadStates;

    //And we want to keep track of whether or not a game pad
    //was ever connected so we'll use another array for that.
    public readonly bool[] GamePadWasConnected;

    //There's only one possible mouse input since there's
    //no mouse for the Xbox.
    MouseState _currentMouseState;
    MouseState _previousMouseState;

    public MouseState CurrentMouseState
    {
        get { return _currentMouseState; }
    }

    public MouseState PreviousMouseState
    {
        get { return _previousMouseState; }
    }

    public InputState()
    {
        CurrentKeyStates = new KeyboardState[_maxInputs];
        PreviousKeyStates = new KeyboardState[_maxInputs];
        CurrentGamePadStates = new GamePadState[_maxInputs];
        PreviousGamePadStates = new GamePadState[_maxInputs];
        CurrentGamePadStates = new GamePadState[_maxInputs];
        GamePadWasConnected= new bool[_maxInputs];
    }

    public void Update()
    {
        //We update the state of each player.
        for (int i = 0; i < _maxInputs; i++)
        {
            PreviousKeyStates[i] = CurrentKeyStates[i];
            CurrentKeyStates[i] = Keyboard.GetState((PlayerIndex)i);
            PreviousGamePadStates[i] = CurrentGamePadStates[i];
            CurrentGamePadStates[i] = GamePad.GetState((PlayerIndex)i);
            
            //if a game pad was ever connected we set that to true.
            if (CurrentGamePadStates[i].IsConnected)
            {
                GamePadWasConnected[i] = true;
            }
        }

        _previousMouseState = _currentMouseState;
        _currentMouseState = Mouse.GetState();
    }

    //This method checks to see if a key has just been pressed this frame.
    //We have a PlayerIndex as a nullable parameter; if it is null we'll check
    //for input from every player, otherwise just from the specified player.  
    //The out parameter, playerIndex, returns which player pressed the key.
    public bool IsNewKeyPressed(
        Keys key,
        PlayerIndex? controllingPlayer,
        out playerIndex)
    {
        if (controllingPlayer != null)
        {
            playerIndex = controllingPlayer.Value;
            int i = (int)playerIndex;
            
            return (CurrentKeyState[i].IsKeyDown(key) &&
                PreviousKeyState[i].IsKeyUp(key));
        }
        else
        {
            return (IsNewKeyPressed(key, PlayerIndex.One, out playerIndex) ||
                IsNewKeyPressed(key, PlayerIndex.Two, out playerIndex) ||
                IsNewKeyPressed(key, PlayerIndex.Three, out playerIndex) ||
                IsNewKeyPressed(key, PlayerIndex.Four, out playerIndex));
        }
    }

    //We do basically the same thing for game pad buttons.
    public bool IsNewButtonPressed(
        Buttons button,
        PlayerIndex? controllingPlayer,
        out playerIndex)
    {
        if (controllingPlayer != null)
        {
            playerIndex = controllingPlayer.Value;
            int i = (int)playerIndex;
            
            return (CurrentGamePadState[i].IsButtonDown(button) &&
                PreviousGamePadState[i].IsButtonUp(button));
        }
        else
        {
            return (IsNewButtonPressed(key, PlayerIndex.One, out playerIndex) ||
                IsNewButtonPressed(key, PlayerIndex.Two, out playerIndex) ||
                IsNewButtonPressed(key, PlayerIndex.Three, out playerIndex) ||
                IsNewButtonPressed(key, PlayerIndex.Four, out playerIndex));
        }
    }

    //And a simple method to check for a left mouse click.
    public bool WasMouseLeftClicked()
    {
        return (_currentMouseState.LeftButton == ButtonState.Pressed &&
            _previousMouseState.LeftButton == ButtonState.Released);
    }
}

That's all we need for now.
Let's work on the ScreenControl class. These will be used for our buttons and labels and such.

abstract class ScreenControl
{
    Vector2 _position;
    GameScreen _screen;
    
    public Vector2 Position
    {
        get { return _position; }
        set { _position = value; }
    }

    public GameScreen Screen
    {
        get { return _screen; }
    }

    public abstract int Width { get; set; }
    public abstract int Height { get; set; }

    public ScreenControl(GameScreen screen)
    {
        _screen = screen;
    }

    public virtual void LoadContent(ContentManager content) { }
    
    //The screens transition on and off and the positionTransform parameter will help us have
    //our controls slide in and out of view as the screen transitions.
    public virtual void HandleInput(InputState input, Matrix positionTransform) { }

    public virtual void Update(GameTime gameTime, Matrix positionTransform) { }

    //The alpha parameter has a similar purpose to the positionTransform.
    public virtual void Draw(GameTime gameTime, Matrix positionTransform, float alpha) { }
    
    public virtual Rectangle CalculateControlRectangle(Matrix positionTransform)
    {
        Vector2 transformedPosition = Vector2.Transform(_position, positionTransform);
        return new Rectangle(
            (int)transformedPosition.X,
            (int)transformedPosition.Y,
            Width,
            Height);
    }
}

Next up is the GameScreen class. We need it to be able to transition on and off smoothly so it will contain an enum that represents its transition state as well as how far transitioned it is, the total time it takes to transition on or off, whether or not it's a pop-up screen, and several other fields and helper methods.

//The transition state of the screen.
public enum ScreenState
{
    TransitionOn,
    TransitionOff,
    Active,
    Hidden,
}
abstract class GameScreen
{
    PlayerIndex? _controllingPlayer;
    ScreenManager _screenManager;
    bool _isExiting = false;
    bool _isPopup = false;
    ScreenState _state = ScreenState.TransitionOn;
    TimeSpan _transitionOnTime = TimeSpan.Zero;
    TimeSpan _transitionOffTime = TimeSpan.Zero;
    
    //_transitionPosition at 1f means full transition while 0f means no transition.
    float _transitionPosition = 1f;

    bool _otherScreenHasFocus;
    List<ScreenControl> _controls = new List<ScreenControl>();

    public PlayerIndex? ControllingPlayer
    {
        get { return _controllingPlayer; }
        internal set { _controllingPlayer = value; }
    }

    public ScreenManager ScreenManager
    {
        get { return _screenManager; }
        internal set { _screenManager = value; }
    }

    public bool IsPopup
    {
        get { return _isPopup; }
        protected set { _isPopup = value; }
    }

    public bool IsActive
    {
        get
        {
            return !_otherScreenHasFocus &&
                (_state == ScreenState.TransitionOn ||
                _state == ScreenState.Active);
        }
    }

    public ScreenState ScreenState 
    {
        get { return _state; }
        protected set { _state = value; }
    }

    public float TransitionAlpha 
    {
        get { return 1f - _transitionPosition; }
    }

    public float TransitionPosition 
    {
        get { return _transitionPosition; }
    }

    public bool IsExiting
    {
        get { return _isExiting; }
        protected internal set { _isExiting = value; }
    }

    public TimeSpan TransitionOnTime
    {
        get { return _transitionOnTime; }
        protected set { _transitionOnTime = value; }
    }

    public TimeSpan TransitionOffTime
    {
        get { return _transitionOffTime; }
        protected set { _transitionOffTime = value; }
    }

    public IList<ScreenControl> Controls
    {
        get { return _controls; }
    }

    //Loads the content of each control.  We're getting the
    //content manager from ScreenManager.Game but we can override this.
    public virtual void LoadContent() 
    {
        ContentManager content = ScreenManager.Game.Content;
        foreach (ScreenControl control in _controls)
        {
            control.LoadContent(content);
        }
    }

    public virtual void UnloadContent() { }

    //This helper method determines how to move the controls while
    //we're transitioning in or out and can be overridden for different behavior.
    //A control can also determine its own transition behavior since this Matrix
    //is passed along in the Update, HandleInput and Draw methods and the
    //ScreenControl can use it or not.
    protected virtual Matrix CalculateTransitionOffset()
    {
        float transitionOffset = (float)Math.Pow(TransitionPosition, 2);
        Vector2 positionTranslation;
        if (_state == ScreenState.TransitionOn)
        {
            positionTranslation = new Vector2(-256 * transitionOffset, 0);
        }
        else if (_state == ScreenState.TransitionOff)
        {
            positionTranslation = new Vector2(512 * transitionOffset, 0);
        }
        else
        {
            positionTranslation = Vector2.Zero;
        }
        Matrix transform = Matrix.CreateTranslation(new Vector3(positionTranslation, 0));
        return transform;
    }

    //This helper method increments the _transitionPosition the appropriate
    //amount and then returns true if it's still transitioning
    //or false if it's done.
    bool UpdateTransition(
        GameTime gameTime,
        TimeSpan time,
        int direction)
    {
        float transitionDelta;
        if (time == TimeSpan.Zero)
        {
            transitionDelta = 1;
        }
        else
        {
            transitionDelta =
                (float)(gameTime.ElapsedGameTime.TotalMilliseconds / time.TotalMilliseconds);
        }

        _transitionPosition += transitionDelta * direction;

        if ((direction < 0 && _transitionPosition <= 0) ||
            (direction > 0 && _transitionPosition >= 1))
        {
            _transitionPosition = MathHelper.Clamp(
                _transitionPosition, 0f, 1f);
            return false;
        }

        return true;
    }

    //This updates the transition state as well as the
    //the controls.
    //if a screen is exiting it transitions off and then removes itself
    //from the ScreenManager and if it's covered by another screen
    //then it transitions off to hide.
    //otherwise, it's either active or transitioning on.
    public virtual void Update(
        GameTime gameTime,
        bool otherScreenHasFocus,
        bool coveredByOtherScreen)
    {
        _otherScreenHasFocus = otherScreenHasFocus;
        if (_isExiting)
        {
            _state = ScreenState.TransitionOff;
            if (!UpdateTransition(gameTime, _transitionOffTime, 1))
            {
                ScreenManager.RemoveScreen(this);
            }
        }
        else if (coveredByOtherScreen)
        {
            if (UpdateTransition(gameTime, _transitionOffTime, 1))
            {
                _state = ScreenState.TransitionOff;
            }
            else
            {
                _state = ScreenState.Hidden;
            }
        }
        else
        {
            if (UpdateTransition(gameTime, _transitionOnTime, -1))
            {
                _state = ScreenState.TransitionOn;
            }
            else
            {
                _state = ScreenState.Active;
            }
        }

        foreach (ScreenControl control in _controls)
        {
            Matrix transform = CalculateTransitionOffset();
            control.Update(gameTime, transform);
        }
    }

    public virtual void HandleInput(InputState input)
    {
        foreach (ScreenControl control in _controls)
        {
            Matrix transform = CalculateTransitionOffset();
            control.HandleInput(input, transform);
        }
    }

    public virtual void Draw(GameTime gameTime)
    {
        SpriteBatch spriteBatch = ScreenManager.SpriteBatch;
        Matrix transform = CalculateTransitionOffset();

        spriteBatch.Begin();
        foreach (ScreenControl control in _controls)
        {
            control.Draw(
                gameTime,
                transform,
                TransitionAlpha);
        }
        spriteBatch.End();
    }

    public void ExitScreen()
    {
        if (_transitionOffTime == TimeSpan.Zero)
        {
            ScreenManager.RemoveScreen(this);
        }
        else
        {
            _isExiting = true;
        }
    }
}

Since we'll be using the mouse for this tutorial, let's make a Cursor class and add an image to draw for a mouse cursor.
Here's a cursor image.

And the Cursor class:

class Cursor
{
    Texture2D _texture;
    Vector2 _position;

    public Texture2D Texture
    {
        get { return _texture; }
        set { _texture = value; }
    }

    public void LoadContent(ContentManager content)
    {
        if (_texture == null)
        {
            _texture = content.Load("cursor_texture");
        }
    }

    public void Update(InputState input)
    {
        _position = new Vector2(
            (float)input.CurrentMouseState.X,
            (float)input.CurrentMouseState.Y);

    }

    public void Draw(SpriteBatch spriteBatch)
    {
        spriteBatch.Draw(
            _texture,
            _position,
            Color.White);
    }
}

Now let's move on to the ScreenManager which as the name suggests, will manage a collection of screens. This class will inherit from DrawableGameComponent so it will contain a Game object passed in through the constructor. It will also override some virtual functions for loading content, updating and drawing.
At this point we're also going to need a few more assets to load. Go ahead and right click on the content project and select Add -> New Item... and then in the dialogue that appears select Sprite Font and give it a name. I named mine "menu_font.spritefont". While we're here let's add an image to use as a background. Here's some ugly blue ellipses.

And a button texture for later.

class ScreenManager : DrawableGameComponent
{
    List<GameScreen> _screens = new List<GameScreen>();
    List<GameScreen> _screensToUpdate = new List<GameScreen>();
    InputState _input = new InputState();
    SpriteBatch _spriteBatch;
    SpriteFont _font;
    Texture2D _blankTexture;
    bool _isInitialized = false;
    Cursor _cursor = new Cursor();

    public SpriteBatch SpriteBatch
    {
        get { return _spriteBatch; }
    }

    public SpriteFont Font
    {
        get { return _font; }
    }

    public ScreenManager(Game game)
        : base(game) { }


    public override void Initialize()
    {
        base.Initialize();
        //Now we have a GraphicsDevice initialized in the Game class
        //and we set _isInitialized to true.
        _isInitialized = true;
    }

    protected override void LoadContent()
    {
        ContentManager content = Game.Content;
        _spriteBatch = new SpriteBatch(Game.GraphicsDevice);

        _font = content.Load<SpriteFont>("menu_font");

        //We have a 1 by 1 white texture we can use for
        //different effects like fading to black.            
        _blankTexture = new Texture2D(Game.GraphicsDevice, 1, 1);
        Color[] colorData = { Color.White };
        _blankTexture.SetData<Color>(colorData);

        _cursor.LoadContent(content);
        foreach (GameScreen screen in _screens)
        {
            screen.LoadContent();
        }
    }

    protected override void UnloadContent()
    {
        foreach (GameScreen screen in _screens)
        {
            screen.UnloadContent();
        }
    }

    public override void Update(GameTime gameTime)
    {
        _input.Update();
        
        _cursor.Update(_input);

        //Here we populate a temporary list to update.
        _screensToUpdate.Clear();
        foreach (GameScreen screen in _screens)
        {
            _screensToUpdate.Add(screen);
        }

        //We'll need a couple of booleans to keep track
        //of which screens are covered by other screens
        //or accepting input.
        bool otherScreenHasFocus = !Game.IsActive;
        bool coveredByOtherScreen = false;

        //We iterate through the list backwards, popping a screen off the top,
        //updating it and determining whether or not to accept input
        //or cover screens below it.
        while (_screensToUpdate.Count > 0)
        {
            GameScreen screen = _screensToUpdate[_screensToUpdate.Count - 1];
            _screensToUpdate.RemoveAt(_screensToUpdate.Count - 1);

            screen.Update(gameTime, otherScreenHasFocus, coveredByOtherScreen);

            if (screen.ScreenState == ScreenState.TransitionOn ||
                screen.ScreenState == ScreenState.Active)
            {
                if (!otherScreenHasFocus)
                {
                    screen.HandleInput(_input);
                    otherScreenHasFocus = true;
                }
                if (!screen.IsPopup)
                {
                    coveredByOtherScreen = true;
                }
            }
        }
    }

    public override void Draw(GameTime gameTime)
    {
        foreach (GameScreen screen in _screens)
        {
            if (screen.ScreenState != ScreenState.Hidden)
            {
                screen.Draw(gameTime);
            }
        }
        
        SpriteBatch.Begin();
        _cursor.Draw(SpriteBatch);
        SpriteBatch.End();
    }

    //If the game has initialized we can unload or load content.
    public void RemoveScreen(GameScreen screen)
    {
        if (_isInitialized)
        {
            screen.UnloadContent();
        }
        _screens.Remove(screen);
        _screensToUpdate.Remove(screen);
    }

    //Here we set the screen's ScreenManager, which player is
    //controlling the screen, and load its content if appropriate.
    public void AddScreen(GameScreen screen, PlayerIndex? controllingPlayer)
    {
        screen.ScreenManager = this;
        screen.ControllingPlayer = controllingPlayer;
        screen.IsExiting = false;
        _screens.Add(screen);
        if (_isInitialized)
        {
            screen.LoadContent();
        }
    }

    //We want access to the screens in the collection but
    //not the collection itself.
    public GameScreen[] GetScreens()
    {
        return _screens.ToArray();
    }

    //A helper method for fading to black.
    public void FadeBackBufferToBlack(float alpha)
    {
        Viewport viewport = GraphicsDevice.Viewport;
        _spriteBatch.Begin();
        _spriteBatch.Draw(
            _blankTexture,
            new Rectangle(
                0, 0,
                viewport.Width, viewport.Height),
            Color.Black * alpha);
        _spriteBatch.End();
    }
}

Now we have a basic framework that we can build off of. Let's start by making a couple new classes, a ScreenControl for displaying a texture which we can use in a BackgroundScreen.

class TextureDisplay : ScreenControl
{
    int _width;
    int _height;
    Texture2D _texture;

    public Texture2D Texture
    {
        get { return _texture; }
        set { _texture = value; }
    }

    public override int Width
    {
        get { return _width; }
        set { _width = value; }
    }

    public override int Height
    {
        get { return _height; }
        set { _height = value; }
    }

    public TextureDisplay(GameScreen screen)
        : base(screen)
    {
    }

    public override void LoadContent(ContentManager content)
    {
        if (_texture == null)
        {
            _texture = content.Load("blue_ellipses");
        }
        Viewport viewport = Screen.ScreenManager.GraphicsDevice.Viewport;
        if (_width <= 0)
        {
            _width = viewport.Width;
        }
        if (_height <= 0)
        {
            _height = viewport.Height;
        }
    }

    public override void Draw(GameTime gameTime, Matrix positionTransform, float alpha)
    {
        SpriteBatch spriteBatch = Screen.ScreenManager.SpriteBatch;
        spriteBatch.Draw(
            _texture,
            CalculateControlRectangle(positionTransform),
            Color.White * alpha);
    }
}

Now we'll make our BackgroundScreen which will contain a single TextureDisplay control. This screen won't slide in or out so we'll override the CalculateTransitionOffset to return the identity matrix.

class BackgroundScreen : GameScreen
{
    public BackgroundScreen()
    {
        TransitionOnTime = TimeSpan.FromSeconds(.5d);
        TransitionOffTime = TimeSpan.FromSeconds(.5d);
        TextureDisplay background = new TextureDisplay(this);
        Controls.Add(background);
    }

    public override void Update(
        GameTime gameTime,
        bool otherScreenHasFocus,
        bool coveredByOtherScreen)
    {
        //The background screen never hides so it's never covered.
        base.Update(gameTime, otherScreenHasFocus, false);
    }

    protected override Matrix CalculateTransitionOffset()
    {
        return Matrix.Identity;
    }
}

We can test this out now. Here's my Game1 class:

public class Game1 : Microsoft.Xna.Framework.Game
{
    GraphicsDeviceManager graphics;
    ScreenManager screenManager;

    public Game1()
    {
        graphics = new GraphicsDeviceManager(this);
        Content.RootDirectory = "Content";

        screenManager = new ScreenManager(this);
        screenManager.AddScreen(new BackgroundScreen(), null);

        Components.Add(screenManager);
    }

    protected override void Initialize()
    {        
        base.Initialize();
    }

      
    protected override void Update(GameTime gameTime)
    {           
        base.Update(gameTime);
    }

      
    protected override void Draw(GameTime gameTime)
    {
        GraphicsDevice.Clear(Color.Black);           
        base.Draw(gameTime);
    }
}

Which looks like this when we run it:

Before we can handle events, we need to make an EventArgs class that holds a PlayerIndex so we know which player trigger the event.

class PlayerIndexEventArgs : EventArgs
{
    PlayerIndex _playerIndex;

    public PlayerIndex PlayerIndex
    {
    get { return _playerIndex; }
    }

    public PlayerIndexEventArgs(PlayerIndex playerIndex)
    {
        _playerIndex = playerIndex;
    }
}

Let's continue by making two more ScreenControl classes: a ScreenLabel class and a GameButton class.

class ScreenLabel : ScreenControl
{
    string _text;

    public string Text
    {
        get { return _text; }
        set { _text = value; }
    }

    public override int Width
    {
        get
        {
            return (int)Screen.ScreenManager.Font.MeasureString(_text).X;
        }
        set { }
    }

    public override int Height
    {
        get
        {
            return Screen.ScreenManager.Font.LineSpacing;
        }
        set { }
    }

    public ScreenLabel(GameScreen screen, string text)
        : base(screen)
    {
        _text = text;
    }

    //Instead of using the default positionTransform we'll make the
    //labels move up and down during transition.
    Matrix CalculateLabelTransform()
    {
        float transitionOffset = (float)Math.Pow(Screen.TransitionPosition, 2);
        Vector2 translation = new Vector2(0f, -transitionOffset * 100);
        Matrix labelTransform = Matrix.CreateTranslation(new Vector3(translation, 0f));
        return labelTransform;
    }

    public override void Draw(GameTime gameTime, Matrix positionTransform, float alpha)
    {
        SpriteBatch spriteBatch = Screen.ScreenManager.SpriteBatch;
        SpriteFont font = Screen.ScreenManager.Font;

        Matrix labelTransform = CalculateLabelTransform();

        Vector2 drawPosition = Vector2.Transform(Position, labelTransform);
        Vector2 labelOrigin = font.MeasureString(_text) / 2;
        Color labelColor = new Color(192, 192, 192) * alpha;
        float labelScale = 1.25f;
            
        spriteBatch.DrawString(
            font,
            _text,
            drawPosition,
            labelColor,
            0f,
            labelOrigin,
            labelScale,
            SpriteEffects.None,
            0f);
    }
}

And now the GameButton class. This will contain a Clicked event which will be fired whenever the user LeftClicks within the control's bounds.

class GameButton : ScreenControl
{
    int _width = 150;
    int _height = 50;
    Texture2D _buttonTexture;
    string _text;
        
    public event EventHandler<PlayerIndexEventArgs> Clicked;

    public Texture2D ButtonTexture
    {
        get { return _buttonTexture; }
        set { _buttonTexture = value; }
    }

    public string Text
    {
        get { return _text; }
        set { _text = value; }
    }

    public override int Width
    {
        get { return _width; }
        set { _width = value; }
    }

    public override int Height
    {
        get { return _height; }
        set { _height = value; }
    }

    public GameButton(GameScreen screen, string text)
        : base(screen)
    {
        _text = text;
    }

    public override void LoadContent(ContentManager content)
    {
        if (_buttonTexture == null)
        {
            _buttonTexture = content.Load<Texture2D>("button_texture");
        }
    }

    public override void HandleInput(InputState input, Matrix positionTransform)
    {
        Point mousePosition = new Point(
            input.CurrentMouseState.X,
            input.CurrentMouseState.Y);
        Rectangle buttonRectangle = CalculateControlRectangle(positionTransform);
        
        if (input.IsMouseLeftClicked() &&
            buttonRectangle.Contains(mousePosition))
        {
            OnClick(PlayerIndex.One);
        }
    }

    public override void Draw(GameTime gameTime, Matrix positionTransform, float alpha)
    {
        SpriteBatch spriteBatch = Screen.ScreenManager.SpriteBatch;
        SpriteFont font = Screen.ScreenManager.Font;
            
        //We need to position the button text in the center
        //of the button.
        Rectangle buttonRectangle = CalculateControlRectangle(positionTransform);
        Vector2 buttonPosition = Vector2.Transform(Position, positionTransform);
        Vector2 textDimensions = font.MeasureString(_text);
        Vector2 buttonDimensions = new Vector2(
            (int)buttonRectangle.Width, 
            (int)buttonRectangle.Height);
        Vector2 textPosition = buttonPosition + buttonDimensions / 2f - textDimensions / 2f;


        spriteBatch.Draw(
            _buttonTexture,
            buttonRectangle,
            Color.White * alpha);

        spriteBatch.DrawString(
            font,
            _text,
            textPosition,
            Color.White * alpha);
    }

    protected void OnClick(PlayerIndex playerIndex)
    {
        if (Clicked != null)
        {
            Clicked(this, new PlayerIndexEventArgs(playerIndex));
        }
    }
}

Now we can use both of these new ScreenControls in making our MenuScreen and MainMenuScreen classes.

abstract class MenuScreen : GameScreen
{
    ScreenLabel _menuTitle;

    public MenuScreen(string title)
    {
        TransitionOnTime = TimeSpan.FromSeconds(.5);
        TransitionOffTime = TimeSpan.FromSeconds(.5);

        _menuTitle = new ScreenLabel(
            this,
            title);
        Controls.Add(_menuTitle);
    }

    public override void LoadContent()
    {
        base.LoadContent();
        Viewport viewport = ScreenManager.GraphicsDevice.Viewport;
        _menuTitle.Position = new Vector2(viewport.Width / 2, 80f);
    }

    protected virtual void OnCancel(PlayerIndex playerIndex)
    {
        ExitScreen();
    }

    //This let's us hook the OnCancel method to control events.
    protected void OnCancel(object sender, PlayerIndexEventArgs e)
    {
        OnCancel(e.PlayerIndex);
    }
}

And finally our MainMenuScreen:

class MainMenuScreen : MenuScreen
{
    GameButton _exit;

    public MainMenuScreen()
        : base("Main Menu")
    {
        _exit = new GameButton(this, "Exit");
        _exit.Clicked += OnCancel;
        Controls.Add(_exit);
    }

    public override void LoadContent()
    {
        base.LoadContent();
        Viewport viewport = ScreenManager.GraphicsDevice.Viewport;
        _exit.Position = new Vector2(
            (int)viewport.Width / 2 - _exit.Width / 2,
            160f);
    }

    protected override void OnCancel(PlayerIndex playerIndex)
    {
        ScreenManager.Game.Exit();
    }
}

Now we can test it out! Change your Game1 class to look this this:

public class Game1 : Microsoft.Xna.Framework.Game
{
    GraphicsDeviceManager graphics;
    ScreenManager screenManager;

    public Game1()
    {
        graphics = new GraphicsDeviceManager(this);
        Content.RootDirectory = "Content";
        screenManager = new ScreenManager(this);
        screenManager.AddScreen(new BackgroundScreen(), null);
        screenManager.AddScreen(new MainMenuScreen(), null);

        Components.Add(screenManager);
    }

    protected override void Initialize()
    {        
        base.Initialize();
    }

      
    protected override void Update(GameTime gameTime)
    {           
        base.Update(gameTime);
    }

      
    protected override void Draw(GameTime gameTime)
    {
        GraphicsDevice.Clear(Color.Black);           
        base.Draw(gameTime);
    }
}

And running this should produce a Main menu that transitions in.

I'm going to leave it at that for this article but will probably pick it up again in a future one.
Thanks for reading!

The Iterator Pattern

2011-12-23T07:11:00.000-08:00

It doesn't take long in one's c# education before one discovers the 'foreach' loop. What they may not know is that this is actually the Iterator pattern built into the language through the IEnumerator and IEnumerable interfaces.
In this article I'll go over the pattern and show you how to build an iterator from scratch. While you may never implement this exact pattern in any of your projects it's good to know how it's done and will hopefully help you understand how to extend the built-in iteration system within the c# language.
Ignoring our 'foreach' capabilities for the moment let's see what the problem is.

//Here's a simple class that can be kept in
//some sort of collection.  We don't know what kind of
//collection but we'd like to go through each Item and 
//print out the description.
class Item
{
    string _description;

    public string Description
    {
        get { return _description; }
    }

    public Item(string description)
    {
        _description = description;
    }
}

class Program
{
    static void Main(string[] args)
    {
        List<Item> itemList = new List<Item>();
        
        int maxArraySize = 3;
        Item[] itemArray = new Item[3];
        
        //populate the collections.
        for (int i = 0; i < maxArraySize; i++)
        {
            Item ithItem = new Item("Item" + i.ToString());

            itemArray[i] = ithItem;
            itemList.Add(ithItem);
        }
        
        //Iterate over the List...
        for (int i = 0; i < itemList.Count; i++)
        {
            Console.WriteLine(itemList[i].Description);
        }
        
        //Iterate over the Array...
        for (int = 0; i < itemArray.Length; i++)
        {
            Console.WriteLine(itemArray[i].Description);
        }
    }
}

Again, temporarily forgetting about the 'foreach' loop (we'll get to it), this is a mess with no obvious solution. For every type of collection we have we'd need to loop over it in a different way. The List has a Length property while arrays have a Count property and there's no telling how some other collection may be looped through.
Let's make a simple Store interface to help illustrate. Some stores may want use Arrays, and some may want to use Lists or any other type of collection at all, but they all need to be able to print out the description of their inventory. A Store can be thought of here as an Item collection.

interface IStore
{
    void PrintInventory();
}

public class ListStore : IStore
{
    List<Item> _inventory;

    public ListStore()
    {
        _inventory.Add(new Item("Soap"));
        _inventory.Add(new Item("Fan"));
        _inventory.Add(new Item("Fish Tank"));
    }

    public void PrintInventory()
    {
        //Here's the problem...
        for (int i = 0; i = _inventory.Count; i++)
        {
            Console.WriteLine(_inventory[i].Description);
        }
    }
}

public class ArrayStore : IStore
{
    const int maxSize = 3;
    Item[] _inventory;

    public ListStore()
    {
        _inventory = new Item[maxSize];

        _inventory[0] = new Item("Shoes");
        _inventory[1] = new Item("Duct Tape");
        _inventory[2] = new Item("Venti Cappuccino");
    }

    public void PrintInventory()
    {
        //Here's the problem...
        //Duplicating code at all or with slight differences
        //should make your refactoring senses tingle!
        for (int i = 0; i = itemList.Count; i++)
        {
            Console.WriteLine(itemList[i].Description);
        }

    }
}

What's changing here is the particulars of the iteration. We'd like to encapsulate iteration and the Iterator pattern does just that by introducing an Iterator interface that will allow us to control how we loop through any collection in any way we want.
It's not too tricky so let's take a look.

interface IIterator
{
    //This will tell us if there is a
    //next element in a collection...
    bool HasNext();

    //And this will return the next element.
    object Next();
}

//Let's see how these iterators are implemented.
//first for a List...
class ListIterator : IIterator
{
    List<Item> _items;

    //_position keeps track of where we
    //are in the iteration of the list.
    int _position = 0;

    public ListIterator(List<Item> items)
    {
        _items = items;
    }

    public object Next()
    {
        Item item = _items[_position];
        _position++;
        return item;
    }

    public bool HasNext()
    {
        if (_position >= items.Count)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
}

//And now for the array...
class ArrayIterator : IIterator
{
    Item[] _items;
    int _position = 0;

    public ListIterator(Item[] items)
    {
        _items = items;
    }

    public object Next()
    {
        Item item = _items[_position];

        //Increment our position...
        _position++;
        return item;
    }

    public bool HasNext()
    {
        if (_position >= items.Length)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
}

Now we need to make some small changes to the Store interface...

interface IStore
{
    //All we need is a method to retrieve
    //the appropriate iterator.
    IIterator GetIterator();
}

public class ListStore : IStore
{
    List<Item> _inventory;

    public ListStore()
    {
        _inventory.Add(new Item("Soap"));
        _inventory.Add(new Item("Fan"));
        _inventory.Add(new Item("Fish Tank"));
    }

    public void GetIterator()
    {
        //this iterator is passed a list item
        //to loop through.
        return new ListIterator(_list);
    }
}

public class ArrayStore : IStore
{
    const int maxSize = 3;
    Item[] _inventory;

    public ListStore()
    {
        _inventory = new Item[maxSize];

        _inventory[0] = new Item("Shoes");
        _inventory[1] = new Item("Duct Tape");
        _inventory[2] = new Item("Venti Cappuccino");
    }

    public void GetIterator()
    {
        return new ArrayIterator(_inventory);
    }
}

Now we can loop through each element in a collection regardless of the type, as long as the class associated with the collection returns the correct Iterator type.
Let's see this in action.

class Program
{
    static void Main(string[] args)
    {
        IStore listStore = new ListStore();
        IStore arrayStore = new ArrayStore();
        
        IIterator listStoreIterator = listStore.GetIterator();
        IIterator arrayStoreIterator = arrayStore.GetIterator();
        
        //Now it doesn't matter what type of
        //collection our stores use in their implementation
        //as long as they know their iterator!   
        PrintInventory(listStoreIterator);
        PrintInventory(arrayStoreIterator);
    }

    //we could have also kept this in the store class and
    //done the iteration internally.
    void PrintInventory(IIterator iterator)
    {
        while (iterator.HasNext())
        {
            Item storeItem = (Item)iterator.Next();
            Console.WriteLine(storeItem.Description);
        }
    }
}

This is, as I may have mentioned before, a very simplified example with a simple version of the pattern and is not the only way to implement this or any pattern. Just for one example we could have used generics in the iterator's Next() method to return an exact type instead of an object type.
We could iterate through a collection in any way as well: backwards, skipping every other one or anything, really.
This is basically what c# uses when you use a foreach loop, except they use an IEnumerator interface instead of our Iterator and the IEnumerable interface for returning the appropriate iterator or enumerator, ie. the GetIterator() method in our IStore interface. The actual 'foreach' keyword is syntactic sugar for making the code easier to read or write but is basically using something like our while loop.
In actual c# programming you'll never actually need to make an iterator from scratch since there's such a nice one built in with such simple syntax, but I thought it might be illuminating to see how it's actually done.
Because this is an article about design patterns and not about all the neat features of c# I won't go into how to extend IEnumerable or IEnumerator here but here are some links for doing just that.

Further reading:

MSDN.com
codebetter.com
this article shows us how to code the same behavior without using a seperate iterator interface, the iteration is done in the collection class using the yield keyword.

The Composite Pattern

2011-12-13T10:59:00.001-08:00

The Composite pattern defines a tree structure. A tree structure is a hierarchical composition of nodes, kind of a nested collection; a node can be composed of other nodes or not. Nodes that contain other nodes are called parent-nodes while the nodes they contain are not surprisingly called child-nodes. Some nodes are not or cannot be a parent to other nodes. These are called leaf-nodes. One benefit of the Composite pattern is that we can treat the entire tree, a branch (or sub-tree), or a single node equally since they're all the same data type, ie. nodes.
Graphically, the structure resembles a tree hence the name.

An obvious example would the be folders or directories on your hard drive, which can contain other folders, which can contain others and so on. Files would be our leaf-nodes since they cannot contain further folders. While searching for a file, your computer visits each folder and each file within each folder in a certain order until the desired file is found. The process of visiting each node is called tree traversal.
There are many uses for tree structures ranging from collision detection to list sorting algorithms.
In this article we will use the Composite pattern to set up a tree structure and learn how to traverse it in different ways.
Let's take a quick look at the class diagram.

As you can see, the Node which defines the interface that our client class will be working with contains methods for adding, removing and retrieving nodes. A leaf-node cannot contain other nodes but must still inherit from the Node interface so these methods are superfluous, moreover, there may be methods or properties that apply only to a leaf node and not a component node. While this does break the "one class, one responsibility" paradigm, we get the benefit of being able to treat every part of the tree the same: as a Node. This can make for somewhat dangerous code if the client tries accessing something that does not apply to the object but there are ways to handle it and the ability to treat each part of the tree uniformly can be worth the added overhead.
For our example we'll build a mock folder tree with "folders" and "files". The folders will have a name and be able to contain either other folders or files. The files will have a name and a "description" string field but will be unable to contain other nodes. Likewise, our folders will have no description field.

//The interface all nodes will implement.
interface IDirectoryNode
{
    string Name { get; }
    string Description { get; set; }
    void AddNode(IDirectoryNode node);
    void RemoveNode(IDirectoryNode node);
    IDirectoryNode[] GetNodes();
}

//Our Composite node class.
class Folder : IDirectoryNode
{
    string _name;
    List<IDirectoryNode> _nodes = new List<IDirectoryNode>();

    string Name
    {
        get { return _name; }
    }

    string Description
    {
        //This is one way of handling this.
        //we return a null description and the
        //setter does nothing.  We could have
        //thrown an exception among other solutions.
        get { return null; }
        set { }
    }

    public Folder(string name)
    {
        _name = name;
    }

    public void AddNode(IDirectoryNode node)
    {
        _nodes.Add(node);
    }

    public void RemoveNode(IDirectoryNode node)
    {
        _nodes.Remove(node);
    }

    public IDirectoryNode[] GetNodes()
    {
        return _nodes.ToArray();
    }
}

//Now for the leaf nodes.
class File : IDirectoryNode
{
    string _name;
    string _description;

    string Name
    {
        get { return _name; }
    }

    string Description
    {
        get { return _description; }
        set { _description = value; }
    }

    public File(string name, string description)
    {
        _name = name;
        _description = description;
    }

    //These do nothing.
    public void AddNode(IDirectoryNode node) { }
    public void RemoveNode(IDirectoryNode node) { }

    public IDirectoryNode[] GetNodes()
    {
        return null;
    }
}

This is good is the sense that we can create Folders and Files and build our tree but there's not much we can do with it from there. We need a ways to traverse the tree. There are two ways to do this: with a depth-first search where we start at a node and visit all of its children before backtracking or a breadth-first search where we visit all the nodes on the same level before exploring their children.
We will implement both as a way to search for names and descriptions.
First we'll make methods that perform a depth-first search and return a list of nodes that match what we're looking for. We'll be using recursion in this example but there are iterative ways to do it as well. Let's add these new search methods to our interface and classes.

interface IDirectoryNode
{
    string Name { get; }
    string Description { get; set; }
    void AddNode(IDirectoryNode node);
    void RemoveNode(IDirectoryNode node);
    IDirectoryNode[] GetNodes();
    List<IDirectoryNode> SearchForNames(string name);
    List<IDirectoryNode> SearchForDescriptions(string descriptions);
}

class Folder : IDirectoryNode
{
    string _name;
    List&lt;IDirectoryNode&gt; _nodes = new List&lt;IDirectoryNode&gt;();

    string Name
    {
        get { return _name; }
    }

    string Description
    {
        get { return null; }
        set { }
    }

    public Folder(string name)
    {
        _name = name;
    }

    public void AddNode(IDirectoryNode node)
    {
        _nodes.Add(node);
    }

    public void RemoveNode(IDirectoryNode node)
    {
        _nodes.Remove(node);
    }

    public IDirectoryNode[] GetNodes()
    {
        return _nodes.ToArray();
    }

    public List<IDirectoryNode> SearchForNames(string name)
    {
        List<IDirectoryNode> results = new List<IDirectoryNode>();
        foreach (IDirectoryNode node in _nodes)
        {
            string nodeName = node.Name;

            //Some debugging to make sure we're traversing
            //the tree in the correct order.
            Console.WriteLine(
                "Visiting " + nodeName + " " + "the " + node.ToString());

            if (nodeName == name)
            {
                results.Add(node);
            }

            //Here is where we recurse down into the tree.
            results.AddRange(node.SearchForNames(name));
        }
        return results;
    }

    public List<IDirectoryNode> SearchForDescriptions(string description)
    {
        List<IDirectoryNode> results = new List<IDirectoryNode>();

        foreach (IDirectoryNode node in _nodes)
        {
            string nodeDescription = node.Description;

            //Some debugging to make sure we're traversing
            //the tree in the correct order.
            Console.WriteLine(
                "Visiting " + node.Name + " " + "the " + node.ToString());

            if (nodeDescription != null &&
                nodeDescription == description)
            {
                results.Add(node);
            }

            results.AddRange(node.SearchForDescriptions(description));
        }

        return results;
    }
}

class File : IDirectoryNode
{
    string _name;
    string _description;

    string Name
    {
        get { return _name; }
    }

    string Description
    {
        get { return _description; }
        set { _description = value; }
    }

    public File(string name, string description)
    {
        _name = name;
        _description = description;
    }

    //These do nothing.
    public void AddNode(IDirectoryNode node) { }
    public void RemoveNode(IDirectoryNode node) { }

    public IDirectoryNode[] GetNodes()
    {
        return null;
    }

    //These are not applicable so we just
    //return an empty list.
    public List<IDirectoryNode> SearchForNames(string name)
    {
        return new List<IDirectoryNode>();
    }

    public List<IDirectoryNode> SearchForDescriptions(string description)
    {
        return new List<IDirectoryNode>();
    }
}

Let's test this out by building a tree and searching for some things.

class Program
{
    static void Main(string[] args)
    {
        //Building our tree...
        IDirectoryNode documentsFolder = new Folder("Documents");
        IDirectoryNode gamesFolder = new Folder("Games");
        IDirectoryNode musicFolder = new Folder("Music");
        IDirectoryNode someGame = new File("Fun Time Game", "Whooo, fun!");
        IDirectoryNode someSong = new File("Happy Song", "La la la");
        IDirectoryNode textDocument = new File("Journal", "I had a good day!");
        IDirectoryNode textDocumentTwo = new File("Journal", "I had a bad day!");

        documentsFolder.AddNode(gamesFolder);
        documentsFolder.AddNode(musicFolder);
        documentsFolder.AddNode(textDocument);
        gamesFolder.AddNode(someGame);
        musicFolder.AddNode(someSong);
        musicFolder.AddNode(textDocumentTwo);

        //Now we can do searches.
        List<idirectorynode> nameResults = new List<idirectorynode>();
        nameResults = 
            documentsFolder.SearchForNames("Journal");

        foreach (IDirectoryNode node in nameResults)
        {
            Console.WriteLine(node.Name);
        }

        Console.WriteLine();

        List<idirectorynode> descriptionResults = 
            documentsFolder.SearchForDescriptions("La la la");

        foreach (IDirectoryNode node in descriptionResults)
        {
           Console.WriteLine(node.Name);
        }

        Console.ReadLine();
   }
}

As you can see, each child is being completely explored before moving on to the next.
Now let's try to make the breadth-depth search.
We'll be using a queue to keep track of the nodes we still need to explore. Once a node in the queue has been explored, it's removed from line and its children are added. This is repeated until the queue is empty.
This image from wikipedia illustrates the algorithm beautifully.

The grey nodes are the ones currently enqueued and the black nodes are the ones being visited.
For the sake of brevity I will write out just search methods. The interface needs the new stubs as well.

//The breadth-first Folder search implementation.
public List<IDirectoryNode> BreadthFirstNameSearch(string name)
{
    List<IDirectoryNode> result = new List<IDirectoryNode>();
    Queue<IDirectoryNode> searchQueue = new Queue<IDirectoryNode>();

    foreach (IDirectoryNode node in _nodes)
    {
        searchQueue.Enqueue(node);
    }

    while (searchQueue.Count != 0)
    {
        IDirectoryNode currentNode = searchQueue.Dequeue();

        Console.WriteLine(
            "Examining " + currentNode.ToString() + ", " + currentNode.Name);

        if (currentNode.Name == name)
        {
            result.Add(currentNode);                   
        }
        foreach (IDirectoryNode node in currentNode.GetNodes())
        {
            searchQueue.Enqueue(node);
        }
    }

    return result;
}

public List<IDirectoryNode> BreadthFirstDescriptionSearch(string description)
{
    List<IDirectoryNode> result = new List<IDirectoryNode>();
    Queue<IDirectoryNode> searchQueue = new Queue<IDirectoryNode>();

    foreach (IDirectoryNode node in _nodes)
    {
        searchQueue.Enqueue(node);
    }

    while (searchQueue.Count != 0)
    {
        IDirectoryNode currentNode = searchQueue.Dequeue();

        Console.WriteLine(
            "Examining " + currentNode.ToString() + ", " + currentNode.Name);


        if (currentNode.Description != null &&
            currentNode.Description == description)
        {
            result.Add(currentNode);                   
        }

        foreach (IDirectoryNode node in currentNode.GetNodes())
        {
            searchQueue.Enqueue(node);
        }
    }

    return result;
}

Since we cannot search files their implementations simply return empty lists.
If we had used a stack instead of a queue this would have resulting in a depth-first search. Testing this out:

class Program
{
    static void Main(string[] args)
    {
        IDirectoryNode documentsFolder = new Folder("Documents");
        IDirectoryNode gamesFolder = new Folder("Games");
        IDirectoryNode musicFolder = new Folder("Music");
        IDirectoryNode someGame = new File("Fun Time Game", "Whooo, fun!");
        IDirectoryNode someSong = new File("Happy Song", "La la la");
        IDirectoryNode textDocument = new File("Journal", "I had a good day!");
        IDirectoryNode textDocumentTwo = new File("Journal", "I had a bad day!");

        documentsFolder.AddNode(gamesFolder);
        documentsFolder.AddNode(musicFolder);
        documentsFolder.AddNode(textDocument);
        gamesFolder.AddNode(someGame);
        musicFolder.AddNode(someSong);
        musicFolder.AddNode(textDocumentTwo);

        List<IDirectoryNode> nameResults = new List<IDirectoryNode>();
        nameResults = 
            documentsFolder.BreadthFirstNameSearch("Journal");

        foreach (IDirectoryNode node in nameResults)
        {
            Console.WriteLine(node.Name);
        }

        Console.WriteLine();

        List<IDirectoryNode> descriptionResults = 
            documentsFolder.BreadthFirstDescriptionSearch("La la la");

        foreach (IDirectoryNode node in descriptionResults)
        {
            Console.WriteLine(node.Name);
        }

        Console.ReadLine();
    }
}

Notice the different order in which each node is visited.
This is just one very simple way to do this, there are more sophisticated and generalized ways of going about this but the algorithms themselves are the same or very similar.

And this concludes my Design Pattern series (for now)! Next I'll start focusing more on collision algorithms and game physics.
I hope you've enjoyed reading them as much as I have writing them!
Feel free to leave comments, questions, corrections or what have you. Thanks!

The Command Pattern

2011-12-13T10:42:00.000-08:00

The Command pattern is way to separate a request for an action to be performed from the object that actually performs the action. It encapsulates method invocation allowing one to parameterize or change the object making the invocation on the fly.
It's also really neat.
First let's look at a very simple situation where we may need something like this.
Let's say we have two types of objects, a glass bottle and I don't know, a wooden box. If we drop the glass bottle it shatters instantly and is gone. The box however can be dropped a few times before breaking.
Let's see how two simple versions of these classes may be set up.

class Bottle
{
    bool _broken = false;

    public void Break()
    {
        if (_broken)
        {
            Console.WriteLine("The bottle is already broken");
        }
        else
        {
            _broken = true;
            Console.WriteLine("The bottle shatters");
        }
    }
}

class Box
{
    bool _broken = false;
    int _hitPoints = 3;

    public void Hit()
    {
        if (_broken)
        {
            Console.WriteLine("The box is broken irreparably.")
        }
        else
        {
            _hitPoints--;
            if (_hitPoints <= 0)
            {
                _broken = true;
                Console.WriteLine("The box breaks.")
            }
        }
    }
}

The methods Hit() and Break() are clearly fairly different from one another other besides the fact that they are both void and parameterless and they are both probably going to called during very similar situations.
So how would a client class have to deal with this? We can set up a very simple situation to demonstrate the problems that arise.

class Program
{        
    static void Main(string[] args)
    {
        Bottle bottle = new Bottle();
        Box box = new Box();
        string input = "";

        while (input.ToLower() != "q")
        {
            Console.WriteLine(
                "Press B to drop the (B)ottle, O to drop the B(o)x or Q to (Q)uit.");
            input = Console.ReadLine();

            if (input.ToLower() == "b")
            {
                bottle.Break();
            }
            else if (input.ToLower() == "o")
            {
                box.Drop();
            }               
        }
    }
}

It works now but this clearly will not do.
The above code is pretty bad on a number of levels. For starters the more objects added that can be dropped, the bulkier and just awful our client class becomes.
Secondly the client class (in this over simplified case it's the Program class) has too many responsibilities: accepting and interpreting user input and responding to the input (that problem specifically I'm not actually going over in this article but it's something to think about). A general design guideline is: one class, one responsibility. Moreover, in some cases our client class may not even have access to Bottles and Boxes as they may be hidden.
The Command pattern helps by introducing a new type of object called a command object which will contain a single method, Execute().
It's not an easy pattern to grasp at first (it wasn't for me anyway) but it's usefulness became apparent once I did.
Before we dive into the code, let's look at a real world analogy that mirrors how the command pattern works.
In a cafe we can can order many different types of beverages and each have a different procedure for making it. We give our drink order to the chashier who writes down the specifics of the drink we want. The slip encapsulates our drink order. It is then passed off to the barrista who interprets what's written on the slip and makes your drink.
You, the customer, know how to order a drink so you create a command (your order) and pass it off to the chashier. The chashier in turn takes the command you created and passes it to the barrista who makes the drink. Most real life cafe cashiers, of course, must also need to know how to prepare a drink, but for our purposes they do not and have completely separate responsibilities.
Now let's look at the various pieces of the pattern and see how they fit into the cafe scenario.
The Command pattern has a client class which is responsible for creating our command objects (the customer), the client then passes the command to the invoker. The invoker contains one or more references to a command objects which the client sets. Now the invoker can invoke one of these commands at any time, which is like having the barrista make the drinks. Since the invoker can call these methods at any time, we can even set up ques of commands to be executed in a certain order.
Moving back to our Box/Bottle issue, let's take a look at some code now to hopefully help gel the whole idea.
Starting with our command interface and objects:

interface ICommand
{
    void Execute();
}

class BottleDropCommand : ICommand
{
    Bottle _bottle;

    public BottleDropCommand(Bottle bottle)
    {
        _bottle = bottle;
    }

    public void Execute()
    {
        _bottle.Break();
    }
}

class BoxDropCommand : ICommand
{
    Box _box;

    public BoxDropCommand(Box box)
    {
        _box = box;
    }

    public void Execute()
    {
        _box.Drop();
    }
}

Now we need our invoker, a sort of item dropping interface to work with. This will hold two ICommand objects that we can execute at any time.

class SimpleItemDropper
{
    //We have two ICommand's at the moment but this can be extended
    //deal with any amount.
    ICommand _commandOne;
    ICommand _commandTwo

    public void SetCommandOne(ICommand command)
    {
        _commandOne = command;
    }

    public void SetCommandTwo(ICommand command)
    {
        _commandTwo = cammand;
    }
    
    //The item dropper doesn't care if it's a box or a bottle, it just
    //executes the set command!
    public void ExecuteOne()
    {
        _commandOne.Execute();
    }

    public void ExecuteTwo()
    {
        _commandTwo.Execute();
    }
}

Now our client class becomes:

class Program
{        
    static void Main(string[] args)
    {
        Bottle bottle = new Bottle();
        Box box = new Box();
        SimpleItemDropper itemDropper = new SimpleItemDropper();

        ICommand dropBottle = new BottleDropCommand(bottle);
        ICommand dropBox = new BoxDropCommand(box);

        itemDropper.SetCommandOne(dropBottle);
        itemDropper.SetCommandTwo(dropBox);

        itemDropper.ExecuteOne();
        itemDropper.ExecuteOne();
        itemDropper.ExecuteTwo();
        itemDropper.ExecuteTwo();
        itemDropper.ExecuteTwo();
        itemDropper.ExecuteTwo();
        itemDropper.ExecuteTwo();
        
        Console.ReadLine();
    }
}

Our output should look something like this:

And that's the Command pattern, a great way to
* encapsulate method invocation
* separate the invocation of a method from the object receiving the invocation request.

There are many more great uses of this pattern as it can do some very clever things. I suggest investigating further and more importantly experimenting with the pattern yourself. This is a very simple (and useless) example and the pattern can be tweaked and extended to your needs (just like any pattern!) but I've successfully conveyed how powerful this pattern is.
Thanks for reading!

The Facade Pattern

2011-12-09T08:54:00.001-08:00

The Facade pattern is an incredibly simple pattern. In fact, there's a good chance you've implemented it in your projects before without being aware that you were using a design pattern.
This is a short and simple article, but it is a very useful pattern. The Facade pattern simplifies an interface.
A system can be made up of many classes, with complicated interdependencies, each with their own unique interface.
The Facade pattern is a way to simplify how the client interacts with these objects.
Let's say we have a bunch a classes that control various appliances in the house.

class KitchenLight
{
    public void On()
    {
        Console.WriteLine("Kitchen light on.");
    }
    
    public void Off()
    {
        Console.WriteLine("Kitchen light off.");
    }
}

class LivingRoomLight
{
    public void On()
    {
        Console.WriteLine("Living room light on.");
    }

    public void Off()
    {
        Console.WriteLine("Living room light off.");
    }
}

class TV
{
    int _channel;

    public int Channel
    {
        get { return _channel; }
    }

    public void On()
    {
        Console.WriteLine("TV on.");
    }

    public void Off()
    {
        Console.WriteLine("TV off.");
    }

    public void ChangeChannel(int channel)
    {
        _channel = channel;
    }
}

class DVD
{
    string _name;
    
    public string Name
    {
        get { return _name; }
    }

    public DVD(string name)
    {
        _name = name;
    }
}

class DVDPlayer
{
    TV _tv;
    DVD _dvd;

    public DVDPlayer(TV tv)
    {
        _tv = tv;
    }

    public void On()
    {
        Console.WriteLine("DVD on.");
    }

    public void Off()
    {
        Console.WriteLine("DVD off.");
    }

    public void PlayMovie()
    {
        if (_tv.Channel == 4)
        {
            if (_dvd != null)
            {
                Console.WriteLine("Playing " + _dvd.Name);
            }
            else
            {
                Console.WriteLine("No disc in player.");
            }
        }
        else
        {
            Console.WriteLine("TV must be on channel 4.");
        }
    }

    public void InsertDVD(DVD dvd)
    {
        Console.WriteLine("Inserting " + _dvd.Name);
        _dvd = dvd;
    }    
}

Seems simple but now what if we want to watch a movie? From our client class we'd have to....

class Program
{
    static void Main(string[] args)
    {
        KitchenLight kitchenLight = new KitchenLight();
        LivingRoomLight livingRoomLight = new LivingRoomLight();
        TV tv = new TV();
        DVDPlayer dvdPlayer = new DVDPlayer(tv);
        DVD dvd = new DVD("Memento");

        //We'd have to do all this!
        kitchenLight.Off();
        tv.On();
        tv.ChangeChannel(4);
        dvdPlayer.On();
        dvdPlayer.InsertDVD(dvd);
        livingRoomLight.Off();
        dvdPlayer.PlayMovie();
    }
}

That's a lot just to watch a dvd. And when we're done, we'll have to do the whole thing again in reverse.
And, oh no! We just got an XBox and a new game!

class XBoxGame
{
    string _name;

    public string Name
    {
        get { return _name; }
    }

    public XBoxGame(string name)
    {
        _name = name;
    }
}

class XBox
{
    TV _tv;
    XBoxGame _game;

    public DVDPlayer(TV tv)
    {
        _tv = tv;
    }

    public void On()
    {
        Console.WriteLine("XBox on.");
    }

    public void Off()
    {
        Console.WriteLine("XBox off.");
    }

    public void PlayGame()
    {
        if (_tv.Channel == 4)
        {
            if (_game != null)
            {
                Console.WriteLine("Playing " + _game.Name);
            }
            else
            {
                Console.WriteLine("No game in console.");
            }
        }
        else
        {
            Console.WriteLine("TV must be on channel 4.");
        }
    }

    public void InsertGame(XBoxGame game)
    {
        Console.WriteLine("Inserting " + _game.Name);
        _game = game;
    }    
}

This is getting ridiculous.
Luckily the facade pattern can help. A facade is basically a class that holds all these interconnected classes and knows how to interact with them.
Let's see how.

class HomeApplianceFacade
{
    TV _tv;
    DVDPlayer _dvdPlayer;
    KitchenLight _kitchenLight;
    LivingRoomLight _livingRoomLight;
    XBox _xbox;

    public HomeApplianceFacade(
        TV tv,
        DVDPlayer dvdPlayer,
        KitchenLight kitchenLight,
        LivingRoomLight livingRoomLight,
        XBox xbox)
    {
        _tv = tv;
        _dvdPlayer = dvdPlayer;
        _kitchenLight = kitchenLight;
        _livingRoomLight = livingRoomLight;
        _xbox = xbox;
    }

    public void WatchMovie(DVD dvd)
    {
        kitchenLight.Off();
        tv.On();
        tv.ChangeChannel(4);
        dvdPlayer.On();
        dvdPlayer.InsertDVD(dvd);
        livingRoomLight.Off();
        dvdPlayer.PlayMovie();
    }

    public void FinishedMovie()
    {
        _livingRoomLight.On();
        _dvdPlayer.Off();
        _tv.Off();
        _kitchenLight.On();
    }

    public void PlayGame(XBoxGame game)
    {
        _kitchenLight.Off();
        _tv.On();
        _tv.ChangeChannel(4);
        _xBox.On();
        _xBox.InsertGame(game);
        _livingRoomLight.Off();
        _xBox.PlayGame();
    }

    public void FinishedPlayingGame()
    {
        _livingRoomLight.On();
        _xBox.Off();
        _tv.Off();
        _kitchenLight.On();

    }
}

Now we have a few methods that deal with all the low level classes correctly so we don't have to deal with it every time.
When we want to watch a movie or something we deal directly with the Facade we've created. We can still access the low level stuff if we want to, but the simplified interface is there if we need it.

class Program
{
    static void Main(string[] args)
    {
        //We still have to 'install' our system.
        KitchenLight kitchenLight = new KitchenLight();
        LivingRoomLight livingRoomLight = new LivingRoomLight();
        TV tv = new TV();
        DVDPlayer dvdPlayer = new DVDPlayer(tv);

        //But now we have a facade to handle all the complicated stuff.
        HomeApplianceFacade applianceFacade =
            new HomeApplianceFacade(tv, dvdPlayer, kitchenLight, livingRoomLight, xBox);

        //Our simplified interface.
        applianceFacade.WatchMovie(new DVD("Memento"));
        applianceFacade.FinishedMovie();
        applianceFacade.PlayGame(new XBoxGame("Skyrim"));
        applianceFacade.FinishedPlayingGame();
    }
}

And that's pretty much it! The Facade pattern; a great way to create a unified interface to simplify a complicated subsystem.

Thanks, as always for reading and I hope you enjoyed the article.

Intersection Testing in 2D

2011-12-04T20:47:00.001-08:00

Whether or not you plan on making a game with a fancy physics engine you'll more than likely still have to check for collisions at some point. In games, a collision is generated when two or more pieces of geometry are intersecting. Testing to see if two geometrical figures are in intersection (or sometimes called interpenetration) can be a complicated and expensive task.

In this article I will go over several common shapes in 2 dimensions and investigate how we can test a pair of them for intersection. We will also discuss a general method for testing shapes of a certain class.
Responding to the intersections (and finding them fast) is beyond the scope of this article. This article is concerned only with checking for intersection but is still a pretty large subject.

If you're a little shaky on your mathematics, then I suggest that you refresh yourself thoroughly at least. A good understanding of high school math as well as a lot of college level stuff is integral in the development of games. There's no way around it.
That said, I am not trying to scare you so I will try to be as gentle as possible. The more you do it the easier it gets.

We'll go over the 2D shapes covered briefly then investigate how to test for an intersection between pairs of them.

The Circle

A circle is the set of points in the plane that are the same distance from a common point called its center. This distance from a point in the set to the center is its radius.
We can denote the center of a circle by a point in space with its x and y values, or by a vector and its radius by a real number. Although we'll be working with floats or doubles instead of the infinitude of the reals.
Now we can represent a circle by the equation:

$(x-c_x)^2+(y-c_y)^2=r^2$

Where,

$C = (c_x, c_y)$

is the circle's center point with its x and y components and r is the radius.
Every pair of reals, x and y that satisfy this equation for a given real number, r and a point C, is a point on the (unique) circle of radius, r centered at, C.

We can represent a circle simply by storing its position and radius into memory.

class Circle
{
    public Vector2 Center;
    public float Radius;
}

Rectangle

We'll be dealing with two kinds of rectangles here, axis-aligned, often called bounding boxes and non-axis-aligned. When we're referring to the axis-aligned situation we'll specifically say so, otherwise we'll just say 'rectangle' or 'box'.

Axis-aligned boxes have each of their edges parallel to the coordinate axis while the regular boxes do not.
The built-in Rectangle structure that comes with XNA is axis-aligned.
Many calculations become much simpler when we're dealing with rectangles that are axis-aligned but we'll be looking at both cases.
An axis-aligned box simply has a location (usually referring to the upper-left corner), a width and a height. No other information is needed to describe the bounding box.

class AxisAlignedBox
{
    public Vector2 Position;
    public float Width;
    public float Height;
}

In the other case we need to store a position, a width, a height and an angle of rotation.

Here, P is the position and,

$\theta$

(pronounced 'theta') is the angle. A positive angle is measured counter-clockwise.
In XNA, by default the origin is the upper-left hand corner of the sprite we're rotating but we'll normally be rotating a box about it's center or perhaps it's center of mass. We'll see how to deal with these things later on.

Other Polygons

There are many different polygons and the only ones we'll look at in any depth are the convex polygons. This is where it get very complicated very quickly and we'll briefly discuss a general method of testing.

Circle-circle test

Two circles in the plane don't intersect if the distance between their centers is greater than the sum of their radii. That is,

$d(c1, c2) = \sqrt{(c1_x-c2_x)^2+(c1_y-c2_y)^2} > r1+r2$

d(c1, c2) is the distance between the centers and c1 and c2 are the centers subscripted by their x or y component.

The distance from center to center is larger than their combined radii. No intersection.

The distance between their centers is smaller than the sum of their radii, hence, they intersect.

To avoid expensive square root computations we usually compare the square of the distance to the square of the sum of the radii since the inequality remains true.

$(c1_x-c2_x)^2+(c1_y-c2_y)^2 >(r1+r2)^2$

the above is true if the circles don't touch.
Adding this to our Circle class,

class Circle
{
    public Vector2 Center;
    public float Radius;

    //Returns true if this circle intersects another
    //or they are 'just touching'.
    public bool Intersects(Circle circle)
    {
        Vector2 center1 = Center;
        Vector2 center2 = circle.Center;
        float radius1 = Radius;
        float radius2 = circle.Radius;

        float distanceSquared = 
            (float)Math.Pow((center1.X - center2.X), 2) +
            (float)Math.Pow((center1.Y - center2.Y), 2);
        float sumOfRadiiSquared = (float)Math.Pow(radius1 + radius2, 2);
        
        if (distanceSquared <= sumOfRadiiSquared)
        {
            return true;
        }
        else
        {
            return false;
        } 
    }
}

Box-box test (axis aligned)

The test for two axis-aligned boxes is fairly straight forward. We'll need to add a few properties to our class first though,

class AxisAlignedBox
{
    public Vector2 Position;
    public float Width;
    public float Height;

    //y value of uppermost side.
    public float Top
    {
        get { return Position.Y; }
    }

    //y value of lowest side.
    public float Bottom
    {
        get { return Position.Y + Height; }
    }

    //x value of left most side.
    public float Left
    {
        get { return Position.X; }
    }
    
    //x value of right most side.
    public float Right
    {
        get { return Position.X + Width; }
    }
}

The basic idea is that is if the rectangles intersect, then the top side of one (or the bottom side) will be within the bounds set by the top and bottom sides of the other rectangle. Likewise the left side of one (or the right side) will be within the bounds set by the left and right sides of the other rectangle.
Take a look at this picture.

Here, we are testing three different rectangles against the shaded rectangle we'll call, R.
The bottom side of A is below the top side of R and above the bottom side of R, ie. the bottom side of A is within the bounds set by the top and bottom sides of R. Both the left and right sides of A are within the left-right bounds of R. Even though the top side of A is not within the top-bottom bounds, it still intersects.
For B, the top side is within the top and bottom bounds of R and the left side is within R's left and right bounds.
C, while its right side is within the left-right bounds of R, neither it's top nor its bottom sides are within the proper top-bottom bounds of R and it doesn't intersect.
Take a look at the follow case, though.

Rectangle D clearly intersects, but neither it's top nor bottom is within the top-bottom range of R. However, both the top and bottom of R are in D's top-bottom range.
So, roughly in logical terms,
(bottom OR top is within top-bottom bounds of one OR the same with the other) AND
(left OR right is within left-right bounds of one OR the same with the other).
We're pretty much ready to write our algorithm.

class AxisAlignedBox
{
    public Vector2 Position;
    public float Width;
    public float Height;

    //y value of uppermost side.
    public float Top
    {
        get { return Position.Y; }
    }

    //y value of lowest side.
    public float Bottom
    {
        get { return Position.Y + Height; }
    }

    //x value of left most side.
    public float Left
    {
        get { return Position.X; }
    }
    
    //x value of right most side.
    public float Right
    {
        get { return Position.X + Width; }
    }

    public bool Intersects(AxisAlignedBox box)
    {
        bool areBottomsInBounds =
            (Bottom >= box.Top && Bottom <= box.Bottom) ||
            (box.Bottom >= Top && box.Bottom <= Bottom);

        bool areTopsInBounds =
            (Top >= box.Top && Top <= box.Bottom) ||
            (box.Top >= Top && box.Top <= Bottom);

        bool areLeftsInBounds =
            (Left >= box.Left && Left <= box.Right) ||
            (box.Left >= Left && box.Right <= Right);

        bool areRightsInBounds =
            (Right >= box.Left && Right <= box.Right) ||
            (box.Right >= Left && box.Right <= Right);

        bool intersects = (areBottomsInBounds || areTopsInBounds) &&
            (areLeftsInBounds || areRightsInBounds);


        return intersects;
    }
}

Another, way to do this which will also be enlightening later on is to note that for rectangle A in the above illustration, the distance from the top of A to the bottom of R is less than the sum of the height of A and the height of R, while at the same time, the distance between the left of A and the right of R is less than the sum of the width of A and width of R. In general, the distance between the uppermost and lowermost points is less than the sum of the heights and the distance between the leftmost and rightmost points is less than the sum of the widths.
The code for the other method,

class AxisAlignedBox
{
    public Vector2 Position;
    public float Width;
    public float Height;

    //y value of uppermost side.
    public float Top
    {
        get { return Position.Y; }
    }

    //y value of lowest side.
    public float Bottom
    {
        get { return Position.Y + Height; }
    }

    //x value of left most side.
    public float Left
    {
        get { return Position.X; }
    }
    
    //x value of right most side.
    public float Right
    {
        get { return Position.X + Width; }
    }

    public bool Intersects(AxisAlignedBox box)
    {
        //The nested Max calls find the maximum of four different values.
        //Similarly with the nested Min values we find the minimum of more than two values.
        float horizontalDistance = Math.Max(Right, 
                                       Math.Max(box.Right, 
                                           Math.Max(Left, box.Left))) - 
                                   Math.Min(Right, 
                                       Math.Min(box.Right, 
                                           Math.Min(Left, box.Left)));
        float verticalDistance =  Math.Max(Top, 
                                      Math.Max(box.Top, 
                                          Math.Max(Bottom, box.Bottom))) - 
                                  Math.Min(Top, 
                                      Math.Min(box.Top, 
                                          Math.Min(Bottom, box.Bottom)));

        bool intersects = (float)Math.Abs(horizontalDistance) <= Width + box.Width &&
                          (float)Math.Abs(verticalDistance) <= Height + box.Height
     
        return intersects;       
    }
}

Box-box test (general)

Before continuing further we need to talk about an important mathematical theorem called the separating axis theorem. We've already used a result of this theorem in the last example and it will end up being the basis for many other intersection problems in the future. We'll go into the theorem in some depth, what it implies and how we can use it to test for intersections.

The Separating Axis Theorem

The separating axis theorem states that two convex polygons do not intersect if and only if there exists a line such that when we project the shapes onto that line, the projections do not overlap. The line we project onto is called the axis of separation.

First let's clear up the term "projection onto a line".
The term, projection seems a little overloaded with definitions but they are all closely related.
In our case, we can say informally that we're 'casting a shadow' of the object onto a line.
This picture illustrates three shapes being projected onto an arbitrary line, the x-axis and the y axis.

Here we see three shapes being projected onto three lines: The x and y axis and an arbitrary line, L.

The projections are regions of the line. Notice shape C is an axis-aligned box; its x and y projections are the same left-right and top-bottom bounds that we used earlier. In fact, the term in the conditional that states the box we're testing must have its bottom OR top side within the top-bottom bound of the other box is analogous to saying that the boxes' projections onto the y-axis overlap (look at the illustration from the axis aligned box-box section to make sure you see why).
None of these shapes intersect so according to the theorem, there exists a line such that the shapes projections onto that line are separate. Here we see two: the x-axis and the line, L.
This theorem says a lot about when shapes don't intersect but what can we say about when they do? Well, we simply have to negate the theorem to see that two convex polygons intersect if and only if there does not exit a line with said properties. That is, no matter how many lines you project your polyhedra onto, the projections will always overlap.
This poses a problem since there are infinitely many lines we could check.
Luckily in the case of convex polygons there are only a few axis we need to check.
Notice in the axis-aligned box-box method, we only checked the projections of two lines: the x and the y axis. Since both boxes were aligned to those axis those were the only two we had to check.
For a convex polygon, it is sufficient to check the shapes against the axis determined by the normals of each edge (source). If we come across projections that don't overlap we have an early out which will speed up the calculation and if we get through them all and all the projections overlap, then the shapes intersect.
Once we have projections (or the length of them) we can check to see if they overlap similarly to the axis aligned case above.

Before we checked the total distance between the uppermost or lowermost points against the sum of the widths or heights depending.
Now we're checking the distance between the extreme points of the projections along the axis and testing that against the sum of the lengths of the projections. But how do we project these polygons against an axis and find these lengths to begin with?

To start, we'll need to know about vector projection.

The projection of $\bar{a}$ onto $\bar{b}$ is,

$(\bar{a}\cdot\bar{b})\bar{b}=(|\bar{a}|\cos{\theta})\bar{b}$

This can be thought of as the "$\bar{b}$ component of $\bar{a}$". It's in the direction of $\bar{b}$ with a magnitude that varies between $|\bar{a}|$ (when $\bar{a}$ is parallel to $\bar{b}$) and 0 (when $\bar{a}$ is normal to $\bar{b}$).

We also need to tweak our Box class a bit. A lot of the math becomes easier when we keep track of the box's center, its half-height and its half-width. These are similar to a circle's radius except they're vector quantities.

class Box
{
    //Pseudo-code...
    public Vector2 Center;
    public Vector2 HalfHeight;
    public Vector2 HalfWidth;
    public float Angle;
}

Now to measure a projection along a certain axis, take a look at the following illustration,

The half-width and half-height projections give us a handy way to measure a shape along an axis. As for the total distance we need only to project the distance between centers onto the axis and find that length. This give us half the total distance. So we can check the length of the projected vectors against that.

To sum up the algorithm we've been piecing together so far:
1. Get the normals of each box, removing duplicates and normals in the opposite direction.
For each normal:
2. Project both of the boxes' half-widths and half-heights onto it and find the sum of their lengths (note: not the length of their sum, since the projections point in opposite directions they tend to cancel eachother). We'll call these H1 and H2 for each box.
3. Project the difference vector of the boxes' centers onto the normal and find its length, we'll call it D.
4. if D > H1 + H2, then there's no overlap, hence no intersection. Otherwise:
5. if there's more normals get the next normal and repeat. Otherwise, all projections overlap and we have an intersection!
And now we're ready to take a look at our new Box class with the interection method.

class Box
{
    public Vector2 Center;
    //We store these as floats for now,
    //we only need the vector versions during
    //intersection testing.
    public float HalfWidth;
    public float HalfHeight;
    public float Angle;

    public bool Intersects(Box box)
    {
        //Transform the half measures
        Vector2 halfWidthVectOne = Vector2.Transform(
            HalfWidth * Vector2.UnitX, Matrix.CreateRotationZ(Angle));
        Vector2 halfHeightVectOne = Vector2.Transform(
            HalfHeight * Vector2.UnitY, Matrix.CreateRotationZ(Angle));
        Vector2 halfWidthVectTwo = Vector2.Transform(
            box.HalfWidth * Vector2.UnitX, Matrix.CreateRotationZ(box.Angle));
        Vector2 halfHeightVectTwo = Vector2.Transform(
            box.HalfHeight * Vector2.UnitY, Matrix.CreateRotationZ(box.Angle));
            
        //They'll work as normals too.
        Vector2[] normals = new Vector2[4];
        normals[0] = halfWidthVectOne;
        normals[1] = halfWidthVectTwo;
        normals[2] = halfHeightVectOne;
        normals[3] = halfHeightVectTwo;

        for (int i = 0; i < 4; i++)
        {
            normals[i].Normalize();

            //Project the half measures onto the normal...
            Vector2 projectedHWOne =
                Vector2.Dot(halfWidthVectOne, normals[i]) * normals[i];
            Vector2 projectedHHOne =
                Vector2.Dot(halfHeightVectOne, normals[i]) * normals[i];
            Vector2 projectedHWTwo =
                Vector2.Dot(halfWidthVectTwo, normals[i]) * normals[i];
            Vector2 projectedHHTwo =
                Vector2.Dot(halfHeightVectTwo, normals[i]) * normals[i];

            //Calculate the half lengths along the separation axis.
            float halfLengthOne = projectedHWOne.Length() + projectedHHOne.Length();
            float halfLengthTwo = projectedHWTwo.Length() + projectedHHTwo.Length();

            //Find the distance between object centers along the separation axis.
            Vector2 difference = (Center - box.Center);
            Vector2 projectedDiff =
                Vector2.Dot(difference, normals[i]) * normals[i];
            float projectedDistance = projectedDiff.Length();
            
            //Test for early out.
            if (projectedDistance > halfLengthOne + halfLengthTwo)
            {
                return false;
            }
        }
        //We tested every normal axis,
        //we must be in intersection!
        return true;
    }
}

This test secretly assumes that the rotation is about the center point. Otherwise, we'd need to transform the centers to account for the rotation about a different point. If we were dealing with an origin that was located in the upper-left corner of the box, for example, we'd translate the position by the rotated half-measures to get the correct center.
Also, while we were able to remove a few normals because we knew they were boxes (the ones in the opposite direction as another), we did not go through and test for duplicates. For larger polygons with more normals it may be faster to filter out the duplicate normals.

Circle-box test

For convex polygons there are a finite, if not very large number of normals to check. For a circle one could say there are an infinite amount of normals to check. On the plus side, if we can find a sufficient amount of normals to check, the projection is always the same.
Using the same source, we're going to implement the 'naive' axis test where we test against every axis determined by the circles center and a vertex on the box.
Ideally we would only need to check against the one determined by the closest vertex.
Adding a new method to our Box class,

public bool Intersects(Circle circle)
{
    //Transform the half measures
    Vector2 halfWidthVect = Vector2.Transform(
        HalfWidth * Vector2.UnitX, Matrix.CreateRotationZ(Angle));
    Vector2 halfHeightVect = Vector2.Transform(
        HalfHeight * Vector2.UnitY, Matrix.CreateRotationZ(Angle));

    Vector2[] normals = new Vector2[6];
    normals[0] = halfHeightVect;
    normals[1] = halfWidthVect;
    normals[2] = circle.Center - (Center + halfHeightVect);
    normals[3] = circle.Center - (Center - halfHeightVect);
    normals[4] = circle.Center - (Center + halfWidthVect);
    normals[5] = circle.Center - (Center - halfWidthVect);

    for (int i = 0; i < 6; i++)
    {
        normals[i].Normalize();
        Vector2 projectedHalfWidth =
            Vector2.Dot(halfWidthVect, normals[i]) * normals[i];
        Vector2 projectedHalfHeight =
            Vector2.Dot(halfHeightVect, normals[i]) * normals[i];

        float halfLength = projectedHalfHeight.Length() + projectedHalfWidth.Length();

        Vector2 difference = Center - circle.Center;
        Vector2 projectedDifference =
            Vector2.Dot(difference, normals[i]) * normals[i];
        float projectedDistance = projectedDifference.Length();

        if (projectedDistance > halfLength + circle.Radius)
        {
            return false;
        }
    }
    return true;
}

I also added a method in the Circle class,

public bool Intersects(Box box)
{
    return box.Intersects(this);
}

When I tested this I needed to set the box's origin properly:

protected override void Draw(GameTime gameTime)
{
    GraphicsDevice.Clear(Color.CornflowerBlue);

    Color color = circle.Intersects(rotatedBoxTwo)||circle.Intersects(rotatedBoxOne) ? 
        Color.Red : Color.White;


    spriteBatch.Begin();

    Vector2 scaleOne = new Vector2(
        rotatedBoxOne.Width / (float)boxTexture.Width,
        rotatedBoxOne.Height / (float)boxTexture.Height);
    Vector2 scaleTwo = new Vector2(
        rotatedBoxTwo.Width / (float)boxTexture.Width,
        rotatedBoxTwo.Height / (float)boxTexture.Height);

    float circleScale = 2f* circle.Radius / (float)circleTexture.Width;

    //Remembering the origin is in texture coordinates, we must scale it down.
    spriteBatch.Draw(
        boxTexture,
        rotatedBoxOne.Center,
        null,
        color,
        rotatedBoxOne.Angle,
        new Vector2(rotatedBoxOne.HalfWidth, rotatedBoxOne.HalfHeight) / scaleOne,
        scaleOne,
        SpriteEffects.None,
        0f);

    spriteBatch.Draw(
        boxTexture,
        rotatedBoxTwo.Center,
        null,
        color,
        rotatedBoxTwo.Angle,
        new Vector2(rotatedBoxTwo.HalfWidth, rotatedBoxTwo.HalfHeight) / scaleTwo,
        scaleTwo,
        SpriteEffects.None,
        0f);

    spriteBatch.Draw(
        circleTexture,
        circle.Center,
        null,
        color,
        0f,
        new Vector2(circle.Radius, circle.Radius) / circleScale,
        circleScale,
        SpriteEffects.None,
        0f);
                
    spriteBatch.End();

    base.Draw(gameTime);
}

I hope this cleared a lot of stuff up about intersections between shapes. Again, if you're intersested, check out this page for more information. There's algorithms about some convex shapes too.
Thanks for reading!

The Adapter Pattern

2011-12-03T05:33:00.001-08:00

In this post we'll the talking about the Adapter Pattern.
The Adapter pattern, in short, makes one class look like another. We've all seen adapters in the real world: many electrical plugs in the U.S. have three prongs while many of the older outlets or extension cords only have two slots for it. We'd still like to be able to use them, after all there's still a plug, an outlet and they both are made for running an electrical current through it.

To get around this we can buy an adapter for the plug. It's got three slots on one side and two prongs in the other. We simply plug it into the adapter and the outlet will accept it.

Let's say there's a client class that expects a certain type of object to work but we want to use an object of a type that, while similar, just doesn't fit. All we have to do is write an adapter for it and pass our client the adapter in place of our original class and we're set. The adapter sits in between the client and the vendor class and acts as sort of a translator between the two.

Let's take a look at some simple classes to illustrate. Going back to car examples...

//First we'll need a Vehicle interface.
interface Vehicle
{
    void TurnOn();
    void TurnOff();
    void Drive();
    void FillGasTank();
}

class Car : Vehicle
{
    public void TurnOn()
    {
        Console.WriteLine("Starting ignition.")
    }

    public void TurnOff()
    {
        Console.WriteLine("Shutting off engine.")
    }

    public void Drive()
    {
        Console.WriteLine("Vroom!");
    }

    public void Break()
    {
        Console.WriteLine("Screetch!");
    }

    public void FillGasTank()
    {
        Console.WriteLine("Filling tank.");
    }
}

Now let's say we have a client class with methods that accepts vehicles.

class VehicleTester
{
    public void TestVehicle(Vehicle vehicle)
    {
        vehicle.TurnOn();
        vehicle.Drive();
        vehicle.Break();
        vehicle.FillGasTank();
        vehicle.TurnOff();
    }
}

Seems like a fine vehicle tester but let's take a look at another class, a LawnMower.

class LawnMower
{
    public void TurnOn()
    {
        Console.WriteLine("Pulling cord to start engine.")
    }

    public void TurnOff()
    {
        Console.WriteLine("Push off button");
    }

    public void Push()
    {
        Console.WriteLine("Pushing mower around.");
    }

    public void FillGasTank()
    {
        Console.WriteLine("Filling the tank");
    }
}

We would like to be able to test our new LawnMower with the tester we've already implemented but we shouldn't inherit from Vehicle. It's not exactly a vehicle and there's no Break method.
We could write a separate TestMower method, but that's more coding and there will be code duplication. And if we come up with similar classes in the future that we'd like to test, the code will become messy and confusing quickly as we add these tester methods.

We can fix this by making a class called an adapter which will inherit from the target interface and hold a reference to the object we are adapting. In the adapter's overridden methods, we simply call the corresponding methods on the adaptee.
Let's look at the adapter code to help illustrate.

//The adapter inherits the Vehicle class so that our 
//VehicleTester class method will accept it as a parameter
class LawnMowerAdapter : Vehicle
{
    //The adapter contains a LawnMower reference.
    LawnMower _mower;

    //The constructor is passed a LawnMower to adapt.
    public LawnMowerAdapter(LawnMower mower)
    {
        _mower = mower
    }

    //The adapter must implement all the Vehicle methods
    //and there we'll call the appropriate methods on the mower.
    public void TurnOn()
    {
        _mower.TurnOn();
    }

    public void TurnOff()
    {
        _mower.TurnOff();
    }

    public void Drive()
    {
        _mower.Push()
    }

    public void Break()
    {
        //Traditional lawn mowers don't have a break, you just stop pushing.
        //This method can be left blank.
        //One could code some logic for stopping however this would
        //increase the coupling between Adapter and LawnMower. 
    }

    public void FillGasTank()
    {
        _mower.FillGasTank();
    }
}

Now if we have a VehicleTester that we'd like to use to test our LawnMower, we have a neat way to do that. With an adapter.
We first create the adapter giving it the mower we want to test, then we pass the adapter object off to the VehicleTester's TestVehicle method, who accepts it happily since the adapter implements the Vehicle interface. It tests the Mower with no problems or even the knowledge that it's really dealing with a LawnMower (wrapped in an adapter).

The adapter links the client, the VehicleTester, to the adaptee, the LawnnMower. It does this by tricking the client into thinking that it's dealing with the target when it's really just calling methods on the adaptee.

Which methods being called is completely up the adapter. It acts as a translator for the client.

Let's see this in action

public class Program
{
    public void Main(string[] args)
    {
        VehicleTester tester = new VehicleTester();

        //Create the car.
        Car car = new Car();
        
        //Test the car.
        tester.TestVehicle(car);

        //We now create the LawnMower.
        LawnMower mower = new LawnMower();

        //Although we'd like to we can't do this:
        //tester.TestVehicle(mower);
        
        //so we create an adapter object.
        //passing the mower to its constructer.
        LawnMowerAdapter adapter = new LawnMowerAdapter(mower);

        //Now we can test it via the adapter.
        tester.TestVehicle(adapter);
    }
}

Now the console should print something like this out:

Starting ignition.
Vroom!
Screetch!
Filling tank.
Shutting off engine.
Pulling cord to start engine.
Pushing mower around.
Filling the tank.
Push off button.

Perfect!
The Adapter pattern, turning one class into another.

We'll wrap up with a quick look at the class diagram.

That's all for now. Hope you enjoyed learning about the adapter pattern and thanks for reading.

The Template Method Pattern

2011-12-01T07:05:00.001-08:00

The Template Method patter is a simple but very widely used pattern. In fact, if you ever used the XNA framework, you took advantage of the fact that XNA implements a variation of the Template Method pattern perhaps without even being aware of it!
The Template Method pattern allows us to encapsulate algorithms while also being able to delegate some of the steps of the algorithm to subclasses
Before we see how though, let's look at a simple example.

Many of us love our pets or plants and we have to take care of them. One of the responsibilities is feeding them.
An algorithm for feeding a dog may simply involve getting a can of dog food, opening the can and scooping the contents into a bowl.
Feeding a cat could be quite similar. One could get a can of cat food, open the can and scoop it into a bowl.

Let's build some pet-owner classes and see how this might work.

class DogOwner
{
    public void FeedDog()
    {
        CallDogOver();
        GetDogFood();
        GetCanOpener();
        OpenCan();
        FillBowl();
    }

    void CallDogOver()
    {
        Console.WriteLine("Calling dog's name.")
    }

    void GetDogFood()
    {
        Console.WriteLine("Getting a can of dog food.");
    }
    
    void GetCanOpener()
    {
        Console.WriteLine("Getting a can opener");
    }

    void OpenCan()
    {
        Console.WriteLine("Opening can.");
    }
    
    void FillBowl()
    {
        Console.WriteLine("Empty can into bowl.");
    }
}

class CatOwner
{
    public void FeedCat()
    {
        //These two methods have different implementations
        //Depending on the pet!
        CallCatOver();
        GetCatFood();
        //All of these methods are the same as
        //the DogOwner's...
        GetCanOpener();
        OpenCan();
        FillBowl();
    }

    void CallCatOver()
    {
        Console.WriteLine("Making a ticking noise to get the cat's attention.");
    }

    void GetCanOpener()
    {
        Console.WriteLine("Getting a can opener");
    }

    void GetCatFood()
    {
        Console.WriteLine("Getting a can of cat food.");
    }

    void OpenCan()
    {
        Console.WriteLine("Opening can.");
    }
    
    void FillBowl()
    {
        Console.WriteLine("Empty can into bowl.");
    }
}

A big red flag that a design needs to be reworked is code duplication. For the methods that are the same regardless of pet, we're copying the exact same code into the methods; both involve getting a can opener, opening the can and pouring the contents into a bowl and we should to do something about this duplication.
Even the methods that have different implementations are similar: we still get the pet's attention and retrieve some sort of food.
What we'd like is a framework that allows us to avoid code duplication while also allowing for different implementations on some of the methods in the algorithm. The Template Method pattern allows us to do just that.

Following one of our guidelines to program to an interface (or abstract class), let's rework this a little and code an abstract PetOwner class like so,

abstract class PetOwner
{
    //This is called the Template Method.
    public void FeedPet()
    {
        //These are the steps in the algorithm.
        CallPet();
        GetCanOfFood();
        GetCanOpener();
        OpenCan();
        FillBowl();
    }

    //We delegate the implementation of these methods to
    //any class that inherits from it.
    protected abstract void CallPet();
    protected abstract void GetCanOfFood();

    void GetCanOpener()
    {
        Console.WriteLine("Getting a can opener");
    }

    void OpenCan()
    {
        Console.WriteLine("Opening can.");
    }
    
    void FillBowl()
    {
        Console.WriteLine("Empty can into bowl.");
    }
}

Now any class that inherits from PetOwner must implement both the CallPet and GetCanOfFood methods. The subclasses will be responsible for handling these.

Let's code our DogOwner and CatOwner classes now.

class DogOwner : PetOwner
{
    protected override CallPet()
    {
        Console.WriteLine("Calling the dog's name.");
    }

    protected override GetCanOfFood()
    {
        Console.WriteLine("Getting dog food.");
    }
}

class CatOwner : PetOwner
{
    protected override CallPet()
    {
        Console.WriteLine("Making a ticking noise to get the cat's attention.");
    }

    protected override GetCanOfFood()
    {
        Console.WriteLine("Getting cat food.");
    }
}

This seems to be working out well! But what about a gerbil? (for our example gerbil food now comes in tin cans. No analogy is perfect after all!) One doesn't need to get their attention to eat, one simply fills their bowl. But there's still enough similarities so that we should be able to feed a gerbil with our design.

We can do this by making what's called a hook. A hook is simply a virtual method that by default does nothing but subclasses can hook into it and implement their own behavior if they want to.
Changing the PetOwner class just a little:

abstract class PetOwner
{
    public void FeedPet()
    {
        CallPet();
        GetCanOfFood();
        GetCanOpener();
        OpenCan();
        FillBowl();
    }

    //CallPet is now a hook method.
    protected virtual void CallPet() { }
    protected abstract void GetCanOfFood();

    void GetCanOpener()
    {
        Console.WriteLine("Getting a can opener");
    }

    void OpenCan()
    {
        Console.WriteLine("Opening can.");
    }
    
    void FillBowl()
    {
        Console.WriteLine("Empty can into bowl.");
    }
}

Now CallPet is virtual and by default does nothing. We don't have to change our CatOwner or DogOwner classes at all but in our GerbilOwner class we simply do not have to override it.

class GerbilOwner : PetOwner
{
    protected override GetCanOfFood()
    {
        Console.WriteLine("Getting gerbil food.");
    }
}

We don't need to override the hook method since it's in a cage, probably, and knows exactly when you're about to feed it.

Let's add one more hook to this example so that we can pet the animal after feeding.

abstract class PetOwner
{
    public void FeedPet()
    {
        CallPet();
        GetCanOfFood();
        GetCanOpener();
        OpenCan();
        FillBowl();
        PetAnimal();
    }

    //hooks can be overriden if desired.
    protected virtual void CallPet() { }
    protected virtual void PetAnimal() { }

    //abstract methods must be implemented
    protected abstract void GetCanOfFood();

    void GetCanOpener()
    {
        Console.WriteLine("Getting a can opener");
    }

    void OpenCan()
    {
        Console.WriteLine("Opening can.");
    }
    
    void FillBowl()
    {
        Console.WriteLine("Empty can into bowl.");
    }
}

Now our pet owner classes can pet their animals after feeding if they want to.

class DogOwner : PetOwner
{
    protected override CallPet()
    {
        Console.WriteLine("Calling the dog's name.");
    }

    protected override GetCanOfFood()
    {
        Console.WriteLine("Getting dog food.");
    }

    protected override PetAnimal()
    {
        Console.WriteLine("Petting dog on the the head and scratches behind the ears.");
    }
}

//A fish doesn't need to be called
//And petting one isn't pleasant for you or the fish...
class FishOwner
{
    //Again, for our limited example, fish food comes in cans. (gross)
    protected override GetCanOfFood()
    {
        Console.WriteLine("Getting gerbil food.");
    }
}

The Template Method pattern is arguably the simplest and most widely used pattern around. I mentioned how XNA uses it? Well maybe it's apparent to you how by now but let's consider this.
When you make a new Game project, we automatically get a Game1 class which contains methods for loading content, Updating and Drawing.
Underneath the hood there is an algorithm that first calls Initialize() and LoadContent(), and then a game loop which cycles through the Update() and Draw() methods until the game exits.
The pseudo code might look something very similar to this:

class Game
{
    public void Run()
    {
        Initialize();
        LoadContent();

        //do game loop until we exit the game.
        Update();
        Draw();
    }

    //In this version of the Template Method they're all hooks!
    virtual void Initialize() { }
    virtual void LoadContent() { }
    virtual void Update() { }
    virtual void Draw() { }
}

The same thing applies to GameComponent and DrawableGameComponent.
The methods you see when you first start a game aren't the only hook methods your game can hook into as well, just put your cursor somewhere in the class (but outside a method). And type in 'override'. You'll see a whole slew of things you can override and handle in your own way. Many have default behaviors (called using the base keyword) so watch out for that if you start getting bugs.

That covers the Template Method pattern, a simple but powerful pattern that encapsulates the steps of an algorithm while being able to delegate some of those steps in the algorithm to subclasses.
There are, of course, many variations of the pattern that may not even quite resemble what I've shown you but the idea and purpose is always the same

Hope you enjoyed the article!

The Abstract Factory Pattern

2011-11-29T15:53:00.001-08:00

In our last tutorial we talked about the factory method pattern which is a useful way to separate out our object creation and delegate the creation specifics to creator subclasses.
Let's take a look at another possible Car class.

abstract class Car
{
    //A car is made up of parts like an engine and wheels.
    Engine _engine;
    Wheel[] _wheels = new Wheel[4];

    //methods...
}

Here we have a Car class complete with parts. The Engine and Wheel classes would also be abstract since their types could vary. We may want a Car with a HybridEngine or special PunctureProofWheels. Different Car subclasses like Toyota or Honda could have options for different Wheels or Engines and we want to encapsulate both the creation of Cars and its parts while keeping the whole thing flexible for extension.
This may seem daunting but there is a fairly simple pattern that can help called the Abstract Factory pattern.
In this pattern we'll make Factory interface for creating families of products like different Wheels and Engines.
So let's jump right in and make a CarPartFactory class.

interface CarPartFactory
{
    Engine CreateEngine();
    Wheel[] CreateWheels();
}

Any factory class that inherits from CarPartFactory will be responsible for which concrete parts we create. Let's make a couple to see how.

class StandardCarPartFactory : CarPartFactory
{
    public Engine CreateEngine()
    {
        return new CombustionEngine();
    }

    public Wheel[] CreateWheels()
    {
        Wheel[] wheels = new Wheel[4];
        for (int i = 0; i < wheels.Length; i++)
        {
            wheels[i] = new StandardCarWheel();
        }
        return wheels;
    }
}

class HybridCarPartFactory : CarPartFactory
{
    public Engine CreateEngine()
    {
        return new HybridEngine();
    }

    public Wheel[] CreateWheels()
    {
        Wheel[] wheels = new Wheel[4];
        for (int i = 0; i < wheels.Length; i++)
        {
            //Pucture proof wheels come standard with the hybrid.
            wheels[i] = new PunctureProofWheels();
        }
        return wheels;
    }
}

We need to make Engine and Wheel classes as well. In this example they are very simple and the ones I wrote just print out that they are being made and what type so I'll leave them out.
Each Car object with be passed a CarPartFactory in its construction that will set the chosen wheels and engine.
Let's rework our Car class a bit.

abstract class Car
{
    protected Engine _engine;
    protected Wheel[] _wheels = new Wheel[4];
       
    //This is where we'll call the factory methods to make its parts.
    public abstract void ConstructCar();

    public void Paint()
    {
        Console.WriteLine("Painting car...");
    }

    public void ApplyNewCarSmell()
    {
        Console.WriteLine("Applying new car smell...");
    }
}

class Toyota : Car
{
    //Each Car has a factory reference.
    CarPartFactory _factory;
        
    public Toyota(CarPartFactory factory)
    {
        _factory = factory;
        Console.WriteLine("New Toyota created.");
    }

    public override void ConstructCar()
    {
        //The factory creates the correct engine and wheels.
        _engine = _factory.CreateEngine();
        _wheels = _factory.CreateWheels();
    }
}

//The Honda class looks very similar.

That takes care of the Cars and the part creators. We still need our old CarLot method for creating cars and choosing the correct factory.

//This should look familiar.  It's the old Factory Method pattern!
abstract class CarLot
{
    public Car BuyCar(string type)
    {
        Car product = CreateCar(type);

        product.ConstructCar();
        product.Paint();
        product.ApplyNewCarSmell();

        return product;
    }
    //factory method...
    protected abstract Car CreateCar(string type);
}

class ToyotaCarLot : CarLot
{
    protected override Car CreateCar(string type)
    {
        CarPartFactory factory;
        //Except now the 'string type' parameter declares a factory for creating parts.
        if (type == "Hybrid")
        {
            factory = new HybridCarPartFactory();
        }
        else if (type == "Standard")
        {
            factory = new StandardCarPartFactory();
        }
        else
        {
            factory = new StandardCarPartFactory();
        }
        //And we get a Toyota...
        Car car = new Toyota(factory);
        return car;
    }
}

class HondaCarLot : CarLot
{
    protected override Car CreateCar(string type)
    {
        CarPartFactory factory;
        if (type == "Hybrid")
        {
            factory = new HybridCarPartFactory();
        }
        else if (type == "Standard")
        {
            factory = new StandardCarPartFactory();
        }
        else
        {
            factory = new StandardCarPartFactory();
        }
        Car product = new Honda(factory);
        return product;
    }
}

Both lots have a Standard and Hybrid options but the ToyotaCarLot return Toyotas and the HondaCarLot returns Hondas.
Let's test it out and buy some cars.

class Program
{
    static void Main(string[] args)
    {
        CarLot _hondaLot = new HondaCarLot();
        CarLot _toyotaLot = new ToyotaCarLot();
        Car myHybrid = _hondaLot.BuyCar("Hybrid");
        Car myStandard = _toyotaLot.BuyCar("Standard");
        Console.ReadLine();
    }
}

Running this should print out this result.

That's the Abstract Factory pattern! It encapsulates the creation of families of objects and allows for easy extension of any interface we'd like, cars or parts.

The Factory Method Pattern

2011-11-29T09:06:00.001-08:00

There are a couple rules of thumb for design and refactoring that are pretty useful. The first, as one might put it, is to stay abstract. That is, program to interfaces or abstract classes and have your objects deal with them, rather than concrete classes. This is because we want extendability in our designs. If we stick to dealing with interfaces, we can pass along any class that inherits from that interface without issue.
Another important paradigm is to separate what changes from what stays the same and encapsulate what changes.
We've seen both of these at work in every pattern so far. In the strategy pattern we encapsulated object behavior to allow it to change flexibly during runtime.
Now we're going to look at object creation and apply the same principles.
Taking the car example again, let's say before a car can be shipped out it needs to be prepared.

public abstract class Car
{
    //Each type of car handles these differently.
    public abstract void ConstructCar();
    public abstract void Paint();   
    public abstract void ApplyGloss();

    public void ApplyNewCarSmell()
    {
        //They really do this!
        Console.WriteLine("Spraying new car smell into car...");
    }
}

Every car that comes off the lot has to have these methods called on it before it's ready.
So often times when we get to creating the cars we get code that looks like this:

public Car BuyCar(string type)
{
    Car myCar;

    if (type == "Honda")
    {
        myCar = new Honda();
    }
    else if (type == "ElCamino")
    {
        myCar = new ElCamino();
    }
    else if (type == "Toyota")
    {
        myCar = new Toyota();
    }
    //etc...

    //prepare the car for purchase.
    myCar.ConstructCar();
    myCar.Paint();
    myCar.ApplyGloss();
    myCar.ApplyNewCarSmell();

    return myCar;
}

This clearly gets out of hand but what we can see is that the type of car varies but the initialization of the car is the same.
Each type of car knows how to paint itself and apply gloss, and spraying new car smell is the same for every car.
So we should try to separate out the creation and encapsulate it.
Let's do this by creating a class that handles Car creation.

public class SimpleCarFactory
{
    public Car CreateCar(string type)
    {
        Car myCar;

        if (type == "Honda")
        {
            myCar = new Honda();
        }
        else if (type == "ElCamino")
        {
            myCar = new ElCamino();
        }
        else if (type == "Toyota")
        {
            myCar = new Toyota();
        }
        //etc...
        
        return myCar;
    }
}

Now let's create a client class to buy cars from.

public class CarLot
{
    //Contains a reference to a factory object.
    SimpleCarFactory _carFactory;
    
    public CarLot(SimpleCarFactory carFactory)
    {
        _carFactory = carFactory;
    }

    public Car BuyCar(string type)
    {
        //Delegates creation to the factory object.
        Car product = _carFactory.CreateCar(type);

        //This is the same...
        product.ConstructCar();
        product.Paint();
        product.ApplyGloss();
        product.ApplyNewCarSmell();
        
        return product;
    }
}

This is called a Simple Factory. It's commonly used but isn't technically considered a design pattern.
What we would ideally like is a higher level of abstraction in the Creator class. There may be different CarLots that prepare there cars differently. Maybe certain brands of paint aren't available in certain regions or worse the steering wheel is on a different side!

This conveniently brings us to the Factory Method Pattern. Let's change our CarLot class a little:

public abstract class CarLot
{
    public Car BuyCar(string type)
    {
        //Now this calls a method from within our CarLot.
        Console.WriteLine("Creating your " + GetType().ToString());
        Car product = CreateCar(type);

        product.ConstructCar();
        product.Paint();
        product.ApplyGloss();
        product.ApplyNewCarSmell();
        
        return product;
    }

    //Each CarLot handles their own Car creation.
    protected abstract Car CreateCar(string type);
}

And make two different lots, a Unitited States CarLot and a United Kingdoms CarLot.

public class USCarLot : CarLot
{
    protected override Car CreateCar(string type)
    {
        Car product;
        if (type == "Honda")
        {
            //We have new subclasses for US Cars now.
            product = new USHonda();
        }
        else if (type == "Toyota")
        {
            product = new USToyota();
        }
        //etc...
        else
        {
            return null
        }
        return product;
    }
}

public class UKCarLot : CarLot
{
    protected override Car CreateCar(string type)
    {
        Car product;
        if (type == "Honda")
        {
            //And new subclasses for UK Cars now.
            product = new UKHonda();
        }
        else if (type == "Toyota")
        {
            product = new UKToyota();
        }
        //etc...
        else
        {
            return null
        }

        return product;
    }
}

Now for the cars.

public class USHonda : Car
{
    public override ConstructCar()
    {
        Console.WriteLine("Steering wheel goes on the left.");
    }

    public override Paint()
    {
        Console.WriteLine("Painting car...");
    }

    public override ApplyGloss()
    {
        Console.WriteLine("Applying glossy finish...");
    }

}

public class UKHonda : Car
{
    public override ConstructCar()
    {
        Console.WriteLine("Steering wheel goes on the right.");
    }

    public override Paint()
    {
        Console.WriteLine("Painting car...");
    }

    public override ApplyGloss()
    {
        Console.WriteLine("Applying glossy finish...");
    }
}

//In our simple example, the Toyota classes look similar...

Now let's say we want to buy a car. First we choose a type of CarLot to make, then we choose the type of car we want, finally we call the the CarLot's BuyCar method passing in the appropriate string. The type of care that comes out depends on the CarLot that we chose.

class Program
{
    static void Main(string[] args)
    {
        CarLot usCarLot = new USCarLot();
        CarLot ukCarLot = new UKCarLot();

        Car myUSHonda = usCarLot.BuyCar("Honda");
        Car myUKHonda = ukCarLot.BuyCar("Honda");

        Console.ReadLine();
    }
}

And the output should read:

Creating your USHonda
Steering wheel goes on the left.
Painting car...
Applying glossy finish...
Creating your UKHonda
Steering wheel goes on the right.
Painting car...
Applying glossy finish...

That's the Factory Method pattern and it, like all factories, encapsulates object creation. It gives us an interface for creating objects while allowing specific instances of that interface to decide which class to instantiate.
To wrap up, let's take a look at the class diagram.

In the Creator we have a 'factory method' that all subclasses must implement so the ConcreteCreator actually makes the product and is responsible for which ConcreteProduct to make.
Each ConcreteProduct must implement the Product interface so that classes dealing with the products all have a common interface they know how to manipulate.

That's it for this article and thanks for reading!

The XML Content Importer

2011-11-27T08:38:00.001-08:00

A while ago, I wrote a quick rundown of XNA's Content Pipeline, the classes needed to extend it and how they work together. However for the most part, one wouldn't need to do all that since the built in XML Importer is so powerful. One can load almost any class through the content pipeline using only XML.
We'll go few some examples to illustrate this.
If you want to follow along with the code, go ahead and make a new XNA Game Project. I named mine XMLPipelineTutorial.
Right click on the Content Project, select Add New Item... and select XML file. I named mine SimpleString.xml because that's what it will load. The following XML should appear:

<?xml version="1.0" encoding="utf-8" ?>
<XnaContent>
  <!-- TODO: replace this Asset with your own XML asset data. -->
  <Asset Type="System.String"></Asset>
</XnaContent>

The Node named Asset has an attribute called Type which is set to "System.String". This is what will be returned when we call the Content Manager's Load method.
What we put inside the Asset tags is the actual content
I've changed the XML to look like this:

<?xml version="1.0" encoding="utf-8" ?>
<XnaContent>
  <Asset Type="System.String">
    Hello World!
  </Asset>
</XnaContent>

Now in Game1.cs I changed the LoadContent() method so it looks like this:

protected override void LoadContent()
{
    // Create a new SpriteBatch, which can be used to draw textures.
    spriteBatch = new SpriteBatch(GraphicsDevice);

    string xmlContent = Content.Load<string>("SimpleString");
    Console.WriteLine(xmlContent);
}

The line Console.WriteLine(xmlContent) is a little trick I use for debugging games when I don't want to bother loading a font and drawing it on the screen. The output appears on the 'Output' window which you can find in Visual Studio via Debug -> Windows -> Output.
Easy enough. We can load arrays of things:

<?xml version="1.0" encoding="utf-8" ?>
<XnaContent>
  <!-- TODO: replace this Asset with your own XML asset data. -->
  <Asset Type="System.Int32[]">
    4 5 1 6 9 4 10 100032
  </Asset>
</XnaContent>

I named this one IntegerArray.xml.
We can load this just as easily.

protected override void LoadContent()
{
    // Create a new SpriteBatch, which can be used to draw textures.
    spriteBatch = new SpriteBatch(GraphicsDevice);

    string xmlContent = Content.Load<string>("SimpleString");
    Console.WriteLine(xmlContent);

    int[] xmlContent2 = Content.Load<int[]>("IntegerArray");
    for (int i = 0; i < xmlContent2.Length; i++)
    {
        Console.WriteLine(xmlContent2[i].ToString());
    }
}

This is all very well and good but doesn't really show off the flexibility. Let's import a Dictionary of Vectors keyed by Rectangles just for kicks.

<?xml version="1.0" encoding="utf-8" ?>
<XnaContent>
  <!-- TODO: replace this Asset with your own XML asset data. -->
  <Asset Type="System.Collections.Generic.Dictionary[Microsoft.Xna.Framework.Rectangle, 
         Microsoft.Xna.Framework.Vector2]">
    <Item>
      <Key>0 12 24 5</Key>
      <Value>5 5.4</Value>
    </Item>
    <Item>
      <Key>12 3 6 2</Key>
      <Value>0 0</Value>
    </Item>
  </Asset>
</XnaContent>

Each KeyValuePair in the Dictionary is put in between Item nodes. We could had done this for the simple array but we don't have to. Each Key and Value is inside a node of the same name. The XML importer uses reflection to figure out what's what (which is why it's so flexible and powerful).
The Keys, being rectangles are just a list of int's representing X, Y, Width and Height respectively and the Values being Vectors are written as two float's X and Y, respectively. For some reason the pipeline expects these to be in this format and won't let me put values between Width/Height tags or X/Y tags. I suppose for convenience.
Now to load and test it out.

protected override void LoadContent()
{
    // Create a new SpriteBatch, which can be used to draw textures.
    spriteBatch = new SpriteBatch(GraphicsDevice);

    Dictionary<Rectangle, Vector2> xmlContent = 
        Content.Load<Dictionary<Rectangle, Vector2>>("VectorRectangleDictionary");

    foreach (Rectangle rectangle in xmlContent.Keys)
    {
        Console.WriteLine(rectangle.ToString());
    }

    foreach (Vector2 vector in xmlContent.Values)
    {
        Console.WriteLine(vector.ToString());
    }
}

And all is as it should be.
But these are all classes from preexisting libraries, one might point out, what if I want to load my own class?
Not a problem! Since the XML importers uses reflection, we can load any class we want through it.
To do this though we must add a Game Library Project to keep any classes we want to load. Then add a reference to that project in the content project.
We need the Library Project because the content project doesn't know anything about the XMLPipelineTutorial namespace so it won't be able to find any types you try to give it and trying to add a reference to it would cause a circular dependency.
Remember to add a reference to the Game Library not only in the content project but also the main game project.
Here's a simple class:

public class GameItem
{
    public string Name = null;
    public double Value;
}

And here's an XML file for loading it:

<?xml version="1.0" encoding="utf-8" ?>
<XnaContent>
  <Asset Type="XMLTutorialData.GameItem">
    <Name>Sword</Name>
    <Value>350</Value>
  </Asset>
</XnaContent>

Make sure the namespace in the Type attribute match yours.
Now we can load it just like any other asset

protected override void LoadContent()
{
    // Create a new SpriteBatch, which can be used to draw textures.
    spriteBatch = new SpriteBatch(GraphicsDevice);

    GameItem item = Content.Load<GameItem>("Item");

    Console.WriteLine(item.Name + " " + item.Value.ToString());
}

And you should see, "Sword 350" in the output window.
There is a subtlety here that's worth pointing out. To illustrate I've defined another GameItem object and loaded it with the same file. Here's the new LoadContent method. See if you can predict the output before running.

protected override void LoadContent()
{
    // Create a new SpriteBatch, which can be used to draw textures.
    spriteBatch = new SpriteBatch(GraphicsDevice);

    GameItem itemOne = Content.Load<GameItem>("Item");
    GameItem itemTwo = Content.Load<GameItem>("Item");

    Console.WriteLine(itemOne.Name + " " + itemOne.Value.ToString());
    Console.WriteLine(itemOne.Name + " " + itemOne.Value.ToString());

    //Changed the name of itemOne...
    itemOne.Name = "Boot";

    //Print out the name of itemTwo.
    Console.WriteLine(itemTwo.Name);
}

What the?! Changing itemOne's name changed itemTwo's name as well! This is because GameItem is a reference object. What we have are two references to the same object. Go ahead and try this with a value type like a single integer or a Vector2 object and you won't get the same behavior.

The importer will by default only deserialize public fields and properties. If you have private fields you'd like to add you must mark them with a [ContentSerializer] attribute and if you have public fields or properties you'd like ignored by the serializer, you must use the [ContentSerializerIgnor] attribute (excluding readonly fields and properties).
So let's change the GameItem class so not everything is public.

public class GameItem
{
    [ContentSerializer]
    string _name = null;
    [ContentSerializer]
    double _value;

    public string Name
    {
        get { return _name; }
    }

    public double Value
    {
        get { return _value; }
    }
}

The Name and Value properties are readonly so they don't require an attribute to ignore them.
Here's the new Item.xml where the node names match the new field names

<?xml version="1.0" encoding="utf-8" ?>
<XnaContent>
  <Asset Type="XMLTutorialData.GameItem">
    <_name>Sword</_name>
    <_value>350</_value>
  </Asset>
</XnaContent>

And this works exactly the same as before except the GameItem class is better encapsulated.
That's all for now. The built in XML importer has a lot of features and is quite flexible. There's a lot more to explore and perhaps I'll go into more in future articles.

Update: I cam across this question in StackOverflow where someone's demonstrated a nice way to print out how exactly the intermediate serializer expects to see your .xml formatted for some specific object. Definitely worth checking out.

The State Pattern

2011-11-26T10:30:00.001-08:00

The State Pattern allows for a class to change its behavior dynamically according to an internal state.
Let's say we want to design an Enemy class for a game. An Enemy object will be behaving differently depending on it's hit points or other stats, or what's happening around it in the world. If its hit points are low then maybe we use a different animation where it limps and if its hit points reach zero it dies. If it's aware of the Player it may start chasing, attacking, or evading behavior or when nothing in particular is going on perhaps it wanders around or patrols an area.

First let's try representing the Enemy's state with an enumerator giving it only a couple states at first and throw together a quick Enemy class with some methods.

public enum EnemyState
{
    Idle,
    Dead,
}

public class Enemy
{
    int _hitPoints = 20;
    EnemyState _state = EnemyState.Idle;
    
    public void WanderAround()
    {
        if (_state != EnemyState.Dead)
        {
            _state = EnemyState.Idle;
            Console.WriteLine("The Enemy aimlessly wanders...");
        }
        else
        {
            Console.WriteLine("The Enemy is dead so it can't wander around.");
        }
    }

    public void TakeDamage(int damage)
    {
        if (_state != EnemyState.Dead)
        {
            _hitPoints -= damage;
            Console.WriteLine("Enemy takes " + damage.ToString() + " points of damage");
            if (_hitPoints <= 0)
            {
                _state = EnemyState.Dead;
                Console.WriteLine("Enemy is dead!");
            }
        }
        else
        {
            Console.WriteLine("Hit points already at zero.");
        }
    }
    
    public void Attack()
    {
        if (_state != EnemyState.Dead)
        {
            Console.WriteLine("The Enemy attacks!");
        }
    }
}

Pretty straight forward. The methods' behaviors depend on the internal state object, and the state is changed depending on internal conditions, completely hidden from the user. Seems okay until we need to add new states. Let's add an Evading state.

public enum EnemyState
{
    Idle,
    Dead,
    Evading,
}

public class Enemy
{
    int _hitPoints = 20;
    EnemyState _state = EnemyState.Idle;
    
    public void WanderAround()
    {
        if (_state == EnemyState.Dead)
        {
            Console.WriteLine("The Enemy is dead so it can't wander around.");
        }       
        else if (_state == EnemyState.Evading)
        {
            Console.WriteLine("The Enemy can't wander around while it's running away!");
        }
        else 
        {
            _state = EnemyState.Idle;
            Console.WriteLine("The Enemy aimlessly wanders...");
        }
    }

    public void TakeDamage(int damage)
    {
        if (_state != EnemyState.Dead)
        {
            _hitPoints -= damage;
            Console.WriteLine("Enemy takes " + damage.ToString() + " points of damage");
            
            if (_hitPoints <= 5)
            {
                //If the enemy's hit points drops low enough it 
                //becomes scared and runs away.
                _state = EnemyState.Evading;
                Console.WriteLine("Enemy is running away!");
            }
            if (_hitPoints <= 0)
            {
                _state = EnemyState.Dead;
                Console.WriteLine("Enemy is dead!");
            }
        }
        else
        {
            Console.WriteLine("Hit points already at zero.");
        }
    }
    
    //A method to call when the enemy 'feels safe'
    //enough to go back to its Idle state.
    public void StopEvading()
    {
        if (_state == EnemyState.Dead)
        {
            Console.WriteLine("The enemy is dead");
        }
        else
        {
            _state = EnemyState.Idle;
            //Start wandering aimlessly...
            WanderAround();
        }
    }

    public void Attack()
    {
        if (_state == EnemyState.Dead)
        {
            Console.WriteLine("The Enemy can't attack while dead.");
        }
        else if (_state == EnemyState.Evading)
        {
            Console.WriteLine("The Enemy won't attack if it's running away.");
        }
        else
        {
            Console.WriteLine("The Enemy attacks!");
        }
    }
}

Keeping track of the internal state is starting to become complicated. Every time we add a new state we need to account for it in every method, and if we want to add a method we need to account for the state how the state effects it and how it may change the state.
The State Pattern handles this by representing a state as an object itself. These state objects will handle the enemy's behavior when it is in the corresponding state.
Each State class will implement methods to handle requests from the enemy.
Let's look at some code. First we'll implement a State interface. This will replace our enum entirely.

public interface EnemyState
{
    void HandleWanderAround();
    void HandleDamage(int hitPoints);
    void HandleStopEvading();
    void HandleAttack();
}

Notice the method stubs are similar but not exactly like the ones in the Enemy class. The enemy will make requests to its state which will call the appropriate handling method.
Now let's rework the Enemy class.

public class Enemy
{
    int _hitPoints = 20;
    EnemyState _state;
    
    public Enemy()
    {
        //We need to initialize the state to something other than null.
        _state = new IdleState(this);
    }

    public void WanderAround()
    {
        _state.HandleWanderAround();
    }

    public void TakeDamage(int damage)
    {
        _hitPoints -= damage;
        _state.HandleDamage(_hitPoints);
    }
   
    public void StopEvading()
    {
        _state.HandleStopEvading();
    }

    public void Attack()
    {
        _state.HandleAttack();
    }

    public EnemyState GetState()
    {
        return _state;
    }

    public void SetState(EnemyState state)
    {
        _state = state;
    }
}

Much more concise, let's code our IdleState class to see how this works.

public class IdleState : EnemyState
{
    Enemy _enemy;

    public IdleState(Enemy enemy)
    {
        _enemy = enemy;
    }

    public void HandleWanderAround()
    {
        Console.WriteLine("The enemy wanders around.");
    }

    public void HandleDamage(int hitPoints)
    {
        if (hitPoints <= 5 && hitPoints > 0)
        {
            _enemy.SetState(new EvadingState(_enemy));
        }
        if (hitPoints <= 0)
        {
            _enemy.SetState(new DeadState(_enemy));
        }
    }

    public void HandleStopEvading()
    {
        Console.WriteLine("The enemy isn't evading.");     
    }

    public void HandleAttack()
    {
        Console.WriteLine("The enemy attacks!");
    }
}

No long string of state checks required since we know that if these methods are being called, then this is the state the enemy is in. We have a reference to the enemy in case we want to set it's state from another.
Let's finish up with our DeadState and EvadingState classes.

public class EvadingState : EnemyState
{
    Enemy _enemy;

    public EvadingState(Enemy enemy)
    {
        _enemy = enemy;
    }

    public void HandleWanderAround()
    {
        Console.WriteLine("The enemy can't wander around if it's evading!");
    }

    public void HandleDamage(int hitPoints)
    {
        if (hitPoints <= 0)
        {
            _enemy.SetState(new DeadState(_enemy));
        }
    }

    public void HandleStopEvading()
    {
        _enemy.SetState(new IdleState(_enemy));
        _enemy.WanderAround();   
    }

    public void HandleAttack()
    {
        Console.WriteLine("The enemy won't attack if it's running away.");
    }
}

public class DeadState : EnemyState
{
    Enemy _enemy;

    public DeadState(Enemy enemy)
    {
        _enemy = enemy;
    }

    public void HandleWanderAround()
    {
        Console.WriteLine("The enemy can't wander around if it's dead!");
    }

    public void HandleDamage(int hitPoints)
    {
        Console.WriteLine("The enemy is already dead.");
    }

    public void HandleStopEvading()
    {
        Console.WriteLine("The enemy is dead.");   
    }

    public void HandleAttack()
    {
        Console.WriteLine("The enemy can't attack if it's dead.");
    }
}

Everything about an enemy's behavior while it's in a certain state is encapsulated in these State classes. We can change State behavior easier because we know where all the code associated with that state is and we can easily add new States without altering much existing code.
If you've noticed a similarity between the State Pattern and the Strategy Pattern, that's no coincidence; they're very similar. However the State Pattern acts more autonomously, switching from one state to the other based on internal criteria, on its own without the user even being aware of it. The user just calls the Enemy's methods and get the correct behavior!
Thanks for reading and I hope you're enjoying this series on design patterns!

The Singleton Pattern

2011-11-25T19:00:00.001-08:00

The Singleton Pattern is a way of making sure that only one instance of a class gets instantiated. It also sets up a global access point for the object.
Having a class that we can only have one instance of can be useful if, say, our class held a sort of global library of data. The Singleton would make sure there'd never be any confusion over the values of our data, ie. they never come up with two conflicting values, and we would also have a way of retrieving things from our global pool of data from anywhere.
The UML diagram looks very trivial for this pattern because of how simple it is. However, it does have its subtleties. Let's take a look.

The class contains an instance of itself (the one and only one instance) and a method for retrieving that instance.
Let's take a closer look

public class Singleton
{
    static Singleton _uniqueInstance;
    
    Singleton() { }

    public static Singleton GetInstance()
    {
        if (_uniqueInstance == null)
        {
            _uniqueInstance = new Singleton();
        }
        return _uniqueInstance;
    }
}

Perhaps you've noticed the private constructor. This is the key to the pattern. With a private constructor, we can only call new Singleton() from within the Singleton class itself. This allows us to have the class carefully monitor how it's instantiated through the public static method Singleton.GetInstance(), our global access point to the unique instance.
The first time we call Singleton.GetInstance(), the method checks to see if _uniqueInstance is null and since it is, it assigns a new Singleton() to _uniqueInstance and returns it.
The next time we call Singleton.GetInstance() (and every time afterwards), the check for null, returns false and the method returns the one and only one instance.

There is a problem with this set up as is though and maybe you've already noticed it. It isn't thread safe. If two threads were both accessing Singleton.GetInstance(), we could run into problems. Let's walk through a possible method call to see why.

Thread 1:

if (_uniqueInstance == null) //Thread 1 evaluates this to true

Thread 2 gets a turn:

if (_uniqueInstance == null) //Thread 2 also evaluates this to true

Thread 1:

_uniqueInstance = new Singleton(); //Thread 1 creates a new object.
return _uniqueInstance;

Thread 2's turn once again

_uniqueInstance = new Singleton(); //Thread 2 calls the constructor again.
return _uniqueInstance;

Oh no! Since Thread 2 had already evaluated true for the null check, it calls the constructor again and we get a second instance of _uniqueObject completely breaking everything!
Luckily, there's a way around this using the lock keyword.
lock essentially forces a thread to complete a section of code before another thread can get a turn.
Here's our new Singleton class:

public class Singleton
{
    static Singleton _uniqueInstance;
    static readonly object padLock = new object();

    Singleton() { }

    public static Singleton GetInstance()
    {
        lock(padLock)
        {
            if (_uniqueInstance == null)
            {
                _uniqueInstance = new Singleton();
            }
            return _uniqueInstance;
        }
    }
}

That's it! A simple but powerful way to make sure an object only ever has one instance.

Thanks for reading!

The Decorator Pattern

2011-11-25T07:11:00.001-08:00

Subclassing is a powerful way of extending the behavior of a class while keeping what was already there intact. And is, of course, an integral part of object oriented programming. It does however have its drawbacks. I'll illustrate some with a simple example.

Let's say you're in a shop selling a dagger. Maybe there is a base price for the dagger but what you get for the dagger can rely on many factors. The type and quality of the dagger for example, and perhaps there's even an enchantment on it that increases it's value.
So, let's say a dagger class looks something like this:

public abstract class Dagger
{
    public abstract double GetValue();
}

Short, yes but this is all we need for our example.
We'll make a new class now, BronzeDagger, that will inherit from our Dagger class.

public class BronzeDagger : Dagger
{   
    public double GetValue()
    {
        //Return the dagger's base value.
        return 200d;
    }
}

Seems okay so far... we could continue, easily enough to make more classes for Iron, Silver, etc.
But what about that enchantment? If we were to continue in this fashion we'd be forced to make EnchantedBronzeDagger classes and EnchantedSilverDaggerClasses.

Perhaps though, one might suggest that we simply keep track of fields inside the base class like condition and an enchantment type of some kind. Let's see what that would look like.

public abstract class Dagger
{
    double _conditionFactor = .74d;
    double _enchantmentFactor = 2d;

    public abstract double GetValue();

    public double GetConditionFactor()
    {
        return _conditionFactor;
    }

    public double GetEnchantmentFactor()
    {
        return _enchantmentFactor;
    }
}

public class BronzeDagger : Dagger
{
    public double GetValue()
    {
        return 200d * GetCondition() * GetEnchantmentFactor();
    }
}

public class SilverDagger : Dagger
{
    public double GetValue()
    {
        return 500d * GetCondition() * GetEnchantmentValue();
    }
}

However, as more price altering factors are needed, the amount of code we have to write gets out of hand and we'd be forced to change the base class code each time.

The Decorator Pattern allows us to extend behavior dynamically without subclassing and without altering existing code.
The basic idea is to encapsulate the extended behavior into their own classes. We 'wrap' these extended behaviors, or decorators around the class we wish to add to.

Here's what a UML diagram for the Decorator pattern looks like:

The Component would be the object we wish to decorate. The Decorator class inherits from this base class and also contains a reference to one. In this diagram it's the abstract decorator that contains a Component reference which is fine, probably ideal, but for this quick example the Component reference is kept in the ConcreteDecorator classes. Finally there is a ConcreteComponent which inherits from the Component class as well.
That's the set-up, but how we use it will become clearer as we move along.

In our example we'd still have our base abstract Dagger (our Component) class:

public abstract class Dagger
{
    public abstract double GetValue();
}

And some subclasses:

public class BronzeDagger : Dagger
{
    public double GetValue()
    {
        return 200d;
    }
}

public class SilverDagger : Dagger
{
    public double GetValue()
    {
        return 200d;
    }
}

Now we'll make our abstract decorator class.

public abstract class DaggerDecorator : Dagger
{
    public abstract double GetValue();
}

It's important to note here while decorator class inherits from Dagger we're not using it in the normal sense. We're using it here for the type matching or mirroring. Let's make some concrete decorators.

public abstract class EnchantmentDecorator : DaggerDecorator
{
    //We have a reference to the object (or its outer most wrapper)
    //that we're decorating.
    Dagger _dagger;

    //The constructor gets passed a dagger which can 
    //be a decorator since the types match.
    public EnchantmentDecorator(Dagger dagger)
    {
        _dagger = dagger;
    }

    public double GetValue()
    {
        //This decorator multiplies the value by two.
        return 2 * _dagger.GetValue();
    }
}

public abstract class ConditionDecorator : DaggerDecorator
{
    //We have a reference to the object (or its outer most wrapper)
    //that we're decorating.
    Dagger _dagger;
    
    //The constructor gets passed a dagger which can 
    //be a decorator since the types match.
    public Decorator(Dagger dagger)
    {
        _dagger = dagger;
    }

    public double GetValue()
    {
        return .75d * _dagger.GetValue();
    }
}

Each decorator adds its own contribution to the value by delegating the method call, GetValue().
Let's see this in action and create a dagger, decorate it and find its value.

class Program
{
    static void Main(string[] args)
    {
        //Create a BronzeDagger...
        BronzeDagger _kitchenKnife = new BronzeDagger();

        //Wrap it in an EnchantMentDecorator...
        _kitchenKnife = new EnchantmentDecorator(_kitchenKnife);
        
        //Make a SilverDagger.
        SilverDagger _sting = new SilverDagger();
        //This one gets two decorators.
        _sting = new ConditionDecorator(_sting);
        _sting = new EnchantmentDecorator(_sting);
        
        double stingValue = _sting.GetValue();
        double knifeValue = _kitchenKnife.GetValue();

        Console.WriteLine(stingValue.ToString());
        Console.WriteLine(knifeValue.ToString());
    }
}

When we call _sting.GetValue(), it first calls the EnchantmentDecorator's GetValue() method, which then calls the ConditionDecorator's GetValue() which finally calls the original SilverDagger's GetValue() and each call contributes to the final value in some way.
In this example, only multiplication was used in calculating the final value, so the order in which I wrapped them and the order that each decorator delegated its behavior didn't matter. In more complicated examples these things have to be taken into account. We can add as many decorators to an object that we want, extending the class's functionality any time, and the original Dagger class and its subclasses are never altered in the process. Decorators can even add new methods.

Well, that's the Decorator Pattern in a nutshell! I hope you are enjoying this series and thanks for reading!

The Observer Pattern

2011-11-23T12:41:00.001-08:00

Often times, objects need to know what other objects are up to. They may need to be updated of changes and passed new data.
A common example is the view or UI of a program needs to be aware of the state of the objects. In a game, the HUD (Heads Up Display) may need to know information like the players hit points, ammo, or score.
This can be easily achieved through the Observer Pattern. The classes that are kept up to date are called observers and the object being observed is often called the subject. The subject usually has a collection of observers as well as methods for adding or removing observers, also called registering and unregistering respectively. There must also be a way of notifying the registered observers of new data when necessary.
Like many design patterns there are multiple ways doing things and the observer pattern is no exception. I'll go into two main ways that observers are notified of change.

Here's a quick look at a UML diagram for the Observer pattern.

In our simplified example we'll stick with the gaming theme where our subject will be a player, and our observer will be the HUD that will be notified of any change to the player's hit points so that it can be displayed. There can be any number of observers, but we'll stick with one for now. (In fact Observers can register with multiple Subjects, Subjects can, themselves be Observers and vice-versa but we'll keep things simple for now.)

First we'll need our observer interface. It will simply contain a method stub for receiving new data.

public interface IObserver
{
    void Update(double hitPoints);
}

Our Subject contains stubs for adding and removing observers and notifying them of changes.

public interface ISubject
{
    void RegisterObserver(IObserver observer);
    void UnregisterObserver(IObserver observer);
    void NotifyObservers();
}

Let's code our Player class. This will inherit from ISubject and will need to contain a collection of observers and data to be observed.

public class Player : ISubject
{
    //Here's some data that needs to be observed.
    double _hitPoints = 20;

    //We need a collection of observers to notify.
    List<IObserver> _observers = new List<IObserver>();

    //Here's the method that actually changes the hitpoints.
    public void TakeDamage(double damageTaken)
    {
        _hitPoints -= damageTaken;
        //Once this field has been altered, 
        //we automatically notify its observers.
        StateChanged();
    }
   
    public void StateChanged()
    {
        //The observers are notified whenever the class's state, 
        //in this case the Player's hit points changes.
        NotifyObservers();
    }

    public void RegisterObserver(IObserver observer)
    {
        _observers.Add(observer);
    }

    public void UnregisterObserver(IObserver observer)
    {
        _observers.Remove(observer);
    }

    public void NotifyObservers()
    {
        //Here we simply iterate through each registered 
        //observer and pass each one
        //the current hitpoints.
        foreach (IObserver observer in _observers)
        {
            observer.Update(_hitPoints);
        }
    }
}

Notice that whenever the _hitPoints field is changed we call StateChanged() which notifies each observer of the new _hitPoints value.

Now for our concrete observer, the HUD, which will display the Player's hit points if it's registered with it.

class HUD : IObserver
{
    double _hitPointsToDisplay;
    
    //Here is where the observer receives its new data.
    public void Update(double hitPoints)
    {
        _hitPointsToDisplay = hitPoints;
    }

    public void DisplayHitPoints()
    {
        Console.WriteLine("Hit Points: ");
        Console.WriteLine(_hitPointsToDisplay.ToString());
    }   
}

We can now set up a simple test:

class Program
{
    static void Main(string[] args)
    {
        Player _player = new Player();
        HUD _hud = new HUD();

        //Register the HUD observer.
        _player.RegisterObserver(_hud);

        //Once all the observers are registered we'll 
        //initialize them with the proper data.
        _player.StateChanged();

        _hud.DisplayHitPoints();

        //The player takes some damage.  Remember that this 
        //method automatically notifies all
        //observers so there's no reason to call 
        //the NotifyObservers() method again.
        _player.TakeDamage(15.25);

        //The HUD displays the new data.
        _hud.DisplayHitPoints();

        Console.ReadLine();
    }
}

And it works as promised. Every time the Player takes damage (the TakeDamage() method is called), the HUD is notified of the change and we can display it on the screen.

However, there will almost definitely be other data associated with the concrete subject that the observers will need to be aware of.
The Player may have a Score for example. So we'll need to change the classes a bit.

public interface IObserver
{
    void Update(double hitPoints, int score);
}

The Player class now has a score field and a method for incrementing it. Here's the entire Player class with the new changes.

public class Player : ISubject
{
    //Here's some data that needs to be observed.
    double _hitPoints = 20;
    int _score = 0;

    //We need a collection of observers to notify.
    List<IObserver> _observers = new List<IObserver>();

    //Here's the method that actually changes the hitpoints.
    public void TakeDamage(double damageTaken)
   {
        _hitPoints -= damageTaken;
        //Once this field has been altered, we automatically notify its observers.
        StateChanged();
   }

    //This method adds to the player's score.
    public void AddScore(int score)
    {
        _score += score;
        //And again, we notify observers.
        StateChanged();
    }

    public void RegisterObserver(IObserver observer)
    {
        _observers.Add(observer);
    }

    public void UnregisterObserver(IObserver observer)
    {
        _observers.Remove(observer);
    }

    public void StateChanged()    
    {        
        //The observers are notified whenever the class's state,
        //in this case the Player's hit points changes.
        NotifyObservers();
    }

    public void NotifyObservers()
    {
        //Here we simply iterate through each registered 
        //observer and pass each one the current hitpoints.
        foreach (IObserver observer in _observers)
        {
            observer.Update(_hitPoints, _score);
        }
    }
}

Finally the HUD needs to be modified to reflect these changes.

class HUD : IObserver
{
    double _hitPointsToDisplay;
    //Here's the new data that the HUD is interested in keeping up to date with.
    int _scoreToDisplay;

    //Here is where the observer receives its new data.
    public void Update(double hitPoints, int score)
    {
        _hitPointsToDisplay = hitPoints;
        _scoreToDisplay = score;
    }

    public void DisplayHitPoints()
    {
        Console.WriteLine(_hitPointsToDisplay.ToString());
    }

    public void DisplayScore()
    {
        Console.WriteLine(_scoreToDisplay.ToString());
    }
}

Here's the modified program class.

class Program
{
    static void Main(string[] args)
    {
        Player _player = new Player();
        HUD _hud = new HUD();

        //Register the HUD observer.
        _player.RegisterObserver(_hud);

        //Once all the observers are registered we'll 
        //initialize them with the proper data.
        //We can also do this in the concrete observers' constructors.
        _player.NotifyObservers();

        //Display initial values.
        _hud.DisplayHitPoints();
        _hud.DisplayScore();

        //The player takes some damage.  Remember that this 
        //method automatically notifies all
        //observers so there's no reason to call 
        //the NotifyObservers() method again.
        _player.TakeDamage(15.25);

        //The player receives a score for some reason...
        _player.AddScore(5);

        //The HUD displays the new data.
        _hud.DisplayHitPoints();
        _hud.DisplayScore();

        Console.ReadLine();
    }
}

We can already see some problems cropping up. Each piece data we start adding in the player class, we'll need to modify the all the classes that inherit from IObserver.
One way to deal with this is to modify the IObserver interface so that it's Update method stub takes an object as a parameter so one could pass any type of data. It would then be up to the concrete observer class to interpret the argument, which can be tricky. I've set this example up so that each piece of data is of a different type so we won't run into a lot of problems.

Here's our modified IObserver interface.

public interface IObserver
{
    void Update(object arg);
}

The ISubject interface also needs to change.

public interface ISubject
{
    void RegisterObserver(IObserver observer);
    void UnregisterObserver(IObserver observer);
    void NotifyObservers(object arg);
}

The new HUD will receive data as an object type, interpret it and update the appropriate fields.

class HUD : IObserver
{
    double _hitPointsToDisplay;
    int _scoreToDisplay;

    //Here is where the observer receives its new data.
    public void Update(object arg)
    {
        //It's up to the observer to handle the argument passed
        //to it, which can be quite a hassle!
        if (arg is double)
        {
            _hitPointsToDisplay = (double)arg;
        }
        else if (arg is int)
        {
            _scoreToDisplay = (int)arg;
        }
    }

    public void DisplayHitPoints()
    {
        Console.WriteLine("Hit Points: ");
        Console.WriteLine(_hitPointsToDisplay.ToString());
    }

    public void DisplayScore()
    {
        Console.WriteLine("Score: ");
        Console.WriteLine(_scoreToDisplay.ToString());
    }
}

Now we just need to modify the concrete subject, our Player class, to correctly notify its observers.

public class Player : ISubject
{
    //Here's some data that needs to be observed.
    double _hitPoints = 20d;
    int _score = 0;

    //We need a collection of observers to notify.
    List<IObserver> _observers = new List<IObserver>();

    //Here's the method that actually changes the hitpoints.
    public void TakeDamage(double damageTaken)
    {
        _hitPoints -= damageTaken;
        //Once this field has been altered, we automatically notify its observers.
        NotifyObservers(_hitPoints);
    }

    //This method adds to the player's score.
    public void AddScore(int score)
    {
        _score += score;
        //And again, we notify observers.
        NotifyObservers(_score);
    }

    public void RegisterObserver(IObserver observer)
    {
        _observers.Add(observer);
    }

    public void UnregisterObserver(IObserver observer)
    {
        _observers.Remove(observer);
    }

    public void NotifyObservers(object arg)
    {
        //Here we simply iterate through each registered observer and pass each one
        //the current hitpoints.
        foreach (IObserver observer in _observers)
        {
            observer.Update(arg);
        }
    }
}

I've done away with the StateChanged() method and now simply call NotifyObservers(arg) with the appropriate piece of data.

One thing to notice is that the Subject decides what data gets passed to the observers via the Update method. This is called the push method of notification since the Subject pushes the data onto its observers. This may not always be what we want. There may be an observer that's interested in some of the data its subject has but not all of it. Another method, called the pull method, allows the observers to pick and choose which data to take from its subject. Implementing it is not difficult and requires only a few changes to our existing code. I have decided to make the Subject and abstract method so that it can handle the observer collection internally.
The basic idea of the pull method is that instead of passing specific pieces of data to our observers, we pass the Subject object as the Update's argument. As long as the Subject implements some way of getting its data, the observers can decide what to take from its subject and what to ignore.

First let's modify our new IObserver interface.

public interface IObserver
{
    void Update(Subject subject, object arg);
}

Now it takes a Subject object as a parameter as well. We can keep the object arg if we ever want to pass specific data.

Our Subject class is abstract and handles the collection and notification:

public abstract class Subject
{
    List<IObserver> _observers = new List<IObserver>();

    public void RegisterObserver(IObserver observer)
    {
        _observers.Add(observer);
    }

    void UnregisterObserver(IObserver observer)
    {
        _observers.Remove(observer);
    }

    public void NotifyObservers(object arg)
    {
        foreach (IObserver observer in _observers)
        {
            observer.Update(this, arg);
        }
    }

    public void NotifyObservers()
    {
        NotifyObservers(null);
    }
}

We now have two different NotifyObserver methods. One can pass a specific piece of data for an observer to deal with and the other passes null for that argument while they both pass along the Subject.

Our Player class no longer needs to handle its observer collection.

public class Player : Subject
{
    //Here's some data that needs to be observed.
    double _hitPoints = 20d;
    int _score = 0;

    //Here's the method that actually changes the hitpoints.
    public void TakeDamage(double damageTaken)
    {
        _hitPoints -= damageTaken;
        //Once this field has been altered, we automatically notify its observers.
        NotifyObservers();
    }

    //This method adds to the player's score.
    public void AddScore(int score)
    {
        _score += score;
        //And again, we notify observers.
        NotifyObservers();
    }

    public double GetHitPoints()
    {
        return _hitPoints;
    }

    public int GetScore()
    {
        return _score;
    }
}

I'm using the pull method here to show how it works but we don't have to. Just remember that the object parameter might be null and our Observers have to handle cases like this. But for this quick example I'll go ahead and assume we're simply interested in the Subject argument.

class HUD : IObserver
{
    double _hitPointsToDisplay;
    int _scoreToDisplay;

    //Here is where the observer receives its new data.
    public void Update(Subject subject, object arg)
    {
        if (subject is Player)
        {
            Player player = subject as Player;
            _hitPointsToDisplay = player.GetHitPoints();
            _scoreToDisplay = player.GetScore();
        }
    }

    public void DisplayHitPoints()
    {
        Console.WriteLine("Hit Points: ");
        Console.WriteLine(_hitPointsToDisplay.ToString());
    }

    public void DisplayScore()
    {
        Console.WriteLine("Score: ");
        Console.WriteLine(_scoreToDisplay.ToString());
    }
}

In the Update method we grab only the data we want. The subject could have many more fields but our HUD is interested only in the hit points and score.

There you have it. Three different methods of implementing the observer pattern. Each with their own advantages and drawbacks. Deciding which method to use depends on the problem at hand and personal preference. And these are by no means the only ways of doing it, the observer pattern, like most patterns can be tweaked and modified to fit your own needs.

I hope you enjoyed the article and thanks for reading!

The Strategy Pattern

2011-11-22T15:23:00.001-08:00

While they can be abused in various ways, design patterns are an essential subject to become familiar with, so I'm going to dedicate the next series of articles to design patterns.

First up is the strategy pattern. This pattern is very useful for changing a class's behavior at runtime.
Let's say we have a class that implements some method. The method works great but now we'd like to inherit from that class. The method will be inherited as well and will perform the same function. Any additional class we inherit from the base class will also come with this method. But what if one of our subclass' doesn't implement that method in exactly the same way? Well we could always make the method virtual and override it so it does something else but what if we want the class to sometimes perform the method normally and sometimes do it a little different? Here we would run into some problems.

Let's take a simple example. Consider a Car class that implements a Honk() method. Every subclass of Car will have it's own specific honk sound. This is all very well and good, but what if the owner wants to change the honk sound? What if the owner is a bit eccentric and decides they want a different sound for each day of the week? This quickly becomes a maintenance nightmare.

A way around this is to create an interface or an abstract class containing a method stub for Honk behavior. The interface is meant to encapsulate honking. Any concrete strategy class that inherits from the honking interface can implement its Honk method however it wants. The Car class, in turn, will contain a reference to a honking strategy object. When the Car calls its honking method, the strategy's method is called.
This allows for some flexible car honking behavior because now we can write methods to change one Honk interface for another. During runtime a car object can change how it honks!

These abstract behavior classes are called strategies.

Before we get into the code, let's take a quick look at the UML diagram for this pattern. You can skip over this image if you're not familiar with UML as it isn't necessary to follow the article. It can also serve as a handy reference for later.

Our Honk strategy would look something like this:

public interface IHonk
{
    void Honk();
}

Now we can inherit from this interface to make specific honks. We'll make a few here now, a NormalHonk, BrokenHonk, and a GodFatherThemeHonk.

public class NormalHonk : IHonk
{
    public void Honk()
    {
        Console.WriteLine("Honk!");
    }
}

public class BrokenHonk : IHonk
{
    public void Honk()
    {
        Console.WriteLine("fffffffff......");
    }
}

public class GodFatherThemeHonk : IHonk
{
    public void Honk()
    {
        Console.WriteLine("**mandolin music**");
    }
}

Our car class needs a reference to an IHonk object. The car's PerformHonk() method will call the Honk() method from the strategies reference.

public class Car
{
    IHonk _honkStrategy = new NormalHonk();
    
    public void PerformHonk()
    {
        _honkStrategy.Honk();
    }

    public void SetHonkStrategy(IHonk honkStrategy)
    {
        _honkStrategy = honkStrategy;
    }
}

Each car object is initialized with a NormalHonk but we can change this at any time.
Let's create a few cars and see how this works in action

class Program
{
    static void Main(string[] args)
    {
        //Here we initialize a new car, leaving it's honk strategy
        //at its default.
        Car _honda = new Car();
        
        //Here we'll make a car and set it's honk to something else.
        Car _elCamino = new Car();
        _elCamino.SetHonkStrategy(new GodFatherThemeHonk());

        //Each car has it's own honking behavior...
        _honda.Honk();
        _elCamino.Honk();

        //The Honda's horn breaks!
        _honda.SetHonkStrategy(new BrokenHonk());
        
        _honda.Honk();

        Console.ReadLine();
    }
}

We would also, ideally, make the Car class abstract and inherit from it.

public abstract class Car
{
    IHonk _honkStrategy;
    
    public void PerformHonk()
    {
        _honkStrategy.Honk();
    }

    public void SetHonkStrategy(IHonk honkStrategy)
    {
        _honkStrategy = honkStrategy;
    }
}

public class Honda : Car
{
    public Honda()
    {
        SetHonkStrategy(new NormalHonk());
    }
}

public class ElCamino : Car
{
    public ElCamino()
    {
        SetHonkStrategy(new GodFatherThemeHonk());
    }
}

And our Program class becomes simpler.

class Program
{
    static void Main(string[] args)
    {
        Car _honda = new Honda();
        
        Car _elCamino = new ElCamino();
        
        //Each car has it's own honking behavior...
        _honda.Honk();
        _elCamino.Honk();

        //The Honda's horn breaks!
        _honda.SetHonkStrategy(new BrokenHonk());
        
        //The El Camino's owner wants a normal honk.
        _elCamino.SetHonkStrategy(new NormalHonk());
        
        _honda.Honk();
        _elCamino.Honk();

        Console.ReadLine();
    }
}

And that's the Strategy Pattern. It's very simple but extremely effective at changing behavior during runtime.
Thanks for reading and I hope this was an enlightening look at the Strategy Pattern!

Content Pipeline Tutorial

2011-06-26T16:36:00.000-07:00

In this article we'll be building a content pipeline extension.
The content pipeline is a great system for importing and loading outside art assets into your game. The files are converted into a binary (.xnb) file format at compile time that the XNA framework can then deserialize at run time.
The basic process as illustrated in the diagram goes something like this: the file we wish to load is imported into the content pipeline and the importer returns an some object we can work with like a string or an XmlDocument, then the imported type is passed off to the content processor which turns it into an object of the desired type. For example, a .png image is imported and then some doubtlessly complicated logic goes through the data within the file and translates it to a Texture2DContent object (which is turned into a Texture2D object at run time). The object is then passed off to the Content Type Writer which serializes it into the binary .xnb format. All of this happens during compile-time. Then finally at run-time the Content Reader deserializes the .xnb file to our loaded type within the Load method call.

First thing's first. Let's create and set up the projects we'll need. We'll need a total of three projects: An XNA Game project, a Game Library project to hold the types we'll be loading in as well as our content readers, and a Content Pipeline Extension library which will have the importer, processor and writer. Go ahead and create a new solution and then add the other projects.
That finished we now need to add the required references. In the Game project add a reference to the Game Library project. The Content Pipeline Extension project also needs a reference to the Game Library project so it can hold references to the types we'll be loading. Lastly the Content project where you'll have your asset files needs a reference to the Content Pipeline Extension library.
Now let's make our type to be loaded in. We'll make a simple tile map class that will display a grid of textures.
We'll be using the .xml format to import and process our assets. This is mostly to make everything nice and easy since xml is so nice to work with but we could import the data in any form we like.
XNA does already have an importer for the xml format which is very nice and flexible but one can have the control over how data is processed.

The following is the code for our TileMap class which is to go into our Game Library project (I named mine ContentPipelineGameLibrary). It's a very simple class. It uses a single sprite sheet for the tile textures. This is for ease in the serialization and deserialization. I'm using this one with two textures: grass and dirt.
Go ahead and add this code,

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework;

namespace ContentPipelineTutorialGameLibrary
{
    public class TileMap
    {
        string _assetName = "";
        Texture2D _spriteSheet;
        int[,] _textureGrid;
        int _tileWidth = 32;
        int _tileHeight = 32;
        int _tilesPerRow =2;

        Rectangle _drawRectangle = new Rectangle();
        Rectangle _sourceRectangle = new Rectangle();

        public int TilesPerRow
        {
            get { return _tilesPerRow; }
            set { _tilesPerRow = value; }
        }
        public int MapWidth
        {
            get { return _textureGrid.GetLength(1); }
        }
        public int MapHeight
        {
            get { return _textureGrid.GetLength(0); }
        }
        public string AssetName
        {
            get { return _assetName; }
            set { _assetName = value; }
        }
    
        public TileMap(int width, int height)
        {
            _textureGrid = new int[height, width];
            _drawRectangle.Width = _sourceRectangle.Width = _tileWidth;
            _drawRectangle.Height = _sourceRectangle.Height = _tileHeight;
        }

        public void Draw(SpriteBatch spriteBatch)
        {
            for (int x = 0; x < _textureGrid.GetLength(1); x++)
            {
                for (int y = 0; y < _textureGrid.GetLength(0); y++)
                {
                    _drawRectangle.X = x * _tileWidth;
                    _drawRectangle.Y = y * _tileHeight;
                    _sourceRectangle.X =
                        (_textureGrid[y, x] % _tilesPerRow) * _tileWidth;
                    _sourceRectangle.Y =
                        (_textureGrid[y, x] / _tilesPerRow) * _tileHeight;
                    spriteBatch.Draw(
                        _spriteSheet,
                        _drawRectangle,
                        _sourceRectangle,
                        Color.White);
                }
            }
        }
        public void SetTextures(Texture2D spriteSheet, string assetName)
        {
            _spriteSheet = spriteSheet;
        }
        public int GetIndex(int x, int y)
        {
            return _textureGrid[y, x];
        }
        public void SetIndex(int x, int y, int value)
        {
            _textureGrid[y, x] = value;
        }
    }
}

Pretty straight forward stuff. The _tilePerRow field is so we don't have to limit ourselves too much on how we format our sprite sheets. The AssetName setter could prove problematic later on if we want to switch out sprite sheets during run-time but we can tweak things later.

Before we get to any content extension classes, let's set up how we're going to format the data in our file. Like I mentioned before I went with xml since it's so easy to work with but you can just as easily use almost anything (using classes that already have an importer/processor is tricky and I don't recommend it).
Right click on your content project. Select Add -> New Item... and select XML Document in the dialogue. Name it whatever you want, I named mine "TileMap01". The file is automatically given a .xml extension so right click on it and select Rename then change the extension to whatever (I chose ".tilemap"). You will get a warning but pay no heed; we got this.
Now double click the newly created file, delete whatever's inside and add this:

<TileMap Width="4" Height="4">
  <Texture AssetName="TileSheet"/>
  <Layout>
    0 0 0 1
    0 1 0 1
    0 0 0 0
    1 0 1 1
  </Layout>
</TileMap>

Now on to the importer. Right click on your Content Extension Library and select Add -> New Item..., then select Content Importer.
Now replace the automatically generated code with this,

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Content.Pipeline;
using Microsoft.Xna.Framework.Content.Pipeline.Graphics;
using System.Xml;

namespace ContentPipelineTutorialExtensionLibrary
{   
    [ContentImporter(".tilemap", DisplayName = "TileMap Importer", 
        DefaultProcessor = "TileMapProcessor")]
    public class TileMapImporter : ContentImporter<XmlDocument>
    {
        public override XmlDocument Import(
            string filename, ContentImporterContext context)
        {
            XmlDocument document = new XmlDocument();
            document.Load(filename);
            return document;
        }
    }
}

Done. All xml Importers will start this way. Make sure the attribute that declares the extension matches yours.
Now add another new item to the Content Extension Library project, select Content Processor and replace the code with this,

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Content.Pipeline;
using Microsoft.Xna.Framework.Content.Pipeline.Graphics;
using Microsoft.Xna.Framework.Content.Pipeline.Processors;
using System.Xml;
using ContentPipelineTutorialGameLibrary;
using System.IO;

namespace ContentPipelineTutorialExtensionLibrary
{
    [ContentProcessor(DisplayName = "TileMap Processor")]
    public class TileMapProcessor : ContentProcessor<XmlDocument, TileMap>
    {
        public override TileMap Process(
            XmlDocument input, ContentProcessorContext context)
        {
            
            XmlNodeList inputNodeList = input.GetElementsByTagName("TileMap");
            TileMap output = new TileMap(
                int.Parse(inputNodeList[0].Attributes["Width"].Value),
                int.Parse(inputNodeList[0].Attributes["Height"].Value));
            XmlNodeList nodeList = inputNodeList[0].ChildNodes;

            string[] layout;
            string[] rowEntries;

            foreach (XmlNode node in nodeList)
            {
                if (node.Name == "Layout")
                {
                    layout = node.InnerText.Trim().Split('\n');
                    for (int row = 0; row < layout.Length; row++)
                    {
                        rowEntries = layout[row].Trim().Split(' ');
                        for (int rowEntry = 0; rowEntry < rowEntries.Length; rowEntry++)
                        {
                            output.SetIndex(
                                rowEntry, row, int.Parse(rowEntries[rowEntry]));
                        }
                    }
                }
                else if (node.Name == "Texture")
                {
                    output.AssetName = node.Attributes["AssetName"].Value;
                }
            }
            
            return output;
        }
    }
}

So what we're doing here is reading through our xml, setting the texture asset name and setting the map's grid index. Notice we're NOT setting the texture yet. This is because the Texture2D class is not built during compile-time, it's a run-time object so we'll be setting the actual texture in the Content Reader which is called at run-time (when content.Load is called).
That's it for processing our data. Now let's make a Content Writer for the binary serialization.
Like before, add a new item and select Content Writer. The code:

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Content.Pipeline;
using Microsoft.Xna.Framework.Content.Pipeline.Graphics;
using Microsoft.Xna.Framework.Content.Pipeline.Processors;
using Microsoft.Xna.Framework.Content.Pipeline.Serialization.Compiler;
using ContentPipelineTutorialGameLibrary;

namespace ContentPipelineTutorialExtensionLibrary
{
    [ContentTypeWriter]
    public class TileMapWriter : ContentTypeWriter<TileMap>
    {
        protected override void Write(ContentWriter output, TileMap value)
        {
            output.Write(value.MapWidth);
            output.Write(value.MapHeight);
            output.Write(value.AssetName);
            for (int x = 0; x < value.MapWidth; x++)
            {
                for (int y = 0; y < value.MapHeight; y++)
                {
                    output.Write(value.GetIndex(x, y));
                }
            }
        }

        public override string GetRuntimeReader(TargetPlatform targetPlatform)
        {
            return 
                "ContentPipelineTutorialGameLibrary.TileMapReader, ContentPipelineTutorialGameLibrary";
        }
    }
}

In the GetRuntimeReader method, we have the name of our Content Type Reader which we haven't created yet but will be located in the Game Library as opposed to the Content Pipeline Extension library.
And like before, make sure the names match yours (or, rather, what you will name your Content Reader).

Now we need to actually make the reader. Add a new item to the Game Library and select Content Type Reader.
The code:

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.Graphics;

namespace ContentPipelineTutorialGameLibrary
{
    public class TileMapReader : ContentTypeReader<TileMap>
    {
        protected override TileMap Read(ContentReader input, TileMap existingInstance)
        {
            TileMap tileMap = new TileMap(input.ReadInt32(), input.ReadInt32());
            string assetName=input.ReadString();
            tileMap.SetTextures(
                input.ContentManager.Load<Texture2D>(assetName), assetName);
            for (int x = 0; x < tileMap.MapWidth; x++)
            {
                for (int y = 0; y < tileMap.MapHeight; y++)
                {
                    tileMap.SetIndex(x, y, input.ReadInt32());
                }
            }
            return tileMap;
        }
    }
}

This is where we set the texture by from the deserialized asset name.
This also might be a good time to explore the functions available in both the reader and writer. There's pretty much a method for serializing anything you want.
We're not quite done yet. In your content project, left click the tile map file and in the Properties window under Build Action select Compile. Then, under Content Importer and Content Processor select the TileMap Importer and TileMap Processor, respectively.
If they don't appear in the drop-down, try compiling the solution and check again.

Let's load the map and draw it!
Change your Game1.cs class to look like this:

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;
using ContentPipelineTutorialGameLibrary;

namespace ContentPipelineTutorial
{
    public class Game1 : Microsoft.Xna.Framework.Game
    {
        GraphicsDeviceManager graphics;
        SpriteBatch spriteBatch;
        TileMap tileMap;

        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            Content.RootDirectory = "Content";
        }

        protected override void Initialize()
        {        
            base.Initialize();
        }   
        protected override void LoadContent()
        {
            spriteBatch = new SpriteBatch(GraphicsDevice);

            tileMap = Content.Load<TileMap>("TileMap01");
        }      
        protected override void UnloadContent()
        {
      
        }   
        protected override void Update(GameTime gameTime)
        {          
            base.Update(gameTime);
        }
        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.CornflowerBlue);

            spriteBatch.Begin();
            tileMap.Draw(spriteBatch);
            spriteBatch.End();

            base.Draw(gameTime);
        }
    }
}

Now run the solution and you should see something like this:

Okay, so that's pretty small so feel free to change things around a bit :)
That's it for this tutorial. I am happy to answer any questions regarding this tutorial as best I can.

source code