maze 알고리즘 기초개념 및 구현실습
.
그림, 실습코드 등 학습자료 출처 : https://github.com/ythwork
-
미로찾기에서 최단경로 찾기는 a-star알고리즘을 쓴다.
-
미로찾기 알고리즘에서 maze 알고리즘이 어떻게 동작하냐면 최단경로를 찾는 것은 아니다. start에서 destination으로 가는것이 목표이다.
-
maze 알고리즘을 요약하면 좌표를 스텍에 담은다음에 연결리스트로 옮기는 원리이다.
-
실제로 구현할때는 갈수없는 벽(갈색)을 바깥쪽에 만든다. 반면에 갈 수 있는 부분이 회색이다.
-
실제 미로의 크기는 5x5이지만 구현할때 배열을 나열할때는 x와 y좌표를 만들어서 7x7이다. (아래 그림참고)
- current를 기준으로 로우와 컬럼에 1단위로 변화를 주면서 current를 이동시킨다.
- dir = direction, next할때의 방향
- maze 작동예시
current position에서 clockwise로 돌면서 갈 수 있는 공간이면 이동한다.
그래서 갈 수 있는 공간을 다 가서 결국에는 목적지로 가게 된다. 조금은 무식한 방법이라고 할 수 있다.
그리고 지나간 위치는 스텍에다가 집어 넣는다. 그리고 지나간 위치는 다시 갈 수 없다.
단 지금 위치가 갈 곳이 없다면 기존에 스텍에 넣었던 것을 팝하면서 지금 위치에서 back을 한다.
- maze 알고리즘 구현을 위한 stack 구현
class Node:
def __init__(self, data=None):
self.__data=data
self.__next=None
@property
def data(self):
return self.__data
@data.setter
def data(self, data):
self.__data=data
@property
def next(self):
return self.__next
@next.setter
def next(self, n):
self.__next=n
class LStack:
def __init__(self):
self.top=None
def empty(self):
if self.top is None:
return True
else:
return False
def push(self, data):
new_node = Node(data)
if self.empty():
self.top = new_node
return
new_node.next = self.top
self.top=new_node
def pop(self):
if self.empty():
return None
cur = self.top
self.top = self.top.next
return cur.data
def peek(self):
if self.empty():
return None
return self.top.data
if __name__ =="__main__":
s = LStack()
s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.push(5)
while not s.empty():
print(s.pop(), end=" ")
5 4 3 2 1
- maze 알고리즘 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def empty(self):
if not self.head:
return True
return False
def add(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
new_node.next =self.head
self.head = new_node
def traverse(self):
cur = self.head
while cur:
yield cur
cur = cur.next
class Position:
def __init__(self, row, col, dir):
self.row = row
self.col = col
self.dir = dir ## dir = direction, next할때의 방향
class MazeSolver:
direction=((-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1))
## direction을 정의
## next할때 방향을 좌표로 표현한 것
## 이동 시 커런트 위치에 direction을 더할 것이다.
def __init__(self, maze):
## 7 * 7 의 maze를 정의
self.maze = maze
self.EXIT_ROW = len(maze)
self.EXIT_COL = len(maze[0])
## 아래는 벽을 둘러치는 코드
## maze 외곽 옆으로 벽을치는 for문
for row in maze:
row.insert(0, 1)
row.append(1)
## maze 외곽 위 아래로 벽을 치는 코드
added_row = [1 for _ in range(self.EXIT_COL+2)]
maze.insert(0, added_row)
maze.append(added_row)
self.path = LinkedList()
def get_path(self):
## 5 * 5 maze가 있는 상태에서 1로 된벽으로 외곽을 매움
## 마크는 7 * 7 이다.
## 임시적으로 경로를 담을 스택
stack = LStack()
## mark 만드는 코드, 7*7 로 0으로 싹다 채우는 코드
## 방문 여부를 판단하기 위한 maze와 같은 크기의 0으로 채워진 행렬, 벽까지 포함
mark = []
for _ in range(self.EXIT_ROW+2):
mark.append([0 for _ in range(self.EXIT_COL+2)])
# row, col : 현재 행과 열
# dir : 다음에 이동할 방향
# next_row, next_col : 다음에 이동할 위치
# found 최종 목적지 도착 여부 / 목적지를 찾았다면 true로 바뀔 것이다.
row=None; col=None; dir=None; next_row=None; next_col=None; found=False
# 출발점(1,1)을 mark에 1로 표시함
mark[1][1] = 1
# 현재 position을 스택에 push
# 방향은 direction[2] 즉 동쪽 2라고 표시된 dir은 임의로 해도 무방하다. 단 최악의 경우 연산 숫자가 늘어날 뿐이다.
stack.push(Position(1,1,2))
# 스택이 비어있지 않고 도착지를 찾지 못했다면
while not stack.empty() and not found:
## 처음 돌때는 1,1을 뽑고 디렉션은 2를 뽑고 시작할 것이다.
## 그 다음에는 내부 와일문으로 진입한다.
# 스택에서 Position 하나를 꺼내온다
# row, col, dir을 Position 값에서 읽어온다.
pos = stack.pop()
row = pos.row
col = pos.col
dir = pos.dir
# 모든 방향을 탐색하지 않았고, 다시말해 방향의 숫자가 시계방향을 순서로 0 ~ 7이므로.. dir<8이 되는 것이다.
# 아직 도착지를 찾지 못했다면.. 여기서 found는 찾았는지 안찾았는지 true false로 알려준다.
while dir < 8 and not found:
#next_row와 next_col을 구한다
next_row = row + self.direction[dir][0]
next_col = col + self.direction[dir][1]
#next_row와 next_col이 도착지(5,5)에 도달했다면
if next_row == self.EXIT_ROW and next_col == self.EXIT_COL:
#found를 True로 바꾼다
found = True
#스택에 현재 위치와 도착지 위치를 push
stack.push(Position(row,col,dir))
stack.push(Position(self.EXIT_ROW, self.EXIT_COL, 0))
#다음 위치(next_row, next_col)가 미로의 벽이 아니고 도착지에 방문하지 않았을 경우
elif self.maze[next_row][next_col] == 0 and mark[next_row][next_col] == 0:
#다음 위치를 mark에 방문했다고 체크.
mark[next_row][next_col] = 1
#현재 위치를 스택에 push
stack.push(Position(row, col, dir))
#다음 위치로 이동
row = next_row
col = next_col
dir = 0
else:
#방향을 하나 늘려준다.
dir+=1
#목적지를 찾았으면
if found:
#stack에서 꺼내 링크드 리스트에 저장한다.
while not stack.empty():
self.path.add(stack.pop())
else:
print('There is no path in this maze!')
def print_path(self):
g = self.path.traverse()
for node in g:
print("({}, {})".format(node.data.row, node.data.col))
def show_maze(self):
print(' ', end='')
for i in range(self.EXIT_ROW+2):
print(' ' + str(i) + ' ', end='')
print()
for i in range(self.EXIT_ROW+2):
print(' ' + str(i) + ' ', end='')
for j in range(self.EXIT_COL+2):
if self.maze[i][j] == 0:
print(' O ', end='')
else:
print(' # ', end='')
print()
print()
def show_path(self):
path_set = set()
g=self.path.traverse()
for node in g:
path_set.add((node.data.row, node.data.col))
print(' ', end='')
for i in range(self.EXIT_ROW+2):
print(' ' + str(i) + ' ', end='')
print()
for i in range(self.EXIT_ROW+2):
print(' ' + str(i) + ' ', end='')
for j in range(self.EXIT_COL+2):
if (i, j) in path_set:
print(' P ', end='')
elif self.maze[i][j] == 0:
print(' O ', end='')
else:
print(' # ', end='')
print()
print()
if __name__ == "__main__":
maze = [
[0, 1, 1, 0, 0],
[1, 0, 0, 1, 1],
[0, 1, 1, 0, 1],
[0, 1, 0, 1, 1],
[1, 1, 0, 0, 0],
]
maze_solver = MazeSolver(maze)
maze_solver.show_maze()
maze_solver.get_path()
maze_solver.print_path()
maze_solver.show_path()
0 1 2 3 4 5 6
0 # # # # # # #
1 # O # # O O #
2 # # O O # # #
3 # O # # O # #
4 # O # O # # #
5 # # # O O O #
6 # # # # # # #
(1, 1)
(2, 2)
(2, 3)
(3, 4)
(4, 3)
(5, 4)
(5, 5)
0 1 2 3 4 5 6
0 # # # # # # #
1 # P # # O O #
2 # # P P # # #
3 # O # # P # #
4 # O # P # # #
5 # # # O P P #
6 # # # # # # #