proj0. 2048 of CS61B of UCB

Intro

在这个项目中, 我们需要解决四个任务. 我会谈到我是怎么处理这四个问题的.

Task 1. public static boolean emptySpaceExists(Board b)

这个任务要求我们检查 2048 的是否存在空格子. 解决办法很容易想到: 遍历一边所有的格子看看是否有空的即可. 查看其他文件就可以知道要用到什么 API 来完成这个功能. 比如我们可以通过 board.tile(col, row) 来获取对应的格子. 通过返回的状态就可以知道是不是空的.

/** Returns true if at least one space on the Board is empty.
 *  Empty spaces are stored as null.
 * */
public static boolean emptySpaceExists(Board b) {
    int size = b.size();
    for (int col = 0; col < size; col++) {
        for (int row = 0; row < size; row++) {
            if (b.tile(col, row) == null) {
                return true;
            }
        }
    }
    return false;
}

Task 2. public static boolean maxTileExists(Board b)

这个其实跟任务一很类似, 只是此时我们不是要判断格子是否为空, 我们是要判断格子的值是否为一个特定的值, 这其实还是很容易想到的. 因为我们还是通过遍历来解决这个问题, 只是判断的条件变为: t.values() == MAX_PIECE.

/**
 * 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) {
    int size = b.size();
    for (int col = 0; col < size; col++) {
        for (int row = 0; row < size; row++) {
            Tile t = b.tile(col, row);
            // only when t != null should we check t.value()
            if (t != null && t.value() == MAX_PIECE) {
                return true;
            }
        }
    }
    return false;
}

Task 3. public static boolean atLeastOneMoveExists(Board b)

确实, 这个问题对新手来说会比较有挑战性. 问题的关键在于如何判断出 2048 的方格上是否能继续玩下去, 主要有两种情形

1. 2048 的所有方格中至少有一个是空的. 这个可以用前面实现的 emptySpaceExists()
2. 如果移动的方向上有相邻而且值一样的格子, 此时我们可以进行合并. 显然每个格子我们需要检查 4 个方向. 这是通过 dx 和 dy 实现的, 他们表示不同方向上的增量.

/**
 * 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;
    }
    // 4 directions, LEFT/UP/RIGHT/DOWN
    int[] dx = {0, -1, 0, 1};
    int[] dy = {-1, 0, 1, 0};

    int size = b.size();
    for (int col = 0; col < size; col++) {
        for (int row = 0; row < size; row++) {
            // Because we have checked emptySpace, t.values() must exist
            int curTileValue = b.tile(col, row).value();
            for (int move = 0; move < 4; move++) {
                int colNew = col + dx[move];
                int rowNew = row + dy[move];
                // make sure the tile is within the boundary
                if (colNew > 0 && colNew < size && rowNew > 0 && rowNew < size) {
                    Tile newTile = b.tile(colNew, rowNew);
                    if (newTile.value() == curTileValue) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

Task 4. Building the Game Logic

解决这个任务还是花了我不少时间的 😦

:happy: CS61B 这个课程贴心地给我们提供了一些函数使得我们可以只关心在向上的时候要如何处理这个问题. 我们只需要在我们的代码前后加上对应的函数即可⬇️

board.setViewingPerspective(side);
// put your code here
board.setViewingPerspective(Side.NORTH);

最后解决问题的方法是(一列一列处理)⬇️

1. 首先把每一个空的格子移到 “后面”(此时不考虑合并). 保证前面都是连续的有效格子. 这里的前面和后面是相对于我们移动的方向而言的. 可以看看下面的 Gif 图来理解一下.
   

2. 然后我们再考虑合并这件事情, 我们需要检查相邻的格子是否值一样, 从最前面的开始检查, 把它和下一个相邻的格子检查是否可以合并, 如果可以, 就把后面的移动到前面来进行合并, 然后再处理下一个. 比如 [2, 2, 2, x] -> [4, x, 2, x] -> [4, 2, x, x]. 然后我们会移动到下一个位置也就是 2 看看 2 能不能和 x 合并.

代码里面可以看到更多的细节⬇️

/** 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;

    /** The coordinates are:
     *  3
     *  2
     *  1
     *  0 1 2 3
     */
    board.setViewingPerspective(side);
    int size = board.size();
    for (int col = 0; col < size; col++) {
        // Step1. move every non-empty tile in order
        // [x, 2, 2, x] -> [2, 2, x, x]
        // skip merging this step.
        for (int row = size - 1; row >= 0; row--) {
            Tile t = board.tile(col, row);
            if (t != null) {
                // find nextPos which is null
                int nextPos = 3;
                while (nextPos >= row) {
                    if (board.tile(col, nextPos) == null) {
                        break;
                    }
                    nextPos--;
                }
                // check if nextPos is a legal position
                if (nextPos >= row) {
                    board.move(col, nextPos, t);
                    changed = true;
                }
            }
        }
        // Step2. try to merge
        // [2, 2, x, x] -> [4, x, x, x]
        for (int row = 3; row >= 0; row--) {
            Tile curTile = board.tile(col, row);
            int nextLine = row - 1;
            if (nextLine < 0) {
                break;
            }
            Tile nextTile = board.tile(col, nextLine);
            if (curTile == null || nextTile == null) {
                break;
            }
            int nextValue = nextTile.value();
            if (nextValue == curTile.value()) {
                board.move(col, row, nextTile);
                score += curTile.value() * 2;
                for (int p = nextLine - 1; p >= 0; p--) {
                    Tile tt = board.tile(col, p);
                    if (tt == null) {
                        break;
                    }
                    if (p < size) {
                        board.move(col, p + 1, tt);
                    }
                }
                changed = true;
            }
        }
    }
    board.setViewingPerspective(Side.NORTH);

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

Play !

2048 游戏跑起来的时候还是很有成就感滴

完整项目文件在这里👋👋👋