Design Patterns for Games Dung (“Zung”) Nguyen and Stephen B. Wong Dept. of Computer Science Rice University Houston, TX 77005 [email protected], [email protected] Abstract Designing a two-person game involves identifying the game model to compute the best moves, the user interface (the “view”) to play the game, and the controller to coordinate the model and the view. A crucial task is to represent the algorithms used in their highest abstract forms. This can prove to be a difficult and subtle endeavor. It is made easier however by the use of good object-oriented (OO) design principles to help maintain a high level abstract viewpoint during the design process. The state pattern is used to represent the game board and is coupled with the visitor pattern to provide state-dependent, variant behaviors. The min-max algorithm and its variants are implemented as the strategy pattern, which allows flexible and extensible computational capability. Careful analysis is performed to properly abstract the interactions between the model and the view. The command design pattern is used to provide callback services between the model and the view. Leading students through this design process enables them to learn algorithms and architectures that easily scale to full-sized applications. 1 Introduction Standard data structures and algorithms courses cover game trees, and in particular, the min-max principle, to compute the values of the game tree nodes and select the best next move. Even though these algorithms are initially described in high-level abstract terms, this is not reflected in their standard implementations (See for example, [1].) Instead the algorithm code is intertwined with low-level game board implementation details. This not only obscures the essence of the solution, but also makes it impossible to re-use in different types of games. Students end up writing essentially “throw-away” code. To remedy this situation, we seek to design an OO model for two-person games that enables us to express all facets of the games at the highest level of abstraction. The result is a system of cooperating objects that possesses many of the valued qualities in software engineering: correctness, robustness, extensibility, flexibility, and reusability. We lead students through this design process to teach them about abstract problem decomposition, how design patterns can shape their thinking in OO design, understanding system architectures, and expressing algorithms in their most abstract forms. We apply the Model-View-Controller (MVC) pattern to the overall architecture of the program. The MVC pattern calls for decomposing the overall system into three subsystems: the model, the view, and the controller. Section 2 details the analysis of the model, which consists of the game tree and the various algorithms that compute the next moves from a given tree node. Section 3 focuses on the interactions between the view and the model and the interfaces through which they communicate. And finally in Section 4, we illustrate our design with the familiar game of Tic-Tac-Toe. We should stress here that the development of an OO game system must be part of a larger OOP/OOD pedagogy. Before starting such a project, students must be versed in basic OO principles as well as the core design patterns such as the state, strategy, command and visitor patterns [2]. 2 The Model In this paper, for simplicity, we will restrict our discussion to two-dimensional game boards, with only two players. The rules of a game define the legal board configurations plus the winning and the draw (if any) configurations. They are encapsulated by an interface called IBoardModel, which abstractly “knows” how to transition from one legal board configuration to another and reject any request for an illegal move. Different concrete implementations of IBoardModel represent different types of games. There are a variety of algorithms to compute the next move from a given board configuration. They are abstracted into an interface called INextMoveStrategy. The pair, IBoardModel and INextMoveStrategy, and their interactions constitute the model of the game. A single game management class, GameModel, that holdsinstances of the above two interfaces can represent the total game. The relationship between GameModel and INextMoveStrategy is called the strategy pattern. Separating the rules of the game and the strategy to make a move in this manner provides the flexibility to apply the same strategy to different types of games, and vice-versa. The discussion that follows will further elucidate this point. The interaction process between IBoardModel and INextMoveStrategy is independent of whether the game is Tic-Tac-Toe, Othello, checkers, go, etc. The interaction between the players (human and/or computer) and the board can thus be expressed in abstract terms. The player requests to make a move, which the board either accepts or rejects. Once the move is accepted, the game progresses into one of several states. These states, which are states of the board, and not of the overall game management process, are that player #0 has won, player #1 has won, the game is a draw, or that the outcome has yet to be decided. The game then proceeds in a manner that depends on the current state of the board. This includes terminating the game, or requesting that another move be made. Invalid Move State Non-terminal State (No winner yet) Player #0 Wins Player #1 Wins Draw Game Terminal States Valid Move State Figure 1. Game board state diagram The overall state diagram of the board in Figure 1 shows that the board consists of both concrete states and superstates. The state design pattern can be used to model these states. Superstates are depicted as abstract super-classes of the concrete states they contain. At the top level of the hierarchy is an interface called IBoardState. The visitor design pattern is used to provide state-dependent abstract behaviors (For a complete discussion of this technique, see [3]). The visitor interface IBoardStatusVisitor, contains methods corresponding to the various states of the game board and the board provides a means for executing (“accepting”) those visitors. Only the method associated with the current state of the board is called when the board accepts the visitor. While it is extremely important to understand the state nature of a problem before