续上篇文章,我们来一步步实现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上,如下所示:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python | |
# encoding: utf-8 | |
import random | |
import sys | |
class GameState: | |
NORMAL = 0 | |
WIN = 1 | |
LOSE = 2 | |
class SwapDir: | |
LEFT = 0 | |
UP = 1 | |
RIGHT = 2 | |
DOWN = 3 | |
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 = 2 | |
self.total_score = 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 copy(self): | |
new_board = GameBoard(0) | |
new_board.length = self.length | |
new_board.num_of_empty = self.num_of_empty | |
new_board.max_value = self.max_value | |
new_board.total_score = self.total_score | |
new_board.board = self.board[:] | |
return new_board | |
def __len__(self): | |
return self.length | |
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.05: # 简化一下 | |
value = 4 | |
else: | |
value = 2 | |
board.set(x, y, value) | |
board.num_of_empty -= 1 | |
return True | |
return False | |
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) | |
if get_cur(i, j) > board.max_value: | |
board.max_value = get_cur(i, j) | |
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 | |
board.total_score += score | |
return score, moved | |
def init_game(n): | |
# 初始化游戏 | |
board = GameBoard(n) | |
set_random_number(board) | |
return board, GameState.NORMAL | |
def print_game(board): | |
n = len(board) | |
sys.stdout.write(" " + "----"*n + " \n") | |
for i in range(n): | |
sys.stdout.write(" ") | |
for j in range(n): | |
value = board.get(i, j) | |
if value == 0: | |
value = " " | |
sys.stdout.write(str(value).rjust(3) + "|") | |
sys.stdout.write(" \n") | |
sys.stdout.write(" " + "----"*n + " \n") | |
sys.stdout.flush() | |
def get_swap_dir(board): | |
# return random.randint(1, 4) # 测试用 | |
swap_dir = raw_input("your turn:") | |
if swap_dir == 'w': | |
return SwapDir.UP | |
elif swap_dir == 's': | |
return SwapDir.DOWN | |
elif swap_dir == 'a': | |
return SwapDir.LEFT | |
elif swap_dir == 'd': | |
return SwapDir.RIGHT | |
else: | |
return None | |
def play(n, target, swap_func, debug=False): | |
board, state = 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:", board.total_score | |
print_game(board) | |
set_random_number(board) | |
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!" |
换一个思路,我们尝试提取不同方向下的不同点:定位和遍历。例如向左滑动和向右滑动,它们的定位方法是一样的,但是遍历方向相反。向下和向上滑动的遍历方向也是相反的,定位方法一样。向左滑动和向上滑动的遍历方向一样,但是定位方法确实相反的(一个i行j列,一个j行i列。于是我们可以抽象出上述两种操作,使不同方向上的操作得到统一。——不明觉厉wow~ ⊙o⊙