转珠游戏（如神魔之塔等）高Combo路径计算器

不知道有没有人玩过转珠类游戏，比如神魔之塔这种。

它的核心玩法就是在6×5的棋盘上通过一次性移动珠子使得不同颜色的珠子连成3个或以上的直排或横排即可发生消除。

千万别以为是简单的消消乐游戏，其实要达成高Combo（一般5连击以上）还是挺有难度的。

于是，想到了让程序通过穷举法来计算高Combo的路径。

先上Python的代码：

#coding: utf-8
import copy
import time

mx = [
[0,0,1,0,3,2],
[0,2,3,4,1,1],
[3,2,2,1,3,5],
[3,3,1,4,4,5],
[0,3,1,4,5,0],
]

class ZhuanZhu():
def __init__(self, m):
self.m = m
self.max = 0
self.step = 0
self.optimization = []
#self.visited = [m]
self.history = [[m, [(i, j)]] for i in range(5) for j in range(6)]

def move(self):
dir = [(0,1),(1,0),(0,-1),(-1,0)]
history = copy.deepcopy(self.history)
self.history = []
while history:
each = history.pop()
m = each[0]
path = each[1]
pos = path[len(path)-1]
x, y = pos
for d in dir:
dm = copy.deepcopy(m)
dp = copy.deepcopy(path)
nx, ny = x+d[0], y+d[1]
if nx<0 or nx>4 or ny<0 or ny>5:
continue
if (nx, ny) in path:
continue
tmp = dm[nx][ny]
dm[nx][ny] = dm[x][y]
dm[x][y] = tmp
#if dm not in self.visited:
self.step += 1
#self.visited.append(dm)
dp.append((nx,ny))
self.history.append([dm, dp])

def judge(self):
most = 0
maxcount = []
for each in self.history:
m = each[0]
path = each[1]
count = 0
for row in m:
c = 1
for i in range(1,6):
if row[i] == row[i-1]:
c += 1
else:
if c>=3:
c += 1
else:
c = 1
continue
if i == 5 and c>=3:
count += 1
for row in [[m[i][j] for i in range(5)] for j in range(6)]:
c = 1
for i in range(1,5):
if row[i] == row[i-1]:
c += 1
else:
if c>=3:
c += 1
else:
c = 1
continue
if i == 4 and c>=3:
count += 1
if count > most:
most = count
maxcount = each
self.max = most
self.optimization = maxcount

def print(self):
m = copy.deepcopy(self.m)
opt = self.optimization[0]
path = self.optimization[1]
for x,y in path:
m[x][y] = "*"
print("初始：")
for row in self.m:
for e in row:
print(e, end=" ")
print()
print(f"最大连击Combo数：{self.max}")
print("最优解：")
for row in opt:
for e in row:
print(e, end=" ")
print()
print(f'路径：{path}')
for row in m:
for e in row:
print(e, end=" ")
print()
print(f'总共模拟了：{self.step}种组合')


t = time.time()

zz = ZhuanZhu(mx)
for r in range(8):
zz.move()
zz.judge()
zz.print()

print(f"用时：{int(time.time()-t)}秒")

执行结果：

pi@raspberrypi:~/Documents/Python Projects $ /bin/python3 "/home/pi/Documents/Python Projects/zhuanzhu.py"

初始：

0 0 1 0 3 2 

0 2 3 4 1 1 

3 2 2 1 3 5 

3 3 1 4 4 5 

0 3 1 4 5 0 

最大连击Combo数：5

最优解：

0 0 0 1 3 2 

0 2 3 0 1 1 

3 2 1 4 3 5 

3 2 1 4 4 5 

3 3 1 4 5 0 

路径：[(4, 0), (3, 0), (3, 1), (2, 1), (2, 2), (2, 3), (1, 3), (0, 3), (0, 2)]

0 0 * * 3 2 

0 2 3 * 1 1 

3 * * * 3 5 

* * 1 4 4 5 

* 3 1 4 5 0 

总共模拟了：48310种组合

用时：18秒