미로 생성시 모서리를 건드릴 수있는 방법

Question

파이썬 3에서 미로 생성기를 개발하려고했지만 거의 완료되었습니다. 아래 그림과 같이 미로를 만들 수있는 지점까지 있습니다. 그러나 자세히 살펴보면 내가 걱정하고있는 두 가지 문제를 볼 수 있습니다. 어떤 경우에는 경로 모퉁이가 만지고 있습니다. 이것은 분명히 각 잠재 셀 8 모서리와 모서리를 검사하여 피하려고 시도하는 것입니다. 추가 셀을위한 공간이있는 "섬"이있는 곳을 볼 수있는 곳도 있지만 비어 있습니다. 내가 어떻게 그 문제를 해결할 수 있는지에 대한 생각이 있다면 그것은 좋을 것이다. 감사!

import random 
import numpy as np 
from matplotlib import pyplot as plt 

# Width and height of the maze 
mx = 50 
my = 50 

# Maze Array 
maze = np.zeros((mx, my)) 

# Directions to move in the maze 
dx = [-1, 1, 0, 0, -1, 1, 1, -1] 
dy = [0, 0, -1, 1, -1, 1, -1, 1] 

# Visited Cells 
stack = [] 

# Find Which Neighbour Cells Are Valid 
def nextCell(cx, cy): 

    # Set Current Cell To '1' 
    maze[cy, cx] = 1 

    # List Of Available Neighbour Cell Locations 
    n = [] 

    # Check The 4 Available Neighbour Cells 
    for i in range(4): 

     nx = cx + dx[i] 
     ny = cy + dy[i] 

     # Check If Neighbours Cell Is Inbound 
     if nx >= 1 and nx < my - 1 and ny >= 1 and ny < mx - 1: 

      # Check If Neighbour Cell Is Occupied 
      if maze[ny, nx] == 0: 

       # Variable To Store Neighbour Cells Neighbours 
       cn = 0 

       # Loop Through Neighbour Cells Neighbours 
       for j in range(8): 

        ex = nx + dx[j] 
        ey = ny + dy[j] 

        # Check If Neighbour Cells Neighbour Is Inbound 
        if ex >= 0 and ex < my and ey >= 0 and ey < mx: 

         # Check If Neighbour Cells Neighbour Is Occupied 
         if maze[ey, ex] == 1: 
          cn += 1 

       # If Neighbour Cells Neighbour Has Less Than 2 Neighbours, Add Cell To List 
       if cn <= 2: 
        n.append((ny, nx)) 



    # Return The List Of Valid Neighbours 
    return n 

# Generate The Maze 
def GenerateMaze(sx, sy): 

    # Initialize 'x,y' With Starting Location 
    x = sx 
    y = sy 

    # Loop Until Maze Is Fully Generated 
    while True: 

     # Neighbour List 
     n = nextCell(x, y) 

     # Check If 'n' Contains A Neighbour 
     if len(n) > 0: 
      stack.append((y, x)) 

      ir = n[random.randint(0, len(n) - 1)] 

      x = ir[1] 
      y = ir[0] 

     # Go Back Through The Stack 
     elif len(stack) > 1: 
      stack.pop() 

      x = stack[-1][1] 
      y = stack[-1][0] 

     # Maze Is Complete 
     else:  
      break 



if __name__ == "__main__": 

    # Generate Maze 
    GenerateMaze(random.randint(1,8), random.randint(1,8)) 

    # Show Plot 
    plt.imshow(maze, interpolation='nearest') 
    plt.show() 

Answer 1

당신은 점령 인접 셀을 검사 할 때 앞으로 조금 더보고 감동적인 모서리를 제거 할 수 있습니다. 선 후

if maze[ny, nx] == 0: 

은 다음과 같은 추가 :

# Abort if there is an occupied cell diagonally adjacent to this one 
    if maze[ny+dy[i]+dx[i], nx+dx[i]+dy[i]] or maze[ny+dy[i]-dx[i], nx+dx[i]-dy[i]]: 
     continue 

다음은 결과입니다 :

는 섬이다, 내 생각, 조금 난이도를 제거하기. 당신이 정말로 피하고 싶은 것이면, 나는 더 질서 정연한 방식으로 미로를 건설하는 것이 좋습니다. Wikipedia에는 ​​maze generation algorithms에 대한 페이지가 있습니다. 무작위 화 된 Kruskal의 알고리즘은 꽤 좋은 결과를 제공하며, Python에서 구현하기가 아주 간단해야합니다.