非常喜欢推箱子的游戏，想用代码写个解决方案，但是没有足够的时间自己想解决方案了。参考了某博客的代码：https://blog.csdn.net/weixin_33316051/article/details/113670665
代码看是看了，但是没看懂，也没跑通orz……
level_file_path = ‘level_file.txt‘
class gameshortest:
def __init__(self, line, col=10):
"""
给一个图，长度为100的字符串表示。
0空地 1墙 2箱子起始位置 3箱子终点位置 4人的起始位置
:param line: 地图，用字符串表示，每一行表示每一关的地图。
:param col: 地图的长宽，由于设定为10*10，默认为10
"""
self.line = line
# 0-路 1-墙 2-箱子开始 3-箱子结束 4-人
# sta和en 表示开始的状态，结束的状态
# sta只有2,4,0， 2表示箱子开始位置,4表示人的位置,0表示其他。
# en只有1,3,0， 1表示墙,3表示箱子结束位置,0表示其他。
# 现在只需要把sta状态中的2位置移动到en的3的位置即满足条件
self.sta = ‘‘
self.en = ‘‘
self.col = col
# px, py表示人的位置
self.px, self.py = -1, -1
# paths记录最短路径(可能有多条)
self.paths = []
# len记录最短路径长度
self.len = -1
self.pre()
self.bfs()
print(self.paths)
def pre(self):
"""
1.获得sta开始状态和en结束状态
2.获得人的起始位置px,py
第一关的地图可视化为
1111111111
1111111111
1110001111
1110221111
1114201111
1111100111
1111300111
1113300111
1111111111
1111111111
"""
# mp = []
# for pos in range(0, 100, 10):
# mp.append(self.line[pos : pos + 10])
# print(self.line)
# for x in mp:
# print(x)
for pos, enum in enumerate(self.line):
cx, cy = pos // 10, pos % 10 # 当前位置坐标
if enum == ‘4‘:
self.px, self.py = cx, cy # 人的起始位置
# 0-路 1-墙 2-箱子开始 3-箱子结束 4-人
# 开始状态只有 2,4,0，结束状态只有 1,3,0
# 现在只需要把sta开始的状态中的2位置移动到en的3的位置即满足条件
# stadic：0-0 路是路 1-0 ？？ 2-2 箱子开始是箱子 3-0 箱子结束位置是路 4-4 人初始位置是人
# endic：0-0 路是路 1-1 墙是墙 2-0 箱子开始位置变成路 3-3 箱子结束是箱子 4-0 人初始位置变成路
stadic = {‘0‘: ‘0‘, ‘1‘: ‘0‘, ‘2‘: ‘2‘, ‘3‘: ‘0‘, ‘4‘: ‘4‘}
endic = {‘0‘: ‘0‘, ‘1‘: ‘1‘, ‘2‘: ‘0‘, ‘3‘: ‘3‘, ‘4‘: ‘0‘}
# 字符串拼接，得到起止状态
for x in self.line:
self.sta += stadic[x]
self.en += endic[x]
print(self.sta)
print(self.en)
def is_ok(self, sta):
"""
sta状态中的2位置移动到en的3的位置。
:param sta:
:return:
"""
for s, e in zip(sta, self.en):
if e == ‘3‘ and s != ‘2‘:
return False
return True # 当前状态 sta 就是满足要求的最终状态
def bfs(self):
"""
bfs获得最短路径保存到paths中
:return:
"""
# 4个方向，小写代表只是人移动，大写表示人推着箱子一起移动
dirs = [[-1,0,‘u‘,‘u‘],[1,0,‘d‘,‘d‘],[0,1,‘r‘,‘r‘],[0,-1,‘l‘,‘l‘]]
# 把开始的状态进入队列(list模拟)，状态包括字符串表示的当前状态、当前的路径、当前人的位置
states = [[self.sta, ‘‘, self.px, self.py]]
# 访问数组(dict模拟)，访问过的状态(字符串)不再访问
visi = {}
visi[self.sta] = 1
s_len = 1000
while len(states) > 0:
print(states)
sta, path, px, py = states[0] # 初始状态：状态、路径、人的位置
# 4状态的位置
ppos = px * self.col + py # 人的真实位置（0-100）
states = states[1:] # 把前面的状态剔掉
if len(path) > s_len: # 如果路径长度大于 1000，就……不玩了？？
break
print(sta)
# 保存最短路径到paths中
if self.is_ok(sta):
if self.len == -1 or len(path) == self.len: # 应该是 <= 吧？
self.paths.append(path)
self.len = len(path)
continue
for dir in dirs:
# 向四个方向移动一步后人的坐标
cx, cy = px + dir[0], py + dir[1]
pos = cx * self.col + cy
# 向四个方向移动两步后人的坐标
nx, ny = px + 2*dir[0], py + 2*dir[1]
npos = nx*self.col + ny
# 0-路 1-墙 2-箱子 3-箱子结束 4-人
if not (nx>=0 and nx==0 and ny):
continue
# 括号中条件为真（nx=0,ny≠0），继续执行下面的语句
# 括号中条件为假，跳过下面的语句
# python中字符串不可更改，于是把字符串变成list更改状态后再转换为字符串
if sta[pos] == ‘2‘ and sta[npos] == ‘0‘ and self.en[npos] != ‘1‘:
# 人和箱子一起推动，sta中连着的状态为4 2 0，en中第三个不能为1。推完之后sta变为0 4 2
digits = [int(x) for x in sta]
digits[ppos], digits[pos], digits[npos] = 0,4,2
new_sta = ‘‘.join(str(x) for x in digits)
if new_sta not in visi:
visi[new_sta] = 1
states.append([new_sta, path+dir[3], cx, cy])
elif sta[pos] == ‘0‘ and self.en[pos] !=‘1‘:
# 人动箱子不动，sta中连着的状态为4 0，en中第二个不能为1。
digits = [int(x) for x in sta]
digits[ppos], digits[pos] = 0, 4
new_sta = ‘‘.join(str(x) for x in digits)
if new_sta not in visi:
visi[new_sta] = 1
states.append([new_sta, path + dir[2], cx, cy])
if __name__ == ‘__main__‘:
f = open(level_file_path, encoding=‘utf-8‘)
cnt = 0
while(1):
line = f.readline()
line = line.strip(‘\n‘)
if len(line)==0:
break
gs = gameshortest(line)
level_file.txt 文件中的内容是这样的：
1111111111111111111111100011111110221111111420111111111001111111300111111330011111111111111111111111
1111111111104000000110000200111001101011100100101110010010111001011001110030000111111111111111111111
1111111111111111111111111111111110311111140020001110230020111111311111111111111111111111111111111111
1111111111111111111111100011111110221111111013311111102301111110040111111111111111111111111111111111
1111111111111111111111111111111100000111112111001113030020111400100011111111111111111111111111111111
1111111111111111111111111111111110011111100000011111001220111140300311111111111111111111111111111111
1111111111110040001110000000111001110011110011001111020130111100002011111311111111111111111111111111
1111111111111111111111111111111100111111100320001110131210111000000411111111111111111111111111111111
1111111111111111111111111111111100000111100111011110002020111000133411111111111111111111111111111111
1111111111111111111111100111111110004111111101011111312100111132001011113000201111111111111111111111
1111111111111111111111000001111131103111110402011111001201111100100111111111111111111111111111111111
1111111111111111111111100001111113112011110234001111001000111100001111111111111111111111111111111111
1111111111111111111111111001111110204111111020011111300101111130000111111111111111111111111111111111
1111111111111111111111143001111100000111110010211111001203111111101011111110001111111111111111111111
1111111111111111111111111111111100001111110202111111033420111111130011111111111111111111111111111111
1111111111111111111111110001111100230111114032301111110120111111000111111111111111111111111111111111
1111111111111111111111110031111102010111110020011111031401111100001111111111111111111111111111111111
1111111111111111111111111104111113110011110330201111021200111100001111111111111111111111111111111111
1111111111111111111111000111111100330111110011211111100100111112000411111001111111111111111111111111
1111111111111111111111100001111103032111110024001111111010111111100011111111111111111111111111111111
note
- 看代码遇到看不懂的行，不要死磕，试着从运行结果推断其作用。
- 希望有一天能完完全全实现一个自己的解决方案。