使用随机深度优先搜索算法生成多层迷宫2

使用随机深度优先搜索算法生成多层迷宫

源码

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import random
import pygame
#
# Randomized depth-first search
# Recursive implementation
#1。Choose the initial cell, mark it as visited and push it to the stack
#2。While the stack is not empty
#   1。Pop a cell from the stack and make it a current cell
#   2。If the current cell has any neighbours which have not been visited
#       1。Push the current cell to the stack
#       2。Choose one of the unvisited neighbours
#       3。Remove the wall between the current cell and the chosen cell
#       4。Mark the chosen cell as visited and push it to the stack
#随机深度优先搜索
#递归实现
#1。选择初始单元格，将其标记为已访问，并将其压入堆栈
#2。而堆栈不是空的
#   1。从堆栈中弹出一个单元格并使其成为当前单元格
#   2。如果当前单元有任何未被访问的邻居
#       1。将当前单元格压入堆栈
#       2。选择一个未被拜访的邻居
#       3。移除当前单元格和所选单元格之间的墙
#       4。将选中的单元格标记为已访问的，并将其压入堆栈
# 多层迷宫 

# pygame
pygame.init()  # 初始化pygame
size = width, height = 1024, 768  # 设置窗口大小
screen = pygame.display.set_mode(size)  # 显示窗口
pygame.display.set_caption('火苗999℃')
# 颜色
diamond_color_size = 8
COLOR_RED, COLOR_BLUE, COLOR_GREEN, COLOR_YELLOW, COLOR_BLACK, COLOR_GREY, COLOR_GOLDEN, COLOR_NO_DIAMOND = list(range(
    diamond_color_size))
COLOR = {
    COLOR_RED: (255, 0, 0),
    COLOR_BLUE: (0, 0, 255),
    COLOR_GREEN: (0, 255, 0),
    COLOR_YELLOW: (255, 255, 0),
    COLOR_BLACK: (0, 0, 0),
    COLOR_GREY: (250, 240, 230),
    COLOR_GOLDEN : (255,215,0),
    COLOR_NO_DIAMOND: (160, 160, 160),
}
# 格式边长
DIAMOND_LENGTH = 10
# 格子大小
DIAMOND_SIZE = (DIAMOND_LENGTH, DIAMOND_LENGTH)
# 蓝格子
DIAMOND=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND.fill(COLOR[COLOR_BLUE])
# 绿格子 
DIAMOND_GREEN=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_GREEN.fill(COLOR[COLOR_GREEN])
# 红格子 
DIAMOND_RED=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_RED.fill(COLOR[COLOR_RED])
# 黄格子 
DIAMOND_YELLOW=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_YELLOW.fill(COLOR[COLOR_YELLOW])
# 灰格子 
DIAMOND_GRAY=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_GRAY.fill(COLOR[COLOR_GREY])
# 黑格子
DIAMOND_BLACK=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_BLACK.fill(COLOR[COLOR_BLACK])
# 蓝格子
DIAMOND_BLUE=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_BLUE.fill(COLOR[COLOR_BLUE])
# 3层使用不同颜色
DIAMOND_O=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_O.fill((255,128,0))
DIAMOND_G=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_G.fill((0,102,51))
DIAMOND_R=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_R.fill((102,0,0))

# 字体
use_font = pygame.font.Font("FONT.TTF", 16)
# 背景
background=pygame.surface.Surface(size).convert()
background.fill(COLOR[COLOR_NO_DIAMOND])
# 楼梯
mini_font = pygame.font.Font("FONT.TTF", 8)
DIAMOND_U=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_U.fill(COLOR[COLOR_GREEN])
surface_u = mini_font.render("U", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
DIAMOND_U.blit(surface_u, (0, 0))

DIAMOND_D=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_D.fill(COLOR[COLOR_GREEN])
surface_d = mini_font.render("D", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
DIAMOND_D.blit(surface_d, (0, 0))

DIAMOND_UD=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_UD.fill(COLOR[COLOR_GREEN])
surface_ud = mini_font.render("UD", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
DIAMOND_UD.blit(surface_ud, (0, 0))

# 时间
clock = pygame.time.Clock()

#标记 
NOWALL = 0 # 无墙
WALL = 1  # 墙
STAIRS_U = 2 # 楼梯上
STAIRS_D = 4 # 楼梯下
STAIRS_UD = 6 # 楼梯上下


def depth_maze_demo(levels, rows, cols):
    if 0 == rows % 2:
        rows+=1
    if 0 == cols % 2:
        cols+=1
    # 墙0通路1。x,y是墙的坐标。
    # 初始化全为墙
    wall=[[[ WALL for i in range(cols)]for i in range(rows)]for i in range(levels)]
    # 设置起点
    l=0
    r=1
    c=1
    # 起点加入记录
    history = [(l, r, c)]
    # 1。选择初始单元格，将其标记为已访问，并将其压入堆栈
    # 2。堆栈不是空的
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return
        if history:
            if wall[l][r][c] == WALL:
                wall[l][r][c] = NOWALL # 打通格子
            check = []
            # 可以移动到的位置
            if c > 1 and wall[l][r][c-2] == WALL:
                check.append('L')  
            if r > 1 and wall[l][r-2][c] == WALL:
                check.append('F')
            if c < cols-2 and wall[l][r][c+2] == WALL:
                check.append('R')
            if r < rows-2 and wall[l][r+2][c] == WALL:
                check.append('B')    
            if l < levels-1 and wall[l+1][r][c] == WALL:
                check.append('U')    
            if l > 0 and wall[l-1][r][c] == WALL:
                check.append('D')                    
            # 如果当前单元有任何未被访问的邻居
            if len(check): 
                # 选择一个未被拜访的邻居
                # 移除当前单元格和所选单元格之间的墙
                # 将选中的单元格标记为已访问的，并将其压入堆栈
                history.append((l, r, c))
                # 随机移动
                move_direction = random.choice(check)
                # 打通墙壁
                if move_direction == 'L':
                    wall[l][r][c-1] = NOWALL # 打通墙
                    wall[l][r][c-2] = NOWALL # 打通格子
                    c=c-2
                if move_direction == 'F':
                    wall[l][r-1][c] = NOWALL # 打通墙
                    wall[l][r-2][c] = NOWALL # 打通格子
                    r=r-2
                if move_direction == 'R':
                    wall[l][r][c+1] = NOWALL # 打通墙
                    wall[l][r][c+2] = NOWALL # 打通格子
                    c=c+2
                if move_direction == 'B':
                    wall[l][r+1][c] = NOWALL # 打通墙
                    wall[l][r+2][c] = NOWALL # 打通格子
                    r=r+2
                if move_direction == 'U':
                    if wall[l][r][c] == STAIRS_D:
                        wall[l][r][c] = STAIRS_UD # 标记为上下楼梯
                    else:
                        wall[l][r][c] = STAIRS_U # 标记为向上楼梯
                    if wall[l+1][r][c] == STAIRS_U:
                        wall[l+1][r][c] = STAIRS_UD # 标记为上下楼梯
                    else:
                        wall[l+1][r][c] = STAIRS_D # 标记为向下楼梯
                    l=l+1
                if move_direction == 'D':
                    if wall[l][r][c] == STAIRS_U:
                        wall[l][r][c] = STAIRS_UD # 标记为上下楼梯
                    else:
                        wall[l][r][c] = STAIRS_D # 标记为向下楼梯
                    if wall[l-1][r][c] == STAIRS_D:
                        wall[l-1][r][c] = STAIRS_UD # 标记为上下楼梯
                    else:
                        wall[l-1][r][c] = STAIRS_U # 标记为向上楼梯
                    l=l-1
            else: 
                #从堆栈中弹出一个单元格并使其成为当前单元格
                l, r, c = history.pop()
        # 
        screen.blit(background, (0, 0))
        # 格子
        for z in range(levels):
            for x in range(cols):
                for y in range(rows):
                    a = z % 2
                    b = z // 2
                    px, py = 1 + x * DIAMOND_SIZE[0] + a * (cols*DIAMOND_LENGTH+10),  1 + y * DIAMOND_SIZE[1] + b*(rows*DIAMOND_LENGTH+10)
                    s = (z)%3
                    # 向上楼梯使用上层颜色表示，向下楼梯使用下层颜色表示，上下楼梯使用蓝色表示
                    if 0 == s:
                        color_c = DIAMOND_G
                        color_u = DIAMOND_O
                        color_d = DIAMOND_R
                        color_ud = DIAMOND_BLUE
                    elif 1 == s:
                        color_c = DIAMOND_O
                        color_u = DIAMOND_R
                        color_d = DIAMOND_G
                        color_ud = DIAMOND_BLUE
                    else:
                        color_c = DIAMOND_R
                        color_u = DIAMOND_G
                        color_d = DIAMOND_O
                        color_ud = DIAMOND_BLUE
                    if NOWALL == wall[z][y][x]:
                        screen.blit(color_c, (px, py))
                    elif WALL == wall[z][y][x]:
                        screen.blit(DIAMOND_GRAY, (px, py))
                    elif STAIRS_U == wall[z][y][x]:
                        screen.blit(color_u, (px, py))
                    elif STAIRS_D == wall[z][y][x]:
                        screen.blit(color_d, (px, py))
                    elif STAIRS_UD == wall[z][y][x]:
                        screen.blit(color_ud, (px, py))
                    else:
                        screen.blit(DIAMOND_YELLOW, (px, py))
        # 
        if history:
            a = l % 2
            b = l // 2
            px, py = 1 + c * DIAMOND_SIZE[0] + a * (cols*DIAMOND_LENGTH+10),  1 + r * DIAMOND_SIZE[1] + b*(rows*DIAMOND_LENGTH+10)
            screen.blit(DIAMOND_RED, (px, py))
        if not history:
            score_surface = use_font.render("生成完成！", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
            screen.blit(score_surface, (20, ((levels+ 1) // 2 )*(rows*DIAMOND_LENGTH+10)))
        
        time_passed = clock.tick(30)

        pygame.display.update()
    return 


# main
if __name__ == "__main__":
    '''main'''
    depth_maze_demo(3, 21, 31)

生成的多层迷宫

gif演示

随机深度优先搜索算法生成多层迷宫