pygame迷宫生成

一.预习内容：

项目分析
       一个完整的迷宫，需要能够实现产生不同路径供玩家游戏，同时需要能够记录玩家所走过的路，避免由于迷宫的范围太大而导致无法走到最后的结尾。迷宫本身也应该自带友好的交互功能，可以让玩家可以根据提示获得愉快的游戏体验。

实验目标
1.随机生成一个迷宫，并且求解迷宫。
2.要求游戏支持玩家走迷宫，和系统走迷宫路径两种模式。玩家走迷宫，通过键盘方向键控制，并在行走路径上留下痕迹；系统走迷宫路径要求基于A*算法实现，输出走迷宫的最优路径并显示。
3.设计交互友好的游戏图形界面。
 

二.算法设计

深度遍历算法生成迷宫路径
1、整体思路
     1）利用深度遍历的思想。访问到一个节点时，搜索这个节点没有被访问过的相邻节点，选择一个继续做同样的操作，直到没有邻节点为止再回溯到上一个访问的节点，并选择另外的邻节点。
     2）这种方案生成的迷宫会有一条明显的主路，这条主路特别长，贯穿大部分区域的路线，同时，迷宫的路线一般比较扭曲。这种采用深度优先算法（递归回溯算法）生成的迷宫称之为“主路扭曲型”迷宫

2、设计过程
（1）把数组地图初始化为如下结构。选择一个靠近边缘的1作为起点，在它的周围随机找另一个黄色的1（这里的“周围”指的是上下左右4个方向）。找到就把他们联通，并且把两个1之间的0（灰色墙）也变成通路，这里用红色来表示。

（2）选择一个靠近边缘的1作为起点，在它的周围随机找另一个黄色的1（这里的“周围”指的是上下左右4个方向）。找到就把他们联通，并且把两个1之间的0（灰色墙）也变成通路，这里用红色来表示。

 （3）把上一步”终点”的格子作为新的一个“起点”格子，不断循环第2步的过程……
直到，找不到周围有黄色的1，就回溯，回到之前的位置，看看周围是否有黄色的1，如果有，就按照2步骤，不断将黄色1变联通，接下来就是不停地重复上面的步骤，找到就联通，找不到就往回走。

（4）遍历完所有的点即可生成一个迷宫，然后再选择出口与入口，一个完整的迷宫就形成了。

1.整体框架结构

通过二维数组生成迷宫坐标，参考教程使用深度优先算法的递归回溯算法完成对迷宫的随机生成，不断随机访问每一个相邻格子，记录访问路径，最后将网格按访问路径擦除，玩家按照访问路径实现迷宫中的行走。

2.关键代码

（1）递归回溯算法

递归回溯是一个深度优先算法，如果当前单元有相邻的未访问过的迷宫单元，就一直向前搜索，直到当前单元没有未访问过的迷宫单元，才返回查找之前搜索路径上未访问的迷宫单元，所以用堆栈来维护已访问过的迷宫单位。

算法主循环，重复下面步骤2直到堆栈为空：

1 随机选择一个迷宫单元作为起点，加入堆栈并标记为已访问

2 当堆栈非空时，从栈顶获取一个迷宫单元（不用出栈），进行循环

如果当前迷宫单元有未被访问过的相邻迷宫单元

随机选择一个未访问的相邻迷宫单元

去掉当前迷宫单元与相邻迷宫单元之间的墙

标记相邻迷宫单元为已访问，并将它加入堆栈

否则，当前迷宫单元没有未访问的相邻迷宫单元

则栈顶的迷宫单元出栈

（2）墙体绘制

（3）玩家设计

 此处设计了两个玩家，为对抗方式，先到达对方生成点者获胜（自己的出口）

迷宫运行界面如下

可设置是否展示生成过程

 源码

# 导入枚举
from enum import Enum
import random
import pygame as pg

# 全局参数常量
SCREEN_WIDTH = 1200
SCREEN_HEIGHT = 1024
MAZE_WIDTH = 20  # 方格数
MAZE_HEIGHT = 20  #
CELL_COUNT = MAZE_WIDTH * MAZE_HEIGHT  # 总单元格数
BLOCK_SIZE = 8  # 墙厚
PATH_WIDTH = 3  # 道路宽度
# 是否显示迷宫生成过程
SHOW_DRAW = True
# SHOW_DRAW = False
# 墙壁
CELL_SIZE = BLOCK_SIZE * PATH_WIDTH + BLOCK_SIZE  # 右下边缘
MAZE_WIDTH_PX = CELL_SIZE * MAZE_WIDTH + BLOCK_SIZE  # 左边缘
MAZE_HEIGHT_PX = CELL_SIZE * MAZE_HEIGHT + BLOCK_SIZE  # 上边缘
# 颜色
BACK_COLOR = (100, 100, 100)
WALL_COLOR = (18, 94, 32)
MAZE_COLOR = (255, 255, 255)
UNVISITED_COLOR = (0, 0, 0)
PLAYER1_COLOR = (255, 0, 0)
PLAYER2_COLOR = (0, 0, 255)
MESSAGE_COLOR = (0, 255, 0)
# 绘制起点
MAZE_TOP_LEFT_CORNER = (SCREEN_WIDTH // 2 - MAZE_WIDTH_PX // 2, SCREEN_HEIGHT // 2 - MAZE_HEIGHT_PX // 2)


# 用枚举表示格子四方向访问状态
class CellProp(Enum):
    Path_N = 1
    Path_E = 2
    Path_S = 4
    Path_W = 8
    Visited = 16


class Direction(Enum):
    North = (0, -1)
    East = (1, 0)
    South = (0, 1)
    West = (-1, 0)


# 玩家
class Player(pg.sprite.Sprite):
    def __init__(self, color, x, y, radius):
        # 调用父类Sprite构造函数
        super().__init__()

        # 起始点
        self.start_x = x
        self.start_y = y

        # 创建矩形图像，填充并将背景设置为透明
        self.image = pg.Surface([radius * 2, radius * 2])
        self.image.fill(MAZE_COLOR)
        self.image.set_colorkey(MAZE_COLOR)

        # 在透明矩形上绘制圆形玩家
        pg.draw.circle(self.image, color, (radius, radius), radius)

        self.rect = self.image.get_rect()
        self.rect.x = x
        self.rect.y = y

    # 归位
    def reset(self):
        self.rect.x = self.start_x
        self.rect.y = self.start_y


# 迷宫生成器
class MazeGenerator:
    direction_to_flag = {
        Direction.North: CellProp.Path_N,
        Direction.East: CellProp.Path_E,
        Direction.South: CellProp.Path_S,
        Direction.West: CellProp.Path_W
    }

    opposite_direction = {
        Direction.North: Direction.South,
        Direction.East: Direction.West,
        Direction.South: Direction.North,
        Direction.West: Direction.East
    }

    def __init__(self):
        # 初始化
        pg.init()

        # 窗体
        self.screen = pg.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))

        # 标题
        pg.display.set_caption('PyMaze')

        # 用列表存放二维数组
        self.maze = []

        # 随机数种子
        random.seed()

        self.maze_image = None

        # 创建玩家
        self.player1 = Player(PLAYER1_COLOR, MAZE_TOP_LEFT_CORNER[0] + BLOCK_SIZE,
                              MAZE_TOP_LEFT_CORNER[1] + BLOCK_SIZE, (BLOCK_SIZE * 3) // 2)
        self.player1_sprite = None

        self.player2 = Player(PLAYER2_COLOR,
                              MAZE_TOP_LEFT_CORNER[0] + MAZE_WIDTH_PX - CELL_SIZE,
                              MAZE_TOP_LEFT_CORNER[1] + MAZE_HEIGHT_PX - CELL_SIZE,
                              (BLOCK_SIZE * 3) // 2)
        self.player2_sprite = None

        # 获胜判断
        self.win1_flag = False
        self.win2_flag = False

    # 算法部分
    # 获取单元格索引
    def get_cell_index(self, position):
        x, y = position
        return y * MAZE_WIDTH + x

    def generate_maze(self):
        # 用0值初始化
        self.maze = [0] * CELL_COUNT
        visited_count = 0

        # 将第一个单元格 （0，0） 添加到堆栈并增加访问计数
        process_stack = [(0, 0)]
        self.maze[0] |= CellProp.Visited.value

        visited_count += 1

        # 循环访问相邻格子
        while visited_count < CELL_COUNT:
            x, y = process_stack[-1]  # 获取栈顶坐标
            current_cell_index = self.get_cell_index((x, y))

            # 找出所有未访问相邻格，遍历枚举
            # 创建未访问相邻格列表
            neighbors = []
            for direction in Direction:
                dir = direction.value
                new_x, new_y = (x + dir[0], y + dir[1])
                if 0 <= new_x < MAZE_WIDTH and 0 <= new_y < MAZE_HEIGHT:
                    index = self.get_cell_index((new_x, new_y))
                    # 若未访问过
                    if not self.maze[index] & CellProp.Visited.value:
                        neighbors.append((new_x, new_y, direction))
            # 检查未访问相邻格
            if len(neighbors) > 0:
                # 随机选择邻格
                cell = neighbors[random.randrange(len(neighbors))]
                cell_x, cell_y, cell_direction = cell
                cell_position = (cell_x, cell_y)
                cell_index = self.get_cell_index(cell_position)

                # 用相连接的方向状态开辟路径
                flag_to = MazeGenerator.direction_to_flag[cell_direction]
                flag_from = MazeGenerator.direction_to_flag[MazeGenerator.opposite_direction[cell_direction]]

                self.maze[current_cell_index] |= flag_to.value
                self.maze[cell_index] |= flag_from.value | CellProp.Visited.value

                process_stack.append(cell_position)
                visited_count += 1
            else:
                # 回溯未访问的格子
                process_stack.pop()
            if SHOW_DRAW:
                self.draw_maze()
                pg.display.update()
                # pg.time.wait(500)
                pg.event.pump()

        self.draw_maze()
        pg.display.update()
        self.maze_image = self.screen.copy()

    def draw(self, color, x, y):
        x_offset = MAZE_TOP_LEFT_CORNER[0] + BLOCK_SIZE
        y_offset = MAZE_TOP_LEFT_CORNER[1] + BLOCK_SIZE
        pg.draw.rect(self.screen, color, (x * BLOCK_SIZE + x_offset,
                                          y * BLOCK_SIZE + y_offset,
                                          BLOCK_SIZE, BLOCK_SIZE))

    def draw_maze(self):

        self.screen.fill(BACK_COLOR)
        # 底色（墙）
        pg.draw.rect(self.screen, WALL_COLOR, (MAZE_TOP_LEFT_CORNER[0], MAZE_TOP_LEFT_CORNER[1],
                                               MAZE_WIDTH_PX, MAZE_HEIGHT_PX))
        # 循环迷宫列表
        for x in range(MAZE_WIDTH):
            for y in range(MAZE_HEIGHT):
                for py in range(PATH_WIDTH):
                    for px in range(PATH_WIDTH):
                        cell_index = self.get_cell_index((x, y))
                        if self.maze[cell_index] & CellProp.Visited.value:
                            self.draw(MAZE_COLOR, x * (PATH_WIDTH + 1) + px, y * (PATH_WIDTH + 1) + py)
                        else:
                            self.draw(UNVISITED_COLOR, x * (PATH_WIDTH + 1) + px, y * (PATH_WIDTH + 1) + py)

                # 检查是否有连接的路径，打通墙壁
                for p in range(PATH_WIDTH):
                    if self.maze[y * MAZE_WIDTH + x] & CellProp.Path_S.value:
                        self.draw(MAZE_COLOR, x * (PATH_WIDTH + 1) + p, y * (PATH_WIDTH + 1) + PATH_WIDTH)

                    if self.maze[y * MAZE_WIDTH + x] & CellProp.Path_E.value:
                        self.draw(MAZE_COLOR, x * (PATH_WIDTH + 1) + PATH_WIDTH, y * (PATH_WIDTH + 1) + p)
        # 迷宫出口
        pg.draw.rect(self.screen, PLAYER2_COLOR, (MAZE_TOP_LEFT_CORNER[0],
                                                  MAZE_TOP_LEFT_CORNER[1] + BLOCK_SIZE, BLOCK_SIZE, BLOCK_SIZE * 3))

        pg.draw.rect(self.screen, PLAYER1_COLOR,
                     (MAZE_TOP_LEFT_CORNER[0] + MAZE_WIDTH_PX - BLOCK_SIZE,
                      MAZE_TOP_LEFT_CORNER[1] + MAZE_HEIGHT_PX - BLOCK_SIZE * 4,
                      BLOCK_SIZE, BLOCK_SIZE * 3))

    # 处理所有绘画
    def draw_screen(self):
        # self.draw_maze()
        self.screen.blit(self.maze_image, (0, 0))
        self.player1_sprite.draw(self.screen)
        self.player2_sprite.draw(self.screen)

        pg.display.update()

    # 玩家操作
    def can_move(self, direction, player):
        # 左上角第一格
        corner_offset_x = MAZE_TOP_LEFT_CORNER[0] + BLOCK_SIZE
        corner_offset_y = MAZE_TOP_LEFT_CORNER[1] + BLOCK_SIZE

        # 计算玩家占用单元格
        square = BLOCK_SIZE * 4
        p1 = (player.rect.x - corner_offset_x, player.rect.y - corner_offset_y)
        p2 = (p1[0] + square - 1, p1[1] + square - 1)
        player_pos1 = (p1[0] // square, p1[1] // square)
        player_pos2 = (p2[0] // square, p2[1] // square)
        cell_index1 = self.get_cell_index((player_pos1[0], player_pos1[1]))
        cell_index2 = self.get_cell_index((player_pos2[0], player_pos2[1]))

        functions = {
            Direction.North: self.can_move_up,
            Direction.East: self.can_move_right,
            Direction.South: self.can_move_down,
            Direction.West: self.can_move_left
        }

        # 检查迷宫出口
        # 检查玩家是否在对方玩家的起点（获胜判断）
        if self.player1.rect.x == self.player2.start_x and self.player1.rect.y == self.player2.start_y:
            self.win1_flag = True
        elif self.player2.rect.x == self.player1.start_x and self.player2.rect.y == self.player1.start_y:
            self.win2_flag = True

        return functions[direction](cell_index1, cell_index2)

    def can_move_up(self, index1, index2):
        if index1 == index2:
            return self.maze[index1] & CellProp.Path_N.value
        else:
            return index2 == index1 + MAZE_WIDTH

    def can_move_right(self, index1, index2):
        if index1 == index2:
            return self.maze[index1] & CellProp.Path_E.value
        else:
            return index2 == index1 + 1

    def can_move_down(self, index1, index2):
        if index1 == index2:
            return self.maze[index1] & CellProp.Path_S.value
        else:
            return index2 == index1 + MAZE_WIDTH

    def can_move_left(self, index1, index2):
        if index1 == index2:
            return self.maze[index1] & CellProp.Path_W.value
        else:
            return index2 == index1 + 1

    def move_up(self, player):
        if self.can_move(Direction.North, player):
            player.rect.y -= 1

    def move_right(self, player):
        if self.can_move(Direction.East, player):
            player.rect.x += 1

    def move_down(self, player):
        if self.can_move(Direction.South, player):
            player.rect.y += 1

    def move_left(self, player):
        if self.can_move(Direction.West, player):
            player.rect.x -= 1

    # 获胜提示
    def display_win(self):
        msg = 'Player 1 Wins!!!' if self.win1_flag else 'Player 2 Wins!!!'

        font = pg.font.SysFont('Arial', 72, True)
        size = font.size(msg)
        s = font.render(msg, True, MESSAGE_COLOR, (0, 0, 0))
        self.screen.blit(s, (SCREEN_WIDTH // 2 - size[0] // 2, SCREEN_HEIGHT // 2 - size[1] // 2))
        pg.display.update()
        pg.time.wait(3000)

    # 初始化
    def initialize(self):
        self.player1_sprite = None
        self.player1.reset()
        self.player2_sprite = None
        self.player2.reset()

        self.generate_maze()
        self.player1_sprite = pg.sprite.RenderPlain(self.player1)
        self.player2_sprite = pg.sprite.RenderPlain(self.player2)

    def run_game(self):
        # 帧率
        clock = pg.time.Clock()
        # print(self.maze)
        self.initialize()

        # 游戏运行循环
        run = True
        while run:
            for event in pg.event.get():
                if event.type == pg.QUIT:
                    run = False

            # pg.draw.rect(self.screen, (255, 255, 255), (50, 50, 100, 100))
            # pg.display.update()

            if not self.win1_flag and not self.win2_flag:
                keys = pg.key.get_pressed()
                if keys[pg.K_LEFT]:
                    self.move_left(self.player2)
                if keys[pg.K_RIGHT]:
                    self.move_right(self.player2)
                if keys[pg.K_UP]:
                    self.move_up(self.player2)
                if keys[pg.K_DOWN]:
                    self.move_down(self.player2)
                if keys[pg.K_a]:
                    self.move_left(self.player1)
                if keys[pg.K_d]:
                    self.move_right(self.player1)
                if keys[pg.K_w]:
                    self.move_up(self.player1)
                if keys[pg.K_s]:
                    self.move_down(self.player1)

                if self.win1_flag or self.win2_flag:
                    self.display_win()
                    self.initialize()
                    self.win1_flag = self.win2_flag = False

            self.draw_screen()
            # 帧率显示
            pg.display.set_caption(f'PyMaze ({str(int(clock.get_fps()))} FPS)')
            clock.tick()

        pg.quit()


mg = MazeGenerator()
mg.run_game()

 参考资料Build a 2-player maze game with Python Part 4 - Coding TidBits (danduda.com)文章来源地址https://www.toymoban.com/news/detail-755856.html

到了这里，关于pygame迷宫生成的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！