一个“一笔画”问题的求解器

发布于 1970年 01月 01日 08:00

回老家跟侄子玩,因为不想惯着他玩手机的臭毛病,就跟他玩一些纸笔游戏,比如这个:

从起点出发抵达终点,如何在不走重复格子的前提下,走过尽可能多的格子,并吃到尽可能多的金币?其中,黑色格子是墙壁不能走。

感觉还挺有意思的,不妨就来写一个“一笔画”的求解器,找出所有最优的轨迹。

思路:

可以先输出所有从起点到终点的轨迹,然后建立一个评分系统对所有轨迹进行评估:每走一个格子+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
View Code

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()  
View Code