我正在尝试用python构建一个Sokoban益智应用程序。在
(规则说明: http://en.wikipedia.org/wiki/Sokoban)
我成功地实现了这个游戏,但我认为如果计算机能够计算出解决某个特定难题的最佳解决方案,那会更好。在
当我在寻找推荐信的时候,我遇到了这样一个代码: http://rosettacode.org/wiki/Sokoban#Python
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
和{sdata
和{
有什么想法吗?在
谢谢:)
sdata保存来自迷宫的静态数据(在我们搜索时不发生变化的部分),而ddata保存动态数据(在我们搜索时发生变化的部分),并用于保存初始状态。在
这样做很可能是因为长方体和目标可能处于同一位置,这将使代码的实现更加复杂。在
最初将ddata作为搜索的起始位置被推到“打开列表”上,然后进入“访问集”以标记已搜索的位置。在
如果查看数据映射到的内容:
ssata似乎是一个终点和墙的地图。在
ddata似乎是玩家和钻石的地图。在
相关问题 更多 >
编程相关推荐