python实现地牢迷宫生成的完整步骤

基本属性

定义当前地牢的等级，地图长宽，房间数量，房间的最小最大长度，如下

class Map:
   def __init__(self):
       self.width = 30
       self.heigh = 30
       self.level = 1
       self.roomNum = 5
       self.map = np.zeros((self.heigh,self.width))
       self.roomMin = 3
       self.roomMax = 11

生成房间

编写initRoom()随机生成房间，限制最多循环次数，为了简单起见，先做一个不会重叠的房间。基本思路是：随机房间的中心点，随机房间的长宽，再进行判断房间有无重叠（在后续会生成通道，简单起见在这里也保证房间不会紧贴），若无重叠，房间有效，房间数加1。贴代码

   def initRoom(self):
       count = 0
       roomCount = 1
       while True:
           count += 1
           if count > 300:
               break
           if roomCount > self.roomNum:
               break
           x = random.randint(1,self.width-1)
           y = random.randint(1,self.heigh-1)
           wd = random.randint(self.roomMin,self.roomMax)
           ht = random.randint(self.roomMin, self.roomMax)
           r1 = ceil(y - ht/2)
           r2 = ceil(y + ht/2)
           c1 = ceil(x - wd/2)
           c2 = ceil(x + wd/2)
           if r1 < 1:
               r1 = 1
           if r2 >= self.heigh - 1:
               r2 = self.heigh - 2
           if c1 < 1:
               c1 = 1
           if c2 >= self.width - 1:
               c2 = self.width - 2
           w = c2 - c1 + 1
           h = r2 - r1 + 1
           if h / w >= 3 or w / h >= 3: #保证房间不是细长的
               continue
           judge = self.isValidRoom(r1,r2,c1,c2)
           if judge == 0:
               roomCount += 1
               self.room.append(Room(r1,r2,c1,c2))
               for i in range(r1,r2):
                   for j in range(c1,c2):
                       self.map[i,j] = 1

def isValidRoom(self,r1,r2,c1,c2):
       #检测有无覆盖
       for i in range(r1,r2):
           for j in range(c1,c2):
               if self.map[i,j] == 1:
                   return -1
       #检测有无紧贴房间
       for i in range(r1,r2):
           if self.map[i,c1-1] == 1 or self.map[i,c2+1] == 1:
               return 2
       for i in range(c1,c2):
           if self.map[r1-1,i] == 1 or self.map[r2+1,i] == 1:
               return 2
       return 0

看一下效果

生成墙壁

编写initTile()生成包围房间和通道的墙壁，直接贴代码

   def initTile(self):
       offset = [[-1,0],[0,-1],[1,0],[0,1],[-1,-1],[1,1],[1,-1],[-1,1]]
       for i in range(self.heigh):
           for j in range(self.width):
               if self.map[i,j] == 0:
                   tag = 0
                   for it in offset:
                       if i+it[0] >= self.heigh or j+it[1] >= self.width or i+it[0] < 0 or j+it[1] < 0:
                           continue
                       if self.map[i+it[0],j+it[1]] != 3 and self.map[i+it[0],j+it[1]] != 4:
                           tag += self.map[i+it[0],j+it[1]]
                   if tag:
                       self.map[i,j] = 3

效果

生成门口

随机选取房间的一个外围点当做房门，思路是在房间的长宽内随机两个数作为偏移量，预定义好四个方向的覆盖模板对偏移量进行加权和偏置，在这里我编写房间的类，加进地图的属性列表里。

除此之外，房间连通的思路是：在所有房间列表中随机抽出两个房间，将这两个房间连通，再随机选一个房间加回原来的房间列表，直至最后列表里只剩下一个房间。那么现在先来生成房门，代码如下

class Room():
   def __init__(self,r1,r2,c1,c2):
       w = c2 - c1
       h = r2 - r1
       self.width = w
       self.height = h
       self.cx = c1 + ceil(w/2)
       self.cy = r1 + ceil(h/2)
       self.xStart = c1
       self.xEnd = c2 - 1
       self.yStart = r1
       self.yEnd = r2 - 1

def randomTile(self):
       direction = random.randint(0,3)
       dir = [[0,1,-1,0],[1,0,0,-1],[1,0,0,self.height],[0,1,self.width,0]]
       x_off = random.randint(0,self.width-1)
       y_off = random.randint(0,self.height-1)
       x = self.xStart + x_off*dir[direction][0] + dir[direction][2]
       y = self.yStart + y_off*dir[direction][1] + dir[direction][3]
       if y == 0 or x == 0:
           return self.randomTile()
       else:
           return [y,x]
class Map:
   def initPath(self):
       #初始化门
       rm = self.room.copy()
       while len(rm) > 1:
           r1 = random.choice(rm)
           rm.remove(r1)
           r2 = random.choice(rm)
           rm.remove(r2)
           point0 = r1.randomTile()
           while point0[0] == self.heigh-1 or point0[1] == self.width-1:
               point0 = r1.randomTile()
           self.map[point0[0],point0[1]] = 2
           self.door.append(point0)
           self.breakTile(point0)
           point1 = r2.randomTile()
           while point1[0] == self.heigh-1 or point1[1] == self.width-1:
               point1 = r2.randomTile()
           self.map[point1[0],point1[1]] = 2
           self.breakTile(point1)
           self.door.append(point1)
           rn = random.randint(0,1)
           #a*算法寻找从point0到point1的路径
           #self.aStar(point0,point1)
           if rn == 0:
               rm.append(r1)
           else:
               rm.append(r2)

def breakTile(self,p):
       # 打通堵住的周围的墙壁
       if self.map[p[0] - 1, p[1]] == 1 and self.map[p[0] + 1, p[1]] == 3:
           self.map[p[0] + 1, p[1]] = 2
       elif self.map[p[0], p[1] - 1] == 1 and self.map[p[0], p[1] + 1] == 3:
           self.map[p[0], p[1] + 1] = 2
       elif self.map[p[0] + 1, p[1]] == 1 and self.map[p[0] - 1, p[1]] == 3:
           self.map[p[0] - 1, p[1]] = 2
       elif self.map[p[0], p[1] + 1] == 1 and self.map[p[0], p[1] - 1] == 3:
           self.map[p[0], p[1] - 1] = 2

看下效果

生成通道

接着完善上述函数，在随机选取房门后，连接两个房门。

在这我选择的是A星算法，打通两个房门，直接上代码

   def aStar(self,p0,p1):
       open_list = []
       close_list = []
       offset = [[-1,0],[0,-1],[1,0],[0,1]]
       f = h = abs(p0[0] - p1[0]) * 10 + abs(p0[1] - p1[1]) * 10
       g = 0

def isInClose(p):
           for it in close_list:
               if it.value[3] == p:
                   return True
           return False
       def isInOpen(p):
           for it in open_list:
               if it.value[3] == p:
                   return True
           return False
       def findFather(p):
           for it in close_list:
               if it.value[3] == p:
                   return it.value[4]
           return [-1,-1]
       def findInOpen(p):
           for it in open_list:
               if it.value[3] == p:
                   return it
           return None

open_list.append(Node([f,g,h,p0,[-1,-1]]))
       while open_list:
           #for it in open_list:
           #    print(it.value)
           open_list.sort(key=(lambda x:x.value[0]))
           f_min = open_list[0]
           close_list.append(f_min)
           open_list.remove(f_min)
           for it in offset:
               p2 = [f_min.value[3][0]+it[0], f_min.value[3][1]+it[1]]
               if p2[0] == p1[0] and p2[1] == p1[1]:
                   #找到
                   close_list.append(Node([f,g,h,p2,f_min]))
                   p_father = f_min.value[3]
                   while True:
                       self.map[p_father[0],p_father[1]] = 2
                       p_father = findFather(p_father)
                       if p_father[0] == -1:
                           break
                   self.map[p0[0], p0[1]] = 4
                   return
               if p2[0] < 0 or p2[0] >= self.heigh or p2[1] < 0 or p2[1] >= self.width:
                   continue
               if (self.map[p2[0],p2[1]] != 0 and self.map[p2[0],p2[1]] != 2 and self.map[p2[0],p2[1]] != 4) or isInClose(p2):
                   continue
               h = abs(p2[0] - p1[0]) * 10 + abs(p2[1] - p1[1]) * 10
               g = f_min.value[1] + 10
               f = h + g
               if not isInOpen(p2):
                   open_list.append(Node([f,g,h,p2,f_min.value[3]]))
               else:
                   #比较最小的G 值
                   temp = findInOpen(p2)
                   if g < temp.value[1]:
                       open_list.remove(temp)
                       open_list.append(Node([f,g,h,p2,f_min.value[3]]))

效果

这样，一个随机房间的地牢就已经生成，贴上完整代码

import random
import numpy as np
from math import ceil

class Node():
   def __init__(self, val=None):
       if val is None:
           val = [0, 0, 0, [-1, -1], [-1, -1]]
       self.value = val

class Room():
   def __init__(self,r1,r2,c1,c2):
       w = c2 - c1
       h = r2 - r1
       self.width = w
       self.height = h
       self.cx = c1 + ceil(w/2)
       self.cy = r1 + ceil(h/2)
       self.xStart = c1
       self.xEnd = c2 - 1
       self.yStart = r1
       self.yEnd = r2 - 1

def info(self):
       print('r1 c1 r2 c2:  ',self.yStart,self.xStart,self.yEnd,self.xEnd)
       print('cx    cy:     ',self.cx,self.cy)
       print('width height: ',self.width,self.height)

def randomTile(self):
       direction = random.randint(0,3)
       dir = [[0,1,-1,0],[1,0,0,-1],[1,0,0,self.height],[0,1,self.width,0]]
       x_off = random.randint(0,self.width-1)
       y_off = random.randint(0,self.height-1)
       x = self.xStart + x_off*dir[direction][0] + dir[direction][2]
       y = self.yStart + y_off*dir[direction][1] + dir[direction][3]
       if y == 0 or x == 0:
           return self.randomTile()
       else:
           return [y,x]

class Map:
   def __init__(self):
       self.width = 30
       self.heigh = 30
       self.level = 1
       self.roomNum = 5
       #0 is null, 1 is room, 2 is path, 3 is wall, 4 is door, 5 is up stair, 6 is downstair
       self.map = np.zeros((self.width,self.heigh))
       self.roomMin = 3
       self.roomMax = 11
       self.room = []
       self.door = []

self.initRoom()
       self.initTile()
       self.initPath()
       #self.initTile()
       #self.initDoor()

def initRoom(self):
       count = 0
       roomCount = 1
       while True:
           count += 1
           if count > 300:
               break
           if roomCount > self.roomNum:
               break
           x = random.randint(1,self.width-1)
           y = random.randint(1,self.heigh-1)
           wd = random.randint(self.roomMin,self.roomMax)
           if wd ％ 2 == 0:
               wd += 1
           ht = random.randint(self.roomMin, self.roomMax)
           if ht ％ 2 == 0:
               ht += 1
           r1 = ceil(y - ht/2)
           r2 = ceil(y + ht/2)
           c1 = ceil(x - wd/2)
           c2 = ceil(x + wd/2)
           if r1 < 1:
               r1 = 1
           if r2 >= self.heigh - 1:
               r2 = self.heigh - 2
           if c1 < 1:
               c1 = 1
           if c2 >= self.width - 1:
               c2 = self.width - 2
           w = c2 - c1 + 1
           h = r2 - r1 + 1
           if w == 0:
               continue
           if h == 0:
               continue
           if h / w >= 3 or w / h >= 3:
               continue
           judge = self.isValidRoom(r1,r2,c1,c2)
           if judge == 0:
               roomCount += 1
               self.room.append(Room(r1,r2,c1,c2))
               for i in range(r1,r2):
                   for j in range(c1,c2):
                       self.map[i,j] = 1

def initPath(self):
       #初始化门
       rm = self.room.copy()
       while len(rm) > 1:
           r1 = random.choice(rm)
           rm.remove(r1)
           r2 = random.choice(rm)
           rm.remove(r2)
           point0 = r1.randomTile()
           while point0[0] == self.heigh-1 or point0[1] == self.width-1:
               point0 = r1.randomTile()
           self.map[point0[0],point0[1]] = 2
           self.door.append(point0)
           self.breakTile(point0)
           point1 = r2.randomTile()
           while point1[0] == self.heigh-1 or point1[1] == self.width-1:
               point1 = r2.randomTile()
           self.map[point1[0],point1[1]] = 2
           self.breakTile(point1)
           self.door.append(point1)
           rn = random.randint(0,1)
           #a*算法寻找从point0到point1的路径
           self.aStar(point0,point1)
           if rn == 0:
               rm.append(r1)
           else:
               rm.append(r2)

def initDoor(self):
       for it in self.door:
           self.map[it[0],it[1]] = 4

def breakTile(self,p):
       # 打通堵住的周围的墙壁
       if self.map[p[0] - 1, p[1]] == 1 and self.map[p[0] + 1, p[1]] == 3:
           self.map[p[0] + 1, p[1]] = 2
       elif self.map[p[0], p[1] - 1] == 1 and self.map[p[0], p[1] + 1] == 3:
           self.map[p[0], p[1] + 1] = 2
       elif self.map[p[0] + 1, p[1]] == 1 and self.map[p[0] - 1, p[1]] == 3:
           self.map[p[0] - 1, p[1]] = 2
       elif self.map[p[0], p[1] + 1] == 1 and self.map[p[0], p[1] - 1] == 3:
           self.map[p[0], p[1] - 1] = 2

def initTile(self):
       offset = [[-1,0],[0,-1],[1,0],[0,1],[-1,-1],[1,1],[1,-1],[-1,1]]
       for i in range(self.heigh):
           for j in range(self.width):
               if self.map[i,j] == 0:
                   tag = 0
                   for it in offset:
                       if i+it[0] >= self.heigh or j+it[1] >= self.width or i+it[0] < 0 or j+it[1] < 0:
                           continue
                       if self.map[i+it[0],j+it[1]] != 3 and self.map[i+it[0],j+it[1]] != 4:
                           tag += self.map[i+it[0],j+it[1]]
                   if tag:
                       self.map[i,j] = 3

def isValidRoom(self,r1,r2,c1,c2):
       #检测有无覆盖
       for i in range(r1,r2):
           for j in range(c1,c2):
               if self.map[i,j] == 1:
                   return -1
       #检测有无紧贴房间
       for i in range(r1,r2):
           if self.map[i,c1-1] == 1 or self.map[i,c2+1] == 1:
               return 2
       for i in range(c1,c2):
           if self.map[r1-1,i] == 1 or self.map[r2+1,i] == 1:
               return 2
       return 0

def aStar(self,p0,p1):
       open_list = []
       close_list = []
       offset = [[-1,0],[0,-1],[1,0],[0,1]]
       f = h = abs(p0[0] - p1[0]) * 10 + abs(p0[1] - p1[1]) * 10
       g = 0

def isInClose(p):
           for it in close_list:
               if it.value[3] == p:
                   return True
           return False
       def isInOpen(p):
           for it in open_list:
               if it.value[3] == p:
                   return True
           return False
       def findFather(p):
           for it in close_list:
               if it.value[3] == p:
                   return it.value[4]
           return [-1,-1]
       def findInOpen(p):
           for it in open_list:
               if it.value[3] == p:
                   return it
           return None

open_list.append(Node([f,g,h,p0,[-1,-1]]))
       while open_list:
           #for it in open_list:
           #    print(it.value)
           open_list.sort(key=(lambda x:x.value[0]))
           f_min = open_list[0]
           close_list.append(f_min)
           open_list.remove(f_min)
           for it in offset:
               p2 = [f_min.value[3][0]+it[0], f_min.value[3][1]+it[1]]
               if p2[0] == p1[0] and p2[1] == p1[1]:
                   #找到
                   close_list.append(Node([f,g,h,p2,f_min]))
                   p_father = f_min.value[3]
                   while True:
                       self.map[p_father[0],p_father[1]] = 2
                       p_father = findFather(p_father)
                       if p_father[0] == -1:
                           break
                   self.map[p0[0], p0[1]] = 4
                   return
               if p2[0] < 0 or p2[0] >= self.heigh or p2[1] < 0 or p2[1] >= self.width:
                   continue
               if (self.map[p2[0],p2[1]] != 0 and self.map[p2[0],p2[1]] != 2 and self.map[p2[0],p2[1]] != 4) or isInClose(p2):
                   continue
               h = abs(p2[0] - p1[0]) * 10 + abs(p2[1] - p1[1]) * 10
               g = f_min.value[1] + 10
               f = h + g
               if not isInOpen(p2):
                   open_list.append(Node([f,g,h,p2,f_min.value[3]]))
               else:
                   #比较最小的G 值
                   temp = findInOpen(p2)
                   if g < temp.value[1]:
                       open_list.remove(temp)
                       open_list.append(Node([f,g,h,p2,f_min.value[3]]))

def printMap(self):
       for i in range(self.heigh):
           for j in range(self.width):
               print(int(self.map[i,j]),end='')
           print()

def printRoom(self):
       for r in self.room:
           r.info()

if __name__ == '__main__':
   map = Map()
   map.printMap()

可视化一下

总结 

来源：https://blog.csdn.net/weixin_44715221/article/details/120458006