Game Engine Design: A series of abstractions for better engines.
Abstract:
First and foremost I like to think of myself as a software designer, but often times I like to break this title down a little further and call myself a game designer. Why would I use the term game designer over software designer? Well, because I think in today's day and age the title of software designer is becoming more and more synonymous with getting a software design out the door with great principles in place, but not necesarily with the best design in place. By this, I mean a software designer should know the basic principles of programming and be able to create a relatively decent application, however, they constantly find many management principles sneaking in that begin to erode away the best design.
Game design doesn't necessarily need to fall prey to the same management principles such as resource allocation, harsh time constraints, and feature erosion that sometimes cripple what might have been a great design. Game design, at least for me, is the one type of design where I can be truly passionate, punch off the clock and spend an 80 to 100 hour week making sure the design is perfect and all of the proper principles are in place. Now don't get me wrong, many games do fall prey to the more mainstream design principles that are becoming popular for monetary reasons, but there are a select few companies out there pushing back to produce extremely focused designs (Halo 2 is probably one of the few games where I can say this is probably 95% true).
So with a set of idealistic design principles in mind, I'm going to go ahead and tackle the Tic-Tac-Toe engine that I've blogged about before. Again, I'm choosing this application because the code is relatively simple and I don't necessarily want the code to get in the way of the actual design principles. Most games have complex rule systems that would have to be programmed as part of the engine (even Tic-Tac-Toe has a rules engine that comprises about 30% of the code) and that can often cloud design princples. This article will walk you through the basic real life uses of Tic-Tac-Toe, the design process for creating the engine and the design principles needed, and finally through the actual code to a final assembly that should be able to be used in any other piece of code to present a Tic-Tac-Toe interface.
TOC:
1. What is Tic-Tac-Toe - Examination of the game in the real world.
2. Parts of a Game and a Game Engine - What parts are game and what parts are engine?
3. Game Engine Initialization - Allowing the engine to get set up.
4. From Game Input to Game Progression - Changing game state based on user input.
5. Using the Game State - Checking game states after progression
6. Conclusion - Full code and where to go from here.
1. What is Tic-Tac-Toe
I think that by looking at a game in the real world you can start to understand the concepts of what a game engine should be in the virtual world of computing. With that in mind, how do you go about playing tic-tac-toe in the real world? Well, first you go out and you buy a tic-tac-toe board with the necessary pieces. You can probably find one of these at any toy store. It comes with a full set of rules as well, so if you don't know how to play the game you can try and learn. The point I glean from this is that a game or game engine is nothing more than the necessary pieces needed to play a game. This is actually quite important and we'll be using it again later, so don't forget.
Now that I have my game, I can pretty much play it wherever I want with relative ease. I simpy find another player and we go at it. I can easily play at home, work, or at a party. Of course if you were found playing this much tic-tac-toe people would probably look at you funny, so try to keep it to a minimum.
Time to draw the following analogies:
1. A game in the real world is a standalone component. As long as you have the necessary pieces you can play the game anywhere. A game engine in the virtual world should therefore be able to be easily placed in any piece of software to extend the behavior of tic-tac-toe to that piece of software. This means a true game engine should be portable.
2. A game in the real world generally provides the method for playing the game, the rules describing how the game works, and most likely a presentation layer. However, a game engine in the virtual world is not actually comprised of all these parts. The game engine provides an abstract method for playing the game through code interfaces and enforces any rules, but should be independent of the presentation layer. In a sense, when playing tic-tac-toe on paper, you are behaving as the game engine (your knowledge of how the game is played), while the presentation layer is unimportant (the paper, or a board, or water vapor on some glass).
3. A game in the real world can become unplayable if the rule set is broken or if the state of the game is somehow changed. An example of this might be the train moving your pieces because of some rough areas in the tracks or a small child placing pieces incorrectly because they are uncertain of the game rules. A game engine protects all private data and enforces all rule sets so that the game is always playable.
4. A game in the real world can easily be started, played, examined, and restarted. This means the game engine should have a clean state where all private data is initialized. The game engine should supply methods by which the state can be changed and thus played by some number of players with some method for examining the current game state. Finally, the game engine should be able to be reset to the clean state if possible. Sometimes this last rule isn't adhered to and a new game engine is simply created. Often times in tic-tac-toe you have to simply draw a new board if say using paper and pen (you might say this is in regards to presentation, but in the case of paper and pen for tic-tac-toe the paper is also holding your game state without you even realizing it).
Lots of confusing real-world to game-world analogies are happening, so I'm going to move onto how these analogies actually define various parts of the game engine. Hopefully this peek into the real world hasn't startled any of the virtual hermits with facial tans from their monitors.
2. Parts of a Game and a Game Engine
I want to try and design an entire game here (Tic-Tac-Toe) and then separate out the engine. I'm doing this to show you how important it is to tackle items in a modular way so that your game engine is extensible, maintainable, and portable. Obviously I'm drawing a distinct difference between a completed game and the game engine. Many games today have this abstraction while some of them are sorely lacking any form of abstraction. The basic areas of a current game are:
Pre-Game Setup, this is where a user selects various options and is normally presented with a UI to do so. This can also be done on the command line, through a setup file, through the register, or over a network connection to a matchmaking server. Because this part can be done in so many locations and in so many ways, it should not be part of the game engine. Instead this step should format a piece of setup data that is then passed to the game engine.
Game Initialization, this is where a the setup data is passed to the game engine and it sets internal state. This is part of the actual game engine. Normally code in the pre-game setup creates an instance of the game engine and passes it the user's options directly.
Game State Rendering/Display, this is where the game begins rendering the state to the screen so the user can see the game in progress. This step can be a rich GUI written using Windows Forms, can be displayed within an ASP .NET page using HTML, or done up in 3D with Managed DirectX. Because display can be done in so many ways, it is definitely not part of the game engine, but instead it's own module governing presentation.
Game Input/Play, this is where the user actually plays the game by making moves. Moves are collected by the keyboard, mouse, over the web, from the command line, or piped into the game from some pre-saved input file. All input should be handled in an input module to allow as many forms of input as can is necessary and to ensure that no matter what program this game is put in, the engine can still be re-used. Excel for instance might make use of buttons on the Excel sheet to interact with the game engine. Input is NEVER part of the game engine and all input should be either mapped to actual method calls or formatted into action objects that are then passed to the game engine for processing.
AI, this is where my ideas often do battle with other game designers. I regard AI as nothing more than a part of the previous step. I think that all game AI should think in terms of input actions and game state reads. The human player interacts with the game by visualizing the game state in some manner and also by placing actions into the input queue. This places AI outside of the game engine and on an equal footing with the human player.
Game Progression, this is where user input/actions change the game state and modify the current game state. Since game state is being modified the engine has to own this entirely. Sometimes this step is driven by the engine itself (for example in our example the piece placement code will call the necessary methods to change the game state and check for game conditions) or the step can be driven externally by exporting a method (for instance, a stop game now and tally results button because I'm done and board).
Game State/End Game Conditions, this is where the game state can be examined and where end game conditions can be checked out. The game engine always owns this step and it always owns the conditions in a read-only format. Players or rogue code should never be able to arbitrarily set game conditions or state unless of course you are testing stuff. Generally the state is exported through interfaces or read-only properties of the game engine.
Advanced Features, you are probably wondering where some of the more advanced features come in like network capabilities. Networking in a game is nothing more than intelligently serializing input commands so they can be distributed to all clients. You may also need to intelligently serialize your game state so that it can be remotely viewed. I say intelligently because often times the amount of data can be huge and you have to find ways to compress the information going over the wire. Physics are another advanced feature. I regard physics part of the game engine. At no time does any other module need to do physics work since the game engine can do all the work in a protected form.
So at least now we know what the game engine needs in terms of features. The game engine should be able to initialize itself, control game progession, and provide access to game state and end game conditions. Let's start working on that.
3. Game Engine Initialization
After checking out all the parts in a game, we find that the game engine actually starts during the initialization process. Generally the game engine should be tweaked when it is created by passing in an options structure or by providing a sufficient overload to supply all of the set-up data. Optionally a game can be in a state of being set-up until the game is actually started. The first method is extremely easy to code and doesn't require state variables or post-startup protection code. I'll show examples of both methods in regards to Tic-Tac-Toe.
private static readonly int[,] boardLines = new int[,] { {0, 1}, {3, 1}, {6, 1}, {0, 3}, {1, 3}, {2, 3}, {0, 4}, {2, 2} };
private TicTacToePiece[] boardArray;
private TicTacToePiece firstPiece;
private TicTacToePiece currentPiece;
private TicTacToeState gameState;
private TicTacToePiece winConditions;
public TicTacToeEngine(TicTacToePiece firstPiece) {
InitializeEngine(firstPiece);
}
private void InitializeEngine(TicTacToePiece firstPiece) {
this.boardArray = new TicTacToePiece[9];
this.firstPiece = firstPiece;
this.currentPiece = firstPiece;
this.gameState = TicTacToeState.Initialized;
this.winConditions = TicTacToePiece.None;
}
The code for a setup state is a bit more difficult. In our example above we have a state called TicTacToeState.Initialized. This state basically means the engine is ready to go, but the first move hasn't been made yet. When it has we'll go into TicTacToeState.InProgress. To allow additional setup we'll have to export some properties and protect them with the state flags.
public TicTacToePiece FirstPiece {
get {
return this.firstPiece;
}
set {
if ( gameState == TicTacToeState.Initialized ) {
this.firstPiece = value;
this.currentPiece = value;
}
}
}
I think that this type of code is pretty dirty. Generally, I'd just stick with the one time setup using some form of options class. Always make sure the game engine COPIES the values from this class so that the code passing the class in doesn't change it while the game is running thus messing up PRIVATE game code. Yep, I'm bolding this ENTIRE paragraph since I'm hitting a hugely important point.
Once the game is ready to go you are going to have to start mapping user actions to input. In the case of tic-tac-toe there will be a method that game code can call to play the next piece. Let's see what that looks like.
4. From Game Input to Game Progression
Never let the user directly affect private game data. And by user I mean the actual user, code using the game engine, the graphics engine, or whatever else might think they know what the game should be doing. I say this because it makes adding features to the actual game and the game engine easier. Features are easier to add to the game because the game engine is forced to have a well documented, well defined interface for all engine features. Features are easier to add to the engine because all of the code that interfaces with private engine data is located within the engine itself. This comparmentalization means fewer places to worry about code defects, fewer places for game rules to be broken, and fewer places to change code when game engine state formats change.
We can accomplish this in our tic-tac-toe example by exporting an API for moving pieces on the board. The user is allowed to tell us what piece they want to place and where they want to place it. Either in x, y coordinates or through an offset from 0 to 8. Code calling into the game engine doesn't have to worry about the values the user is selecting or even the piece they are choosing to use. The game engine is smart enough to validate all rules. Are rules will be to make sure the game state isn't modified after the game is already over, make sure the user is trying to place the currently playable piece, make sure the board location is valid, and finally make sure the board location isn't already filled. If all of these are met then we need to go ahead and place the piece.
public TicTacToeEngineResponse MovePiece(TicTacToePiece piece, int offset) {
#region Protect the Game State
if ( gameState == TicTacToeState.GameOver ) {
return TicTacToeEngineResponse.GameOver;
}
if ( piece != currentPiece ) {
return TicTacToeEngineResponse.InvalidPiece;
}
if ( offset < 0 || offset > 9 || boardArray[offset] != TicTacToePiece.None ) {
return TicTacToeEngineResponse.InvalidBoardPosition;
}
#endregion
#region Update the Game State
boardArray[offset] = this.currentPiece;
UpdateGameState();
#endregion
#region Return Success Result
if ( gameState == TicTacToeState.GameOver ) {
return TicTacToeEngineResponse.GameOver;
} else {
return TicTacToeEngineResponse.Success;
}
#endregion
}
We are enforcing the rules by returning error codes back to the calling code. GameOver is one code used to tell the calling application the game has completed and more pieces can't be played, InvalidPiece is being used to tell the calling application they aren't placing the correct piece (this would be unusual), and InvalidBoardPosition points out that the position is incorrect or already taken. The user should be able to make the determination as to which case is in effect by simply looking at the game state (we'll get to that in the next section).
After setting the current piece, we call UpdateGameState. This is where the game actually progresses, all by itself I might add, based on the fact that it accepted a user's move. This method is where all of that nasty game logic is located. The function is responsible for setting a game in progress condition, a winning condition, or a stalemate condition. Rather than using a single enumeration for the game state and the winning state, we instead make use of two properties, one that identifies exactly what the game state is (Initialized, InProgress, GameOver) and one that identifies the winning piece (X, 0, None). This ensures there are fewer game state's to switch on when trying to figure out if the game is actually over (GameOver_Stalemate, GameOver_X, etc... could be an example of combining the winning condition and game state).
Since this code is actually using the rules of Tic-Tac-Toe to establish a winner I'm going to just blast the code in. The important parts are that this function is changing game state based on the current game board state or conditions. All of the logic to decide if the game is over or not is in the engine and nothing is controlled by game modules external to the engine.
private void UpdateGameState() {
// Check all 8 board conditions
for(int i = 0; i < 8; i++) {
if ( PiecesUsingStep(boardLines[i, 0], boardLines[i, 1], this.currentPiece) == 3 ) {
winConditions = this.currentPiece;
}
}
// At this point we might have a winner so set GameOver
gameState = TicTacToeState.GameOver;
if ( winConditions == TicTacToePiece.None ) {
// But maybe not
for(int i = 0; i < 9; i++) {
if ( boardArray[i] == TicTacToePiece.None ) {
// Wait, because we are still going
gameState = TicTacToeState.InProgress;
break;
}
}
}
if ( gameState == TicTacToeState.InProgress ) {
currentPiece = (currentPiece == TicTacToePiece.X) ? TicTacToePiece.O : TicTacToePiece.X;
}
}
private int PiecesUsingStep(int offset, int step, TicTacToePiece pieceType) {
int pieces = 0;
for(int i = 0; i < 3; i++, offset+=step) {
if ( boardArray[offset] != pieceType ) {
break;
}
pieces++;
}
return pieces;
}
The code isn't extremely graceful. There are probably 50 or so ways to implement the tic-tac-toe engine, and this was the quickest way I could see without doing the rolled out code of checking each of the 8 conditions. This is also the easiest way to extend the game to larger board sizes and still keep the same code. Agian, the quick points are we look for a win-state and if so, we set the game engine states appropriately. If not we update the engine to accept the placement of the next piece.
This is important, since a good deal of state is being set. The code on the other side of the engine is going to be interested in this state and they are going to want to display it to the world. The next section will cover all of the necessary marshalling.
5. Using the Game State
Access to the game state can be done in several ways. First the game engine can give the appropriate state back to the calling code if the state is small enough. The response from the MovePiece code does this by either returning Success or GameOver. If the response is GameOver the game could short-circuit to the point where it displays end game results. Better yet, the same state data can be proivded to the game through read-only properties. In most cases, especially sequential games like Tic-Tac-Toe these properties are going to be the method of choice. They can be easily interrogated because the game engine isn't changing and we know that we could spend all day looking at properties and always get the same results.
For data that takes a long time to compile or where large resources are being allocated, you'll want to use methods instead. Methods imply that work is being done whereas properties imply that data is simply being returned. This is a general design principle and not just a game design principle. For places where data needs to be distributed to multiple external modules, eventing can often be used as well. The eventing system in .NET is quite awesome. It allows you to only obtain information about pieces of the data that have changed. In the case of Tic-Tac-Toe a client that has to repaint all of it's UI would use properties to get the state of the full UI, but a client that only needs to repaint changed portions of the UI might only be intersted in the state that changes since that is the only thing it needs to update it's display.
We are only going to use properties. We have a limited amount of data and it isn't really a chore to repaint the entire display whenever a single piece of data changes. We'll be returning information on the current piece to play, the state of the game engine, any winning conditions that might exist, and provide indirect access to the board array.
public TicTacToePiece CurrentPiece {
get {
return this.currentPiece;
}
}
public TicTacToeState GameState {
get {
return this.gameState;
}
}
public TicTacToePiece WinConditions {
get {
return this.winConditions;
}
}
public TicTacToePiece this[int offset] {
get {
if ( offset >= 0 && offset <= 8) {
return boardArray[offset];
} else {
return TicTacToePiece.None;
}
}
}
public TicTacToePiece this[int x, int y] {
get {
return this[x+(y*3)];
}
}
That pretty much covers a tic-tac-toe engine. Is it a game yet? Nope, and that isn't the purpose of this article. In the last section I'll provide the full code.
6. Conclusion
The engine needs a few more pieces to be a full engine. Just the code above won't quite get you there because you lack the various enumerations and possibly some smaller pieces of code that I left out for brevity. The point of the article was to examine a full game engine and what a game engine should look like. A game engine is not a graphics engine, so never get the two confused. The fact that this engine has no graphics is a testament to how well designed it is, not a downfall of the engine itself.
So what could you do with this? Well, I hooked it up to a console application to allow tic-tac-toe from the console. That was actually pretty cool. You could easily hook it up to a Windows Forms application or make it available from an ASP .NET page. I know it can be networked since I have the code here for that as well. I know it can be used for secure gameplay since I also have some code for that. I even know that it is AI accessible, because I have that code as well. Was it hard to write all that code? Not at all. It was easy because I followed the game design principles discussed in the article.
I welcome all comments about this article and any of the concepts I've set forth. I don't claim to have an end all situation, but I've found this model to work extremely well for many development projects, game or software. I'd likely say that this is a process for designing modular software as well (all software can be programmed modularly), but I point to the abstract and quickly identify that this process requires a good deal of time and discipline to do right. A quick scan of my hard drive shows thousands of pages of code where I myself didn't have the discipline to stick with these concepts.
Here is the code, have a nice day. I'll post another article with some usage samples another day.
using System;
public enum TicTacToePiece {
None = 0x0,
X = 0x1,
O = 0x2
}
public enum TicTacToeState {
UnInitialized = 0x0,
Initialized = 0x1,
InProgress = 0x2,
GameOver = 0x3
}
public enum TicTacToeEngineResponse {
Success = 0x0,
InvalidPiece = 0x1,
InvalidBoardPosition = 0x2,
GameOver = 0x3,
GameStillInProgress = 0x4
}
public class TicTacToeEngine {
private static readonly int[,] boardLines = new int[,] { {0, 1}, {3, 1}, {6, 1}, {0, 3}, {1, 3}, {2, 3}, {0, 4}, {2, 2} };
private TicTacToePiece[] boardArray;
private TicTacToePiece firstPiece;
private TicTacToePiece currentPiece;
private TicTacToeState gameState;
private TicTacToePiece winConditions;
public TicTacToeEngine(TicTacToePiece firstPiece) {
InitializeEngine(firstPiece);
}
#region Public Game Engine Methods
public TicTacToeEngineResponse Reset(TicTacToePiece firstPiece) {
if ( gameState == TicTacToeState.InProgress ) {
return TicTacToeEngineResponse.GameStillInProgress;
}
InitializeEngine(firstPiece);
return TicTacToeEngineResponse.Success;
}
public TicTacToeEngineResponse MovePiece(TicTacToePiece piece, int offset) {
#region Protect the Game State
if ( gameState == TicTacToeState.GameOver ) {
return TicTacToeEngineResponse.GameOver;
}
if ( piece != currentPiece ) {
return TicTacToeEngineResponse.InvalidPiece;
}
if ( offset < 0 || offset > 9 || boardArray[offset] != TicTacToePiece.None ) {
return TicTacToeEngineResponse.InvalidBoardPosition;
}
#endregion
#region Update the Game State
boardArray[offset] = this.currentPiece;
UpdateGameState();
#endregion
#region Return Success Result
if ( gameState == TicTacToeState.GameOver ) {
return TicTacToeEngineResponse.GameOver;
} else {
return TicTacToeEngineResponse.Success;
}
#endregion
}
public TicTacToeEngineResponse MovePiece(TicTacToePiece piece, int x, int y) {
return MovePiece(piece, x+(y*3));
}
#endregion
#region Public Game Engine State
public TicTacToePiece FirstPiece {
get {
return this.firstPiece;
}
set {
if ( gameState == TicTacToeState.Initialized ) {
this.firstPiece = value;
this.currentPiece = value;
}
}
}
public TicTacToePiece CurrentPiece {
get {
return this.currentPiece;
}
}
public TicTacToeState GameState {
get {
return this.gameState;
}
}
public TicTacToePiece WinConditions {
get {
return this.winConditions;
}
}
public TicTacToePiece this[int offset] {
get {
if ( offset >= 0 && offset <= 8) {
return boardArray[offset];
} else {
return TicTacToePiece.None;
}
}
}
public TicTacToePiece this[int x, int y] {
get {
return this[x+(y*3)];
}
}
#endregion
#region Private Game Engine Methods
private void InitializeEngine(TicTacToePiece firstPiece) {
this.boardArray = new TicTacToePiece[9];
this.firstPiece = firstPiece;
this.currentPiece = firstPiece;
this.gameState = TicTacToeState.Initialized;
this.winConditions = TicTacToePiece.None;
}
private void UpdateGameState() {
// Check all 8 board conditions
for(int i = 0; i < 8; i++) {
if ( PiecesUsingStep(boardLines[i, 0], boardLines[i, 1], this.currentPiece) == 3 ) {
winConditions = this.currentPiece;
}
}
// At this point we might have a winner so set GameOver
gameState = TicTacToeState.GameOver;
if ( winConditions == TicTacToePiece.None ) {
// But maybe not
for(int i = 0; i < 9; i++) {
if ( boardArray[i] == TicTacToePiece.None ) {
// Wait, because we are still going
gameState = TicTacToeState.InProgress;
break;
}
}
}
if ( gameState == TicTacToeState.InProgress ) {
currentPiece = (currentPiece == TicTacToePiece.X) ? TicTacToePiece.O : TicTacToePiece.X;
}
}
private int PiecesUsingStep(int offset, int step, TicTacToePiece pieceType) {
int pieces = 0;
for(int i = 0; i < 3; i++, offset+=step) {
if ( boardArray[offset] != pieceType ) {
break;
}
pieces++;
}
return pieces;
}
#endregion
}