1

我正在尝试用 Python 构建一个推箱子拼图应用程序。

（规则说明： http ://en.m.wikipedia.org/wiki/Sokoban ）

我成功地实现了游戏，但我认为如果计算机能够计算出解决特定难题的最佳解决方案会更好。

在寻找参考资料时，我在 Rosetta Code 上遇到了这个 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和ddata代表什么。它看起来sdata和ddata映射不同的字符，但我不明白为什么。

有任何想法吗？

谢谢 ：）

4

2 回答 2

1

如果您查看数据映射到的内容：

. = end point
@ = the guy
# = wall
$ = diamond
maps = {' ':' ', '.': '.', '@':' ', '#':'#', '$':' '}
mapd = {' ':' ', '.': ' ', '@':'@', '#':' ', '$':'*'}

ssata 似乎是终点和墙壁的地图。

ddata 似乎是玩家和钻石的地图。

于 2013-10-08T15:38:02.017 回答
0

sdata保存来自迷宫的静态数据（在我们搜索时不会改变的部分），ddata保存动态数据（在我们搜索时会改变的部分），并用于保存初始状态。

这样做可能是因为盒子和人可能与目标处于同一位置，这会使许多代码实现起来更加复杂。

最初将ddata推到打开列表中作为搜索的开始位置，并推到已访问集以标记已搜索的位置。

于 2015-10-22T12:27:34.167 回答