迷宫路径规划：Python编程走迷宫的最优
迷宫路径规划：Python编程走迷宫的最优
走迷宫的最优解法，迷宫路径规划:
绿色起点和红色终点
灰色障碍物
黄色表示开放列表中的候选节点
蓝色表示已探索的关闭列表节点
红色线条显示最终路径
通过方向键1调节算法速度按 R 键重新生成迷宫
import pygame
import random
from heapq import heappush, heappop
from collections import deque
class VisualCell:
def __init__(self, x, y, cell_size):
self.rect = pygame.Rect(x * cell_size, y * cell_size, cell_size, cell_size)
self.walls = {'top': True, 'right': True, 'bottom': True, 'left': True}
self.is_obstacle = False
self.came_from = None
self.g_score = float('inf')
self.f_score = float('inf')
class PathFinder:
def __init__(self, cols=25, rows=25, cell_size=30):
self.cell_size = cell_size
self.cols = cols
self.rows = rows
self.grid = [[VisualCell(x, y, cell_size) for x in range(cols)] for y in range(rows)]
# 初始化起点终点
self.start = (0, 0)
self.end = (cols - 1, rows - 1)
self.generate_maze()
self.add_obstacles(0.25)
self.init_algorithm()
def init_algorithm(self):
# 初始化算法数据结构
self.open_set = []
self.closed_set = set()
self.path = deque()
self.found = False
self.done = False
start_cell = self.grid[self.start[1]][self.start[0]]
start_cell.g_score = 0
start_cell.f_score = self.heuristic(self.start, self.end)
heappush(self.open_set, (start_cell.f_score, self.start))
def generate_maze(self):
stack = [self.start]
visited = set(stack)
while stack:
x, y = stack.pop()
current = self.grid[y][x]
neighbors = []
# 获取未访问的邻居
directions = [
('left', x - 1, y),
('right', x + 1, y),
('top', x, y - 1),
('bottom', x, y + 1)
]
for direction in directions:
dir_name, nx, ny = direction
if 0 <= nx < self.cols and 0 <= ny < self.rows:
if (nx, ny) not in visited:
neighbors.append(direction)
if neighbors:
stack.append((x, y))
dir_name, nx, ny = random.choice(neighbors)
next_cell = self.grid[ny][nx]
# 拆除墙壁
if dir_name == 'left':
current.walls['left'] = False
next_cell.walls['right'] = False
elif dir_name == 'right':
current.walls['right'] = False
next_cell.walls['left'] = False
elif dir_name == 'top':
current.walls['top'] = False
next_cell.walls['bottom'] = False
elif dir_name == 'bottom':
current.walls['bottom'] = False
next_cell.walls['top'] = False
visited.add((nx, ny))
stack.append((nx, ny))
def add_obstacles(self, ratio):
candidates = [(x, y) for y in range(self.rows) for x in range(self.cols)
if (x, y) != self.start and (x, y) != self.end]
random.shuffle(candidates)
for x, y in candidates[:int(len(candidates) * ratio)]:
self.grid[y][x].is_obstacle = True
# 确保路径存在
while not self.verify_path():
if not candidates:
break
x, y = candidates.pop()
self.grid[y][x].is_obstacle = False
def verify_path(self):
temp_open = []
heappush(temp_open, (0, self.start))
visited = set()
while temp_open:
current_cost, current = heappop(temp_open)
if current == self.end:
return True
if current in visited:
continue
visited.add(current)
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = current[0] + dx, current[1] + dy
if 0 <= nx < self.cols and 0 <= ny < self.rows:
if self.grid[ny][nx].is_obstacle:
continue
if not self.can_pass(current, (nx, ny)):
continue
heappush(temp_open, (self.heuristic((nx, ny), self.end), (nx, ny)))
return False
def heuristic(self, a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def can_pass(self, from_pos, to_pos):
fx, fy = from_pos
tx, ty = to_pos
cell = self.grid[fy][fx]
if tx == fx + 1: return not cell.walls['right']
if tx == fx - 1: return not cell.walls['left']
if ty == fy + 1: return not cell.walls['bottom']
if ty == fy - 1: return not cell.walls['top']
return False
def algorithm_step(self):
if self.done or not self.open_set:
return
current_f, current = heappop(self.open_set)
current_cell = self.grid[current[1]][current[0]]
if current == self.end:
self.reconstruct_path(current_cell)
self.done = True
return
self.closed_set.add(current)
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = current[0] + dx, current[1] + dy
if 0 <= nx < self.cols and 0 <= ny < self.rows:
neighbor_cell = self.grid[ny][nx]
if neighbor_cell.is_obstacle or (nx, ny) in self.closed_set:
continue
if not self.can_pass(current, (nx, ny)):
continue
tentative_g = current_cell.g_score + 1
if tentative_g < neighbor_cell.g_score:
neighbor_cell.came_from = current_cell
neighbor_cell.g_score = tentative_g
neighbor_cell.f_score = tentative_g + self.heuristic((nx, ny), self.end)
heappush(self.open_set, (neighbor_cell.f_score, (nx, ny)))
def reconstruct_path(self, end_cell):
current = end_cell
while current is not None:
x = current.rect.x // self.cell_size
y = current.rect.y // self.cell_size
self.path.appendleft((x, y))
current = current.came_from
class Visualization:
def __init__(self):
pygame.init()
self.finder = PathFinder()
self.screen = pygame.display.set_mode(
(self.finder.cols * self.finder.cell_size,
self.finder.rows * self.finder.cell_size))
pygame.display.set_caption("Maze Pathfinding Visualization")
self.clock = pygame.time.Clock()
self.speed = 20 # 初始速度：20步/秒
def draw_grid(self):
self.screen.fill((255, 255, 255))
# 绘制所有单元格
for y in range(self.finder.rows):
for x in range(self.finder.cols):
cell = self.finder.grid[y][x]
color = (255, 255, 255)
if cell.is_obstacle:
color = (100, 100, 100)
elif (x, y) == self.finder.start:
color = (0, 255, 0)
elif (x, y) == self.finder.end:
color = (255, 0, 0)
pygame.draw.rect(self.screen, color, cell.rect.inflate(-2, -2))
# 绘制墙壁
if cell.walls['top']:
pygame.draw.line(self.screen, (0, 0, 0),
(cell.rect.left, cell.rect.top),
(cell.rect.right, cell.rect.top), 2)
if cell.walls['right']:
pygame.draw.line(self.screen, (0, 0, 0),
(cell.rect.right, cell.rect.top),
(cell.rect.right, cell.rect.bottom), 2)
if cell.walls['bottom']:
pygame.draw.line(self.screen, (0, 0, 0),
(cell.rect.right, cell.rect.bottom),
(cell.rect.left, cell.rect.bottom), 2)
if cell.walls['left']:
pygame.draw.line(self.screen, (0, 0, 0),
(cell.rect.left, cell.rect.bottom),
(cell.rect.left, cell.rect.top), 2)
# 绘制算法状态
self.draw_algorithm_state()
self.draw_path()
pygame.display.flip()
def draw_algorithm_state(self):
# 开放列表（黄色）
for _, (x, y) in self.finder.open_set:
rect = self.finder.grid[y][x].rect.inflate(-8, -8)
pygame.draw.rect(self.screen, (255, 255, 0), rect)
# 关闭列表（蓝色）
for pos in self.finder.closed_set:
x, y = pos
rect = self.finder.grid[y][x].rect.inflate(-8, -8)
pygame.draw.rect(self.screen, (0, 0, 255), rect)
def draw_path(self):
if self.finder.path:
path = list(self.finder.path)
for i in range(len(path) - 1):
start = (path[i][0] * self.finder.cell_size + self.finder.cell_size // 2,
path[i][1] * self.finder.cell_size + self.finder.cell_size // 2)
end = (path[i + 1][0] * self.finder.cell_size + self.finder.cell_size // 2,
path[i + 1][1] * self.finder.cell_size + self.finder.cell_size // 2)
pygame.draw.line(self.screen, (255, 0, 0), start, end, 4)
def run(self):
last_update = 0
running = True
while running:
current_time = pygame.time.get_ticks()
# 处理事件
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
elif event.type == pygame.KEYDOWN:
if event.key == pygame.K_r: # 重置
self.finder = PathFinder()
elif event.key == pygame.K_UP: # 加速
self.speed = min(100, self.speed + 5)
elif event.key == pygame.K_DOWN: # 减速
self.speed = max(1, self.speed - 5)
# 更新算法
if current_time - last_update > 1000 // self.speed and not self.finder.done:
self.finder.algorithm_step()
last_update = current_time
# 绘制界面
self.draw_grid()
self.clock.tick(60)
pygame.quit()
if __name__ == "__main__":
vis = Visualization()
vis.run()原文地址：https://blog.csdn.net/2301_76444133/article/details/146440124
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！