机器人走迷宫编程题目
import matplotlib.pyplot as plt
from queue import PriorityQueue
class MazeSolver:
def __init__(self, width=20, height=20):
self.width = width
self.height = height
self.maze = None
self.start = (1, 1)
self.end = (height-2, width-2)
def generate_maze(self, density=0.3):
self.maze = np.zeros((self.height, self.width))
生成随机障碍物
for i in range(self.height):
for j in range(self.width):
if np.random.random < density and (i,j) != self.start and (i,j) != self.end:
self.maze[i][j] = 1 1表示障碍物
return self.maze
def solve_astar(self):
A算法实现
directions = [(0,1),(1,0),(0,-1),(-1,0)]
open_set = PriorityQueue
open_set.put((0, self.start))
came_from = {}
g_score = {self.start: 0}
f_score = {self.start: self._heuristic(self.start)}
while not open_set.empty:
current = open_set.get[1]
if current == self.end:
return self._reconstruct_path(came_from)
for dx, dy in directions:
neighbor = (current[0]+dx, current[1]+dy)
if not self._is_valid(neighbor):
continue
tentative_g = g_score[current] + 1
if neighbor not in g_score or tentative_g < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score[neighbor] = tentative_g + self._heuristic(neighbor)
open_set.put((f_score[neighbor], neighbor))
return [] 无解
def visualize(self, path=[]):
plt.figure(figsize=(10,10))
plt.imshow(self.maze, cmap='binary')
plt.plot(self.start[1], self.start[0], 'go') 起点绿色
plt.plot(self.end[1], self.end[0], 'ro') 终点红色
if path:
xs, ys = zip(path)
plt.plot(ys, xs, 'b-', linewidth=2)
plt.xticks([]), plt.yticks([])
plt.show
def _heuristic(self, pos):
return abs(pos[0]
def _is_valid(self, pos):
x, y = pos
return 0 <= x < self.height and 0 <= y < self.width and self.maze[x][y] != 1
def _reconstruct_path(self, came_from):
path = [self.end]
while path[-1] != self.start:
path.append(came_from[path[-1]])
return path[::-1]
if __name__ == "__main__":
solver = MazeSolver(30, 30)
maze = solver.generate_maze(0.25)
path = solver.solve_astar
solver.visualize(path)
numpy>=1.21.0
matplotlib>=3.4.0