多层迷宫生成中的maze.py

多层迷宫生成中的maze.py

maze.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# create by 火苗999℃
import random
from maze_def import *


# 初始化带标记的迷宫
# x和y同为奇数代表房间；
# z奇数时为楼层间夹层；
def maze_init_draw(levels, rows, cols):
    if levels % 2 == 0:
        return []    
    if rows % 2 == 0:
        return []    
    if cols % 2 == 0:
        return []
    # 初始化全为墙
    maze_map = [[[ WALL for z in range(levels)]for y in range(rows)] for x in range(cols)]
    # 标记房间和墙
    for zi in range(0, levels, 1):
        for xi in range(0, cols, 1):
            for yi in range(0, rows, 1):
                if xi%2 == 1 and yi%2==1 and zi%2==0:
                    # 标记为没访问过的房间
                    maze_map[xi][yi][zi]=CELL_NO_VISIT
                    continue
                # 标记不能打通的墙
                if xi == 0:
                    maze_map[xi][yi][zi]=STEEL
                    continue
                if yi == 0:
                    maze_map[xi][yi][zi]=STEEL
                    continue
                if xi == cols-1:
                    maze_map[xi][yi][zi]=STEEL
                    continue
                if yi == rows-1:
                    maze_map[xi][yi][zi]=STEEL
                    continue
                if zi%2==0 and xi%2==0 and yi%2==0:
                    maze_map[xi][yi][zi]=STEEL
                    continue
                if zi%2==1 and not (xi%2==1 and yi%2==1):
                    maze_map[xi][yi][zi]=STEEL
                    continue
                # 可打通的墙壁
                if zi%2==1:
                    continue
                if xi%2==0:
                    continue
                if yi%2==0:
                    continue
                print("error")
    return maze_map



# 初始化带标记的迷宫
# 随机生成房间
# size 扩大的房间数, 不一定能生成够。
# min 最小宽度>3
# max 最大宽度<rows-1, <cols-2
def maze_init_draw2(levels, rows, cols, size, min, max):
    if levels % 2 == 0:
        return []    
    if rows % 2 == 0:
        return []    
    if cols % 2 == 0:
        return []
    # 初始化全为墙
    maze_map = [[[ WALL for z in range(levels)]for y in range(rows)] for x in range(cols)]
    # 标记房间和墙
    for zi in range(0, levels, 1):
        for xi in range(0, cols, 1):
            for yi in range(0, rows, 1):
                if xi%2 == 1 and yi%2==1 and zi%2==0:
                    # 标记为没访问过的房间
                    maze_map[xi][yi][zi]=CELL_NO_VISIT
                    continue
                # 标记不能打通的墙
                if xi == 0:
                    maze_map[xi][yi][zi]=STEEL
                    continue
                if yi == 0:
                    maze_map[xi][yi][zi]=STEEL
                    continue
                if xi == cols-1:
                    maze_map[xi][yi][zi]=STEEL
                    continue
                if yi == rows-1:
                    maze_map[xi][yi][zi]=STEEL
                    continue
                if zi%2==0 and xi%2==0 and yi%2==0:
                    maze_map[xi][yi][zi]=WALL_VISIT
                    continue
                if zi%2==1 and not (xi%2==1 and yi%2==1):
                    maze_map[xi][yi][zi]=WALL_VISIT
                    continue
                # 可打通的墙壁
                if zi%2==1:
                    continue
                if xi%2==0:
                    continue
                if yi%2==0:
                    continue
                print("error")

    if min < 3:
        min = 3
    maxy = max
    maxx = max 
    if maxx > cols-2:
        maxx = cols-2
    if maxy > rows-2:
        maxy = rows-2
    if maxx < min:
        return maze_map

    if maxy < min:
        return maze_map

    ext_size = 0
    for i in range(size):
        # 随机房间大小
        x = random.randint(min, maxx)
        if x %2==0:
            x+=1
        y = random.randint(min, maxy)
        if y %2==0:
            y+=1
        for times in range(3): # 随机放入迷宫
            # 随机房间坐标
            posx = random.randint(1, cols-2-x)
            if posx %2 ==0:
                posx-=1
            posy = random.randint(1, rows-2-y)
            if posy %2 ==0:
                posy-=1
            posz = random.randint(0, levels-1)
            if posz %2 ==1:
                posz-=1
            flag = True # 
            for xi in range(posx, posx+x):
                if not flag:
                    break
                for yi in range(posy, posy+y):
                    if maze_map[xi][yi][posz] == CELL_EXT:
                        flag = False
                        break
            if flag:
                for xi in range(posx, posx+x):
                    for yi in range(posy, posy+y):
                        maze_map[xi][yi][posz] = CELL_EXT
                ext_size+=1
                break
    for zi in range(0, levels, 1):
        for xi in range(0, cols, 1):
            for yi in range(0, rows, 1):
                if maze_map[xi][yi][zi] == CELL_EXT:
                    maze_map[xi][yi][zi] = CELL_NO_VISIT
    return maze_map


def can_move(maze_map, nowx, nowy, nowz, cols, rows, levels, check_move=True):
    # 可以移动到的位置
    directions=[]
    if check_move:
        if nowx > 1 and maze_map[nowx-2][nowy][nowz] == CELL_NO_VISIT:
            directions.append(LEFT)  
        if nowy > 1 and maze_map[nowx][nowy-2][nowz] == CELL_NO_VISIT:
            directions.append(FORWARD)
        if nowx < cols-2 and maze_map[nowx+2][nowy][nowz] == CELL_NO_VISIT:
            directions.append(RIGHT)
        if nowy < rows-2 and maze_map[nowx][nowy+2][nowz] == CELL_NO_VISIT:
            directions.append(BACKWARD)    
        if nowz < levels-2 and maze_map[nowx][nowy][nowz+2] == CELL_NO_VISIT:
            directions.append(UP)    
        if nowz > 1 and maze_map[nowx][nowy][nowz-2] == CELL_NO_VISIT:
            directions.append(DOWN)  
    else:
        # 可随机方向
        if nowy > 1:
            directions.append(FORWARD)
        if nowx > 1:
            directions.append(LEFT)
        if nowy < rows-2:
            directions.append(BACKWARD)
        if nowx < cols-2:
            directions.append(RIGHT)
        if nowz < levels-1:
            directions.append(UP)
        if nowz > 0:
            directions.append(DOWN)             
    return directions


def can_move_d_mod_wall(maze_map, nowx, nowy, nowz, cols, rows, levels):
    check = []
    # 可以移动到的位置
    if nowx > 1:
        if maze_map[nowx-2][nowy][nowz] == CELL_NO_VISIT:
            check.append('L')  
        elif maze_map[nowx-1][nowy][nowz] == WALL_NO_VISIT:
            # 标记墙已访问
            maze_map[nowx-1][nowy][nowz] = STEEL
    if nowy > 1 :
        if maze_map[nowx][nowy-2][nowz] == CELL_NO_VISIT:
            check.append('F')
        elif maze_map[nowx][nowy-1][nowz] == WALL_NO_VISIT:
            # 标记墙已访问
            maze_map[nowx][nowy-1][nowz] = STEEL
    if nowx < cols-2:
        if maze_map[nowx+2][nowy][nowz] == CELL_NO_VISIT:
            check.append('R')
        elif maze_map[nowx+1][nowy][nowz] == WALL_NO_VISIT:
            # 标记墙已访问
            maze_map[nowx+1][nowy][nowz] = STEEL
    if nowy < rows-2:
        if maze_map[nowx][nowy+2][nowz] == CELL_NO_VISIT:
            check.append('B')    
        elif maze_map[nowx][nowy+1][nowz] == WALL_NO_VISIT:
            maze_map[nowx][nowy+1][nowz] = STEEL
    if nowz < levels-2:
        if  maze_map[nowx][nowy][nowz+2] == CELL_NO_VISIT:
            check.append('U') 
        elif maze_map[nowx][nowy][nowz+1] == WALL_NO_VISIT:
            maze_map[nowx][nowy][nowz+1] = STEEL
    if nowz > 1:
        if maze_map[nowx][nowy][nowz-2] == CELL_NO_VISIT:
            check.append('D')   
        elif maze_map[nowx][nowy][nowz-1] == WALL_NO_VISIT:
            maze_map[nowx][nowy][nowz-1] = STEEL                 
    return 


# 标记格子已经访问
def visit_cell(maze_map, x, y, z, cols, rows):
    if maze_map[x][y][z] == CELL_NO_VISIT: 
        maze_map[x][y][z] = CELL_VISIT # 标记访问
    grids = []
    minx = x
    while True:
        if minx > 1 and maze_map[minx-1][y][z] == CELL_NO_VISIT:
            minx -=1
        else:
            break
    maxx = x
    while True:
        if maxx < cols - 2 and maze_map[maxx+1][y][z] == CELL_NO_VISIT:
            maxx+=1
        else:
            break    
    miny=y
    while True:
        if miny > 1 and maze_map[x][miny-1][z] == CELL_NO_VISIT:
            miny -=1
        else:
            break
    maxy=y
    while True:
        if maxy < rows - 2 and maze_map[x][maxy+1][z] == CELL_NO_VISIT:
            maxy +=1
        else:
            break
    
    for xi in range(minx, maxx+1):
        for yi in range(miny, maxy+1):
            if  maze_map[xi][yi][z] == CELL_NO_VISIT: 
                maze_map[xi][yi][z] = CELL_VISIT
            grids.append((xi,yi,z))
    return grids



# 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。将选中的单元格标记为已访问的，并将其压入堆栈
def depth_maze(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:
        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()
        if not history:
            break
    return wall



#Aldous-Broder algorithm
#The Aldous-Broder algorithm also produces uniform spanning trees.

# 1.Pick a random cell as the current cell and mark it as visited.
# 2.While there are unvisited cells:
#   1.Pick a random neighbour.
#   2.If the chosen neighbour has not been visited:
#       1.Remove the wall between the current cell and the chosen neighbour.
#       2.Mark the chosen neighbour as visited.
#   3.Make the chosen neighbour the current cell.

# Aldous-Broder算法
# Aldous-Broder算法也生成统一的生成树。
# 1。选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
# 2。当存在未访问细胞时:
#   1。随机选择一个邻居。
#   2。如果选中的邻居没有被访问:
#       1。移除当前单元格和所选邻居之间的墙。
#       2。标记被选中的邻居已被拜访过。
#   3。使选择的邻居成为当前单元格。
def aldous_broder_maze(levels, rows, cols):
    if 0 == rows % 2:
        rows+=1
    if 0 == cols % 2:
        cols+=1
    # 初始化全为墙
    wall=[[[ WALL for z in range(levels)]for y in range(rows)] for x in range(cols)]
    notusegrids = [] # 没有访问过的格子,单数代表格子，双数是墙壁
    for tz in range(0, levels):
        for tx in range(1, cols, 2):
            for ty in range(1, rows, 2):
                    notusegrids.append((tx, ty, tz))
    # 选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
    nowx,nowy,nowz = random.choice(notusegrids)
    # 标记迷宫
    wall[nowx][nowy][nowz]=NOWALL
    notusegrids.remove((nowx,nowy,nowz))
    # 当存在未访问细胞时:
    while True:
        # 当存在未访问细胞时:
        if  notusegrids:
            directions = []
            # 可随机方向
            if nowy > 1:
                directions.append('f')
            if nowx > 1:
                directions.append('l')
            if nowy < rows-2:
                directions.append('b')
            if nowx < cols-2:
                directions.append('r')
            if nowz < levels-1:
                directions.append('u')
            if nowz > 0:
                directions.append('d')
            if len(directions):
                # 随机一个方向
                move = random.choice(directions)
                # 如果选中的邻居没有被访问:
                    #   1。移除当前单元格和所选邻居之间的墙。
                    #   2。标记被选中的邻居已被拜访过。
                    #   3。使选择的邻居成为当前单元格。
                if move == 'f':
                    newy = nowy-2
                    newx = nowx
                    newz = nowz
                    opwall=(nowx,nowy-1,nowz)
                if move == 'l':
                    newy = nowy
                    newx = nowx-2
                    newz = nowz
                    opwall=(nowx-1,nowy,nowz)
                if move == 'b':
                    newy = nowy+2
                    newx = nowx
                    newz = nowz
                    opwall=(nowx,nowy+1,nowz)
                if move == 'r':
                    newy = nowy
                    newx = nowx+2
                    newz = nowz
                    opwall=(nowx+1,nowy,nowz)
                if move == 'u':
                    newy = nowy
                    newx = nowx
                    newz = nowz+1
                    opwall=None
                if move == 'd':
                    newy = nowy
                    newx = nowx
                    newz = nowz-1
                    opwall=None
                # 如果选中的邻居没有被访问:
                if wall[newx][newy][newz] == WALL:
                    #   1。移除当前单元格和所选邻居之间的墙。
                    if opwall:
                        wall[opwall[0]][opwall[1]][opwall[2]]=NOWALL
                    #   2。标记被选中的邻居已被拜访过。
                    if move == 'd':
                        if wall[nowx][nowy][nowz] == NOWALL:
                            wall[nowx][nowy][nowz]=STAIRS_D
                        else:
                            wall[nowx][nowy][nowz]=STAIRS_UD
                        wall[newx][newy][newz]=STAIRS_U
                    elif move == 'u':
                        if wall[nowx][nowy][nowz] == NOWALL:
                            wall[nowx][nowy][nowz]=STAIRS_U
                        else:
                            wall[nowx][nowy][nowz]=STAIRS_UD
                        wall[newx][newy][newz]=STAIRS_D
                    else:
                        wall[newx][newy][newz]=NOWALL
                    #   3。使选择的邻居成为当前单元格。
                    nowx=newx
                    nowy=newy
                    nowz=newz
                    notusegrids.remove((newx,newy,newz))
                else:
                    # 使选择的邻居成为当前单元格。
                    nowx=newx
                    nowy=newy
                    nowz=newz
        else:
            break
    return wall


# main
if __name__ == "__main__":
    '''main'''
    depth_maze(3, 11, 11)
    aldous_broder_maze(3, 11, 11)