一个“一笔画”问题的求解器
回老家跟侄子玩，因为不想惯着他玩手机的臭毛病，就跟他玩一些纸笔游戏，比如这个：
从起点出发抵达终点，如何在不走重复格子的前提下，走过尽可能多的格子，并吃到尽可能多的金币？其中，黑色格子是墙壁不能走。
感觉还挺有意思的，不妨就来写一个“一笔画”的求解器，找出所有最优的轨迹。
思路：
可以先输出所有从起点到终点的轨迹，然后建立一个评分系统对所有轨迹进行评估：每走一个格子+1分，每吃一个金币+1分，最后输出评分最高的轨迹即可。
Step1：建模
一个如图的迷宫可以很自然地用矩阵描述，对于每一个元素，值0表示空格子，值1表示金币，值-1表示墙壁，值2表示起点，值3表示终点。
import numpy as np ROW, COL = 6, 4 maze = np.zeros((ROW,COL)) START = (0, 3) OUT = (5, 0) maze[START] = 2 maze[OUT] = 3 maze[1, 1] = 1 maze[5, 3] = 1 maze[2, 1] = -1 maze[4, 2] = -1
Step2：寻迹算法
一条轨迹可以拆分成多个“步”，在走每一步之前，所作的事情是一样的：找到下一步能到达的合法位置，然后选择其中一个。如果新位置是死路或者是终点，那么结束或输出该轨迹，并返回到上一步所在的位置，选择其他步。这一过程可以很好地由递归函数表达：
def step(start, track, env): x, y = start next_pos = [] for i, j in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]: if 0 <= i <= ROW-1 and 0 <= j <= COL-1: # 边界限制 if (i, j) in track: # 重复的格子不能走 continue if env[i,j] == -1: # 有墙壁的格子不能走 continue next_pos.append((i, j)) for i, j in next_pos: track_new = track.copy() track_new.append((i, j)) if (i, j) == OUT: global tracks tracks.append(track_new) return start_new = (i, j) step(start_new, track_new, env)
运行一下：
tracks = [] step(START, [START], maze) print(len(tracks))
输出为192，说明从起点到终点的轨迹有192条
Step3：评分器
每走一个格子+1分，每吃一个金币+1分，输出评分最高的轨迹。
def findOptimalTracks(tracks): # 统计所有track的分数 # 分数：每走过一个格子+1，若是金币格子则额外+1 scores = [] for track in tracks: score = 0 if (1, 1) in track: score += 1 if (5, 3) in track: score += 1 score += len(track) scores.append(score) tracks_optimal = [] maxScore = max(scores) for i, score in enumerate(scores): if score == maxScore: tracks_optimal.append(tracks[i]) return tracks_optimal
运行一下：
tracks_optimal = findOptimalTracks(tracks) print(len(tracks_optimal))
输出为9，说明最优的轨迹有9条。
Step4：可视化
其实事情到上一步就已经结束了，这里就当看个乐子吧！用pygame把所有轨迹呈现出来：
class tracksRender(): def __init__(self, tracks, env): pygame.init() SIZE = 75 ROW, COL = env.shape self.window = pygame.display.set_mode((COL*SIZE, ROW*SIZE)) pygame.display.set_caption('一笔画') self.running = True self.clock = pygame.time.Clock() # 帧数控制 self.time = time.time() # 时间控制 self.INTERVAL = 0.1 # 动作间隔 self.FPS = 30 # 帧数 self.env = env self.tracks = tracks self.track = [] # 存放当前将显示的轨迹 self.track_render = [] # 存放当前显示的部分轨迹 def processInput(self): for event in pygame.event.get(): # 按下右上角的退出键 if event.type == pygame.QUIT: self.running = False break def update(self): if time.time() - self.time < self.INTERVAL: # 设定更新间隔 return if self.tracks == []: # 如果已经显示完所有轨迹 则函数返回 return if self.track == []: # 如果当前轨迹已经完全显示 则显示下一条轨迹 self.track = self.tracks.pop(0) self.track_render = [] self.track_render.append(self.track.pop(0)) self.time = time.time() def render(self): SIZE = 75 ROW, COL = self.env.shape BGCOLOR = (226, 240, 217) # 浅草绿 self.window.fill(BGCOLOR) DarkKhaki = (189, 183, 107) # 深卡其布 Wall = (139, 126, 102) # 灰墙 Orange = (255, 165, 0) # 橘子 DodgerBlue = (30, 144, 255) # 道奇蓝 Gold = (255, 215, 0) # 黄金 Font = pygame.font.SysFont('arial', 40) # 画分隔线 for i in range(ROW + 1): pygame.draw.line(self.window, DarkKhaki, (0, i*SIZE), (COL*SIZE, i*SIZE), 3) for i in range(COL + 1): pygame.draw.line(self.window, DarkKhaki, (i*SIZE, 0), (i*SIZE, ROW*SIZE), 3) # 画特殊格子 for i in range(ROW): for j in range(COL): if self.env[i, j] == -1: # 墙壁 pygame.draw.polygon(self.window, Wall, ((j*SIZE, i*SIZE), ((j+1)*SIZE, i*SIZE), ((j+1)*SIZE, (i+1)*SIZE), (j*SIZE, (i+1)*SIZE)) ,0) if self.env[i, j] == 2: # 起点 Start_text = Font.render('S', True, Orange) self.window.blit(Start_text, ((j+0.3)*SIZE, (i+0.2)*SIZE)) if self.env[i, j] == 3: # 终点 Start_text = Font.render('E', True, DodgerBlue) self.window.blit(Start_text, ((j+0.3)*SIZE, (i+0.2)*SIZE)) if self.env[i, j] == 1: # 金币 pygame.draw.circle(self.window, Gold, ((j+0.5)*SIZE,(i+0.5)*SIZE), 20) # 画轨迹线 if len(self.track_render) > 1: for i, point in enumerate(self.track_render): if i == 0: continue x_, y_ = self.track_render[i-1] x, y = point pygame.draw.line(self.window, Orange, ((y_+0.5)*SIZE, (x_+0.5)*SIZE), ((y+0.5)*SIZE, (x+0.5)*SIZE), 5) pygame.display.update() # 刷新显示 def run(self): while self.running: self.processInput() self.update() self.render() self.clock.tick(self.FPS)
效果如下：
整体代码如下：
""" 走迷宫 玩家从起点出发，到达终点走出迷宫 迷宫可由矩阵描述，例如以下6×4的迷宫 [ 0 0 0 2 0 1 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 3 0 0 1 ] 其中，2表示起点，3表示终点，-1表示墙壁（无法行动到该位置），1表示金币 问，如何在不走重复格子的前提下，走出迷宫，并吃到最多的金币，且走过最多的格子？请打印路径 """ import numpy as np import pygame import time def step(start, track, env): x, y = start next_pos = [] for i, j in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]: if 0 <= i <= ROW-1 and 0 <= j <= COL-1: # 边界限制 if (i, j) in track: # 重复的格子不走 continue if env[i,j] == -1: # 有墙壁的格子不能走 continue next_pos.append((i, j)) for i, j in next_pos: track_new = track.copy() track_new.append((i, j)) if (i, j) == OUT: global tracks tracks.append(track_new) return start_new = (i, j) step(start_new, track_new, env) def findOptimalTracks(tracks): # 统计所有track的分数 # 分数：每走过一个格子+1，若是金币格子则额外+1 scores = [] for track in tracks: score = 0 if (1, 1) in track: score += 1 if (5, 3) in track: score += 1 score += len(track) scores.append(score) tracks_optimal = [] maxScore = max(scores) for i, score in enumerate(scores): if score == maxScore: tracks_optimal.append(tracks[i]) return tracks_optimal class tracksRender(): def __init__(self, tracks, env): pygame.init() SIZE = 75 ROW, COL = env.shape self.window = pygame.display.set_mode((COL*SIZE, ROW*SIZE)) pygame.display.set_caption('一笔画') self.running = True self.clock = pygame.time.Clock() # 帧数控制 self.time = time.time() # 时间控制 self.INTERVAL = 0.1 # 动作间隔 self.FPS = 30 # 帧数 self.env = env self.tracks = tracks self.track = [] # 存放当前将显示的轨迹 self.track_render = [] # 存放当前显示的部分轨迹 def processInput(self): for event in pygame.event.get(): # 按下右上角的退出键 if event.type == pygame.QUIT: self.running = False break def update(self): if time.time() - self.time < self.INTERVAL: # 设定更新间隔 return if self.tracks == []: # 如果已经显示完所有轨迹 则函数返回 return if self.track == []: # 如果当前轨迹已经完全显示 则显示下一条轨迹 self.track = self.tracks.pop(0) self.track_render = [] self.track_render.append(self.track.pop(0)) self.time = time.time() def render(self): SIZE = 75 ROW, COL = self.env.shape BGCOLOR = (226, 240, 217) # 浅草绿 self.window.fill(BGCOLOR) DarkKhaki = (189, 183, 107) # 深卡其布 Wall = (139, 126, 102) # 灰墙 Orange = (255, 165, 0) # 橘子 DodgerBlue = (30, 144, 255) # 道奇蓝 Gold = (255, 215, 0) # 黄金 Font = pygame.font.SysFont('arial', 40) # 画分隔线 for i in range(ROW + 1): pygame.draw.line(self.window, DarkKhaki, (0, i*SIZE), (COL*SIZE, i*SIZE), 3) for i in range(COL + 1): pygame.draw.line(self.window, DarkKhaki, (i*SIZE, 0), (i*SIZE, ROW*SIZE), 3) # 画特殊格子 for i in range(ROW): for j in range(COL): if self.env[i, j] == -1: # 墙壁 pygame.draw.polygon(self.window, Wall, ((j*SIZE, i*SIZE), ((j+1)*SIZE, i*SIZE), ((j+1)*SIZE, (i+1)*SIZE), (j*SIZE, (i+1)*SIZE)) ,0) if self.env[i, j] == 2: # 起点 Start_text = Font.render('S', True, Orange) self.window.blit(Start_text, ((j+0.3)*SIZE, (i+0.2)*SIZE)) if self.env[i, j] == 3: # 终点 Start_text = Font.render('E', True, DodgerBlue) self.window.blit(Start_text, ((j+0.3)*SIZE, (i+0.2)*SIZE)) if self.env[i, j] == 1: # 金币 pygame.draw.circle(self.window, Gold, ((j+0.5)*SIZE,(i+0.5)*SIZE), 20) # 画轨迹线 if len(self.track_render) > 1: for i, point in enumerate(self.track_render): if i == 0: continue x_, y_ = self.track_render[i-1] x, y = point pygame.draw.line(self.window, Orange, ((y_+0.5)*SIZE, (x_+0.5)*SIZE), ((y+0.5)*SIZE, (x+0.5)*SIZE), 5) pygame.display.update() # 刷新显示 def run(self): while self.running: self.processInput() self.update() self.render() self.clock.tick(self.FPS) if __name__ == "__main__": ROW, COL = 6, 4 maze = np.zeros((ROW,COL)) START = (0, 3) OUT = (5, 0) maze[START] = 2 maze[OUT] = 3 maze[1, 1] = 1 maze[5, 3] = 1 maze[2, 1] = -1 maze[4, 2] = -1 print(' Maze:\n', maze) tracks = [] step(START, [START], maze) tracks_optimal = findOptimalTracks(tracks) tracksRender = tracksRender(tracks_optimal, maze) tracksRender.run() pygame.quit()