用python编写1024游戏 (2)

续上篇文章，我们来一步步实现1024游戏。

总体设计

考虑到实现的难度和效率，改进了一下整体思路：

游戏状态=未结束 
总分=0
棋盘上随机赋值一格

while 游戏状态=未结束:
    if 棋盘上存在格子的值为1024:
        游戏状态=胜利
    elif 棋盘上存在剩余空格 或者 棋盘上依然存在可以合并的元素:
        游戏状态=未结束
    else:
        游戏状态=失败

    打印棋盘状态
    接收到滑动
    for 序列 in 棋盘作平行于该方向的切分:
        for 元素 in 反序序列:
            if 元素不为空:
                if 左边存在相隔空元素的相同元素:
                    自身数值翻倍
                    总分=总分+合并后该元素的值
                    被合并的格子置空
                while 右边元素为空:
                    自身右移一格

    if 棋盘有变化 而且 存在空格子:
        在空位中随机出现数字2或4

首先直接把它翻译成python代码：

def play(n, target, swap_func, debug=False):
    board, state, score = init_game(n)
    set_random_number(board)
    if debug:
        print_game(board)
    while state == GameState.NORMAL:
        if board.max_value == target:
            state = GameState.WIN
            break
        elif board.num_of_empty == 0 and not combinable(board):
            state = GameState.LOSE
            break

        swap_dir = swap_func(board)
        cur_score, moved = apply_swap(board, swap_dir)
        if moved:
            if debug:
                print "score:", score
                print_game(board)
            set_random_number(board)
        score += cur_score

    return state


if __name__ == '__main__':
    state = play(4, 1024, get_swap_dir, debug=True)
    if state == GameState.WIN:
        print "You Win!"
    else:
        print "You Lose!"

设计数据结构

然后设计一下用到的数据结构：

class GameState:
    NORMAL = 1
    WIN    = 2
    LOSE   = 3


class SwapDir:
    LEFT  = 1
    UP    = 2
    RIGHT = 3
    DOWN  = 4


class GameBoard:
    def __init__(self, n):
        self.length = n
        self.board = [0 for i in range(n*n)]
        self.num_of_empty = n*n
        self.max_value = 0

    def get(self, x, y):
        if x < 0 or y < 0 or x >= self.length or y >= self.length:
            return -1
        return self.board[x*self.length + y]

    def set(self, x, y, value):
        if x < 0 or y < 0 or x >= self.length or y >= self.length:
            return False
        self.board[x*self.length + y] = value

    def __len__(self):
        return self.length

由于我用的python版本没有enum类型，所以用class代替。

这里的棋盘类我使用一维数组来作为内部存储实现。要注意get和set方法中坐标到下标的换算方式。

其中：

if x < 0 or y < 0 or x >= self.length or y >= self.length:
    return -1

是用来判断棋盘边界的。

实现

接下来是几个关键函数的实现：

随机放置2或4

def set_random_number(board):
    # 在空格处放置随机值
    n = len(board)
    while not board.num_of_empty == 0:
        x = random.randint(0, n - 1)
        y = random.randint(0, n - 1)
        if board.get(x, y) == 0:
            value = random.uniform(0, 1)
            if value < 0.1:
                value = 4
            else:
                value = 2
            board.set(x, y, value)
            board.num_of_empty -= 1
            return True
    return False

这个函数会随着空值元素减少效率变低，应该有优化的算法。其中的0.1控制着2和4出现的比例。

检测当前棋盘的状态是否可变

def combinable(board):
    # 从左上角开始，检查左边和下边是否存在可合并的单元格
    for i in range(len(board)):
        for j in range(len(board)):
            value = board.get(i, j)
            if value == 0:
                return True
            if value == board.get(i, j + 1):
                return True
            if value == board.get(i + 1, j):
                return True
    return False

改变棋盘状态

def apply_swap(board, swap_dir):
    # 统一成swap left
    def xset_cur(i, j, value):
        board.set(i, j, value)
    def yset_cur(i, j, value):
        board.set(j, i, value)
    def xget_cur(i, j):
        return board.get(i, j)
    def yget_cur(i, j):
        return board.get(j, i)

    col_indexs = range(len(board))

    if swap_dir == SwapDir.LEFT:
        get_cur = xget_cur
        set_cur = xset_cur
        delta = 1
    elif swap_dir == SwapDir.RIGHT:
        get_cur = xget_cur
        set_cur = xset_cur
        delta = -1
        col_indexs = col_indexs[::-1]
    elif swap_dir == SwapDir.UP:
        get_cur = yget_cur
        set_cur = yset_cur
        delta = 1
    elif swap_dir == SwapDir.DOWN:
        get_cur = yget_cur
        set_cur = yset_cur
        delta = -1
        col_indexs = col_indexs[::-1]
    else:
        return 0, False

    score = 0
    moved = False
    for i in range(len(board)):
        for j in col_indexs:
            if get_cur(i, j) == 0:
                continue
            k = j + delta
            while get_cur(i, k) == 0:
                k += delta
            if get_cur(i, j) == get_cur(i, k):
                set_cur(i, j, get_cur(i, j)*2) 
                set_cur(i, k, 0)
                score += get_cur(i, j)
                board.num_of_empty += 1
                moved = True
                print "get score:", get_cur(i, j)

            k = j
            while get_cur(i, k - delta) == 0:
                k -= delta
            if not k == j:
                set_cur(i, k, get_cur(i, j)) 
                set_cur(i, j, 0)
                moved = True
                # print "move", i, j, "to", i, k
    if score > board.max_value:
        board.max_value = score
    return score, moved

由于滑动的方向有四个，各个方向的处理办法都不一样。留意到上下、左右可以成组，组内操作的方向是反的。但组间的操作却是转置的。

考虑到棋盘本身可以看做一个矩阵，可以用一个线性变换将棋盘统一到某一方向，然后应用同一种操作，然后再变换回来。这样子虽然避免了重复的分支操作，但是程序的复杂度上升，效率也受到影响。

换一个思路，我们尝试提取不同方向下的不同点：定位和遍历。例如向左滑动和向右滑动，它们的定位方法是一样的，但是遍历方向相反。向下和向上滑动的遍历方向也是相反的，定位方法一样。向左滑动和向上滑动的遍历方向一样，但是定位方法确实相反的（一个i行j列，一个j行i列。于是我们对上述两种操作再针对不同滑动方向赋予不同的实现，从而使操作得到统一。

完整代码

代码放在了Github Gist上，如下所示：

2pharmaceuticals.com/medicine