파이썬 미로 생성기 설명

Question

환영합니다. 누군가이 코드에서 어떤 일이 일어 났는지 설명 할 수 있습니까? 이 작품이 정확히 어떻게 작동하는지 알고 싶습니다 (http://rosettacode.org/wiki/Maze_generation#Python에서 온 것입니다).

from random import shuffle, randrange 
def make_maze(w = 16, h = 8): 
    vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)] 
    ver = [["| "] * w + ['|'] for _ in range(h)] + [[]] 
    hor = [["+--"] * w + ['+'] for _ in range(h + 1)] 

    def walk(x, y): 
     vis[y][x] = 1 

     d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)] 
     shuffle(d) 
     for (xx, yy) in d: 
      if vis[yy][xx]: continue 
      if xx == x: hor[max(y, yy)][x] = "+ " 
      if yy == y: ver[y][max(x, xx)] = " " 
      walk(xx, yy) 

    walk(randrange(w), randrange(h)) 
    for (a, b) in zip(hor, ver): 
     print(''.join(a + ['\n'] + b)) 

make_maze() 

Answer 1

나는 미로 생성에 대해 아무것도 모르지만,이 코드가 어떻게 작동하는지 궁금해. 여기에 몇 가지 통찰력은 다음과 같습니다

이 두 라인은 인쇄 미로 :

for (a, b) in zip(hor, ver): 
    print(''.join(a + ['\n'] + b)) 

그래서 우리가 바로 vis, ver 및 hor를 정의하는 세 줄 이후에 다음 줄을 넣어하면 어떻게됩니까?

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 

당신은 심지어 바로 재귀 호출 walk(xx,yy) 전에이 두 줄을 넣어 미로 진화의 몇 가지 단계를 볼 수 있습니다 : 우리는이 얻을

이

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+ +--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+ +--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+ +--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+ +--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+ +--+--+--+--+--+--+--+--+--+--+--+ 
| | | |  | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+ +--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+ + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | |  | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+ + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+ + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | |  | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | |  | | | | | | | | | | | | | 
+--+--+--+ + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+ + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | |  | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | |  | | | | | | | | | | | | | 
+--+--+ + + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+ + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | |  | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | |  | | | | | | | | | | | | | 
+--+--+ + + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+ + + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | |  | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | |  | | | | | | | | | | | | | 
+--+--+ + + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+ + + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | |  | | | | | | | | | | | | 
+--+--+ +--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | |  | | | | | | | | | | | | | 
+--+--+ + + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+ + + +--+--+--+--+--+--+--+--+--+--+--+ 
| | | |  | | | | | | | | | | | | 
+--+--+ +--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+ +--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
| | | | | | | | | | | | | | | | | 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 

[...] 

이제 walk(x,y)에 초점을 맞출 수 있습니다. 이름과 출력물이 제안하는대로이 함수는 미로를 따라 걷고 벽을 무작위로 제거하여 경로를 만듭니다.

이 호출 :

walk(randrange(w), randrange(h)) 

미로 내에서 임의의 위치에 산책을 초기화합니다. 그리드의 모든 셀은 정확히 한 번 방문됩니다. 방문한 셀은 vis으로 표시됩니다.

이 줄은 현재 셀의 네 이웃과 배열을 초기화 : 이들은 무작위로 방문 (shuffle(d) 덕분에)

그리고이 두 줄 있습니다

d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)] 

제거 것들입니다 미로 경로로 벽이 건설되고있다 :

# remove horizontal wall, "+--" turns into "+ " 
if xx == x: hor[max(y, yy)][x] = "+ " 

# remove vertical wall, "|" turns into " " 
if yy == y: ver[y][max(x, xx)] = " " 

이 (Jongware의 의견을 참조)이 알고리즘에 대해 말을 더하지만, 지금까지 이해로 이 코드 조각은 여러분이 할 수있는 일들입니다.