Honor Code

We value academic integrity very highly. Please read the Honor Code section on our course webpage to make sure you understand what is considered as plagiarism and what the penalties are. The following are some of the highlights:

• Do NOT try your "luck" - we use sophisticated plagiarism detection software to find cheaters. We also review codes for potential cases manually.
• The penalty (for BOTH the copier and the copiee) is not just getting a zero in your assignment. Please read the Honor Code thoroughly.
• Serious offenders will fail the course immediately, and there will be additional disciplinary actions from the department and university, upto and including expulsion.

Objectives & Intended Learning Outcomes

The objective of this assignment is to provide you with practice on arrays, functions, and recursion. Upon completion of this assignment, you should be able to:

1. Define and use arrays to store data
2. Modularize your program in functions
3. Describe how to do file input/output
4. Develop recursive functions to solve computational problems

"Candy Crush" is an example of a Match-Three game
Source: https://en.wikipedia.org/wiki/Candy_Crush

Introduction

The goal of this assignment is to implement a text-based "match-three" game. You can check this Wikipedia link here for a historical overview of this genre of games. The rules of the game are as follows:

• The player is presented with a randomized 9 x 9 grid, each tile containing a single digit from 1 to 6.
• In each turn, the player swaps two (horizontally or vertically) adjacent tiles.
• After each move, the game looks for "matches" and processes them:
  • A match is a sequence of three or more consecutive identical items in the same row or column.
  • Each match will be removed. Items above the removed tiles will be shifted down to take up the space, and new items will be created at the top.
  • Each removed tile increases the player's score by 1.
  • The above process is repeated until no more matches exist in the 9 x 9 grid.
• The player's goal is to get the highest score possible under a finite number of moves.

In this assignment, you are required to:

• Implement the game mechanisms outlined above; (Tasks 1, 2, 3)
• Implement a solver, which considers all possible moves and return the move that will result in the highest gain in score. (Tasks 4, 5)

Description

Please read the FAQ section for some common clarifications. You should check that a day before the deadline to make sure you don't miss any clarification, even if you have already submitted your work by then.

Coordinate system

The map is the data structure that records the current position of items in a game. The position of items within a map is initialized from a given input file, and updated accordingly during the game. It is further divided into two regions:

• The bottom part of the map is called the active area. This is the section of the map visible to the player; they can only swap tiles within this region, and only matches within this region will be removed.
• The remaining part is called the hidden area. These tiles will move downwards into the top of the active area whenever matches are eliminated.

In each game, the map is represented by a global 2D array int map[MAX_ROWS][WIDTH]. The following diagram illustrates the structure and coordinate system of the map:

In this assignment, we always set WIDTH = 9, HEIGHT = 9, and MAX_ROWS = 81. Note that the origin is at the bottom-left corner, so the first row map[0] refers to the bottommost row of the map (and the active area).

Project structure

The skeleton project structure is as follows:

PA1
├── game.cpp
├── game.h
├── main.cpp
└── map.txt

main.cpp contains the game interface; game.cpp and game.h provide functions for various game mechanisms; and map.txt is a sample map file. Your job is to complete five functions game.cpp so that the game will function properly. The purposes and specifications for these functions are documented in the Tasks section.

Since you will be asked to submit the completed game.cpp only, making modifications to game.h and main.cpp is strongly discouraged.

Solver

You are required to write a greedy solver that returns the optimal move at the current stage. The solver considers all possible next moves, and return the move that results in the biggest score gain.

When there are multiple candidate moves that lead to the biggest gain, the solver should recursively solve for the best subsequent move for each candidate move, and choose the candidate that can result in the biggest total gain.

Note that as with other greedy algorithms, such a solver do not always return the "actual" optimal move. It is possible that a move with a small gain could lead to another move with a much higher gain in the next round. Nevertheless, it is computationally infeasible to consider too many steps at once, and this greedy solution should produce reasonable results for our purposes.

Gameplay

During each round, the game interface displays the current active area, player score, and no. of remaining moves. The latter two are stored in the global variables score and remaining_moves, defined in game.h. Initially, each player has a score of 0 and a total of 12 remaining moves. The console then asks the user enter one of the below commands:

• swap x_pos y_pos direction - swaps a specific tile with its neighbour in some direction.
• solve - invokes the solver to get the optimal move for this round, and execute this move.
• quit - quits the game.

Additional Remarks

• All console I/O formatting is handled by the skeleton code, and ZINC grading will be done via direct testing of the game state variables and function return values (Unit Testing).
• You are allowed to define your own helper functions, but be careful as ZINC won't be able to know of their existence. This shouldn't be a problem as long as the changes to the game state variables and task function return values are as expected.
• All the task functions are in global scope, and you are allowed to have the task functions call each other for easier implementation. Be careful when two or more functions call each other reciprocally, as they may enter an infinite loop.
• You are free (but not strictly required) to use recursion in any of the task functions. Some recursion hints are given in the tasks, but otherwise the final decision is up to you. Avoid accidental infinite recursion.

Tasks

This section describes the functions that you will need to implement. Note that some parameters are used for function output, i.e. the objective variable is passed to the parameter by reference, and is subsequently modified by the function.

Task 1 - Implement the findMatches() function

Description - Find all tiles that belong to a match; these tiles will be removed at a later stage.

int findMatches(int map[][WIDTH], bool matches[HEIGHT][WIDTH]);

Parameters

• int map[][WIDTH] - Input - game map.
• bool matches[HEIGHT][WIDTH] - Output - 2D boolean array indicating the position of all tiles that are part of some match.

Return value - Number of matched tiles.

Notes

• Do not mark tiles with the value 0 as a match. These indicate placeholder tiles, which are inserted into the map when an entire column of a map is used up and there are no more tiles to draw from. (See Task 2 for more details.)
• While the entire map is passed into this function, only consider matches completely within the active area.

Task 2 - Implement the processMatches() function

Description - Find all matches using findMatches() and remove them. Then, update the game map by shifting tiles downwards to fill up the removed space. Since new matches may exist after updating, recursively call this function until there are no matches on the map.

int processMatches(int map[][WIDTH]);

Parameters

• int map[][WIDTH] - Input - game map.

Return value - Total number of matched tiles, including recursive calls.

Notes

• If no matches are found, simply return 0. This is the base condition for recursion.
• After shifting tiles downwards to fill up the removed space, there will be empty space at the very top of the map. Fill up these tiles with the value 0 as a placeholder value.
• The provided code uses the return value of this function to obtain the increase in score after each move.

Task 3 - Implement the swapTiles() function

Description - Swap two tiles in the map.

void swapTiles(int map[][WIDTH], int x1, int y1, int x2, int y2);

Parameters

• int map[][WIDTH] - Input - game map.
• int x1 - Input - x-coordinate of the first tile to swap.
• int y1 - Input - y-coordinate of the first tile to swap.
• int x2 - Input - x-coordinate of the second tile to swap.
• int y2 - Input - y-coordinate of the second tile to swap.

Task 4 - Implement the considerMoves() function

Description - Given the current map, consider every possible move and return the candidate move(s) that increases the score by the most.

int considerMoves(int map[][WIDTH], int candidate_moves[][4], int& num_candidate_moves);

Parameters

• int map[][WIDTH] - Input - game map.
• int candidate_moves[][4] - Output - a 2D array containing all candidate moves. Each row corresponds to a single move, and contains the coordinates of the two points to be swapped, in the format x1, y1, x2, y2 (same order as Task 3).
• int& num_candidate_moves - Output - the total number of candidate moves.

Return value - The maximal score gain.

Notes

• Note that the first dimension to the 2D array candidate_moves is intentionally left out, as the actual number of candidate moves is not a fixed value. For this assignment, you can pass in a 2D array with the first dimension set to (HEIGHT-1) * WIDTH + (WIDTH-1) * HEIGHT = 144, which is the number of all possible moves, and only use part of the array to store the values.
  • In practice, it is recommended to use dynamically resizable containers (e.g. std::vector) to store data whose size is not determined at compile-time. These will be introduced later in the course.
• In the unlikely case where no moves can create any matches, do not return any candidate move and return 0 as the maximal score gain.
• (Updated 18/09/21) Please iterate through all possible moves and fill in the rows of candidate_moves in the following order:
  • First check all of the right-swaps, then check all of the up-swaps.
  • Ignore all left-swaps and down-swaps, since they are equivalent to right- and up-swaps.
  • When checking for right- and up-swaps, loop through the y-axis (rows) in ascending order.
  • When handling each row, loop through the x-axis (columns) in ascending order.

(Updated 21/09/21) Example - Suppose we check all 144 possible moves. The highest increase in score is 9, and there are four moves that result in an increase of 9. The moves are (1,7) <-> (1,8), (5,1) <-> (6,1), (4,0) <-> (4,1) and (6,7) <-> (6,8).

• Let's determine the order of these 4 moves, using the rules above.
  • (5,1) <-> (6,1) is a right-swap and the other three are up-swaps. Hence, it will come first.
  • Next we rank by y-coordinates. (4,0) <-> (4,1) comes next since it is the bottommost of the three remaining moves.
  • (1,7) <-> (1,8) and (6,7) <-> (6,8) are on the same row, so we rank them by x-coordinates. (1,7) <-> (1,8) comes first since it is to the left of (6,7) <-> (6,8).
• candidate_moves, which is a 144 x 4 array, should be filled up according to the above order, i.e. the first row is [5, 1, 6, 1], the second row is [4, 0, 4, 1], and so on. The top 4 rows is to be filled, and the remaining 140 rows can be left untouched.
• num_candidate_moves should be set to 4. That way, when this function is called somewhere else (e.g. in Task 5), the calling function will know that only the first 4 rows of candidate_moves contain useful information.
• Finally, the function exits with return value of 9, the score gain of the candidate moves.

Task 5 - Implement the solver() function

Description - Find the optimal move using the considerMoves function. If more than one candidate moves exist, then for each of the candidate move:

• Execute the move (to a temporary copy of the map).
• Recursively call solver() on the modified map to determine the subsequent optimal move.
• The candidate move that gives the highest total subsequent score gain is the optimal move.
• (Updated 17/09/21) If there are still multiple candidate moves that have the highest total subsequent score gain, return the one that appears first in candidate_moves returned from considerMoves().

int solver(int map[][WIDTH], int return_coordinates[4]);

Parameters

• int map[][WIDTH] - Input - game map.
• int return_coordinates[4] - Output - the coordinates of the two tiles to be swapped in the optimal move, in the format x1, y1, x2, y2 (same order as Tasks 3 and 4).

Return value - Total score gain of the optimal move, considering all recursive calls.

Notes

• You can use the copyMap function to copy a map.
• Given a typical map, there is very often only one optimal move, and the number of candidate moves does not exceed 3 moves. Thus, there is no need to worry too much about the no. of candidate moves increasing exponentially.
• solver() can be called with a map as the only argument if return_coordinates is not needed. This may be useful for recursive calls of solver().

int solver(int map[][WIDTH]);

• If considerMoves return zero candidate moves, do not return any coordinates and return 0 as the maximal score gain.

(Updated 21/09/21) Example - Suppose we run the demo program on the default map.txt, and keep on calling solve. At the 5th solve, the program chooses (5,4) <-> (6,4) as the optimal move. We explain why below.

• Initially, considerMoves should return two candidate moves, (5,4) <-> (6,4) and (5,1) <-> (5,2). Both of them increase the score by 20. (5,4) <-> (6,4) is in front because it is a right-swap.
• Since there are multiple candidates, we will recursively run solver() on these two moves.
• We first take the move (5,4) <-> (6,4) (on a copy of the map), then run solver().
  • considerMoves should return another two candidate moves, (1,1) <-> (2,1) and (7,3) <-> (8,3). Both of the increase the score by 6. (1,1) <-> (2,1) is in front because it has a smaller y-coordinate.
  • Again, we will recursively run solver() on these two moves.
  • We first take the move (1,1) <-> (2,1) and run solver().
    • considerMoves should return one candidate move, (5,3) <-> (5,4), which increases the score by 12.
    • Since there is only one candidate, solver() exits with return value of 12.
  • We then take the move (7,3) <-> (8,3) and run solver().
    • considerMoves should return one candidate move, (1,1) <-> (2,1), which increases the score by 6.
    • Since there is only one candidate, solver() exits with return value of 6.
  • Hence, for the two candidates at this round, the total score gains are 12 and 6 respectively. We select the larger one value of 12, and add it to this round's increase which is 6. solver() exits with return value of 18.
• Now we take the move (5,1) <-> (5,2).
  • considerMoves should return one candidate move, (2,6) <-> (2,7), which increases the score by 13. Since there is only one candidate, solver() exits with return value of 13.
• Finally, for the two candidates in the initial call, the total score gains are 18 and 13 respectively. We select the larger value of 18, and add it to this round's increase, which is 20. Thus the return value of solver() is 38. Since the candidate (5,4) <-> (6,4) has a higher score, we set return_coordinates to [5, 4, 6, 4].
• In case the total score gains for both candidates are the same, then (5,4) <-> (6,4) should still be chosen over (5,1) <-> (5,2), because of the order in Task 4.

Resources & Sample I/O

• Skeleton code: PA1_skeleton.zip
• Demo programs: Windows / MacOS (please check later)
• Sample program outputs: Sample 1 / Sample 2

Submission & Grading

Deadline: 28 September 2021 Tuesday HKT 23:59.
You may earn 8% course grade for each PA via Automated Grading on the ZINC Online Submission System.
Compress the single source code file game.cpp by itself as PA1.zip for submission to ZINC.

(Updated 21/09/21) There are two revealed stdio test cases (one of them is just the Sample I/O) on ZINC which are both worth 0 points. Their main purpose is to double-confirm that your code can successfully compile and execute on ZINC, and also to provide you with straightforward tests.

It is a good indicator that your code is mostly correct (but not a 100% guarantee) if you can pass both revealed stdio test cases. Please note that the Sample I/O and the revealed stdio test cases on ZINC don't show all possible cases. It is part of the assessment for you to design your own test cases to test your program. Please also remember to remove or comment out any debugging message(s) that you might have added, before submitting your code.

Download the textfiles of the two stdio test cases here: PA1_stdio_revealed.zip

Grading Scheme

The actual grading is with Googletest C++ Unit Testing (GTest). Each test case will be worth 5% in the Grading Scheme table below, for a total of 20 test cases. The actual grading will also only be triggered, with the scores and test cases revealed, after the deadline. This hidden grading policy is for all the PAs in order to prevent reverse-engineering of the test cases, since the PAs are a significant part of the course assessment and course grade. On the other hand, the Labs have a more visible grading policy, as their primary purpose is for hands-on programming practice, with full Lab marks being the expectation.

(Updated 17/09/21) We will execute unit testing on the task functions individually, and some of the test cases may include invalid input values. In general, you can assume that:

• The map input arrays in all tasks are always of correct size and contains valid input
• For candidate_moves (Task 4), only the first N rows is used (where N is the no. of candidate moves), and the values of the remaining rows don't matter (i.e. it can be uninitialized).
• For other input parameters, please check the validness of input when implementing the functions.

Please ensure that you submit to ZINC well before the deadline as all late submissions will be automatically rejected.

Task Function	Grade
Task 1 - findMatches()	10%
Task 2 - processMatches()	20%
Task 3 - swapTiles()	10%
Task 4 - considerMoves()	30%
Task 5 - solver()	30%

Frequently Asked Questions

Q: My code doesn't work, there is an error/bug, here is the code, can you help me fix it?
A: As the assignment is a major course assessment, to be fair, you are supposed to work on it on your own and we should not finish the tasks for you. We are happy to help with explanations and advice, but we shall not directly debug the code for you.

Q: The demo program enters an infinite loop when given unexpected input (e.g. inputting a character when expecting an integer). Is this a bug?
A: This is just the behavior of cin >> variable; when given input that is not type-matched. You don't need to worry about these user-input-error cases for PA1, as all console I/O is already handled for you by the skeleton code in main.cpp. In other words, only your code in game.cpp is graded.

Q: What are the restrictions regarding modifying the header files, writing our own helper functions, including extra header files, etc.?
A: The only hard restriction is that you can only submit game.cpp to ZINC, and we will use the skeleton code versions of game.h and main.cpp. Anything else that you do, while not strictly prohibited, will be at your own risk regarding the PA1 grading result. Please keep in mind that there is a grade penalty for all grade appeals that include modifications to your already submitted code (no matter how trivial the modification is).

Q: Am I allowed to use local function declarations (function declaration inside an existing function) for my helper functions?
A: You are strongly discouraged from doing so, as that "feature" is a leftover merely for backwards compatibility with C. In C++, it is superseded with class functions and lambda functions, which will be taught later in this course.

Q: (Updated 17/09/21) In the demo program, why can we enter invalid commands such as swap 8 0 up or swap 4 8 right?
A: As explained in the previous email, this is caused by incorrect range checking in main.cpp. You can re-download the skeleton code to get the correct version. The sample programs should also be fixed now.

Q: (Updated 19/09/21) What are the difference between "cells" and "tiles"?
A: Both of them refer to a single digit in the game map. To avoid confusion, all occurences of the word "cells" above have been replaced with "tiles".