成都网站建设平台,平台网站建设方案标书,中天建设集团有限公司排名,天猫网站设计特点文章目录前言1 随机房间和房门2 生成走廊2.1生成迷宫2.4 使用循环改进2.3 走廊缩减2.3 走廊再简化总结前言 前面通过随机房间、房门#xff0c;对房门寻路生成走廊。由于使用A星算法#xff0c;寻到的是最短路径#xff0c;这样生成的走廊过直和简单。如果需要生成弯曲的走廊… 文章目录前言1 随机房间和房门2 生成走廊2.1生成迷宫2.4 使用循环改进2.3 走廊缩减2.3 走廊再简化总结前言 前面通过随机房间、房门对房门寻路生成走廊。由于使用A星算法寻到的是最短路径这样生成的走廊过直和简单。如果需要生成弯曲的走廊这样的走廊能增加探险的乐趣和战斗拉扯需要做些什么呢 如果我们要在原基础上修改可以随机选取几个走廊的点将其扩大复杂化那么有没有其他方法呢通过在一块地图上生成一个弯曲的迷宫可以实现这个需求。在这里无论这个地图上有无房间。 首先考虑到数据结构的问题使用什么样的数据表示地图数据包括房间、墙壁、房门、走廊、空白点。在这里我使用一个三维数组表示整个图前两维的点是坐标第三维一共有6个数据前4个依次表示为左上右下是否连通第5个表示为该点是否存在物体或被遍历第6个表示物体的类别id数据表示为map[rows,cols,6]当然第三维不一定全是数字也可以使用二维的链表。 1 随机房间和房门 在地图上随机寻找一定大小的房间如果合适则放入房间。在这里需要限制循环的次数避免无法放置房间时无限循环下去。随机房门时在房间最外围随机寻找一个点当做房门当然也可以使用另一个随机数来设定房门的数量。为了简化代码假定从房间的左上角出发随机产生x和y方向的偏移量使用预定义好的四个权重对x和y加权将x和y映射到四个边上。此外将数据可视化使用matplotlib将地图画到图像上在此需要一个数组表示图像。 如下所示
import random
import numpy as np
from matplotlib import pyplot as pltdef randomRoom(M):height, width, d M.shapemin_size 5max_size 10room_num 20count 0try_count 0room []while count room_num:if try_count 1000:breakr random.randint(min_size, max_size)c random.randint(min_size, max_size)left random.randint(3, width - 4)top random.randint(3, height - 4)f Truefor i in range(top-1,topr2):for j in range(left-1,leftc2):if i height-3 or j width-3:f Falsebreakif M[i,j,5] 1:f Falsebreakif f:room.append([left,top,c,r])for i in range(top, top r 1):for j in range(left, left c 1):if i height-3 or j width-3:continueM[i, j, :] 1count 1try_count 1return roomdef randomDoor(map,room_list):for it in room_list:door_x,door_y randomWall(it)for i in range(it[3]1):map[it[1]i, it[0], 5] 3map[it[1]i, it[0]it[2], 5] 3for i in range(it[2]1):map[it[1], it[0]i, 5] 3map[it[1]it[3], it[0]i, 5] 3map[door_x,door_y,5] 2def randomWall(room):direction random.randint(0,3)dir [[0,1,-1,0],[1,0,0,-1],[1,0,0,room[3]],[0,1,room[2],0]]x_off random.randint(1,room[2]-2)y_off random.randint(1,room[3]-2)x room[0] x_off*dir[direction][0] # dir[direction][2]y room[1] y_off*dir[direction][1] # dir[direction][3]return y,xdef drawMap(M, image):rows, cols, deep M.shapeblock [[2,8,0,2],[0,2,2,8],[2,8,8,10],[8,10,2,8]]color [0,0,230,140]for row in range(0, rows):for col in range(0, cols):unit M[row, col]if unit[5] 1:image[10 * row : 10 * row 10, 10 * col:10 * col 10] 255else:image[10 * row 2: 10 * row 8, 10 * col 2:10 * col 8] 255 - color[unit[5]]for i in range(4):if unit[i] 1:x1 10 * row block[i][0]x2 10 * row block[i][1]y1 10 * col block[i][2]y2 10 * col block[i][3]image[x1:x2,y1:y2] 255 - color[unit[5]]plt.imshow(image, interpolationnone, cmap gray)plt.show()if __name__ __main__:rows int(input(输入房间行数))cols int(input(输入房间列数))map np.zeros((rows,cols,6),np.int16)image np.zeros((rows * 10, cols * 10), dtypenp.uint8)room randomRoom(map)randomDoor(map,room.copy())drawMap(map,image)
这样就生成了房间和房门画出所示图
2 生成走廊
2.1生成迷宫 现在有一个地图地图上有带有房门的房间接下来要做的是是未定区域产生走廊。在这里使用一个新的方法洪水法(flood fill)随机选取一点从这点出发将附近可到达的点填充。在迷宫中有一点不同的是前往下一个点时需要将两点间的墙壁打通。同时在迭代中当发现走入死胡同时回到上一次拐弯的地方选取另外一个方向。 可以想到通过递归来解决这个问题。在选取方向时让电脑随机选取一个方向。当打通两个点间的墙壁时显然一个点向左必然是另一个点的向右它们是对称的。假设用0123来表示三个方向它们之间的关系很明显是在4的有限域内将该点方向加上2模4就是另一点的方向。
def floodFill(M):h, w, d M.shapedef findFree():x random.randint(1,h-2)y random.randint(1,w-2)for i1 in range(x,h-1):for j1 in range(y,w-1):if M[i1,j1,5] 0:return [i1,j1]for i1 in range(1,h-1):for j1 in range(1,w-1):if M[i1,j1,5] 0:return [i1,j1]return Nonedirection [[0,-1],[-1,0],[0,1],[1,0]]def fill(point,dir0):if point[0] 1 or point[0] h-1 or point[1] 1 or point[1] w-1:returnif M[point[0], point[1], 4] 1:returnM[point[0], point[1], 4] 1M[point[0], point[1], 5] 4M[point[0], point[1], (dir2)%4] 1M[point[0]-direction[dir][0], point[1]-direction[dir][1], dir] 1ind random.randint(0,3)for i2 in range(4):index (ind i2) % 4fill([point[0]direction[index][0],point[1]direction[index][1]], index)while True:point findFree()if point None:breakfill(point)if __name__ __main__:rows int(input(输入房间行数))cols int(input(输入房间列数))map np.zeros((rows,cols,6),np.int16)image np.zeros((rows * 10, cols * 10), dtypenp.uint8)room randomRoom(map)randomDoor(map,room.copy())floodFill(map)drawMap(map,image)生成迷宫如下 这样很简单地就生成了房间外的迷宫由于洪水法的特点和所使用的数据结构这样保证了房间是被迷宫的通道包围的从房门打开就进入了迷宫。 此外该迷宫是一个完美的迷宫。完美的迷宫是指在迷宫任意两点间有且只有一条路径。如果不想让迷宫完美也即有多种方法可以到达另一点这往往是我们想要的可以令房间产生多个房门通过房间产生额外的路径或者可以在死胡同周围三面是墙上打洞。
2.4 使用循环改进
上述方法固然简单也是常常想到的方法。但是随着地图增大进行深递归时往往会发生爆栈。一个不是解决方法的方法是使用循环去代替递归改进如下
def floodFill2(M):h,w,d M.shapels []x y 0ls.append([x,y])dir []direction [[0,-1],[-1,0],[0,1],[1,0]]while ls:M[x, y, 4] 1dir.clear()ind 0for it in direction:if xit[0] 0 and yit[1] 0 and xit[0] h and yit[1] w:if M[xit[0],yit[1],4] 0:dir.append(ind)ind 1if len(dir) 0:ls.append([x, y])next random.choice(dir)M[x,y,5] 4M[x,y,next] 1x xdirection[next][0]y ydirection[next][1]M[x,y,(next2)%4] 1else:M[x, y, 5] 4x, y ls.pop()if __name__ __main__:rows int(input(输入房间行数))cols int(input(输入房间列数))map np.zeros((rows,cols,6),np.int16)image np.zeros((rows * 10, cols * 10), dtypenp.uint8)room randomRoom(map)randomDoor(map,room.copy())floodFill2(map)drawMap(map,image)这样即使地图增大也能计算迷宫了放下效果图
2.3 走廊缩减 当主要的关注点是在房间而不是迷宫上时往往不需要迷宫占满整个地图这很浪费时间。 那么需要将迷宫缩减一下入手点是死胡同。我希望这个走廊没有那么多死胡同不至于走到浪费大量的时间在走迷宫上。寻找死胡同也很简单周围三面是墙该点就是死胡同。 首先遍历搜索当前所有的死胡同点加入链表对链表内容循环直至循环超过一定次数/剩余走廊少于一定数量/没有死胡同。这个条件可以自行设置。代码如下
def deleteCorner(M,left_floor500):direction [[0, -1], [-1, 0], [0, 1], [1, 0]]try_num 1000count 0r, c, d M.shapetotal (r-1) * (c-1)corner []for i in range(r):for j in range(c):if sum(M[i,j,:4]) 1:corner.append([i,j])while len(corner):if count try_num or len(corner) 0 or total left_floor:breakcor random.choice(corner)if sum(M[cor[0],cor[1],:4]) ! 1:corner.remove(cor)continueis_door Falsefor it in direction:if M[cor[0]it[0],cor[1]it[1],5] 2:corner.remove(cor)is_door Trueif is_door:continuetemp np.where(M[cor[0], cor[1], :4] 1)front int(temp[0])M[cor[0], cor[1], :] 0M[cor[0] direction[front][0], cor[1] direction[front][1], (front 2) % 4] 0total - 1corner.remove(cor)corner.append([cor[0] direction[front][0], cor[1] direction[front][1]])count 1print(count)if __name__ __main__:rows int(input(输入房间行数))cols int(input(输入房间列数))map np.zeros((rows,cols,6),np.int16)image np.zeros((rows * 10, cols * 10), dtypenp.uint8)room randomRoom(map)randomDoor(map,room.copy())floodFill2(map)deleteCorner(map)drawMap(map,image)可以看到一些死胡同被删除了迷宫也不是占满整个地图。
2.3 走廊再简化 上述方法可以生成一个完整的迷宫和房间了。那么当然了需求是满足不完的尽管做了上述工作还是觉得走廊过于复杂了我不希望它是一条直线也不希望它拐来拐去该怎么办 在递归打通填充下一个点时使用的是随机一个方向那么要保持稳定可以初始随机选定一个方向在填充的过程中有概率拐弯这样的小设定能保持一段直道走廊。
def floodFill3(M):h, w, d M.shapearea 4area_list []def findFree():for i1 in range(1,h-1):for j1 in range(1,w-1):if M[i1,j1,5] 0:return [i1,j1]return Nonedef outRect(p):return p[0] 1 or p[0] h-1 or p[1] 1 or p[1] w-1direction [[0, -1], [-1, 0], [0, 1], [1, 0]]corner []while True:new_point point findFree()if point None:breakdir random.randint(0, 3)while True:point new_pointM[point[0], point[1], 5] areaM[point[0], point[1], 4] 1change random.random()old_dir dirif change 0.9:tran int((random.randint(-1,0)0.5)*2)old_dir dirdir (dir tran) % 4new_point [point[0]direction[dir][0], point[1]direction[dir][1]]f Falseif outRect(new_point):f Trueelif M[new_point[0],new_point[1],4] 1:f Trueif f:for i in range(4):ind (old_dir i) % 4temp [point[0]direction[ind][0], point[1]direction[ind][1]]if outRect(temp):continueelif M[temp[0],temp[1],4] 1:continueelse:new_point tempf Falsedir indif old_dir ! dir and not f:corner.append(point)if not f:M[point[0],point[1],dir] 1M[new_point[0],new_point[1],(dir2)%4] 1else:if len(corner):new_point corner.pop()else:breakarea_list.append(area)area 1return area_listif __name__ __main__:rows int(input(输入房间行数))cols int(input(输入房间列数))map np.zeros((rows,cols,6),np.int16)image np.zeros((rows * 10, cols * 10), dtypenp.uint8)room randomRoom(map)randomDoor(map,room.copy())floodFill3(map)drawMap(map,image) 需要注意的是修改后的方法产生的不是完美迷宫了而是一块一块不连通的迷宫某些时候需要将两个不连通的迷宫打通这需要额外的计算。对死胡同进行消除后看看结果。
#打通区域,ls存放area的列表
def breakArea(map,ls):h,w,d map.shapeknown []direction [[0,-1],[-1,0],[0,1],[1,0]]while len(ls) 1:f Falsefor i in range(h):for j in range(w):if map[i,j,5] in ls and not map[i,j,5] in known:ind 0for it in direction:if map[iit[0],jit[1],5] in ls and map[iit[0],jit[1],5] ! map[i,j,5]:ls.remove(map[iit[0],jit[1],5])map[i, j, ind] 1map[iit[0], jit[1], (ind 2) % 4] 1map[mapmap[iit[0],jit[1],5]] map[i, j, 5]known.append(map[i,j,5])known.append(map[iit[0],jit[1],5])f Truebreakind 1if f:breakif f:break那么这种方法就能生成需求中的迷宫和房间了。 总结
在看着自己随机生成的迷宫不断变化时一件有趣的事情最后的最后让我放上两种迷宫来奖赏自己。
