Python练习——走迷宫

csx

迷宫地图是随机生成的，部分结果如下：

[Python] 纯文本查看 复制代码

import random
import turtle
from random import randint, choice

CELL_SIZE = 16      # 设置用于绘制迷宫的单元格的尺寸
DOT_SIZE = 5          # 设置起点和终点的尺寸
LINE_SIZE = 3       # 设置探索路径的尺寸
scr = turtle.Screen()  # 建立屏幕对象 src
scr.colormode(255)  # 设置颜色模式为rgb数值模式
wallPen = turtle.Turtle()  # 建立画笔对象 wallPen 用于绘制墙体
pointPen = turtle.Turtle()  # 建立画笔对象 pointPen 用于绘制点
linePen = turtle.Turtle()  # 建立画笔对象 linePen 用于绘制探索路径
linePen.pensize(LINE_SIZE)  #设置画笔粗细为路径尺寸
difficulty=[15,25,45]

class CellType:
    ROAD = 0
    WALL = 1

# 墙的方向
class Direction:
    LEFT = 0,
    UP = 1,
    RIGHT = 2,
    DOWN = 3,

# 迷宫地图
class Maze:

    def __init__(self, width, height):
        self.width = width
        self.height = height
        #生成规定长宽的且内部元素全为0的二维表
        self.maze = [[0 for x in range(self.width)] for y in range(self.height)]

    def reset_maze(self, value):
        for y in range(self.height):
            for x in range(self.width):
                self.set_maze(x, y, value)

    def set_maze(self, x, y, value):
        self.maze[x][y] = CellType.ROAD if value == CellType.ROAD else CellType.WALL

    def visited(self, x, y):
        return self.maze[x][y] != 1

def check_neighbors(maze, x, y, width, height, checklist):
    directions = []
    #判断点的上下左右是否有邻居点
    if x > 0:
        if not maze.visited(2 * (x - 1) + 1, 2 * y + 1):
            directions.append(Direction.LEFT)
    if y > 0:
        if not maze.visited(2 * x + 1, 2 * (y - 1) + 1):
            directions.append(Direction.DOWN)
    if x < width - 1:
        if not maze.visited(2 * (x + 1) + 1, 2 * y + 1):
            directions.append(Direction.RIGHT)
    if y < height - 1:
        if not maze.visited(2 * x + 1, 2 * (y + 1) + 1):
            directions.append(Direction.UP)
    #对邻居点之间的墙进行拆墙并把新的添加到checklist中进行下一次的判断
    if len(directions):
        direction = choice(directions)
        if direction == Direction.LEFT:
            maze.set_maze(2 * (x - 1) + 1, 2 * y + 1, CellType.ROAD)
            maze.set_maze(2 * x, 2 * y + 1, CellType.ROAD)
            checklist.append((x - 1, y))
        elif direction == Direction.DOWN:
            maze.set_maze(2 * x + 1, 2 * (y - 1) + 1, CellType.ROAD)
            maze.set_maze(2 * x + 1, 2 * y, CellType.ROAD)
            checklist.append((x, y - 1))
        elif direction == Direction.RIGHT:
            maze.set_maze(2 * (x + 1) + 1, 2 * y + 1, CellType.ROAD)
            maze.set_maze(2 * x + 2, 2 * y + 1, CellType.ROAD)
            checklist.append((x + 1, y))
        elif direction == Direction.UP:
            maze.set_maze(2 * x + 1, 2 * (y + 1) + 1, CellType.ROAD)
            maze.set_maze(2 * x + 1, 2 * y + 2, CellType.ROAD)
            checklist.append((x, y + 1))
        return True
    return False

def random_prime(map, width, height):
    start_x, start_y = (randint(0, width - 1), randint(0, height - 1))
    #把二维表中所有下标x，y为奇数的元素设置为通路（即值为0）
    map.set_maze(2 * start_x + 1, 2 * start_y + 1, CellType.ROAD)
    checklist = [(start_x, start_y)]
    while len(checklist):
        #在通路中随机找到一个通路点位
        entry = choice(checklist)
        #判断该点位是否有邻居点位，若没有就移除该点位，之后不再参与搜索
        if not check_neighbors(map, entry[0], entry[1], width, height, checklist):
            checklist.remove(entry)

def do_random_prime(map):
    #把二维表中所有的元素都设置为墙（即值为1）
    map.reset_maze(CellType.WALL)
    random_prime(map, (map.width - 1) // 2, (map.height - 1) // 2)

def set_entrance_exit(maze):
    entrance = []
    for i in range(maze.height):
        #找到第一个maze[1] == 0的元素，并把maze[0]设置为通路（即值为0）
        if maze.maze[1] == 0:
            maze.set_maze(0, i, 0)
            entrance = [0, i]
            #把起点标记为A，方便后面对起点的填充
            maze.maze[0] = "A"
            break
    exit = []
    for i in range(maze.height - 1, 0, -1):
        # 找到第一个maze[maze.width -2] == 0的元素，并把maze[maze.width-1]设置为通路（即值为0)
        if maze.maze[maze.width - 2] == 0:
            maze.set_maze(maze.width - 1, i, 0)
            exit = [maze.width - 1, i]
            #把终点标记为B，方便后面对终点的填充
            maze.maze[maze.width - 1] = "B"
            break
    return entrance, exit

def generate_maze(width, height):
    # 初始化迷宫
    maze = Maze(width, height)
    # 生成地图
    do_random_prime(maze)
    # 选择起点和终点
    entrance, exit = set_entrance_exit(maze)
    # 返回地图
    return maze.maze, entrance, exit

#绘制墙体单元格
def draw_cell(y0, x0):
    # y0: 单元格所在列序号  x0: 单元格所在行序号
    #计算出单元格左上角的坐标
    tx = y0 * CELL_SIZE - L * CELL_SIZE / 2     #L-列序号  H-行序号
    ty = H * CELL_SIZE / 2 - x0 * CELL_SIZE
    wallPen.penup()  # 提起墙画笔
    #turtle.goto(x,y)       x负左移正右移，y负下移正上移
    wallPen.goto(tx, ty)  # 根据计算出来的坐标移动到单元格左上角
    wallPen.pendown()  # 放下画笔
    wallPen.begin_fill()  # 开启填充，此时经过的形状会被填充
    # 由单元格左上角开始绘制一个边长为CELL_SIZE的正方形
    for i in range(4):
        wallPen.fd(CELL_SIZE)       #向前走cell_size（单元格）像素
        wallPen.right(90)           #基于当前角度向右转90度
    wallPen.end_fill()  # 关闭填充

# 在单元格绘制圆点
def draw_dot(y0, x0, color="black"):
     # x0: 单元格所在行序号  y0: 单元格所在列序号    color: 圆点的颜色
    # 计算出单元格左上角的坐标
    tx = y0 * CELL_SIZE - L * CELL_SIZE / 2
    ty = H * CELL_SIZE / 2 - x0 * CELL_SIZE
    # 计算出所在单元格中心的坐标
    cx = tx + CELL_SIZE / 2
    cy = ty - CELL_SIZE / 2
    pointPen.penup()    #提起画笔

    pointPen.goto(cx, cy)       #根据计算出来的坐标移动到单元格中心
        #turtle.dot(r)绘制一个指定直径和颜色的圆点
    pointPen.dot(DOT_SIZE, color)       #绘制一个直径为DOT_SIZE和颜色为color的圆点

def draw_mazeMap(mazeMap):      #画迷宫
    scr.tracer(0)  # 跳过绘制动画
    for h in range(len(mazeMap)):      # 　h，行号
        row = mazeMap[h]
        for l in range(len(row)):   # l，列号
            item = row[l]
            if item == CellType.WALL:
                draw_cell(l, h)         # 绘制具体的单元格
            elif item == "A":           # 设置起点颜色为红色
                draw_dot(l, h, "red")
            elif item == "B":              # 设置终点颜色为蓝色
                draw_dot(l, h, "blue")

# 绘制路径，以画笔当前所在位置为起点，以单元格（y0, x0）中心作为终点，绘制路径。
def draw_path(y0, x0, color="blue"):
    # 计算出单元格左上角的坐标
    tx = y0 * CELL_SIZE - L * CELL_SIZE / 2
    ty = H * CELL_SIZE / 2 - x0 * CELL_SIZE
    # 计算出所在单元格中心的坐标
    cx = tx + CELL_SIZE / 2
    cy = ty - CELL_SIZE / 2

    linePen.color(color)            #设置填充颜色为color（蓝色）
    linePen.goto(cx, cy)            #根据计算出来的坐标移动到单元格中心

def DFS(mazeMap,y0,x0):
    # 1,找到终点，探索完成，
    if [x0,y0] == exit:
        draw_path(y0, x0)
        return True
    # 2,找到墙或者试探过的点或者越界，试探失败，然后告诉上一步这一步试探是失败的
    if not (0 <= y0 < len(mazeMap) and 0 <= x0 < len(mazeMap)):
        return False
    if mazeMap[x0][y0] in [CellType.WALL, "#"]:
        return False

    mazeMap[x0][y0] = "#"           # 试探后标记该点为已试探过
    draw_path(y0, x0)               #填充路径

    # 右下左上四个探索的方向
    direction = [(0, 1),(0,-1),(1, 0),(-1, 0)]

    for d in direction:         #试探四个方向
        dx, dy = d
        found = DFS(mazeMap, y0 + dy, x0 + dx)
        if found:
        # 3,向某个方向的试探得出的结论是成功的，那么探索完成，不再试探，并且告诉上一步试探这一方向是能够试探成功的
            draw_path(y0, x0, "blue")                 #填充路径为蓝色
            return True
        else:
            # 4,向某个方向的试探得出的结论是失败的，那么换一个方向进行试探
            draw_path(y0, x0, "red")                #填充走过的错误路径为红色
    # 5,向所有方向试探都失败了，那么试探失败，并告诉上一步这一方向试探是失败的
    return False

# 　开始迷宫探索
def find_path(mazeMap):
    # 获取起点所在行和列的序号
    starty, startx = 0, 0                    # 　h，行号
    for h in range(len(mazeMap)):
        row = mazeMap[h]
        for l in range(len(row)):           # l，列号
            item = row[l]
            if item == "A":
                starty, startx = l, h
    linePen.penup()                 #提起路径画笔
    draw_path(starty, startx)       #填充路径
    linePen.pendown()               #放下路径画笔
    DFS(mazeMap, starty, startx)    #进入递归搜索

if __name__=="__main__":
    num=random.randint(0,2)
    t=difficulty[num]
    mazeMap, entrance, exit = generate_maze(t, t)
    H, L = len(mazeMap), len(mazeMap[0])        # 获取迷宫的长宽，H-行数，L-列数
    scr.setup(width=L * CELL_SIZE+20, height=H * CELL_SIZE+20)  # 设置屏幕尺寸大小,显示所有迷宫的单元格
    draw_mazeMap(mazeMap)       #绘制迷宫
    scr.tracer(8)           #绘制速度
    find_path(mazeMap)      #探索出路
    turtle.done()           # 防止绘制完窗口自动退出