跳转至

Project 0 Game 2048§

1. 仓库地址§

2. 辅助函数实现§

2.1 emptySpaceExists(Board b)§

阅读 Board.java 文件, 确定 tile(int col, int row) 与 size() 方法是什么怎么用即可完成.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
/** Return the current Tile at (COL, ROW), where 0 <= ROW < size(),  
 *  0 <= COL < size(). Returns null if there is no tile there. */
public Tile tile(int col, int row) {  
    return vtile(col, row, viewPerspective);  
}

/** Returns the size of the board. */  
public int size() {  
    return values.length;  
}

参考实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
/** Returns true if at least one space on the Board is empty.  
 *  Empty spaces are stored as null. * */
public static boolean emptySpaceExists(Board b) {  
    // TODO: Fill in this function.  

    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;  
}

2.2 maxTileExists(Board b)§

  • 项目文档有意引导大家养成良好的编码习惯, 即不要在程序中直接使用数字或者字符串硬编码. 不然, 一旦有跨平台的需求或者需要修复某些 bug 的时候就会产生严重的灾难.
  • 注释中说明了 value() 是 Tile 类型的方法, 因此直接从当前的 Tile 读取 value 判断是否达到 MAX_PIECE 即可.
  • 需要注意的一点是, value() 方法调用前不会检查调用这一函数的对象是否真的能够调用. 如果上一个函数出现了 null 的情况, 那么调用 value() 就一定会抛出错误.

参考实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**  
 * 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) {  
    // TODO: Fill in this function.  

    for (int i = 0; i < b.size(); ++i) {  
        for (int j = 0; j < b.size(); ++j) {  
            Tile num = b.tile(i, j);  
            if (num != null && num.value() == MAX_PIECE) {  
                return true;  
            }  
        }  
    }  

    return false;  
}

2.3 atLeastOneMoveExists(Board b)§

  • 相比于前两个辅助函数, 这一函数的实现的难度略微大一些. 首先对边界有两种思路, 其一是在边缘添加哨兵, 避免边界状况的发生; 其二是直接在边界状况发生的时候处理掉. 我们选择工程上更节省内存空间更常见的方案二.
  • 对于函数本身, 先判断是否有空格子, 如果有那么一定可以移动; 如果没有空格子, 那么可以判断一个格子周围的是否有值与之相同的格子. 如果有那么就可以合并, 可以移动. 具体实现时结合前面提到的边界处理思路完成代码.

参考实现

 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
/**  
 * 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) {  
    // TODO: Fill in this function.  

    if (emptySpaceExists(b)) {  
        return true;  
    }  

    int bSize = b.size();  
    for (int i = 0; i < bSize - 1; ++i) {  
        for (int j = 0; j < bSize - 1; ++j) {  
            if (b.tile(i, j).value() == b.tile(i, j + 1).value() ||  
                    b.tile(i, j).value() == b.tile(i + 1, j).value()) {  
                return true;  
            }  
        }  
    }  

    // Analyze the bottom right corner separately  
    if (b.tile(bSize - 1, bSize - 1).value() == b.tile(bSize - 2, bSize - 1).value() ||  
            b.tile(bSize - 1, bSize - 1).value() == b.tile(bSize - 1, bSize - 2).value()) {  
        return true;  
    }  

    return false;  
}

3. 主逻辑实现§

分为两步, 第一步实现四种操作的四分之一: 向上移动.

  • 实现这一逻辑需要两部分, 其一是方块移动与合并, 其二是加分. 后者显然可以根据前者移动时是否发生了合并而确定, 因此第一个写好后第二个一定也可以顺便写好. 最显而易见的方法是双指针法, 对应伪代码如下所示
 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
for (int j = 0; j < size; ++j) {
    // Outer loop: Iterate through each column independently
    for (int i = 0; i < size; ++i) {
        // Inner loop: Process rows from top to bottom (target direction)

        // Part 1: Fill the current empty cell (if any)
        if (b[i][j] == null) {
            // Look for the next available tile below the current empty spot
            for (int k = i + 1; k < size; ++k) {
                if (b[k][j] != null) {
                    // Pull the found tile up to the current empty position
                    move(i, j, tile(k, j));
                    break; // Move only the first tile found
                }
            }

            // If the cell is still null, no more tiles exist in this column to move up
            if (b[i][j] == null) {
                break;
            }
        }

        // Part 2: Merge logic
        // Look for the next tile below the current (now non-empty) cell to check for a merge
        for (int k = i + 1; k < size; ++k) {
            if (b[k][j] != null) {
                // If values match, merge the lower tile into the current one
                if (b[k][j].val() == b[i][j].val()) {
                    move(i, j, tile(k, j));
                }
                // Stop searching after encountering the first tile (whether merged or blocked)
                break;
            }
        }
    }
}
  • 注意, 在将伪代码实现为真正的 Java 时, 需要关注这里设计的有些奇怪的函数接口: tile() 的第一个形参是常规的列号, 但是第二个形参是从下往上数的行号. 因此上面的伪代码需要额外做些变换才能让程序正常运行. 另外注意, 根据函数接口的注释要求, 本函数还需要进行计分, 并且返回 board 上是否有数发生改变.

以下为第一步的参考实现

 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
50
51
52
/** Tilt the board toward SIDE. Return true if 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;  

    // TODO: Modify this.board (and perhaps this.score) to account  
    // for the tilt to the Side SIDE. If the board changed, set the  
    // changed local variable to true.    
    if (side == Side.NORTH) {  
        for (int j = 0; j < size(); ++j) {  
            for (int i = size() - 1; i >= 0; --i) {  
                if (board.tile(j, i) == null) {    
                    for (int k = i - 1; k >= 0; --k){  
                        if (board.tile(j, k) != null) {  
                            board.move(j, i, board.tile(j, k));  
                            changed = true;
                            break;  
                        }  
                    }  
                    if (board.tile(j, i) == null) {  
                        break;
                    }  
                }  
                for (int k = i - 1; k >= 0; --k){  
                    if (board.tile(j, k) != null) {  
                        if (board.tile(j, k).value() == board.tile(j, i).value()) {  
                            score += 2 * board.tile(j, k).value();  
                            board.move(j, i, board.tile(j, k));  
                            changed = true;  
                        }  
                        break;  
                    }  
                }  
            }  
        }  
    }  

    checkGameOver();  
    if (changed) {  
        setChanged();  
    }  
    return changed;  
}
  • 第二步, 利用库函数中的 board 旋转函数来避免写四个方向的条件判断. 最终得到
 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/** Tilt the board toward SIDE. Return true if 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;

        // TODO: Modify this.board (and perhaps this.score) to account
        // for the tilt to the Side SIDE. If the board changed, set the
        // changed local variable to true.

        if (side == Side.NORTH) {
            board.setViewingPerspective(Side.NORTH);
        } else if (side == Side.SOUTH) {
            board.setViewingPerspective(Side.SOUTH);
        } else if (side == Side.EAST) {
            board.setViewingPerspective(Side.EAST);
        } else if (side == Side.WEST) {
            board.setViewingPerspective(Side.WEST);
        }

        for (int j = 0; j < size(); ++j) {
            for (int i = size() - 1; i >= 0; --i) {
                if (board.tile(j, i) == null) {
                    for (int k = i - 1; k >= 0; --k){
                        if (board.tile(j, k) != null) {
                            board.move(j, i, board.tile(j, k));
                            changed = true;
                            break;
                        }
                    }
                    if (board.tile(j, i) == null) {
                        break;
                    }
                }
                for (int k = i - 1; k >= 0; --k){
                    if (board.tile(j, k) != null) {
                        if (board.tile(j, k).value() == board.tile(j, i).value()) {
                            score += 2 * board.tile(j, k).value();
                            board.move(j, i, board.tile(j, k));
                            changed = true;
                        }
                        break;
                    }
                }
            }
        }

        board.setViewingPerspective(Side.NORTH);

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

Note

注意, 不同的 2048 游戏规则有着略微不同的区别. 例如, 当有空位置但是此方向上不存在方块移动或者合并的时候是否允许这一方向作为 changed? 如果认为可以, 那么一个测试点是无法通过的. 文档中实际上写明了这一点.

另外, 因为时间原因博主没做风格检查, 甚至 TODO 注释也没去掉, 请在完成时注意进行 Style Check.

评论

Tips: 若评论区主题未随文档主题同步, 刷新页面即可.