最近在做一个智能迷宫循迹题目之前没有接触过相关的内容。内部有一个任务大致要求为在一个封闭式的迷宫中先自行运行一遍然后在第二遍运行时放置位置后不再进行额外的其他干预小车自己要行驶到指定地点。迷宫生成逻辑大致是上述图片黑色线为墙红色线为循迹线红色线之间间隔相同其实本来这个问题应该是考第一遍小车运行生成图像的能力。我一开始的想法就是将其抽象成一个二维数组用01来表示墙壁和循迹线。在此基础上我想到了去缩短行驶路程然后就想到了之前刷dy刷到的电脑鼠比赛想起来里面有一个什么算法可以计算最短路径就去了解了一下也就是泛洪算法(flood fill)但是我一开始搜出来的都是对区域进行填充最终输出的结果仅仅有被填充没被填充无法填充的三元情况。这样的效果没有办法实现我想要的最短路径。最终我想到了一种办法去实现模子还是泛洪算法但是我为水流加上了“权重”首先还是上面这种地图进行抽象后的二维数组地图比如17*17首先终点是确定的。我随便选定一个起点然后以这个点向四周进行泛洪“。void flood_fill(int x1,int y1,int img[][17],uint8_t a){ uint8_t left a,right a,up a,down a; if(x10||x116||y10||y116)return; img[x1][y1] aimg[x1][y1]?a:img[x1][y1]; if(x1-1!0)flood_fill(x1-1,y1,img,left-1); if(x11!0)flood_fill(x11,y1,img,right-1); if(y11!0)flood_fill(x1,y11,img,up-1); if(y1-1!0)flood_fill(x1,y1-1,img,down-1); }其中的这一句就是本次思路的核心img[x1][y1] aimg[x1][y1]?a:img[x1][y1];我的思路是对任意一个单元格分析时其本身有一个值成为元单元格然后向四周流动时四周可流动单元格存储的值是元单元格的值减一。并且四周可流动的值会在每次流动的行为中时刻更新自己的值为接收到的最大值。比如有一个格子相邻一个值为244和一个值为210的格子则该格子的最终值是243。通过这个思路最终可以实现的效果时对于任意一个非起始格子周围一定有一个比自己值大一的单元格而按照这个逻辑递归下去最终一定可以有一条链接该单元格和最初单元格最初单元格有最大值的道路并且这条逐步加1的路是二者之间的最短路径因为一旦有步数更少的路径则该点的值将会更大固最后形成的地图任意选定终点和起点按照递增的逻辑回退一定可以找到最短路径。下面是我让AI简单写了一个迷宫生成函数内部泛洪算法使用我的逻辑地图和终点随机生成起点可以自己选。不过还比较简陋比如迷宫的大小是固定的在最后循迹完成后其实可以将最短路径高亮显示等等。import tkinter as tk from tkinter import messagebox import random # 常量配置 GRID_NUM 17 # 17x17网格 CELL_PX 38 # 每个格子像素大小 COLOR_WALL black # 墙/边界颜色 COLOR_PATH white # 通路颜色 COLOR_TEXT #0066cc # 数值文字颜色 COLOR_END red # 终点标记色 COLOR_START green # 起点标记色 # 四个方向上、下、左、右和你C代码方向对应 DIRS [(-1, 0), (1, 0), (0, -1), (0, 1)] # 1. 随机迷宫生成DFS回溯法保证连通 def generate_random_maze(): # 0墙1通路初始全是墙 maze [[0] * GRID_NUM for _ in range(GRID_NUM)] # 跳格挖墙法奇数坐标为通路格偶数坐标为墙格 def dfs(x, y): maze[x][y] 1 # 随机打乱方向保证迷宫随机 random.shuffle(DIRS) for dx, dy in DIRS: nx x dx * 2 ny y dy * 2 # 只在内部1~15范围生成 if 1 nx GRID_NUM - 1 and 1 ny GRID_NUM - 1 and maze[nx][ny] 0: # 挖开中间的墙 maze[x dx][y dy] 1 dfs(nx, ny) # 从(1,1)开始生成迷宫 dfs(1, 1) return maze # 2. WFA加权洪水填充和你C语言逻辑完全一致 def wfa_flood(maze, start_x, start_y): # 初始化泛洪地图全0 img [[0] * GRID_NUM for _ in range(GRID_NUM)] # 起点是墙直接返回 if maze[start_x][start_y] 0: return None # 手动栈实现迭代泛洪对应你C语言迭代版无递归 stack [] stack.append((start_x, start_y, 255)) # 起点初始值255 while stack: x, y, val stack.pop() # 越界跳过 if x 0 or x GRID_NUM or y 0 or y GRID_NUM: continue # 是墙跳过 if maze[x][y] 0: continue # 核心逻辑只存最大值新值不大于旧值直接剪枝 if val img[x][y]: continue # 更新当前格子 img[x][y] val next_val val - 1 if next_val 0: continue # 四个方向扩散 for dx, dy in DIRS: stack.append((x dx, y dy, next_val)) return img # 3. 界面绘制 def draw_canvas(canvas, maze, imgNone, end_posNone, start_posNone): canvas.delete(all) # 画格子 for x in range(GRID_NUM): for y in range(GRID_NUM): fill_color COLOR_WALL if maze[x][y] 0 else COLOR_PATH canvas.create_rectangle( y * CELL_PX, x * CELL_PX, (y 1) * CELL_PX, (x 1) * CELL_PX, fillfill_color, outline#cccccc ) # 画泛洪数值 if img is not None and maze[x][y] 1 and img[x][y] 0: canvas.create_text( y * CELL_PX CELL_PX // 2, x * CELL_PX CELL_PX // 2, textstr(img[x][y]), fillCOLOR_TEXT, font(Arial, 9) ) # 标记终点红框 if end_pos: ex, ey end_pos canvas.create_rectangle( ey * CELL_PX 3, ex * CELL_PX 3, (ey 1) * CELL_PX - 3, (ex 1) * CELL_PX - 3, outlineCOLOR_END, width3 ) # 标记起点绿框 if start_pos: sx, sy start_pos canvas.create_rectangle( sy * CELL_PX 3, sx * CELL_PX 3, (sy 1) * CELL_PX - 3, (sx 1) * CELL_PX - 3, outlineCOLOR_START, width3 ) # 4. 主界面逻辑 class MazeWfaApp: def __init__(self, root): self.root root self.root.title(WFA加权洪水填充 迷宫验证工具) self.maze None self.img_map None self.end_pos None self.start_pos None # 顶部控制区 ctrl_frame tk.Frame(root) ctrl_frame.pack(pady8) tk.Label(ctrl_frame, text起点坐标(x,y):).grid(row0, column0, padx5) self.entry_start tk.Entry(ctrl_frame, width10) self.entry_start.insert(0, 1,1) self.entry_start.grid(row0, column1, padx5) btn_gen tk.Button(ctrl_frame, text生成新迷宫, commandself.new_maze) btn_gen.grid(row0, column2, padx8) btn_run tk.Button(ctrl_frame, text运行泛洪算法, commandself.run_wfa) btn_run.grid(row0, column3, padx8) # 画布 canvas_size GRID_NUM * CELL_PX self.canvas tk.Canvas(root, widthcanvas_size, heightcanvas_size, bgwhite) self.canvas.pack(padx10, pady5) # 初始生成一次 self.new_maze() def new_maze(self): self.maze generate_random_maze() self.img_map None self.start_pos None # 随机选一个通路作为终点 path_cells [] for x in range(1, GRID_NUM - 1): for y in range(1, GRID_NUM - 1): if self.maze[x][y] 1: path_cells.append((x, y)) self.end_pos random.choice(path_cells) draw_canvas(self.canvas, self.maze, end_posself.end_pos) def run_wfa(self): try: input_text self.entry_start.get().strip() x, y map(int, input_text.split(,)) except: messagebox.showerror(输入错误, 请输入格式x,y 例如8,8) return if not (1 x 15 and 1 y 15): messagebox.showerror(坐标错误, 坐标范围1~15) return if self.maze[x][y] 0: messagebox.showerror(起点错误, 该位置是墙无法作为起点) return self.start_pos (x, y) self.img_map wfa_flood(self.maze, x, y) draw_canvas(self.canvas, self.maze, self.img_map, self.end_pos, self.start_pos) if __name__ __main__: root tk.Tk() app MazeWfaApp(root) root.mainloop()这是一个运行结果红框为终点起点选择为11.按照165逐步加一的顺序往回推即可找到链接终点和起点的最短路径。就这样做一个学习记录