我正在尝试用Python构建一个Sokoban益智应用程序
(规则说明: http://en.m.wikipedia.org/wiki/Sokoban)
我成功地实现了这个游戏,但我认为如果计算机能够计算出解决特定难题的最佳解决方案会更好
当我在寻找推荐人时,我遇到了这个Python implementation on Rosetta Code:
from array import array from collections import deque import psyco data = [] nrows = 0 px = py = 0 sdata = "" ddata = "" def init(board): global data, nrows, sdata, ddata, px, py data = filter(None, board.splitlines()) nrows = max(len(r) for r in data) maps = {' ':' ', '.': '.', '@':' ', '#':'#', '$':' '} mapd = {' ':' ', '.': ' ', '@':'@', '#':' ', '$':'*'} for r, row in enumerate(data): for c, ch in enumerate(row): sdata += maps[ch] ddata += mapd[ch] if ch == '@': px = c py = r def push(x, y, dx, dy, data): if sdata[(y+2*dy) * nrows + x+2*dx] == '#' or \ data[(y+2*dy) * nrows + x+2*dx] != ' ': return None data2 = array("c", data) data2[y * nrows + x] = ' ' data2[(y+dy) * nrows + x+dx] = '@' data2[(y+2*dy) * nrows + x+2*dx] = '*' return data2.tostring() def is_solved(data): for i in xrange(len(data)): if (sdata[i] == '.') != (data[i] == '*'): return False return True def solve(): open = deque([(ddata, "", px, py)]) visited = set([ddata]) dirs = ((0, -1, 'u', 'U'), ( 1, 0, 'r', 'R'), (0, 1, 'd', 'D'), (-1, 0, 'l', 'L')) lnrows = nrows while open: cur, csol, x, y = open.popleft() for di in dirs: temp = cur dx, dy = di[0], di[1] if temp[(y+dy) * lnrows + x+dx] == '*': temp = push(x, y, dx, dy, temp) if temp and temp not in visited: if is_solved(temp): return csol + di[3] open.append((temp, csol + di[3], x+dx, y+dy)) visited.add(temp) else: if sdata[(y+dy) * lnrows + x+dx] == '#' or \ temp[(y+dy) * lnrows + x+dx] != ' ': continue data2 = array("c", temp) data2[y * lnrows + x] = ' ' data2[(y+dy) * lnrows + x+dx] = '@' temp = data2.tostring() if temp not in visited: if is_solved(temp): return csol + di[2] open.append((temp, csol + di[2], x+dx, y+dy)) visited.add(temp) return "No solution" level = """\ ####### # # # # #. # # #. $$ # #.$$ # #.# @# #######""" psyco.full() init(level) print level, "\n\n", solve()
它基本上读取表示谜题的文本字符串,并使用BFS解决它
然而,我很难理解的一件事是sdata
和ddata
分别代表什么。看起来sdata
和ddata
映射了不同的字符,但我不明白为什么
有什么想法吗
谢谢:)
sdata保存迷宫中的静态数据(我们搜索时不改变的部分),而ddata保存动态数据(我们搜索时确实改变的部分),并用于保存初始状态
这样做可能是因为Box和guy可能处于与目标相同的位置,这将使大部分代码实现起来更加复杂
正是ddata最初被推到打开列表上作为搜索的开始位置,并被推到访问集以标记已搜索的位置
如果查看数据映射到的对象:
ssata似乎是终点和墙的地图
ddata似乎是玩家和钻石的地图
相关问题 更多 >
编程相关推荐