Design Patterns Employed

One of the main goals of the project was to explore the use of Design Patterns in the development of a CSG. I will briefly list the design patterns used in the project. Each of the Design Patterns will be described: its intent and applicability. It will be shown how each of the described Design Pattens was used in one or more of the sub-projects.

[note all quotations are from: Design Patterns {isbn: 0201633612}]

 Strategy:

Intent: "Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it." (p. 315)

Applicability: "many related classes differ only in their behavior. Strategies provide a way to configure a class with one of many behaviors." (p. 316)

The MunchkinSimulator used the Strategy pattern to simplify the class hierarchy of the monster cards. Each monster adheres to the interface BadStuff. The behavior of the monsters varies in the implementation of doBadStuff(Player). The use of a BadStuff Strategy allows monster behavior to vary without subclassing.

 Decorator:

Intent:  "Attach additional responsibilities to an object dynamically. Decorators provide a flexible alternative to subclassing for extending functionality." (p. 175)

Applicability:  "To add responsibilities to individual objects dynamically and transparently, that is, without affecting other objects." (p. 177)

Fluxx used a hybrid Strategy-Decorator pattern to modify the game's ruleset at runtmime. Each phase of the turn was implemented with a rule Strategy. By adding Decorator functionality to the rule subclasses, the basic rules could be augmented or overridden by rule added (at runtime) later in the game.

 Composite:

Intent: "Compose objects into tree structures to represent part-whole hierarchies. Composite lets clients treat individual objects and compositions of objects uniformly" (p. 163)

Applicability:  "you want to represent part-whole hierarchies of objects."  "you want clients to ignore the difference between compositions of objects and individual objects." (p. 164)

Palace used a Composite structure for interactive element of the graphic interface. This allowed the mouse handler to treat the entire play area as a cohesive object. By providing the top-level component with a select message (with x and y coordinates) the appropriate sub-component would be returned. Similarly drawing was accomplished with a single call to the top-level component's draw method.

 Visitor: 

Intent:  "Represents an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates." (p. 331)

Applicability:  "many distinct and unrelated operations need to be performed on objects in an object structure, and you want to avoid 'polluting' their classes with these operations." (p. 333)

Visitors were used in Palace to modify both drawing and selection. The visual-interactive toolkit designed for Palace left selection and drawing to the discretion of the composite object. Rather than alter the underlying behavior of the visual-interactive toolkit, Visitors were used to traverse the composite. The Visitors modified the drawing and selection behavior to change the drawing order and allow multiple selection respectively.

 Proxy:

Intent:  "Provide a surrogate or placeholder for another object to control access to it." (p. 207)

Applicability:  "Proxy is applicable and ever there is a need for a more versatile or sophisticated reference to an object than a simple pointer." (p. 208)

JAAC used Java's reflective Proxy class to wrap game-state objects. When a method was invoked on the wrapped object, the Proxy object would inspect the Method object associated with the invocation. Methods tagged with an "Undoable" annotation would be wrapped in Command objects.

 Command:

Intent:  "Encapsulate a request as an object, thereby letting you parameterize clients with different requests,  queue or log requests, and support global undo operations." (p. 233)

Applicability: "Specify, queue, and execute requests at different times. A command object can have a lifetime independent of the original request." "support undo.  The command's execute operation can store state for reversing its effects in the command itself. The command interface must have an added Unexecute operation that reverses the effects of a previous call to Execute. Execute commands are stored in the history list. Unlimited-level undo and redo is achieved by traversing this list backwards and forwards calling  Execute and Unexecute, respectively." (p. 235-6)

JAAC used Command objects to bring together Java's reflective Method objects  with the invoking object and the parameters passed to the method. The methods that were wrapped specified an inverse method in a Java Annotation, which was retained at runtime. The commands were passed to an executor, executed and then stored in a history. This provided rollback functionality upon which min-max and depth first search algorithms were implemented.

Applications in Brief

My work on the project is broken into four sub-projects. From each project an application was produced; the fourth project has two applications. The four sub-projects are: the MunchkinSimulator, Fluxx, Palace and JAAC. A brief description of the application or applications produced for each sub-project is given below.

The MuchkinSimulator implements a simplified version of Munchkin by Steve Jackson Games. MunchkinSimulator implements the full turn-structure from Steve Jackson's Munchkin together with four types of simplified cards: items, one-shots, monsters and curses. The simulator is non-interactive. The game is played by six computer players, which are controlled by random agents. The simulator produces text output, which relates each of the player actions together with all the game events.

The Fluxx application is an implementation of the game Fluxx by LooneyLabs. Fluxx is implemented as a text based game. Fluxx supports both computer and human players. It may be run as a non-interactive simulator or as an interactive game. All but three or four cards were implemented: "X=X+1", "Double Agenda" and "Reverse Order".

Palace is a free-form graphical application. It implements a traditional deck-of-52 game. It represents the playing area with pseudo-depth, allowing cards to overlap and be dragged across the top of the play area. Each of the play areas (i.e. deck, discard pile, hand) may be freely moved within the window by the user at run-time.

JAAC (Java Annotations for Aspect-oriented Commands) has two distinct applications. Both applications have both text and graphical interfaces. The first is a tictactoe game. The second is a Sudoku solver. In the tictactoe application the user plays against a min-max computer player.

The sudoku solver employs a nishio solving strategy, which is similar to depth-first search. The user may load a puzzle in a string representation or fill in the squares of the puzzle.

Motivation

This is a bit of a rehash from previous posts, but I wanted to lay this out clearly and by itself. 

What was the motivation for the project, and what's interesting about it? 

In short, the motivation for the project as a whole was to investigate software technologies, and development strategies toward the production of a card-based strategy game (CSG).  CSGs differ from traditional strategy games; the majority of the rules in a CSG are delineated on the cards. The consequence is that not all of the rules are in effect at the start of the game, nor may all of the rules with which the game started remain in effect throughout the remainder of the game.

What makes this an interesting software problem is variability. In a nutshell, variability is the defining attribute of a software system, which implements a CSG. The behavior of the cards in a CSG usually differ greatly, even if there is a common interface to which they adhere. This accounts for variability at design-time. There is, further, the need to support run-time variability. The rules defined on the cards may override or alter the base rule-system or those defined on other cards.

To support variability in the software Design Patterns were employed in the project development. In particular the behavioral Strategy Design Pattern was used in the Munchkin Simulator. In conjunction with the Strategy, the Decorator pattern was exploited in Fluxx. Palace employs the Visitor pattern. JAAC makes use of the Proxy and Command patterns. 

Progress & Digression

The following is an overview of what I have been working on, where I started, where I am and the way I got here.

Note: Below I refer to a card game, which I know as Palace. There are, however, quite a few names for the game. The best link that I've found refers to it as 'Shithead.' Sorry about the profanity, but it is a good description of the game.

My initial goal was to implement Munchkin. This digressed into the near complete implementation of Fluxx. Testing Fluxx lead to the desire for a graphical interface, which in turn lead to work on a card game called Palace. A good way into Palace, I decided that I'd like to look at using Java annotations to add semantic data about undoing in-game actions--a problem that I had in the back of my mind when I was working on the initial Munchkin mock up.

Towards Munchkin, I had made a mock up, which ran through the basic turn / phase structure of the game. It allowed for the use of basic items, one shots and monsters with varying bad stuff. Trading and help were not implemented. There was a concurrent effort to work on some to the more subtle details of the game in a test driven environment. I also made a hybrid design pattern, which I referred to as a Strategy Decorator. This pattern allowed the behavior of a game object to have several chained modifications applied at run-time, but how enforce a particular order of operations for these modifications remains a bit fuzzy.

Given the fuzziness, which was somewhat generalized, I decided that it would be prudent to get some perspective by working on a card game that was a bit more simple than Munchkin. I decided on Fluxx. This went along fairly smoothly and employed some of the tools developed during Munchkin efforts. The turn structure was a list of "rules" that were followed by each player. Testing for the game was about the same as was used in the Munchkin mock up: random act choosing players. I would run the game hundreds or thousands of times in a loop to collect data about the running time and the types of win conditions that ended the various games. A strange glitch came up about once ever four thousand-or-so games, which crashed the program. I didn't figure out how it happened. So I added a text interface, but it was so boring to play that I felt the need to make a graphical interface.

So, I moved on to Palace. Palace, as it stands, is playable and enforces the rules for the game. It is purely graphical and looks fine. The play feels comfortable, but I'm the only person to have tested it. There is no computer player, it's only two player and the hands are open. I left off of Palace while looking into adding a variety of potential features: network play, more players, some animation and / or refactoring the code to adhere more closely to my goals for Munchkin. Palace was put on hold to pursue an idea that I had for recording and undoing method.

I was familiar with Java reflection and knew that you could get a proxy class that passed method calls from a wrapped object to the proxy as method objects. This is provided in the java.reflection library. I had, further, read about the, then new, annotations that got added in Java 1.5, which allowed for supplemental class data to be retained at runtime. It seems that these could easily be used together to add brief semantic tags to indicate the necessary method to call to undo the tagged method. So, I wrote a couple of test programs to try out my ideas. I wrote a tic-tac-toe game, which uses the recorded method calls to implement a simple min-max computer player. I also wrote a sudoku solver, which uses the same methods to follow a nishio solving technique (similar to depth-first search).

The source for the undoable actions and the sample applications can be found here.

Right now, I am finishing up graphical interfaces for the tic-tac-toe and sudoku programs. I wonder whether to digress further--I'd like to see if the undoable commands would hold up in real-time in an Asteroids clone--, or backtrack to Palace, or to wrap-around back to Munchkin.

In Whole--More or Less

This is a really long post. I offer it, because it is what this blog is about--collecting ideas for games in general and Munchkin in particular. What is follows is the proposal that I submitted just about 3 years ago. I still like the idea. The design seems, in retrospect, confused--but not without virtue. The schedule was a farce--I've omitted it, but I'll tell you that everything was supposed to happen in a semester, which it did not. The background has advanced; Firemox (or the Magic Project) would be a a more current example of what I'd like to achieve. I don't know what I thinking with the Agile/XP comment--I think that the words were intoned in a voodoo sort of way; I think that I meant that it would all happen fast. Here it is:

Master’s Project Proposal: 8-16-05

An Implementation for Munchkin

Student: Kevin Becker
Faculty Advisor: Stephen Houser
Project Time: Fall 2005

Abstract

The purpose of this project is the implementation of a card-based strategy game. Card based strategy games have the general quality that the rules of the game are delineated on the cards. This lends mutability to the normally static nature of a game’s rules; over the course of a game, rules are added with the inclusion of cards into the play and removed form the rule-set with the removal of cards from play. The goal is to create a generalized core structure for player interaction with the rule-set, which would accommodate the introduction of new rule-sets. The general design approach will be an Object-Oriented analysis together with an analysis of applicable Design Patterns. The implementation will follow Agile programming practices.

Introduction

The game to be implemented is Munchkin by Steve Jackson Games . Munchkin is a light-hearted parody of fantasy role-playing. One of the characteristics of rules that govern play (of Munchkin in-particular, and card games by Steve Jackson in general) is novelty of interaction. This aspect of novelty occurs in card distribution: most of the cards in the deck (of about 80) are unique, and in rule application; a card may refer to an attribute contained by only a couple of other cards in the deck.

Although Munchkin is a stand-alone game (all of the rules , and cards come in one box and are playable without further expansions), two expansions have been released, and Munchkin is compatible with three other similar games released by Steve Jackson Games.

The use of design patterns promotes reuse by component composition and loose coupling objects within a software system to manage design and system extensibility. Component composition employs composite objects to vary object structure and behavior. This can be contrasted with a focus on the primary use of inheritance to provide variation between similar types of objects.

This approach is highly applicable to the implementation of a game like Munchkin. The complicated nature of the rule-structure would quickly become unmanageable for a procedural or a tightly coupled Object-Oriented approach. Decoupling of game objects and mediating interaction between objects reduce the complexity of and increase the flexibly of individual game components.

System extensibility is achieved through the reuse of existing light weight components and the ability to vary the construction of existing composite objects with the introduction new component classes.


Background and Related Work

Most of the card-bases games online are collectable games. Collectable card games (CCGs) periodically release new batches of cards for use with the previously released cards. Further, most companies focus on a single game. Most similar to this project are two smaller enterprises: CCG Workshop and GCCG.

CCG Workshop is an online gaming community the client is called the gatlingEngine. The client is an interpreter for a proprietary markup language and scripting language. The scripting language is supposed to allow the automation of any rule event, “However, there are a handful of games available to play that are completely automated.”

GCCG is open-source project hosted by sourceforge written in C++, has a lot of focus on network architecture and card trading. It is meant to be a generic system for CCG's. There does not seem to be implementation for the interaction of the rules described on individual cards, but rather on layout and legal deck composition.

Neither GCCG nor CCG Workshop seem to focus on rule-structure as the starting point in design. Both appear to focus on managing a collection of cards, chat and trading, and network infrastructure. The rules of the games that are played are left to the players understand and follow at their discretion. The focus of this implementation is to begin with a complete and flexible rule structure upon which further layers can be built.

Design Approach

The nature of cards based games is mutability. Turn-order may change; phases (the sub-component of a turn) may be played out of turn. The general rules of the game may be over-ridden by cards, which are brought into play; these rules in turn may be modified by new cards that are played.

Given the dynamic rule-system, which governs play, it follows that object-orientation throughout the implementation would be appropriate. Some examples of how game concepts will translate into Design Pattern structures could include:

Turns as Visitors,
Mediator of Rule application,
Composite Rules,
Elemental Rules as Flyweight,
Card Attributes as Flyweight,
Actions as Command.

The primary activity will be mapping game structures and activities into a framework of Design Patterns. With a solid representation of the game in place, higher level abstractions can be developed.

An arbiter, which mediates between player actions and game-state effects can be designed and implemented. This arbiter (the Game Master or GM) can disallow player actions, which are contrary to the rules. The GM can also observe the game-state to delineate legal actions which could be taken.

If the Game master is extended to allow roll-back of actions, this would provide a ground to look-ahead for the effects of a potential action. Above of the Game Master layer Agents can be implemented. Using the Game Master to delineate potential actions and choosing among available options.

Development Methodology

The development phase of this project will be based on the following principles: short iterations, Test Driven Development, simplicity, and flexibility. These principles are largely from the XP/Agile development methodology.

Specific practices will include:

XP / Agile: rapid iterations, consistent metaphor, coding standard, continuous integration.
TDD: no code without a testing strategy, refactoring.
Design Patterns: flexible, extensible, top-down complexification.
Programming by intention (self-commenting, cohesive, loosely coupled)

The GM (described above) is an essential aspect of this project. The support structure for agent implementation is also a root goal of the project. Since these two attribute of the game implementation are fundamental, they should be present from an early iteration, and allowed to evolve together with the game structure.

Over the course of implementation, the system will evolve. Although iterations are delineated in the working schedule, the development process will be somewhat more fluid. Integration and refactoring are central to the Agile methodology.

[Schedule Omitted]

References

http://www.sjgames.com/munchkin/game/
http://www.sjgames.com/
http://www.sjgames.com/munchkin/game/img/rules.pdf
http://www.sjgames.com/errata/munchkin.html
http://www.ccgworkshop.com/
http://www.ccgworkshop.com/gEngine.overview.jsp
http://www.ccgworkshop.com/faq.jsp “Are the games automated?”
http://gccg.sourceforge.net/
http://xprogramming.com/xpmag/whatisxp.htm

Fowler, M., Beck, K..
Refactoring : improving the design of existing code. [Chapter 4.]
Reading, MA : Addison-Wesley, 1999

Shalloway, A., Trott, J..
Design patterns explained: a new perspective on object-oriented design.
Boston, Ma. : Addison-Wesley, 2002


That was it. What's happened in almost 3 years? More reading, a lot of code, some writing. And now I am going to start pulling it together and figure out just where I am.

A Modest Proposal

The following is the abstract from my master's project.

The purpose of this project is the implementation of a card-based strategy game. Card based strategy games have the general quality that the rules of the game are delineated on the cards. This lends mutability to the normally static nature of a game’s rules; over the course of a game, rules are added with the inclusion of cards into play and removed form the rule-set with the removal of cards from play. The goal is to create a generalized core structure for player interaction with the rule-set, which would accommodate the introduction of new rule-sets. The requirements are to be met with two primary structures: the Rule (as a first-class citizen) and the GM. The Rule, as a first class citizen of the program environment, is self-describing and able to be loaded or unloaded from the system at runtime. The GM (for game master), serves as both referee and an impartial observer. The GM is able to verify the legality of an attempted move or delineate possible moves and their effects. The GM encapsulates a layer upon which both player help and agent behavior can be built.

Over the course of this blog I will, for the most part, be collecting the notes that I have written down in my notebooks. My goal is to have material for a requirements document, a final paper, and some ideas for future work.