Wednesday, December 9, 2009

Representing a mutable game state using continuation-passing and aspect-oriented concepts.

I've been a fan of the World of Warcraft Trading Card Game for a while now. As a geek that somehow missed the Magic: The Gathering rush, I feel like I'm retroactively patching up some holes in my nerd-dom defense.

The game makes me cringe when I look at it through developer eyes. It has an interesting hook; while there are basic rules associated with the game, the printed card text always trumps the rules. And new cards are coming out all the time. As I play and watch absurd card after absurd card completely change up the game, I think... can this be implemented in a sane way?

The game state is completely mutable. No rules are truly set in stone. For example, cards have class restrictions, but class restrictions can be circumvented. Players take one turn, but might be able to play a card to take another turn. Cards can bring in cards that don't even exist in the concept of a game. I've read horror stories of games where a player's deck is crafted in such a way that the player can eventually swap their deck out with a raid deck.

In fact, there are cards that turn resource cards into ally cards while still providing the benefits of a resource card.

So, how do I model that?

I was knee-deep in implementation on something that sort of kind of worked. I had the idea of "firm" rules with cards that were somewhat dynamic. This worked up to a point. I had a good majority of my common cases working, but as the less-common cases rolled in, I realized that the most intuitive, charge-in-ask-questions-later approach wouldn't work. Ever. In a million years. I was way off.

I bounced ideas off of my own personal design committee for hours. I'd highly recommend throwing one of these together if you haven't already, by the way. They're really great about reminding me that my designs are awful and I'm almost completely inept.

What we came up with was pretty spectacular. I didn't know it at the time, but we implemented a continuation-passing style design pattern in the context of modeling a card game. And, we threw a dash of aspect oriented programming in there, too!

Consider an object graph that contains several nodes. Each node on the graph contains several lists of functions (pre-, default or mask, and post-functions). Pre-functions evaluate, followed by either default or mask functions, followed by post-functions. That's our aspect-oriented flavor and allows us to do cool things like, "Before a player draws a card, make them take a billionty damage." More AOP goodness can be found here: http://en.wikipedia.org/wiki/Aspect_oriented_programming

The default functions associated with each node on the graph are responsible for doing something and then putting another node on the queue of nodes to evaluate. For example, let's say we have a set of rules for picking a player. Once we've evaluated those rules, we want to move on to the "Play the game" part of our code. This is where we get our continuation-passing style influences from. For more information on CPS, check out this informative Wiki: http://en.wikipedia.org/wiki/Continuation_passing_style

To see if this approach would fly, I decided to implement The Game of War (http://en.wikipedia.org/wiki/War_(card_game) ). The Game of War is one of the easiest card games to implement, and I figured this would be a great test bed for introducing the kinds of game-changing rules I would expect from more complex card games.

When we consider The Game of War in the context of our object graph, we end up with something like this:

    0. Shuffle the deck.

    1. Determine the active player.

    2. Draw a card for the active player.

    3. Compare card values with the opposing player. If the opposing player doesn't have a card, GOTO 1. If there's a tie, make each player draw three cards and GOTO 1.

    4. Declare a winner.

    5. GOTO 1.

This flow represents the "ideal" state of the game; that is, the default rules. And hey, this worked out pretty well! Not bad for implementing one of the simplest card games in the world within a series of obscure design patterns.

So now, with epic Game of War in place, I decided to add a slight twist. Each player would have a deck of standard playing cards. However, each player would also have a side deck of ability cards. In step 0, each player's side deck of abilities gets shuffled into the deck of standard playing cards.

I want ability cards to be able to mutate the state of the game. When an ability card is drawn, I want functions associated with the card to evaluate and cause weird stuff to happen. Weird stuff is good! They make games interesting.

The ability cards I decided to implement were:

Gain 1 Point: "Immediately gain one point and draw another card."

Fortune: "Immediately draw until you have 5 standard cards. Choose the card with the highest value and add the remaining cards to the pot."

"Gain 1 Point" isn't terribly interesting, but does throw an interesting wrench into our standard game flow. In step 2, we draw a card and move to step 3. However, in this case, we draw a card and go back to draw a card. The card has manipulated the flow of the game, and this is exactly what I want to enable.

The "Gain 1 Point" card does this by... well, I'm one of the unfortunate types that can't explain anything without a whiteboard, so let's take a look at the code instead.

new AbilityCard

{

    Name =

"Gain 1 Point",

    Description =

"Upon drawing this card, immediately gain one point and draw another card.",

    Action = () =>

    {

        testGame.GameState.ActivePlayer.Points++;

        testGame.GameWorkflow.ExecutionQueue.Add(testGame.DrawCardNode);

    }

}

Okay, so a card has an Action. The Action is evaluated when the card is drawn. In this case, the action of the card is to grant the active player (determined by step 1) a point. And then, we take the execution queue and add a "DrawCardNode" to it. A DrawCardNode is just the typed representation of Step 2. So, we drew a card (we were in the draw card node!) and added another draw card node to the queue of stuff to evaluate. We went from step 2 right back to step 2 again, and in a convoluted way! Joy!

Don't worry about GameWorkflow or ExecutionQueue just yet. Suffice to say, the execution queue is responsible for evaluating each node in the object graph I described above.

So, Fortune is a bit trickier. We have to draw 5 cards, and then pick the high card, and then use that for comparison. We also have to add all the cards we drew to the pot. Our game isn't conducive to this at all! It has no notion of the absurd stuff this card is trying to do. Luckily, it doesn't have to!

Let's take a look at the Fortune card code. Apologies in advance! There's a lot going here:

 

new AbilityCard

{

    Name =

"Fortune!",

    Description =

"Upon drawing this card, draw until you have 5 standard cards. Choose the highest card and add the remaining cards to the pot.",

    Action = () =>

    {

        List<Card> cards = new List<Card>();

        while((from card in cards where card is StandardCard select card).Count() < 5)

        {

            Card cardToAdd = testGame.GameState.ActivePlayer.Deck.Draw();

            cards.Add(cardToAdd);

}

        StandardCard highCard = (from StandardCard card in cards where card is StandardCard orderby card.Value descending select card).First();

        testGame.GameState.ActivePlayer.HighCard = highCard;

        int potValue = cards.Count;

        testGame.CompareCardNode.PreRules.Add(

"fortune", () =>

        {

            if (testGame.GameState.Player1.HighCard != null && testGame.GameState.Player2.HighCard != null)

{

                if (testGame.GameState.Player1.HighCard.Value > testGame.GameState.Player2.HighCard.Value)

{

testGame.GameState.Player1.Points = testGame.GameState.Player1.Points + potValue;

}

                else if (testGame.GameState.Player2.HighCard.Value > testGame.GameState.Player1.HighCard.Value)

{

testGame.GameState.Player2.Points = testGame.GameState.Player2.Points + potValue;

}

}

}

testGame.GameWorkflow.ExecutionQueue.Add(testGame.CompareCardNode);

}

Okay, the Fortune card looks scary. It manipulates quite a bit of game state. It's also responsible for quite a bit. The first 10 lines or so of the action are dedicated to drawing up to 5 standard cards and picking the highest card. This process also determines the pot value. Can you tell that I love LINQ? So far, so good?

Immediately after that, we add a pre-rule to the "Compare Card" node in which we determine that, if both players have drawn cards, give the winning player the pot determined by the fortune card. This means that, the next time we evaluate Step 3, run this arbitrary function that our Fortune card has just created.

Okay, so there's a nuance here! You might be wondering why this is a pre-condition of comparing cards. Consider that, in The Game Of War, when a tie happens, each player draws three cards. Those cards get added to the pot.

So, we might have a particularly crazy Game of War With A Twist (GOWWAT?) in which a player draws a fortune card, picks the high card, but ties with the other player! And has to go back and draw three more cards, and then do a comparison again.

Here's the output of such a game, with these game rules hooked up to a test harness:

 

Player 1 drew a Fortune card!

Player 1 drew 2 of Hearts

Player 1 drew 1 of Clubs

Player 1 drew 11 of Clubs

Player 1 drew 0 of Hearts

Player 1 drew 7 of Hearts

Player 2 drew a 11 of Clubs

Draw! Drawing three cards...

Player 2 drew a 1 of Clubs

Player 1 drew a 12 of Spades

Player 1 wins the Fortune pot!

Player 1 wins with 12 points!

So, we have a somewhat tricky design that allows us to deal with some rather tricky cards. In this implementation, the gameplay is almost entirely mutable. We can take a rather mundane concept and mutate it to add flare.