0.没图说个*
1.DFS算法和pygame代码:
代码:
from maze_gen import *
import pygame,sys,time
def suwall(x,y):
pygame.draw.rect(wind, (0,0,0), (x-(b/2),y,b,k), 0)
def hewall(x,y):
pygame.draw.rect(wind, (0,0,0), (x,y-(b/2),k,b), 0)
def showmap(wall):
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit()
su=wall[0]
hen=wall[1]
for y in range(len(su)):
for x in range(len(su[y])):
if (su[y][x]):
suwall((x*k)+k+b,(y*k)+b)
for y in range(len(hen)):
for x in range(len(hen[y])):
if (hen[y][x]):
# suwall((x*60+60),y*60)
hewall((x*k)+b,((y*k)+k)+b)
# [[-1,0],[1,0],[0,-1],[0,1]]:#上下左右
def isok(p1,p2):
if((p2[0]<0) or (p2[0]>height-1) or (p2[1]<0) or (p2[1]>Width-1) or p2 in luj):
# print("超出边界")
return False
if([p2[0]-p1[0],p2[1]-p1[1]]==[1,0]):
# print("下")
if(p1>p2):
if wall[1][p2[0]][p2[1]]:
return False
else:
return True
else:
if(wall[1][p1[0]][p1[1]]):
return False
else:
return True
if([p2[0]-p1[0],p2[1]-p1[1]]==[-1,0]):
# print("上")
if(p1>p2):
if wall[1][p2[0]][p2[1]]:
return False
else:
return True
else:
if(wall[1][p1[0]][p1[1]]):
return False
else:
return True
if([p2[0]-p1[0],p2[1]-p1[1]]==[0,1]):
# print("右")
if(p1>p2):
if wall[0][p2[0]][p2[1]]:
return False
else:
return True
else:
if(wall[0][p1[0]][p1[1]]):
return False
else:
return True
if([p2[0]-p1[0],p2[1]-p1[1]]==[0,-1]):
# print("左")
if(p1>p2):
if wall[0][p2[0]][p2[1]]:
return False
else:
return True
else:
if(wall[0][p1[0]][p1[1]]):
return False
else:
return True
def luy(x,y):
li=[]
if Width<height:
for i in [[1,0],[0,1],[0,-1],[-1,0]]:#下右左上
p1=[x,y]
p2=[x+i[0],y+i[1]]
# print(p1,p2)
f=isok(p1,p2)
# print(f)
if f:
li.append(i)
else:
for i in [[0,1],[1,0],[0,-1],[-1,0]]:#右下左上
p1=[x,y]
p2=[x+i[0],y+i[1]]
# print(p1,p2)
f=isok(p1,p2)
# print(f)
if f:
li.append(i)
return li
def dfs(x,y,luj):
lu=luy(x,y)
for u in lu:
p1=[x,y]
p2=[x+u[0],y+u[1]]
if(isok(p1,p2) and( p2 not in luj) ):
# print(6)
luj_o=luj[:]
luj.append([x+u[0],y+u[1]])
wind.blit(background,(0,0))#pygame 绘制背景
wind.blit(background,(0,0))
pygame.draw.rect(wind, (0,0,0), (0,0,(Width*k)+(b*2),(height*k+(b*2))), (b*2))#绘制外墙
showmap(wall)#绘制，迷宫
pygame.draw.rect(wind, (255,0,0), (b+b,b+b,k-b-b,k-b-b), 0)#绘制起点
pygame.draw.rect(wind, (0,255,0), ((Width*k)-(k-b-b),(height*k)-(k-b-b),k-b,k-b), 0)#绘制终点
pygame.draw.lines(wind, (0,0,255), 0, [[(i[1]*k)+(k/2)-b,(i[0]*k)+(k/2)-b] for i in luj], 1 if(b==1) else b+1)#绘制解法
l=time.time()-t
pygame.display.set_caption(f"迷宫正在解用时{l}毫秒")
pygame.display.update()#刷新屏幕
if([x+u[0],y+u[1]]==[height-1,Width-1]):
return luj
ret = dfs(x+u[0],y+u[1],luj)
if (type(ret)== type([])):
return ret
luj=luj_o[:]
sys.setrecursionlimit(9000000) #递归算法深度这里设置大一些
Width=10#迷宫宽度20格
height=10#迷宫高度20格
k=int(800/height)#画面比例系数,固定画面高度为800
b=int(k/10)#墙厚
if(b<=0):
b=1
wall=generate_maze(Width, height, density=20)
pygame.init()
wind=pygame.display.set_mode([(Width*k)+(b*2),(height*k)+(b*2)])
pygame.display.set_caption("迷宫")
background = pygame.Surface(wind.get_size())
background.fill((255, 155, 155))
wind.blit(background,(0,0))
luj=[[0,0]]#存放路径,设定起点
t=time.time()#计时开始
jie_ok=dfs(0,0,luj)#解迷宫
l=time.time()-t#计时结束
pygame.display.set_caption(f"迷宫解完用时{l}毫秒")
while True:
wind.blit(background,(0,0))
pygame.draw.rect(wind, (0,0,0), (0,0,(Width*k)+(b*2),(height*k+(b*2))), (b*2))
showmap(wall)
pygame.draw.rect(wind, (255,0,0), (b+b,b+b,k-b-b,k-b-b), 0)#绘制起点
pygame.draw.rect(wind, (0,255,0), ((Width*k)-(k-b-b),(height*k)-(k-b-b),k-b,k-b), 0)#绘制终点
pygame.draw.lines(wind, (0,255,0), 0, [[(i[1]*k)+(k/2)+b,(i[0]*k)+(k/2)+b] for i in jie_ok], 1 if(b==1) else b+1)#绘制解法
# pygame.draw.lines(wind, (0,255,0), 0, [[i[1]*k+k/2,i[0]*k+k/2] for i in jie_ok], b+1)#绘制解法
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit()
pygame.display.update()#刷新屏幕
迷宫生成代码:
代码:
""" 迷宫生成代码 """
import random
from wall import Wall
def generate_maze(size_x, size_y, density=0.9):
"""
生成一个给定大小的迷宫，以"右墙"数组的形式返回迷宫
"底墙"。
例如，以下迷宫：
+---+---+---+
| | |
+---+ + +
| |
+ +---+---+
| |
+---+---+---+
# 00010
# 11010
# 00000
# 00000
将表示为：
right_walls: [
[f, t],
[f, f],
[f, f]
]
bottom_walls: [
[t, f, f],
[f, t, t]
]
(where t = True, f = False).
"""
class Node:
def __init__(self, group_id, position):
self.group_id = group_id
self.position = position
class Edge:
"""
这个类用来做保存两个节点间的单个连接的数据结构
"""
def __init__(self, orientation, position, enabled):
self.orientation = orientation
self.position = position
self.enabled = enabled
nodes = [Node(i + j * size_x, (i, j))
for j in range(size_y)
for i in range(size_x)]
edges = [
Edge("r", (i, j), True)
for j in range(size_y)
for i in range(size_x - 1)
] + [
Edge("b", (i, j), True)
for j in range(size_y - 1)
for i in range(size_x)
]
random.shuffle(edges)
for edge in edges:
if edge.orientation == "r":
parent_nodes = [nodes[edge.position[0] + size_x * edge.position[1]],
nodes[edge.position[0] + 1 + size_x * edge.position[1]]]
else:
parent_nodes = [nodes[edge.position[0] + size_x * edge.position[1]],
nodes[edge.position[0] + size_x * (edge.position[1] + 1)]]
if parent_nodes[0].group_id != parent_nodes[1].group_id:
edge.enabled = False
dead_group_id = parent_nodes[1].group_id
for node in nodes:
if node.group_id == dead_group_id:
node.group_id = parent_nodes[0].group_id
enabled_edges = list(filter(lambda edge: edge.enabled, edges))
random.shuffle(enabled_edges)
for i in range(round((size_x - 1) * (size_y - 1) * (1 - density))):
enabled_edges[i].enabled = False
right_edges = [[True for i in range(size_x - 1)] for i in range(size_y)]
bottom_edges = [[True for i in range(size_x)] for i in range(size_y - 1)]
for edge in edges:
if edge.orientation == "r":
right_edges[edge.position[1]][edge.position[0]] = edge.enabled
if edge.orientation == "b":
bottom_edges[edge.position[1]][edge.position[0]] = edge.enabled
return (right_edges, bottom_edges)
def generate_walls_from_maze(width, height, maze):
""" 把右墙/底墙中给定的墙转换为宽度正确的矩形墙。 """
walls = []
# Edges
walls.append(Wall.generate_horizontal_wall(0, 0, width))
walls.append(
Wall.generate_horizontal_wall(0, height, width)
)
walls.append(Wall.generate_vertical_wall(0, 0, height))
walls.append(Wall.generate_vertical_wall(width, 0, height))
(right_walls, bottom_walls) = maze
# 水平墙
for y in range(height - 1):
x = 0
current_wall_start_x = 0
current_wall_length = 0
while x < width:
while x < width and bottom_walls[y][x]:
x += 1
current_wall_length += 1
if current_wall_length > 0:
walls.append(
Wall.generate_horizontal_wall(
current_wall_start_x,
y + 1,
current_wall_length
)
)
x += 1
current_wall_start_x = x
current_wall_length = 0
# 竖直墙
for x in range(width - 1):
y = 0
current_wall_start_y = 0
current_wall_length = 0
while y < height:
while y < height and right_walls[y][x]:
y += 1
current_wall_length += 1
if current_wall_length > 0:
walls.append(
Wall.generate_vertical_wall(
x + 1,
current_wall_start_y,
current_wall_length
)
)
y += 1
current_wall_start_y = y
current_wall_length = 0
return walls
def print_maze(walls):
""" 终端打印迷宫 """
right_walls, bottom_walls = walls
size_x = len(bottom_walls[0])
size_y = len(right_walls)
print("+---" * size_x + "+")
for y in range(size_y):
print("| ", end="")
for x in range(size_x - 1):
if right_walls[y][x]:
print("| ", end="")
else:
print(" ", end="")
print("|")
if y != size_y - 1:
for x in range(size_x):
if bottom_walls[y][x]:
print("+---", end="")
else:
print("+ ", end="")
print("+")
print("+---" * size_x + "+")
if __name__ == "__main__":
# print_maze(generate_maze(10, 10, density=0.9))
print(len(generate_maze(10, 10, density=0.9)))