文章目錄

• 前言
• 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,top+r+2):for j in range(left-1,left+c+2):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, interpolation='none', 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), dtype=np.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,dir=0):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], (dir+2)%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), dtype=np.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 x+it[0] >= 0 and y+it[1] >= 0 and x+it[0] < h and y+it[1] < w:if M[x+it[0],y+it[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 = x+direction[next][0]y = y+direction[next][1]M[x,y,(next+2)%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), dtype=np.uint8)room = randomRoom(map)randomDoor(map,room.copy())floodFill2(map)drawMap(map,image)

這樣即使地圖增大，也能計算迷宮了，放下效果圖

2.3 走廊縮減

??當主要的關注點是在房間，而不是迷宮上時，往往不需要迷宮占滿整個地圖，這很浪費時間。

??那么需要將迷宮縮減一下，入手點是死胡同。我希望這個走廊沒有那么多死胡同，不至于走到浪費大量的時間在走迷宮上。尋找死胡同也很簡單，周圍三面是墻該點就是死胡同。

??首先遍歷搜索當前所有的死胡同點加入鏈表，對鏈表內容循環直至循環超過一定次數/剩余走廊少于一定數量/沒有死胡同。這個條件可以自行設置。代碼如下

def deleteCorner(M,left_floor=500):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), dtype=np.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],(dir+2)%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), dtype=np.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[i+it[0],j+it[1],5] in ls and map[i+it[0],j+it[1],5] != map[i,j,5]:ls.remove(map[i+it[0],j+it[1],5])map[i, j, ind] = 1map[i+it[0], j+it[1], (ind + 2) % 4] = 1map[map==map[i+it[0],j+it[1],5]] = map[i, j, 5]known.append(map[i,j,5])known.append(map[i+it[0],j+it[1],5])f = Truebreakind += 1if f:breakif f:break

那么這種方法就能生成需求中的迷宮和房間了。

---

總結

在看著自己隨機生成的迷宮不斷變化時一件有趣的事情，最后的最后，讓我放上兩種迷宮來獎賞自己。

總結

以上是生活随笔為你收集整理的地牢房间迷宫走廊生成（二），Python实现洪水法、完美迷宫的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。