Статья Автор: Лебедев Дмитрий Алексеевич

Создаем "идеальные лабиринты"

Для создания идеальных лабиринтов будем использовать метод Крускала

def generate_kruskal(width, height):
    """Генерация лабиринта алгоритмом Краскала"""
    def find(p):
        if parent[p] == p: return p
        parent[p] = find(parent[p])
        return parent[p]
    def union(p, q):
        r1, r2 = find(p), find(q)
        if r1 != r2:
            parent[r1] = r2
            return True
        return False
    # Список всех возможных внутренних стен: ((x1, y1), (x2, y2))
    walls = []
    for x in range(width):
        for y in range(height):
            if x < width - 1: walls.append(((x, y), (x + 1, y)))
            if y < height - 1: walls.append(((x, y), (x, y + 1)))
    
    # DSU (Система непересекающихся множеств) для отслеживания связей клеток
    parent = {(x, y): (x, y) for x in range(width) for y in range(height)}
    # Перемешиваем стены для случайности
    random.shuffle(walls)
    
    passages = []
    for c1, c2 in walls:
        if union(c1, c2):
            # Если клетки были в разных множествах, убираем стену (добавляем в проходы)
            passages.append((c1, c2))
            
    MZ=[]
    for j in range(W):
        a =[]
        for i in range (H):
            a.append(['0','0','0','0'])
        MZ.append(a)    
    for (x1, y1), (x2, y2) in passages:
        if x1 == x2 and y1 < y2: MZ[x1][y1][0],MZ[x2][y2][1] = '1', '1'
        elif x1 == x2 and y1 > y2: MZ[x1][y1][1],MZ[x2][y2][0] = '1', '1'
        elif y1 == y2 and x1 < x2: MZ[x1][y1][2],MZ[x2][y2][3] = '1', '1'
        elif y1 == y2 and x1 > x2: MZ[x1][y1][3],MZ[x2][y2][2] = '1', '1'
    maze = []
    for y in range (H):
        sb = ''
        for x in range (W):
            a = MZ[x][y]
            sb += hex(int(''.join(a),2))[-1].upper()
        maze.append(sb)    
    return maze

W, H = map(int,input().split())
maze = generate_kruskal(W, H)
print(maze)

import turtle as tr
def draw(x, y, a, t, m):
  t.up(); t.goto(x,y)
  k = 15 - int(a,16)
  b = ''
  for _ in range(4):
    b = str(k%2) + b
    k = k // 2
  if b[3] == '0' : t.up()
  else : t.down()
  t.seth(90); t.fd (m)
  if b[0] == '0' : t.up()
  else : t.down()
  t.seth(0); t.fd (m)
  if b[2] == '0' : t.up()
  else : t.down()
  t.seth(270); t.fd (m)
  if b[1] == '0' : t.up()
  else : t.down()
  t.seth(180); t.fd (m)
  
def draw_maze(A, m = 20):
  W, H = len(A[0]), len(A)
  xx, yy = -m*W//2, -m*H//2
  t = tr.Pen(); t.speed(0)
  for i in range(H) :
    y = yy + i*m
    x = xx
    ss = A[i]
    for s in ss :
      draw(x, y, s, t, m)
      x += m
  tr.done()    
A = ['8ABB39', '65C48C', 'ABDA5C', '446525'] 
#['888A1233B1', '6F7F39AB71', 'AF142D4E39', '4C8884ADA5', 'A77DCA5461', 'E18E5CAB31', '63563F5488', '2BBB3F31E5', '8C4CAF3B79', '6525442714'] 
#['2339A39A18','2B1E716F1C','AD8CAB163D','CEF54C8A3D','4463375614']
draw_maze(A, 30)

def generate_kruskal4(width, height):
    """Генерация лабиринта алгоритмом Краскала"""
    def find(p):
        if parent[p] == p: return p
        parent[p] = find(parent[p])
        return parent[p]
    def union(p, q):
        r1, r2 = find(p), find(q)
        if r1 != r2:
            parent[r1] = r2
            return True
        return False
    # Список всех возможных внутренних стен: ((x1, y1), (x2, y2))
    walls = []
    for x in range(width):
        for y in range(height):
            if x < width - 1: walls.append(((x, y), (x + 1, y)))
            if y < height - 1: walls.append(((x, y), (x, y + 1)))
    
    # DSU (Система непересекающихся множеств) для отслеживания связей клеток
    parent = {(x, y): (x, y) for x in range(width) for y in range(height)}
    # Перемешиваем стены для случайности
    random.shuffle(walls)
    
    passages = []
    for c1, c2 in walls:
        if union(c1, c2):
            # Если клетки были в разных множествах, убираем стену (добавляем в проходы)
            passages.append((c1, c2))
            
    MZ=[]
    for j in range(W):
        a =[]
        for i in range (H):
            a.append(['0','0'])
        MZ.append(a)    
    for (x1, y1), (x2, y2) in passages:
        if x1 == x2 and y1 < y2: MZ[x1][y1][0] = '1'
        elif y1 == y2 and x1 <  x2: MZ[x2][y2][1] = '1'
    maze = []
    for y in range (H):
        sb = ''
        for x in range (W):
            a = MZ[x][y]
            sb += str(int(a[0])*2 +int(a[1]))
        maze.append(sb)    
    return maze

W, H = map(int,input().split())
maze = generate_kruskal4(W, H)
print(maze)

import turtle as tr
def draw4(x, y, a, t, m):
  t.up(); t.goto(x,y)
  k = int(a)
  if k // 2 == 0 : t.up()
  else : t.down()
  t.seth(-90); t.fd (m); t.fd(-m)
  if k % 2 == 0 : t.up()
  else : t.down()
  t.seth(0); t.fd (m);
  
def draw_maze(A, m = 20):
  W, H = len(A[0]), len(A)
  xx, yy = -m*W//2, -m*H//2
  t = tr.Pen(); t.speed(0)
  for i in range(H) :
    y = yy + i*m
    x = xx
    ss = A[i]
    for s in ss :
      draw4(x, y, s, t, m)
      x += m
  tr.done()    
A = ['0323232111', '2310120311', '0220130113', '2132011332', '0011111001']
#['1111110', '2200102', '3123222', '2002122', '3331312'] 
#['888A1233B1', '6F7F39AB71', 'AF142D4E39', '4C8884ADA5', 'A77DCA5461', 'E18E5CAB31', '63563F5488', '2BBB3F31E5', '8C4CAF3B79', '6525442714'] 
#['2339A39A18','2B1E716F1C','AD8CAB163D','CEF54C8A3D','4463375614']
draw_maze(A, 30)

Печать