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.

Thursday, October 29, 2009

Three Wolf Pumpkin

I'm pretty proud of my Halloween pumpkin :)

Thursday, September 24, 2009

Noooo…..

Jeff Dunham has a whole new series, starting October 22.

No.

No.

No.

There are a lot of pains I will accept. 

  • World hunger
  • AIDS in Africa
  • Blasphemy
  • Rising tides
  • Global thermonuclear war
  • Evil, compounded by evil, committing evil against evil, with innocence in the crossfire

But, a bad ventriloquist, with his own show?  No.  This will not stand.

He’s been doing this whole “on a stick” schtick for over 2 decades.  He’s safe comedy, invoking shock to the level that would titillate your older aunt who mocks outrage at the slightest mention of vulgarity or the most timid racial references, like she’s never heard it before.  Jay Leno is more controversial and entertaining… with Pat Morita…

It’s lazy.  I don’t tolerate rewarded laziness.

Monday, May 4, 2009

Mr. Wizard and the Atari Joystick

I found it. I finally found it. After 15 years of having access to the internets, I've finally found this clip.

This Mr. Wizard segment was about 50% responsible for my current career as a programmer. It was my first realization that I could actually understand how computers worked, and could bend them to my will.

Now, clearly, Mr. Wizard is way out of his league here.  It’s the early 80’s and computers are taking everything we knew about science and electronics and shoving them into some tiny little array of microchips.  Science and TV exposure isn’t going to help an old man come to grips with a new world in which a single person can’t possibly understand a technology from top to bottom.

In this clip, we see such basic errors as

  • Radioactive interference – he thought the metal casing shielded the rest of the world from the computer’s television station, rather than outside interference mucking with the computer’s internals.
  • He did get chips vs. their housings concept right (clearly through much coaching).  I have to give him credit there… though, he did call the connections “bumps”, and kind of mumbled off into something about other places… glossing over the difference between ROM and RAM.  Common rookie mistakes.
  • 8-bit computer - thinking 8 chips meant 8-bit, rather than the width of the data bus.  And he thought that each sends a “byte” off to the screen and each little “dot” has to have a signal from each one of them.
  • Input controlling –  it goes through all the little things and goes all over the place… something something…

The man concedes the value of the engineers who put this marvel together.  However, it was the controller stuff that stuck with me most, lodged in my memory for decades almost completely unmolested by time.

Let’s leave aside all the horribly inept aspects of Mr. Wizard’s understanding of computers.  At a very young age, through this clip, I was unknowingly introduced to the idea of abstraction.  It’s the idea that a programmer can rely on the layers below him to make it possible to produce something great for those above him, without fully understanding what’s happening below.

In this clip, it was told to me that controlling video games was as simple as mastering these 5 switches for up, down, left, right and the “start” button.  To make a video game, I just needed to write something to react to up, down, left, right and “start”.

It’s more complex than that, but in a completely different way than the complexity we deal with now.  Inheritance, inversion of control, decorators, database access, html rendering, persistence frameworks… it’s all just flavors of the same concept…  It doesn’t matter where you are in the chain, you’re always a middleman (unless you’re drawing traces in some p-charged well in a substrate… which, even now, is abstracted).  This is what makes this field great.

Somebody always has an interest in the layer below you, and sometimes it’s you who is that layer.  It’s thrilling to use what someone else has done to improve the lives of those above you.  Sometimes, it’s enjoyable to be the top of the software chain making it possible for real-world users to do their job better.

It’s what software people do.  They solve the hard problems so others don’t have to.  We thrive on this.

It reminds me of the old yarn about dwarfs and giants.

"Bernard of Chartres used to say that we are like dwarfs on the shoulders of giants, so that we can see more than they, and things at a greater distance, not by virtue of any sharpness of sight on our part, or any physical distinction, but because we are carried high and raised up by their giant size."

Which brings us to an all-time great comeback by the Gipper.  I’m not sure if it’s genuine, but it’s great nonetheless.

At one campus meeting, a student told Reagan that it was impossible for people of Reagan's generation to understand young people. [The student said] 'You grew up in a different world. Today we have television, jet planes, space travel, nuclear energy, computers.' Without missing a beat Reagan replied, 'You’re right. It's true that we didn't have those things when we were young. We invented them.'"

So, enjoy your frameworks.  Love your languages.  Everything becomes too complex at some point to completely understand from top to bottom.  Rely on those below you to make your tools, and use them to make something better for those above.

Wednesday, March 18, 2009

Take away this kid's screwdriver!!!

Watch this sweet commercial. He's so precocious.



Watch again... Watch it!!!

I know this commercial is supposed to be all adorable and about how the kid is exploring his world of electronics, and his parents have big dreams of his future in the world of computer science. He's taking things apart, learning about computers and electrical systems... I was that kid. I took things apart to see how they worked, and not everything went back together quite right (always had a pile of important looking shit left over).

But he's taking a screwdriver and digging up the traces on the motherboard, before he jams that wretched tool into the IDE and power ports and bends all the pins into a completely unusable state!

He's destroyed what would be, to a consummate computer professional as myself, merely a $100 piece of equipment. But, given his retard parents, he's probably demolishing their entire $1000 Dell desktop with no hope of repair. Say goodbye to all that savings you devoted to Lit 101 and 102!

I want to encourage any kid I have someday to explore his interests. But I don't want him opening the hood to my car, jamming a screwdriver through the fuel line, knifing the timing belt and trying his hand with the wire cutters on the brake lines. That's not learning... it's just vandalism.

Wednesday, February 18, 2009

Fairness doctrine in action

Tonight I gave a chance to a reprehensively bad episode of the new Fox breakout: Lie to Me.  Besides the criminal use of Tim Roth in this one-trick pony of a team of deus ex machina truth detectors, I saw the Fairness Doctrine in action without the need for government intervention.

I saw the team, over the course of an hour, demonstrate the effect of "microexpressions" (in the form of ham-fisted displays of obviousness) to solve their crimes CSI-style.  They even-handedly used images and video of Condoleezza Rice, Donald Rumsfeld and Chief Justice John Roberts, juxtaposed over the hour with videos of President Obama and President Bill Clinton to illustrate examples of people lying.

This show decided to use government officials as example of liars, which is well within reason.  But it knew not to go the now standard Bush-bashing route (oddly, I didn't see any imagery of Bush himself) to sell its product.

It does a decent job of using the weaknesses of our government controlling a message or keeping a secret, but at least it doesn't paint the whole apparatus as an institutional lie factory.

Still… terrible show.

Thursday, February 5, 2009

Just a weapons malfuction... how are you?

Holy Christ, this old guy isn't afraid of death.

Your delta-wing plane has no engines. Physics dictates that you and your passengers are doomed to a fiery death. How do you deal with it?

Apparently, when you're a millionty years old... calm and composed.




Hats off, of course. Enough crazy has happened in the last couple of weeks to wipe clean the achievement of a perfect water landing (in layman's terms, a horrific firey drowning exercise). But the composure of not only the pilot jarting headlong into hydro-doom... but of the air traffic controller executing emergency procedures and activating emergency response in the unlikely event that some star child were to survive the splashdown. Wow... just, wow. How are you?



My favorite part is the guy on the edge of the wing falling into the water. When you're the considerate nice guy first out of the plane, you walk to the furthest edge of the wing. What's your reward? Wet coldness with your life-raft (read: AirBus 320) floating away. I feel for you, Properly-Walking-To-The-End-Of-The-Wing-Guy.

Awwwww

We give trophies to dipshit kids for losing every game in the season.

Then, this happens. Sometimes, the most inspiring things come from the least exceptional of us.



This gives me a happy.