Game Design Atoms

Cory Ondrejka

I went to an interesting talk by Raph Koster at GDC on "Game Design Atoms."  Raph focused on the use of notation in music and choreography and discussed his attempts to create a rigorous notation for game design.  He pointed out the advantages of notation -- reproducibility, error detection, rigorous definitions, content independence, and detection of bad game ideas -- and proceeded to diagram some of the game of checkers as a way to demonstrate the idea.  An interesting, and intellectually appealing, endeavor.

However, I believe that it is making some fundamental mistakes about what games are.  Are games more like music or more like the real world?  While the design space of all music is certainly vast, it is vastly smaller than the design space and complexity available to games.  As a result, in attempting to describe what games are, we should take a lesson from the real world.  And for rigorous descriptions of reality, we turn to mathematics.  Mathematics provide a formal description of the laws that govern the universe.

For games' universes, a similar formal description already exists: the code.  Read on . . .

When building games, a common tactic is to create a "blue squares" demo.  If your gameplay isn't fun with a bunch of blue squares running around, it isn't going to be fun with The Matrix license, Claudia Christian's voice work, or offset-mapped, trilinear-filtered, buzzword enabled graphics.  While this lesson is regularly forgotten, most good games have a moment when they were fun long before all the other junk is grafted on.

Raph suggested that the audience create a better notation than he had chosen, so I offer the following notation for checkers:

// checkers.cpp

#include <iostream>
#include <vector>
#include <algorithm>

class CheckerSquare;

class CheckerPiece
{
public:
    CheckerPiece(CheckerSquare *square, bool is_black)
        : mSquare(square), mIsBlack(is_black), mIsKing(false)
    {
    }

    ~CheckerPiece() {}

    void moveTo(CheckerSquare *square);

    void king()
    {
        mIsKing = true;
    }

    friend std::ostream& operator<< (std::ostream& os, const CheckerPiece& p)
    {
        if (p.mIsBlack)
        {
            if (p.mIsKing)
            {
                return os << "\t\tB";
            }
            else
            {
                return os << "\t\tb";
            }
        }
        else
        {
            if (p.mIsKing)
            {
                return os << "\t\tR";
            }
            else
            {
                return os << "\t\tr";
            }
        }
    }

    CheckerSquare *mSquare;
    bool mIsBlack;
    int mIsKing;
};

typedef enum e_square_connections
{
    SC_FWD_LEFT,
    SC_FWD_RIGHT,
    SC_BACK_LEFT,
    SC_BACK_RIGHT,
    SC_MAX_CONNECTIONS
} SquareConnections;

class CheckerSquare
{
public:
    CheckerSquare(int pos)      
        : mPiece(NULL), mBoardPosition(pos)
    {
        int i;
        for (i = SC_FWD_LEFT; i < SC_MAX_CONNECTIONS; i++)
        {
            mConnections[i] = NULL;
        }
    }
    ~CheckerSquare()   
    {
        delete mPiece;
    }

    friend std::ostream& operator<< (std::ostream& os, const CheckerSquare& s)
    {
        if (s.mPiece)
        {
            return os << *s.mPiece << "[" << s.mBoardPosition << "]";
        }
        else
        {
            return os << "\t\t[" << s.mBoardPosition << "]";
        }
    }

    CheckerSquare   *mConnections[SC_MAX_CONNECTIONS];
    CheckerPiece    *mPiece;
    int             mBoardPosition;
};

typedef std::vector<CheckerSquare *> squares_t;

const int gRows = 8;
const int gCollums = 4;
const int gSpaces = gRows * gCollums;

const int gNumberCheckerRows = 3;
const int gNumberCheckers = gNumberCheckerRows * gCollums;

typedef enum e_board_conditions
{
    BC_NULL,
    BC_BLACK_PIECES = 1,
    BC_RED_PIECES = 2,
    BC_BLACK_FORCE = 4,
    BC_RED_FORCE = 8,
} BoardConditions;

struct DeletePointer
{
    template<typename T> void operator()(T* ptr) const
    {
        delete ptr;
    }
};

class CheckerBoard
{
public:
    CheckerBoard()
        : mBlackMove(true), mBoardCondition(0)
    {
        int i;
        for (i = 0; i < gSpaces; i++)
        {
            mBoard.push_back(new CheckerSquare(i));
        }

        squares_t::const_iterator it = mBoard.begin();
        squares_t::const_iterator base = it;
        squares_t::const_iterator end = mBoard.end();

        for(; it != end; ++it)
        {
            CheckerSquare *cs = (*it);

            int position = cs->mBoardPosition;
            int collum = position % gCollums;
            int row = position / gCollums;
            int oddrow = row % 2;

            int left_edge = collum ? false : true;
            int right_edge = collum == gCollums - 1 ? true : false;

            int connect_left = !left_edge || !oddrow;
            int connect_right = !right_edge || oddrow;

            int fwd_left = position - gCollums - oddrow;
            int fwd_right = fwd_left + 1;
            int back_left = position + gCollums - oddrow;
            int back_right = back_left + 1;

            if (fwd_left >= 0 && connect_left)
            {
                cs->mConnections[SC_FWD_LEFT] = *(base + fwd_left);
            }

            if (fwd_right >= 0 && connect_right)
            {
                cs->mConnections[SC_FWD_RIGHT] = *(base + fwd_right);
            }

            if (back_left < gSpaces && connect_left)
            {
                cs->mConnections[SC_BACK_LEFT] = *(base + back_left);
            }

            if (back_right < gSpaces && connect_right)
            {
                cs->mConnections[SC_BACK_RIGHT] = *(base + back_right);
            }

            if (position < gNumberCheckers)
            {
                cs->mPiece = new CheckerPiece(cs, false);
            }
            else if (position >= gSpaces - gNumberCheckers)
            {
                cs->mPiece = new CheckerPiece(cs, true);
            }
        }
    }

    ~CheckerBoard()
    {
        std::for_each(mBoard.begin(), mBoard.end(), DeletePointer());
    }

    void getOptions(CheckerPiece *piece, int &start, int &end)
    {
        if (piece->mIsKing)
        {
            start = SC_FWD_LEFT;
            end = SC_BACK_RIGHT;
        }
        else if (piece->mIsBlack)
        {
            start = SC_FWD_LEFT;
            end = SC_FWD_RIGHT;
        }
        else
        {
            start = SC_BACK_LEFT;
            end = SC_BACK_RIGHT;
        }

    }

    bool checkKing(CheckerPiece *piece)
    {
        if (piece->mIsBlack)
        {
            if (piece->mSquare->mBoardPosition < gCollums)
            {
                return true;
            }
        }
        else
        {
            if (piece->mSquare->mBoardPosition >= gSpaces - gCollums)
            {
                return true;
            }
        }
        return false;
    }

    bool checkForce(CheckerPiece *piece, bool check_destination = false, int destination = 0, bool move = false)
    {
        int start, end;

        getOptions(piece, start, end);

        for (int direction = start;  direction <= end; direction++)
        {
            if (piece->mSquare->mConnections[direction])
            {
                if (  (piece->mSquare->mConnections[direction]->mPiece)
                    &&(piece->mSquare->mConnections[direction]->mPiece->mIsBlack != piece->mIsBlack))
                {
                    if (piece->mSquare->mConnections[direction]->mConnections[direction])
                    {
                        if (!piece->mSquare->mConnections[direction]->mConnections[direction]->mPiece)
                        {
                            if (check_destination)
                            {
                                if (piece->mSquare->mConnections[direction]->mConnections[direction]->mBoardPosition == destination)
                                {
                                    if (move)
                                    {
                                        delete piece->mSquare->mConnections[direction]->mPiece;
                                        piece->mSquare->mConnections[direction]->mPiece = NULL;
                                        piece->moveTo(piece->mSquare->mConnections[direction]->mConnections[direction]);
                                        if (checkKing(piece))
                                        {
                                            piece->king();
                                        }
                                    }
                                }
                            }
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    bool doMove(CheckerPiece *piece, int destination)
    {
        int start, end;

        getOptions(piece, start, end);

        for (int direction = start;  direction <= end; direction++)
        {
            if (piece->mSquare->mConnections[direction])
            {
                if (  (!piece->mSquare->mConnections[direction]->mPiece)
                    &&(piece->mSquare->mConnections[direction]->mBoardPosition == destination))
                {
                    piece->moveTo(piece->mSquare->mConnections[direction]);
                    if (checkKing(piece))
                    {
                        piece->king();
                    }
                    return true;
                }
            }
        }
        return false;
    }

    bool doMove(int start, int end)
    {
        CheckerPiece *piece = mBoard[start]->mPiece;

        if (!piece)
        {
            std::cout << "No piece found" << std::endl;
            return false;
        }

        if (piece->mIsBlack != mBlackMove)
        {
            std::cout << "Not your piece!" << std::endl;
            return false;
        }

        if (checkForce(piece, true, end, true))
        {
            checkBoard();
            if (!checkForce(piece))
            {
                mBlackMove = !mBlackMove;
            }
            return true;
        }

        if (mBlackMove && (mBoardCondition & BC_BLACK_FORCE))
        {
            std::cout << "Black failed to take forced jump" << std::endl;
            return false;
        }

        if (!mBlackMove && (mBoardCondition & BC_RED_FORCE))
        {
            std::cout << "Red failed to take forced jump" << std::endl;
            return false;
        }

        if (doMove(piece, end))
        {
            mBlackMove = !mBlackMove;
            return true;
        }
        std::cout << "Not a legal move!" << std::endl;
        return false;
    }

    bool doTurn()
    {
        char temp[255];
        int start, end;

        if (mBlackMove)
        {
            std::cout << "Black to move" << std::endl;
            if (mBoardCondition & BC_BLACK_FORCE)
            {
                std::cout << "Forced jump" << std::endl;
            }
        }
        else
        {
            std::cout << "Red to move" << std::endl;
            if (mBoardCondition & BC_RED_FORCE)
            {
                std::cout << "Forced jump" << std::endl;
            }
        }

        std::cout << *this << std::endl;

        std::cout << "Piece to move?" << std::endl;
        std::cin >> temp;
        start = atoi(temp);
        std::cout << "Destination?" << std::endl;
        std::cin >> temp;
        end = atoi(temp);

        doMove(start, end);
        checkBoard();

        if ((mBoardCondition & BC_RED_PIECES) && (mBoardCondition & BC_BLACK_PIECES))
            return true;
        else
            return false;
    }

    void checkBoard()
    {
        mBoardCondition = 0;
        squares_t::const_iterator it = mBoard.begin();
        squares_t::const_iterator end = mBoard.end();
        for(; it != end; ++it)
        {
            if ((*it)->mPiece)
            {
                if ((*it)->mPiece->mIsBlack)
                {
                    mBoardCondition |= BC_BLACK_PIECES;
                    if (checkForce((*it)->mPiece))
                    {
                        mBoardCondition |= BC_BLACK_FORCE;
                    }
                }
                if (!(*it)->mPiece->mIsBlack)
                {
                    mBoardCondition |= BC_RED_PIECES;
                    if (checkForce((*it)->mPiece))
                    {
                        mBoardCondition |= BC_RED_FORCE;
                    }
                }
            }
        }
    }

    friend std::ostream& operator<< (std::ostream& os, const CheckerBoard& b)
    {
        squares_t::const_iterator it = b.mBoard.begin();
        squares_t::const_iterator end = b.mBoard.end();
        for(; it != end; ++it)
        {
            if ((*it)->mBoardPosition % 8 == 0)
            {
                os << "\t";
            }
            os << *(*it);
            if ((*it)->mBoardPosition % 4 == 3)
            {
                os << "" << std::endl;
            }
        }

        return os;
    }

    squares_t   mBoard;
    int         mBoardCondition;
    bool        mBlackMove;
};

void CheckerPiece::moveTo(CheckerSquare *square)
{
    mSquare->mPiece = NULL;
    mSquare = square;
    mSquare->mPiece = this;
}

int main(int argc, char* argv[])
{
    CheckerBoard *cb = new CheckerBoard();
    while(cb->doTurn())
        ;
    if (cb->mBoardCondition & BC_BLACK_PIECES)
    {
        std::cout << "Black WINS!" << std::endl;
    }
    else
    {
        std::cout << "Red WINS!" << std::endl;
    }
    return(0);
}

So, the question that Raph is posing is whether some description is superior to just building the blue squares version.  Code has all of the properties that Raph was looking for in notation, plus additional advantages.  It would be easy to add AI to this, change the board shape or size, or experiment with other rules changes.  You can also freely graft content onto it when you're happy with the gameplay.  Sure, it was banged out in a hurry and isn't very clean, but just about any programmer could look at the code and understand the game of checkers.  It probably has bugs, but testing will reveal these.  More importantly, they could actually play checkers, which returns to the complexity issue.

A talented musician can "hear" music based on reading the score.  After all, a primary function of our big, squishy, pattern matching and feedback laden brains is to simulate reality.  However, the larger and more complex the simulation, the more likely that we're chunking away some useful piece and potentially missing something important.  So being able to actually play the game is a vital part of analysis and critique.  Even Richard Garfield, as brilliant a game designer as any, play tested Magic: the Gathering (and Lighting Bolt was still imbalanced!)

Of course, I'm a programmer, so I am undoubtedly biased.  I am not, however, dismissing the value of other descriptive forms.  Just as song, art and poetry all have their place in describing the world and the human condition, Raph's approach might be an important tool in our understanding of games.  But for problems he wanted to solve with notation, I submit that code already serves us extremely well.