CS61B-sp21 Project0

Project 0: 2048

要求实现游戏 2048 ，GUI 和骨干代码已给出，只需要在 model.java 中实现四个核心函数：emptySpaceExists、maxTileExists、atLeastOneMoveExists、tilt。

public static boolean emptySpaceExists(Board b)

Task

This method should return true if any of the tiles in the given board are null. You should NOT modify the Board.java file in any way for this project. For this method, you’ll want to use the tile(int col, int row) and size() methods of the Board class. No other methods are necessary.

Note: We’ve designed the Board class using a special keyword private that disallows you from using the instance variables of Board directly. For example, if you try to access b.values[0][0], this will not work. This is a good thing! It forces you to learn to use the tile method, which you’ll use throughout the rest of the project.

Try opening the TestEmptySpace.java folder. Run the tests. You should see that 6 of the tests fail and 2 of them pass. After you’ve correctly written the emptySpaceExists method, all 8 tests in TestEmptySpace should pass.

简单来说就是查找对象 board 中是否存在在空格，非常简单，套两个循环即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
/** Returns true if at least one space on the Board is empty.
     *  Empty spaces are stored as null.
     * */
public static boolean emptySpaceExists(Board b) {
        for(int i = 0; i < b.size(); i++) {
            for(int j = 0; j < b.size(); j++) {
                if(b.tile(i,j)==null) {
                    return true;
                }
            }
        }
        return false;
    }

public static boolean maxTileExists(Board b)

Task

This method should return true if any of the tiles in the board are equal to the winning tile value 2048. Note that rather than hard coding the constant 2048 into your code, you should use MAX_PIECE, which is a constant that is part of the Model class. In other words, you shouldn’t do if (x == 2048) but rather if (x == MAX_PIECE).

Leaving in hard coded numbers like 2048 is a bad programming practice sometimes referred to as a “magic number”. The danger of such magic numbers is that if you change them in one part of your code but not another, you might get unexpected results. By using a variable like MAX_PIECE you can ensure they all get changed together.

注意先判断是否为 null 再取 .value()

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
    * Returns true if any tile is equal to the maximum valid value.
    * Maximum valid value is given by MAX_PIECE. Note that
    * given a Tile object t, we get its value with t.value().
    */
   public static boolean maxTileExists(Board b) {
       for(int i = 0; i < b.size(); i++) {
           for(int j = 0; j < b.size(); j++) {
               Tile t = b.tile(i,j);
               if(t != null && t.value() == MAX_PIECE) {
                   return true;
               }
           }
       }
       return false;
   }

public static boolean atLeastOneMoveExists(Board b)

Task

This method is more challenging. It should return true if there are any valid moves. By a “valid move”, we mean that if there is a button (UP, DOWN, LEFT, or RIGHT) that a user can press while playing 2048 that causes at least one tile to move, then such a keypress is considered a valid move.

There are two ways that there can be valid moves:

  1. There is at least one empty space on the board.
  2. There are two adjacent tiles with the same value.

For example, for the board below, we should return true because there is at least one empty space.

1
2
3
4
|   2|    |   2|    |
|   4|   4|   2|   2|
|    |   4|    |    |
|   2|   4|   4|   8|

For the board below, we should return false. No matter what button you press in 2048, nothing will happen, i.e. there are no two adjacent tiles with equal values.

1
2
3
4
|   2|   4|   2|   4|
|  16|   2|   4|   2|
|   2|   4|   2|   4|
|   4|   2|   4|   2|

For the board below, we would return true since a move to the right or left would merge the two 64 tiles, and also a move up or down would merge the 32 tiles. Or in other words, there exist at least two adjacent tiles with equal values.

1
2
3
4
|   2|   4|  64|  64|
|  16|   2|   4|   8|
|   2|   4|   2|  32|
|   4|   2|   4|  32|

After you’ve written the method, the tests in TestAtLeastOneMoveExists.java should pass.

这相当于判断游戏是否结束的函数。游戏结束当且仅当满格且任何操作都不能合并已存在方块：前者等效为不存在空快，直接调用刚刚实现的 emptySpaceExists，后者遍历 board，按照某个方向检查相邻方块是否可合并。

注意的是，由于该函数地目的是实时检查每一次更新后是否仍然可以进行游戏，而非判断当前是否可解（也压根没法判，每次移动都在增加方块），所以只需要检查相邻块即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
     * Returns true if there are any valid moves on the board.
     * There are two ways that there can be valid moves:
     * 1. There is at least one empty space on the board.
     * 2. There are two adjacent tiles with the same value.
     */
    public static boolean atLeastOneMoveExists(Board b) {
        if(emptySpaceExists(b)) {
            return true;
        }
        for(int i = 0; i < b.size(); i++) {
            for(int j = 0; j < b.size(); j++) {
                int check = b.tile(i,j).value();
                if(i != b.size() - 1) {
                    int x = b.tile(i + 1, j).value();
                    if(x == check) {
                        return true;
                    }
                }
                if(j != b.size() - 1) {
                    int y = b.tile(i, j + 1).value();
                    if(y == check) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

public boolean tilt(Side side)

Task

The tilt method does the work of actually moving all the tiles around. For example, if we have the board given by:

1
2
3
4
>|   2|    |   2|    |
>|   4|   4|   2|   2|
>|    |   4|    |    |
>|   2|   4|   4|   8|

And press up, tilt will modify the board instance variable so that the state of the game is now:

1
2
3
4
>|   2|   8|   4|   2|
>|   4|   4|   4|   8|
>|   2|    |    |    |
>|    |    |    |    |

In addition to modifying the board, two other things must happen:

  1. The score instance variable must be updated to reflect the total value of all tile merges (if any). For the example above, we merged two 4s into an 8, and two 2s into a 4, so the score should be incremented by 8 + 4 = 12.
  2. If anything about the board changes, we must set the changed local variable to true. That’s because at the end of the skeleton code for tilt, you can see we call a setChanged() method: this informs the GUI that there is something to draw. You will not make any calls to setChanged yourself: only modifying the changed local variable.

All movements of tiles on the board must be completed using the move method provided by the Board class. All tiles of the board must be accessed using the tile method provided by the Board class. Due to some details in the GUI implementation, you should only call move on a given tile once per call to tilt. We’ll discuss this constraint further in the Tips section of this document.

前面三个函数属于是洒洒水熟悉 java 语法来的，这个函数属于是实现游戏主要逻辑了。简答来说，该函数接受移动方向作为参数，更新 board 为移动后状态，并根据是否合并来更新分数。返回值 changed 为 board 是否更新（没细看代码，我估计是与生成新的方块有关）。

开始想如何实现移动和合并，打算自己写一个方法实现，可找了半天也没找到 setvalue() 这种接口，定睛一看才发现 board 类给实现了 move()，board.move() 还自带判断是否可 merge()，绷，原来 project 最前面有一小段介绍作为文档了，不细看英语导致的。

然后在介绍内容的 Google Form quiz 也给足了提示：对于四个方向，我们不必维护四个方向的遍历。board 类实现了方法 setViewingPerspective()。那么我们只需要实现一个方向（例如 北）的代码实现，对于其他方向先改方向再移动再修改回原方向（即 setViewingPerspective(Side.NORTH) 给他掰回来）。

至于移动部分算法，我写的多少有点 leetcode 味了：枚举每一列的所有非空元素，再自上向下地检查每一个元素。如果是空元素，那么移动到这里；如果和待移动元素相同，执行合并逻辑。

注意的是，每个方块在一次移动过程中只能合并一次，如何维护？（答案是在 board 类实现 visited (划掉) ）。我想到的是在每次列内枚举时维护一个 beginidx。每次移动元素都实现更新，如果移动元素至空位置或不移动，那么 beginidx 移动到该元素移动后位置；如果移动元素执行合并，那么 beginidx 移动到 row - 1 的位置。

题外话，我开始实现的时候忘记在移动元素至空位置和不移动时更新 idx 了。这会很诡异，比如一列元素为 2 4 8 2，执行一次按理说不会改变，但是我最初那一版会直接更新为 4 4 8 0。关键是我这么写 TestModel 全过了，autograder 也全过了！哈人！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/** Tilt the board toward SIDE. Return true iff this changes the board.
 *
 * 1. If two Tile objects are adjacent in the direction of motion and have
 *    the same value, they are merged into one Tile of twice the original
 *    value and that new value is added to the score instance variable
 * 2. A tile that is the result of a merge will not merge again on that
 *    tilt. So each move, every tile will only ever be part of at most one
 *    merge (perhaps zero).
 * 3. When three adjacent tiles in the direction of motion have the same
 *    value, then the leading two tiles in the direction of motion merge,
 *    and the trailing tile does not.
 * */
public boolean tilt(Side side) {
    boolean changed;
    changed = false;

    board.setViewingPerspective(side);
    for(int col = 0; col < board.size(); col++) {
        int beginidx = board.size() - 1;
        for(int row = board.size() - 1; row >= 0; row--) {
            Tile t = board.tile(col, row);
            if (t != null) {
                for (int row2 = beginidx; row2 > row; row2--) {
                    Tile t2 = board.tile(col, row2);
                    if (t2 == null) {
                        board.move(col, row2, t);
                        changed = true;
                        break;
                    } else if (t2.value() == t.value()) {
                        board.move(col, row2, t);
                        score += t2.value() * 2;
                        changed = true;
                        beginidx = row2 - 1;
                        break;
                    } else {
                        beginidx = row2;
                    }
                }
            }
        }
    }

    board.setViewingPerspective(Side.NORTH);

    checkGameOver();
    if (changed) {
        setChanged();
    }
    return changed;

Autograder Results

Student

  • Tanpinsary

Total Points

- / 640 pts

Autograder Score640.0 / 640.0

第一次逻辑和修改过的都过了？数据这事得多水啊（