In this step we use C++ to complete the implementation of a very simplified Candy Crush game. The implementation allows game play to be suspended and restarted by serializing current game state to a file and later deserializing back into a running instance. In the next assignment we will send serialized game state over the Internet, allowing the display to be separated from the game logic. In the final step, we will modify the now "headless" game logic to play the game, replacing the human player with software chosen moves. We introduce some terminology (that we made up) that will help in the discussion that follows.
We call the patterns of like colored candies used to modify the board templates. Example templates are three in a row horizontally and four in a row vertically. When some portion of the board matches a template, the template fires. Firing causes each candy in the cells matching the template to explode, leaving an empty cell. Empty cells are filled by sliding adjacent cells into them. We describe that as gravity. In this homework gravity always draws cells in a single direction, down towards the bottom of the screen (which is row 0 of the board).
Settling is the process of performing all possible template firings until the board contains no template patterns. We admit here that it is conceivable that some board may never settle, but defer discussion of that situation to a later section.
To keep development effort contained, we define a very simple version of the game. Like the actual game, a move is a swap of a candy with an immediately adjacent candy (in the four NEWS directions). A move is allowed only if it results in at least one template firing.The only templates our game has are three in a row, horizontally and vertically, and four in a row, horizontally and vertically. We have only one kind of candy, which we call regular. When a regular candy explodes it empties only the board square in which it resided. (There are no striped candies, bombs, or other more exotic candies, although the design anticipates them as extensions.)
To win the game, the player must cause each square of the board to experience candy explosions some specified number of times. We call the number of remaining firings the state of that square, and use board state to mean the states of all squares. As an example, if the initial board state has value 1 in all squares it corresponds to something like each square being covered with jelly. The objective of the game is to remove all the jelly by causing at least one explosion in each square.
At this point, the game has no objective - you just play until you stop.
Many parts of the specifications for this project are affected by our long term goals. We imagine reaching a point where your software would upload to our server both a next move and the game state resulting from taking that move. We'd like to be able to verify that the state you provide is in fact the one reached when your move is taken. To do that, the changes to the board resulting from taking a move must be deterministic, so that you and we compute the same resulting state.Achieving deterministic play requires that we specify many details. We do that later in this write up. For now, we focus on one particular issue: when candies explode, the candies above them slide down, effectively moving the empty board squares to the top row. New candies must be generated to fill those empty squares. For our purposes, the candies that slide in from the top must be chosen deterministically.
We do that by defining the extension board. The extension board has the same number of columns as the game board, but has (potentially) many more rows. The extension board supplies the candies to slide into the game board.
For instance, if a game is played on a 3x3 board, the extension board might be 7x3. The game board is initially empty, and so the first three rows of the extension board are slid down into the game board by gravity. If three candies in column 0 explode, the "next three" candies in column 0 of the extension board (i.e., those in rows 3, 4, and 5) are slid into the game board. If the game lasts long enough to have slid in all the candies in some column of the extension board, you start over again at row 0 of the extension board for that column: if three candies in column 0 explode again, you slide in candies from rows 6, 0, and 1 of the extension board.
Note that row 0 of the game board is the one displayed at the bottom of the window. In our figure above, the rows of the game board are as they should be displayed on the screen. Gravity heads down on the screen, so towards row 0.
Our serialization defines three components. At the top level is a game instance. It is simply a container for the a game definition and, optionally, a game state. An example serialization of a game instance (for an unrealistically small 2x2 game) is shown here:
{ "gamedef": { "gameid" : 12345,
"extensioncolor": { "rows": 8,
"columns" : 2,
"data": [0, 1, 2, 3, 4, 5,
0, 1, 2, 3, 4, 5,
0, 1, 2, 3]
},
"boardstate": { "rows" : 2,
"columns" : 2,
"data": [1, 1, 1, 1]
},
"colors": 6
},
"gamestate" : { "boardcandies" : { "rows": 2,
"columns" : 2,
"data" : [ { "color": 0, "type": 0},
{ "color": 1, "type": 0},
{ "color": 2, "type": 0},
{ "color": 1, "type": 0}
]
},
"boardstate" : { "rows": 2,
"columns": 2,
"data": [1, 1, 1, 0]
},
"movesmade": 4,
"currentscore" : 142,
"extensionoffset": [2, 2]
}
}
The game definition defines the game, before any moves have been made. The game state describes the game while being played.
Game Definition
Game State
A game instance serialization may contain only the gamedef object, and no gamestate object. That is a valid serialization. In such cases, the initial game state can be derived from the game definition.
The initial game state is derived from the game definition by applying gravity and then settling the board. The score is updated by any template firings that takes place during this settling.Settling must be performed in a particular way. Templates have priorities. Templates are applied to the board one at a time, from highest to lowest priority. The priority order is four in a row vertically (vFour), four in a row horizontally (hFour), three in a row vertically (vThree), and three in a row horizontally (hThree). This means that the entire board is searched for applications of vFour before any other templates are considered, etc.
There can be candies on the board that allow more than one firing of a single template. For instance, a vertical run of five candies of one color admits two distinct vFour template firings. We resolve that ambiguity by requiring the search for template matching be done in row major order, starting with row 0. As each row is traversed you try to match the template currently under consideration in a way that it contains the current square of the traversal. As an example, settling begins by trying to match vFour on square [0,0]. You then try on square [0,1], [0,2], etc., until you reach the end of the row, when you move to [1,0] and traverse that row. When you have searched the entire board you move to template hFour.
All templates firings are performed before gravity is applied. We call that one step of settling. At the conclusion of each step, a new step is started. This process continues until there is a step in which no templates have fired.
It's possible that the board will never settle, but will instead go into a settling loop. (For example, imagine an extension board that contains only a single color.) To guard against that, we arbitrarily bound the number of steps taken during settling at 1000.
There are two issues you're likely to face in building this project, due to mixing C code (from HW2, jansson, and GTK) with C++ code (your solution to this homework). One is related to mangled names. The other involves callbacks.Problem 1: Mangled Names
As mentioned in class, C++ allows polymorphism by mangling method names. It rewrites the method's name into a new name that reflects the types of the arguments and return value, so that the same programmer assigned method name results in distinct names as seen by the linker, even when polymorphism is used. As an example, consider this code:
int sub(float f);
int func() {
return sub(2.0);
}
When compiled in C (using gcc) the two function symbols in the
resulting .o file are sub and func. When compiled
as C++ (using g++), the two function symbols are _Z3subf
and _Z4funcv. This means that if you compile a method in C
and then call it from C++, you'll end up with linker errors, because
C++ will generate a call to the mangled name but C won't have
produced a method with the mangled name.
Problem 1: Solution
The solution is to inform the C++ compiler that some methods you'll be calling are C methods. You do that with syntax like this:
extern "C" {
#include "hw2.h"
}
That prevents the C++ compiler from mangling the names on calls to the methods
declared within the braces.
Problem 2: Callbacks
Your HW2 code and the GTK+ library both use callbacks. In both cases you pass a function pointer to them to tell them what method to call. GTK+ additionally lets you pass a single pointer that it will then pass back to the callback function. One problem is that a single callback argument probably isn't enough. A second problem is that, when using C++, the callback you want is likely to be a method invoked on some object. The C code you're using that invokes the callback obviously doesn't support that. (For instance, you can't get GTK+ to invoke a method on an object.)
Problem 2: A Solution Approach
The basic approach is to provide an adapter function that can be called as a C function and then makes a C++ invocation on an object. To do that, it needs a pointer to the object it will invoke the operation on, as well as arguments to provide. You achieve that by having the single pointer GTK+ provides to the callback function point at a struct that contains all the information your adapter needs. When you register the callback you give the adapter as the callback function and the pointer to the struct as the pointer argument to the callback.
One not very nice complication of this approach is that you need to free the structures used to convey the arguments to the adapter functions. That requires figuring out when they can be freed. It's not hard, but it makes the adapter approach a bit cumbersome.
Your adapters can be implemented either as regular methods, outside of any class, or as static methods of some class. Either works, but I find static class methods aesthetically cleaner.
File hw4-sample-solution.tar.gz [V1.0.01] contains everything that we provide. We provide:
Why do candies sometimes display different color backgrouns backgrounds in the sample solution?
Do I have to be able to create serializations of the in-memory game instance object?
Yes. The specification of this homework doesn't say anything about how the user can cause a serialization to be written, and we don't much care. But, the next project will be sending serializations over the Internet. You want to write the serialization code as part of this project, and not wait to the next one. (The sample executable always writes a serialization to file test.out as it terminates.)
How in the world will you grade this?
In person grading is our salvation.