재귀호출을 활용한 GUI 랜덤미로 생성
개요
이번엔 Python, PyQt5를 이용해 랜덤 미로 생성기 (Maze Generator) 를 만들어 보았습니다.
자세한 내용은 소스코드 분석을 참조하기 바라며, 동작방식은 아래와 같습니다.
화면에 표시되는 위젯(윈도우)을 15x15 크기로 잘라, 작은
격자 사각형을 2차원 리스트에 저장해 둡니다.
미로 생성이 시작되면 현재 격자의 행,열에서 이동가능한 방향 (상, 하, 좌, 우)을 랜덤으로 선택해 이동합니다. (단, 이미 방문한 곳이 아닌 경우, 재귀호출, Push Stack)
만약 더 이상 이동가능한 방향이 없는 경우는 재귀호출의 스택이 풀리며 (Pop Stack) 퇴각 검색 (Backtrack)이 진행되고, 이동가능한 방향이 있는지 다시 찾는
원리로 모든 격자를 방문하게 됩니다.
- 15 X 15 크기의 랜덤 미로 생성. (사이즈 변경가능)
- DFS (Depth First Search), 재귀호출을 이용해 구현.
- 미로 진행 방향에 따른 벽 생성 및 벽 삭제. (상,하,좌,우)
개발 환경
- Python 3.8.8 (64bit), PyQt5 5.15.3
- PyCharm 2021.2.1 (Community Edition)
소스 코드
2개의 파이썬 파일 (*.py)로 구성되어 있으며, 위젯의 생성을 담당하는 main.py 와 미로를 생성하는 maze.py 로 구성.
두 파일을 같은 경로에 두고 main.py 를 실행하면 됩니다.
main.py 소스코드
Qt의 위젯을 생성하는 간단한 코드와 메인함수로 구성되어 있습니다.
from PyQt5.QtWidgets import QApplication, QWidget
from PyQt5.QtGui import QPainter
from maze import MazeMap
import sys
class Form(QWidget):
def __init__(self):
super().__init__()
self.setWindowTitle('Maze Generator')
self.setFixedSize(1200,1200)
self.mazeMap = MazeMap(self)
# start_row, start_col, maze_size, delay
self.mazeMap.startMap(0, 0, 15, 0.3)
def paintEvent(self, e):
qp = QPainter()
qp.begin(self)
self.mazeMap.draw(qp)
qp.end()
def closeEvent(self, e):
self.mazeMap.closeMap()
if __name__ == '__main__':
app = QApplication(sys.argv)
w = Form()
w.show()
sys.exit(app.exec_())
[라인 1~4]
필요한 패키지와 모듈을 불러옵니다.
PyQt5는 외부 패키지 이므로 코드 실행전에 설치되어 있어야 합니다.
[라인 6~14]
Qt의 QWidget에서 상속받은 Form Class의 구현부입니다.
생성자 함수에서 뒤에 소개할 maze.py 파일에 선언된 MazeMap 클래스의 객체를 생성 후, startMap() 함수의 전달인자로 4가지 값 (시작행, 시작열, 미로크기, 지연시간) 을 전달해 미로 생성을 시작합니다.
4번째 전달인자인 지연시간은 미로 생성시 그리는 과정을 지연시켜 사용자에게 미로가 생성되는 과정을 볼 수 있도록 합니다.
[라인 16~ 20]
QWidget이 가지고 있는 paintEvent() 함수에 대한 오버라이딩이며, 이 함수는 위젯을 새로 그려야 할 필요가 있을 때 마다 호출되게 됩니다.
여기서 그림을 그리는 팔 역할을 하는 QPainter의 객체 (qp) 를 생성하고, 생성자에서 만든 MazeMap 객체에 이 그림을 그리는 팔을 전달해 MazeMap 클래스가 대신 그림을 그리도록 합니다.
이런 방식으로 코드를 작성하면 위젯과 미로라는 두 개념을 분리해 각자의 클래스가 서로의 역할에 집중하도록 하고 코드가 한 파일에 편중되는 것을 막아 설계상의 이점이 있습니다.
[라인 22~23]
QWidget이 가지고 있는 closeEvent() 함수에 대한 오버라이딩이며, 이 함수는 위젯이 종료될 때 호출되게 됩니다.
이때, 생성자에서 만든 MazeMap 클래스의 closeMap() 함수를 호출해 미로생성 중 만들어진 각종 자원들을 해제시켜 주도록 합니다.
[라인 25~29]
앱의 시작점인 메인 함수이며, 위에 설명한 Form 클래스의 객체를 생성해 앱을
실행하도록 합니다.
maze.py 소스코드
미로생성을 수행하는 코드로 구성되어 있습니다.
아래 3가지 클래스로 구성되어 있으며, 그림을 참조하기 바랍니다.
-
Dir, 미로 방향을 뜻하는 열거형 클래스.
-
MazeItem, 하나의 미로
-
MazeMap, 미로 전체
|
||
| [MazeMap vs MazeItem] |
소스코드는 아래와 같습니다.
from PyQt5.QtCore import QObject, pyqtSignal, QRectF, Qt
from PyQt5.QtGui import QColor, QBrush, QPen
from threading import Thread
from enum import Enum
import time
import random
class Dir(Enum):
# row, col
UP = (-1, 0)
DOWN = (1, 0)
LEFT = (0, -1)
RIGHT = (0, 1)
class MazeItem:
def __init__(self, row, col, dir=list(), idx=-1):
self.row = row
self.col = col
self.dir = dir
self.idx = idx
class MazeMap(QObject):
update_signal = pyqtSignal()
def __init__(self, w):
super().__init__()
self.parent = w
self.rect = w.rect()
self.inrect = QRectF(self.rect)
gap = 10
self.inrect.adjust(gap, gap, -gap, -gap)
self.mazeItems = []
# signal
self.update_signal.connect(self.parent.update)
def initMazeMap(self, size, delay):
self.idx = 0
self.size = size
self.delay = delay
self.gap = self.inrect.width() / (self.size)
self.rects = []
self.visited = []
x = self.inrect.left()
y = self.inrect.top()
for r in range(self.size):
rt = []
vt = []
for c in range(self.size):
rect = QRectF(x+c*self.gap, y+r*self.gap, self.gap, self.gap)
rt.append( rect )
vt.append( False )
self.rects.append(rt)
self.visited.append(vt)
def startMap(self, r, c, size=10, delay=0.3):
self.initMazeMap(size, delay)
self.run = True
self.t = Thread(target=self.threadFunc, args=(r, c))
self.t.start()
def closeMap(self):
self.run = False
self.mazeItems.clear()
def genMaze(self, r, c, dir):
if not self.run:
return
desc = f'Push Stack [({self.idx}) Row:{r} Col:{c}]'
print(desc)
time.sleep(self.delay)
if not self.visited[r][c]:
self.mazeItems.append( MazeItem(r, c, dir, self.idx) )
self.update_signal.emit()
self.idx += 1
self.visited[r][c] = True
nr, nc, nd = self.getNext(r, c)
if nr!=-1 and nc!=-1:
self.genMaze(nr, nc, nd)
item = self.findMazeItem(r, c)
if item==None:
return
desc = f'Pop Stack [({item.idx}) Row:{r} Col:{c}]'
print(desc)
nr, nc, nd = self.getNext(r, c)
if nr != -1 and nc != -1:
item.dir = list()
self.genMaze(nr, nc, list())
def getNext(self, r, c):
seldir = set()
while True:
dir = random.choice(list(Dir))
nr = r + dir.value[0]
nc = c + dir.value[1]
if self.isValidDir(nr, nc):
break
seldir.add(dir)
if len(seldir) == len( list(Dir) ):
return -1, -1, list()
# delete direction for previous mazeItem.
try:
self.mazeItems[-1].dir.remove(dir)
except:
pass
# make current direction
nd = self.makeDir(dir)
return nr, nc, nd
def isValidDir(self, nr, nc):
if (nr>=0 and nr<self.size) and (nc>=0 and nc<self.size) and not self.visited[nr][nc]:
return True
else:
return False
def makeDir(self, dir):
dirs = [d for d in Dir]
try:
if dir==Dir.LEFT:
dirs.remove(Dir.RIGHT)
elif dir==Dir.RIGHT:
dirs.remove(Dir.LEFT)
elif dir==Dir.UP:
dirs.remove(Dir.DOWN)
else:
dirs.remove(Dir.UP)
except:
pass
return dirs
def findMazeItem(self, r, c):
for item in self.mazeItems:
if item.row == r and item.col == c:
return item
return None
def draw(self, qp):
b = QBrush(QColor(0,255,0))
qp.setBrush(b)
p = QPen(QColor(0,0,0), 3)
qp.setPen(p)
for item in self.mazeItems:
r = item.row
c = item.col
i = item.idx
d = item.dir
#qp.drawRect(self.rects[r][c])
if d:
self.drawMazeEdge(qp, d, self.rects[r][c])
qp.drawText(self.rects[r][c], Qt.AlignCenter, str(i))
def drawMazeEdge(self, qp, dir, rect):
for d in dir:
if d==Dir.LEFT:
qp.drawLine(rect.topLeft(), rect.bottomLeft())
elif d==Dir.RIGHT:
qp.drawLine(rect.topRight(), rect.bottomRight())
elif d==Dir.UP:
qp.drawLine(rect.topLeft(), rect.topRight())
else:
qp.drawLine(rect.bottomLeft(), rect.bottomRight())
def threadFunc(self, row, col):
self.genMaze(row, col, list())
print('Finished!!!')
[라인 1~6]
코드에 필요한 패키지, 모듈을 불러옵니다.
미로가 그려지는 과정을 지연시켜 보기위해 Thread처리를 해 두었습니다.
[라인 8~13]
C++에서 유용하게 사용하던 열거형 (Enum)이 파이썬에는 없어 아쉬웠지만, 3.4 버전부터 지원됩니다.
방향을 처리하는 열거형 클래스 입니다.
방향을 나타내는 이름과 값이 묶인 구조이며, 값 UP의 (-1, 0) 이 의미하는 것은
위로 가면 행(row)이 감소되기 때문에 -1, 열(col)은 변화가 없기 때문에 0
입니다.
[라인 15~20]
미로를 구성하는 여러 미로(칸) 중 하나를 의미하는 MazeItem 클래스이며, 행번호, 열번호, 방향, 인덱스로 이루어져 있습니다.
나중에 미로 생성시 MazeItem의 객체를 생성해 리스트에 저장하는 방식으로 구성합니다.
[라인 22~38]
전체 미로의 생성을 담당하는 MazeMap 클래스의 생성부 입니다.
그려지는 과정을 화면에 업데이트 하기 위해 위젯의 update함수를 호출하도록 신호를 생성하고 연결합니다.
Qt에서 이를 시그널 (신호), 슬롯 (신호발생시 호출되는 함수) 이라고 합니다.
미로가 위젯 창 화면에 꽉차면 보기 싫으므로 약간의 여백(gap)을 둡니다.
이제부터 코드의 라인 순서가 아닌 이벤트의 발생 순서로 코드를 설명해 보겠습니다.
[라인 60~64]
main.py에서 앱이 시작될 때 MazeMap의 객체를 생성하고 이 함수를 호출합니다.
바로 미로 생성의 진짜 시작입니다.
initMazeMap() 함수를 호출해 미로를 초기화 하고 별도의 실행흐름인 쓰레드를 생성해 threadFunc() 함수가 메인쓰레드와 별개로 실행되도록 합니다.
[라인 40~58]
미로 초기화 함수입니다. 생성크기, 번호, 그려지는 간격 등을 초기화합니다.
self.rects 리스트는 미로의 생성크기에 맞는 한 칸의 사각형 (QRectF type)들을 저장하는 2차원 리스트입니다.
self.visited 리스트는 해당 미로칸의 행,열에 방문여부(bool type)를 저장하는 2차원 리스트 입니다. 최초에는 모든 값이 False로 설정되며
방문시 True로 변경됩니다.
|
| [미로 초기화] |
[라인 178~180]
별도의 실행흐름인 쓰레드에서 호출되는 함수이며, genMaze() 함수를 최초로 호출해 스택(Stack)의 가장 아래부분에 저장합니다.
[라인 70~97]
이 함수는 실제 미로칸 (MazeItem)을 생성해 리스트에 저장하는 과정을 반복합니다.
재귀 호출로 이루어져 있으며 아래와 같이 동작하게 됩니다.
<미로 생성 과정>
1. 해당 미로 행,열 방문여부 체크
2. 방문하지 않았다면 방명록 작성하고 다음 미로칸 행, 열, 방향 랜덤 결정
3. 다음 미로칸 형, 열, 방향을 가지고 재귀 호출하며, Push Stack (1~3 반복)
4. 다음 미로칸 4방향이 모두 막혀있다면, pop Stack 하며 이전위치에서 방향 탐색
5. 만약 모든 미로칸의 다음 방향이 모두 막혀있다면 모든 스택이 풀리고 종료.
잘 이해되지 않는다면 동영상의 Push Stack, Pop Stack 시점을
살펴보기 바랍니다.
[라인 99~121]
현재 미로칸의 행, 열에서 이동가능한 다음 미로칸을 찾는 함수입니다.
다만, 다음 미로칸의 방향에 따라 현재 미로칸과의 사이 선이 제거되어야 하므로 이를 처리합니다. (만약 현재 위치에서 오른쪽방향으로 다음 위치가 결정되면, 현재 미로칸의 오른쪽 직선을 제거해 칸이 서로 연결되어 그려지도록 합니다.)
이어서, 다음 미로칸도 이전 미로칸이 이어 그려지도록 이동 방향의 반대를 제거합니다.
[라인 123~127]
전달 인자로 받은 미로칸의 행, 열이 유효(이동 가능)한지 확인하는 함수입니다.
[라인 129~142]
현재 미로칸에서 그려질 상, 하, 좌, 우 방향 선이 이전 미로칸을 참조해 연결되어 그려지도록 합니다.
[라인 144~148]
행, 열값을 이용해 해당 미로칸 객체(MazeItem)를 찾아 리턴시켜주는 함수입니다.
미로칸 생성중, 아직 미로가 완성되지 않았지만 더이상 갈 곳이 없는 경우에 getMaze() 함수의 스택이 풀리며(Pop) 퇴각검색(Backtracking)이 진행됩니다.
이때, 다음 방향이 있는 미로칸 아이템을 백 트래킹하며 찾은 경우 상, 하, 좌, 우 선을 없애도록 해야할 필요가 있는데 그때 이 함수를 이용해 행, 열값만으로 해당 MazeItem을 찾아 선을 그리는 방향을 모두 제거해 줍니다.
[라인 150~165]
Qt의 Painter를 이용, 미로가 그려지는 과정을 시각화 시키는 함수입니다.
MazeItem 리스트를 순회하며, 해당 미로칸의 방향에 따라 선을 그려주는 drawMazeEdge() 함수를 호출하고, 미로칸에 생성 번호를 표시합니다.
[라인 167~176]
미로칸의 방향(상, 하, 좌, 우) 정보에 따라 선을 그려주는 역할을
수행합니다.
이상으로 모든 설명을 마칩니다.
감사합니다.
댓글
댓글 쓰기