图书馆网站建设的建议,建设厅网站实名制系统如何解聘,网站建设实验报告格式,兰州做网站哪家专业学习路径计算之前需要一个场景#xff0c;网上查了下迷宫生成方法花了点时间写了个简单的迷宫生成器 基本原理十分简单#xff1a; 使用2维矩阵表示迷宫#xff0c;每一个节点有四面墙#xff0c;使用深度搜索#xff0c;随机顺序向四个方向移动,#xff0c;如果遇到已到…学习路径计算之前需要一个场景网上查了下迷宫生成方法花了点时间写了个简单的迷宫生成器 基本原理十分简单 使用2维矩阵表示迷宫每一个节点有四面墙使用深度搜索随机顺序向四个方向移动,如果遇到已到节点则停止该方向没有走过则把两个节点之间的墙消除掉。这样可以保证每一个节点都可以覆盖到而且每一个节点都会有一条路通向出口。
简单的算法有一个很明显的缺点每一个节点只有一条固定的路不会有多条路通向某个节点。 深度搜索使用递归十分简洁不赘述。 具体实现比较容易受坑的地方是如何简洁实现上下左右随机移动消除墙壁并且不用一千个if 首先是方向表示这里使用了一个列表 directions [[0,-1],[1,0],[0,1],[-1,0]] 分别表示上右下左 对[0,1,2,3]使用random.shuffle()函数然后对这个列表进行遍历可以实现随机获取上下左右矢量 每一个节点有四面墙壁使用[0,0,0,0]表达序列方向与上面direction相同。 在消除一个节点之间的墙壁的时候需要消除上一个墙壁对立面的节点 还是对方向进行操作direction[i]表达了方向矢量在这里加号是右移右移一位的时候是顺时针旋转45度向左移1位则是旋转逆时针45度 数字i右移2位并投影到0-3上则可以实现方向对调。 简单来说就是进行右移并除余 每次搜索的时候如果遇到之前已访问节点则退出函数函数中记录已覆盖节点如果达到节点总数则直接退出 运行效果如下 可以看到递归深度优先的算法的特点在一条路走到最后之后会返回到上一个节点 import pygame as pg
import time
import randomclass Tile():def __init__(self,grid_size,screen_size,x,y): #主要是储存数据和绘制图形与算法无关self.x,self.y x,yself.connected [0,0,0,0] # up,right,down,left 0 for not connectedself.grid_size grid_sizeself.tile_size [(screen_size[0]-100)/grid_size[0],(screen_size[1]-100)/grid_size[1]]self.rectangle (self.x*self.tile_size[0]50,self.y*self.tile_size[1]50,self.tile_size[0],self.tile_size[1])self.points [ [self.x*self.tile_size[0]50,self.y*self.tile_size[1]50], #uppper left[self.x*self.tile_size[0]50self.tile_size[0],self.y*self.tile_size[1]50], #upper right[self.x*self.tile_size[0]50self.tile_size[0],self.y*self.tile_size[1]50self.tile_size[1]], #lower right[self.x*self.tile_size[0]50,self.y*self.tile_size[1]50self.tile_size[1]], #lower left] self.visited Falsedef draw(self,color (255,253,150)): #x,y represents the tile coordinates pg.draw.rect(screen,color,self.rectangle) #绘制节点for i in range(4): #绘制四面墙壁if not self.connected[i]:pg.draw.line(screen,(150,175,255),(self.points[i]),(self.points[((i1)%4)]),5)def maze_gen(path):global tile_covered #覆盖节点数量当覆盖节点数量到达网格数量则停止x,y path[-1]if x 0 or x grid_size[0] or y 0 or y grid_size[1]: #超出网格范围则退出print(findex out of range at {x,y})returnmatrix[y][x].draw()if matrix[y][x].visited: #已访问节点则退出print(fnode already visited at {x,y})returnelif tile_covered grid_size[0]*grid_size[1]: #覆盖节点数量未到达网格总数量tile_covered 1matrix[y][x].visited Truepath_choice [0,1,2,3]random.shuffle(path_choice)directions [[0,-1],[1,0],[0,1],[-1,0]] # up,right,down,left 0 for not connectedfor i in path_choice:x_,y_ xdirections[i][0],ydirections[i][1]path.append([x_,y_])if maze_gen(path):matrix[y][x].connected[i] 1 #walls of current nodematrix[y_][x_].connected[(i2)%4] 1#reverse the vector directionmatrix[y][x].draw()matrix[y_][x_].draw()path.pop(-1)pg.display.update()return Trueelse:print(all node visited)returnscreen_size [800,800]
grid_size [40,40]
exit [10,10]
tile_covered 0
run Truescreen pg.display.set_mode(screen_size)matrix []
for y in range(grid_size[1]): #创建二维矩阵x,y代表坐标temp []for x in range(grid_size[0]):tile Tile(grid_size,screen_size,x,y)temp.append(tile)matrix.append(temp)pg.init()
path [[0,0]]screen.fill((255,255,255))
maze_gen(path)pg.display.update()print( Generation Finished )
while run: #生称完毕之后不退出使用循环for event in pg.event.get():if event.type pg.QUIT:time.sleep(0.1)pg.quit()exit()
